5

给定数组中的模值及其余数值，如何在 Matlab 中找到最小可能值？例如：

A=[ 23 90 56 36] %# the modulo values
B=[  1  3 37 21] %# the remainder values

这导致了答案93；这是最小的可能值。

编辑：

这是我的代码，但它似乎只将剩余数组的最后一个值显示为最小值：

z = input('z=');
r = input('r=');
c = 0;
m = max(z);
[x, y] = find(z == m);
r = r(y);
f = find(z);
q = max(f);
p = z(1:q);
n = m * c + r;
if (mod(n, p) == r)
    c = c + 1;
end
fprintf('The lowest value is %0.f\n', n)
4

1 回答 1

3

好的，所以你的目标是找到x满足B(i) = mod(x, A(i))每个i.

此页面包含一个非常简单（但彻底）的解释，说明如何使用中国剩余定理求解您的方程组。因此，这是 MATLAB 中所描述方法的实现：

A = [23, 90];                                  %# Moduli
B = [1, 3];                                    %# Remainders

%# Find the smallest x that satisfies B(i) = mod(x, A(i)) for each i
AA = meshgrid(A);
assert(~sum(sum(gcd(AA, AA') - diag(A) > 1)))  %# Check that moduli are coprime
M = prod(AA' - diag(A - 1));
[G, U, V] = gcd(A, M);
x = mod(sum(B .* M .* V), prod(A))

x =
    93

您应该注意，此算法仅适用于互质A的模（ 的值）！

在您的示例中，它们不是，因此这不适用于您的示例assert（如果模不是互质的，我已经放置了一个命令来破坏脚本）。您应该尝试为自己实现非压缩模数的完整解决方案！

PS
另请注意，该gcd命令使用Euclid's algorithm。如果您需要自己实现它，this和this可能会为您提供很好的参考。

于 2012-09-23T17:22:58.640 回答