|
Здравствуйте.По возможности буду краток.В книге Д.Кнута дается определение алгоритма Евклида по нахождению НОД,с помощью теории множеств.При чтении у меня возникло недопонимание некоторых частей Метод вычислений - четверка вида(Q,I,O,f). Q - содержит в себе множества I и O. f - функция отображения множества в себя.Причем f(q)=q для всех q из множества O. Пусть элементами Q будут: все величины(n) все упорядоченные пары (m,n) все упорядоченные четверки (m,n,r,1),(m,n,r,2),(m,n,p,3)(Почему в последней четверке после n следует p?) m,n,p - целые положительные числа r - неотрицательное целое число I - подмножество всех пар (m,n) O - подмножество всех величин (n) Определение функции f: f((m,n)) = (m,n,0,1); f((n))=(n); f((m,n,r,1))=(m,n,остаток от деления m на n,2) f((m,n,r,2))=(n),если r=0, в противном случае (m,n,r,3) (Почему в 2 верхних строках число,следующее за r,увеличивается?) f((m,n,p,3))=(n,p,p,1)(Почему в левой части этого равенства у за n идет p,а в правой присутствуют 2 символа p ?) Заранее спасибо. задан 23 Авг '12 15:28 
Bool800 |
|
А Вы знаете алгоритм Евклида в нормальной формулировке? На всякий случай - вот он: Итак, если $%m\ne 0$%, то $%НОД(m, n)= НОД(n, p)$%, где снова имеем $%n > p$%. Это один шаг алгоритма. Конец вычислений наступает тогда, когда очередной вычисленный остаток равен 0. Тогда в качестве НОД берется меньшее (второе) число пары. Именно этот алгоритм представлен в Вашем вопросе, только в него добавлены два параметра. Почему в определении множества Q пишется то r, то p? В принципе можно писать любые буквы, ведь это независимые переменные. Просто через p обозначены натуральные числа, а r может также быть равным 0. При вычислении f((m,n,r,2)) идет проверка выхода из цикла, поэтому проверяется, не обратился ли уже остаток r в 0. Если нет, его далее обозначают через p. При вычислении f((m,n,p,3)) происходит замена старой пары (m, n) на новую (n, p). Чему равно при этом третье значение в четверке, по сути уже не важно. отвечен 23 Авг '12 23:09 
DocentI |