Модуль и остаток (китайская теорема об остатке) в MATLAB

Question

Как найти наименьшее возможное значение в 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) 

Answer 1

Итак, ваша цель найти самый маленький 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 Команда использует алгоритм Евклида. Если вам необходимо реализовать это самостоятельно, это может послужить хорошим справочным материалом.