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

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

matlab modulo chinese-remainder-theorem
person Jey    schedule 23.09.2012    source источник
comment
См. китайскую теорему об остатках.   -  person Maurits    schedule 23.09.2012
comment
В файловом обмене MATLAB уже есть несколько реализаций CRT, например: "nofollow noreferrer">здесь и здесь...   -  person Eitan T    schedule 23.09.2012
comment
@EitanT, не могли бы вы помочь мне в создании этой программы? я действительно хромаю в программировании, и нам разрешено использовать только команды rem и mod, и я не получаю никакого прогресса   -  person Jey    schedule 23.09.2012
comment
@Jey Этот вопрос кажется идентичным вашему . Кроме того, было бы лучше, если бы вы что-то сделали (вставили этот код в исходный вопрос), чтобы его можно было улучшить до работающей программы.   -  person Eitan T    schedule 23.09.2012
comment
@EitanT: Если вы понимаете, что вопрос является дубликатом, подумайте о закрытом голосовании.   -  person Jonas    schedule 23.09.2012
comment
@ Джонас, извини, я думал, что это не дубликат, потому что другой вопрос не разрешает rem и mod, в то время как мой разрешает только команды rem и mod   -  person Jey    schedule 23.09.2012
comment
@Jonas Я уже исчерпал свой дневной лимит :) @ Джей, если ты все еще застрял, обнови этот вопрос и вставь в него свой код. Вам будет легче помочь, когда у вас уже что-то получится...   -  person Eitan T    schedule 23.09.2012
comment
@EitanT хорошо, я обновлю это позже! но мне немного стыдно за свою программу, потому что она очень плохая из-за моих плохих навыков работы с MATLAB.   -  person Jey    schedule 23.09.2012
comment
@Jey Не будь! Вы не сможете стать лучше, если не попробуете.   -  person Eitan T    schedule 23.09.2012
comment
г = вход ('г ='); г = ввод ('г ='); с=0; м=макс(г); [x,y]=найти(z==m); г=г(у); е = найти (г); д=макс(е); р=г(1:д); п=м*с+г; если (mod(n,p)==r) c=c+1; end fprintf('Самое низкое значение %0.f\n',n) Вот мой код, но он отображает только последнее значение остаточного массива как наименьшее значение @EitanT   -  person Jey    schedule 23.09.2012
comment
Завершите строку двумя пробелами, чтобы добавить разрыв строки ‹br/›, похоже, это не работает   -  person Jey    schedule 23.09.2012
comment
Теги @Jey ‹br/› не работают в комментариях, потому что форматирование в комментариях несколько ограничено. Я вставил ваш код в исходный вопрос.   -  person Eitan T    schedule 23.09.2012
comment
@EitanT спасибо! но если вы вводите значения в первом вопросе, он дает только 21 как наименьшее значение, которое является последним числом в массиве B.   -  person Jey    schedule 23.09.2012

Ответы (1)


arrow_upward
3
arrow_downward

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

person Eitan T    schedule 23.09.2012