Здравствуйте.По возможности буду краток.В книге Д.Кнута дается определение алгоритма Евклида по нахождению НОД,с помощью теории множеств.При чтении у меня возникло недопонимание некоторых частей

Метод вычислений - четверка вида(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

10|600 символов нужно символов осталось
0

А Вы знаете алгоритм Евклида в нормальной формулировке? На всякий случай - вот он:
Пусть даны целые числа $%m, n, m > n.$% Имеем $%НОД(m, n) = НОД(m-n, m)=...= НОД(p, n)$%, где p - остаток от деления m на n.

Итак, если $%m\ne 0$%, то $%НОД(m, n)= НОД(n, p)$%, где снова имеем $%n > p$%. Это один шаг алгоритма. Конец вычислений наступает тогда, когда очередной вычисленный остаток равен 0. Тогда в качестве НОД берется меньшее (второе) число пары.

Именно этот алгоритм представлен в Вашем вопросе, только в него добавлены два параметра.
Последнее число в четверке - номер действия внутри одного шага вычислений. Он меняется от 1 до 3. Естественно, оно возрастает от действия к действию, но после 3 идет снова 1.
Третье число - новый вычисленный остаток.

Почему в определении множества 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

изменен 23 Авг '12 23:10

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×41
×6

задан
23 Авг '12 15:28

показан
1198 раз

обновлен
23 Авг '12 23:10

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru