Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Варпаховский Ф.Л. Элементы теории алгоритмов
 
djvu / html
 

дачи: для каждого числа п узнать, каков остаток от деления этого числа на данное число р. Как могут быть закодированы условия и решения соответствующих частных задач?
Упражнение 2. Не прибегая к процессу последовательного вычитания, а пользуясь известным признаком делимости на 9, указать правило, которое для каждого натурального числа п позволяло бы определить, делится это число на 9 или нет. Как обосновать «конечность» применяемой процедуры?
Пример 2. Найти правило, позволяющее для любых двух натуральных чисел а и 6, не равных одновременно нулю, определить за конечное число шагов их наибольший общий делитель.
Правило нахождения наибольшего общего делителя, известное со времен древности и называемое алгоритмом Евклида, состоит в следующем. Пусть fl^6>01. Делим а на 6, получаем остаток ri0, то искомый делитель совпадает с наибольшим общим делителем чисел 6 и /ч. Поэтому делим 6 на /ч, и если новый остаток г2=0, то /ч — искомый делитель, если ri>r2>0, то делим /ч на г2. Продолжая этот процесс, получим:
а>Ь> Г!>г2 > ... >гл>гл+1 =0.
Последнее отличное от нуля число в этой цепочке (гп) и будет искомым. При этом весь процесс закончится в конечное число шагов, поскольку натуральных чисел, меньших числа 6, — конечное число.
Приведенная здесь процедура применима к любой паре чисел, не равных одновременно нулю, и для каждой такой пары дает ответ после выполнения конечного числа операций. Если, например, взять пару 124, 44, то получим:
rt =36, г2=8, г3=4, г4=0.
Искомый делитель равен 4.
УСЛОВИЯ и ответы к частным задачам снова могут быть выражены в подходящем алфавите, например в алфавите Л={|, 0}. Так, условие рассмотренной числовой
1 Если в точности одно число из пары a, b отлично от нуля, то оно и будет искомым общим делителем.

 

1 2 3 4 5 6 7 8 9 10 20


Математика