Отправляет email-рассылки с помощью сервиса Sendsay

Всё о работе в Интернет

Подписаться Бесплатная «Серебряная» новостная рассылка Подписчиков 7.350 RSS
←   Декабрь 2009   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней 1 выпусков (1 раз в 2 месяца)


Сайт рассылки: http://bestinvestblog.com
Открыта: 10-02-2009

Автор
bestinvestblog

Статистика

7.350 подписчиков
0 за неделю
←   Все выпуски   →

Занятие 58. Поиск наибольшего общего делителя двух заданных натуральных чисел.


Начиная с сегодняшнего занятия, уважаемые подписчики, мы с вами рассмотрим несколько важнейших циклических алгоритмов вычислительной математики.

Прописные истины. Молодые программисты не умеют работать. Зато опытные умеют не работать...

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ

Поиск наибольшего общего делителя двух положительных целых чисел – одна из наиболее известных задач теории чисел. Решение этой задачи базируется на алгоритме Евклида.

Евклид – древнегреческий математик, который создал свой главный математический труд “Начала” ещё в 3 веке до н.э. Один из разделов “Начал” посвящён теории чисел. В советское время теорией чисел занимался выдающийся математик, академик Академии Наук СССР Виноградов И.М. В его изложении алгоритм Евклида выглядит следующим образом.

Пусть M и N – положительные целые, причём M > N. Тогда число M можно единственным образом представить в виде M = N  q1 + r1, где q1 – называется неполным частным, а 0 < r1 < N – остатком от деления M на N. В частном случае, если r1 = 0, то говорят, что M кратно N, или, что M делится на N без остатка, или, что N является делителем числа M.

Например, при M = 140 и N = 12 имеем 140 = 12  11 + 8, или, иначе говоря, неправильную дробь всегда можно представить в виде смешанной: M / N = q1 + r1 / N, то есть 140 / 12 = 11 + 8 / 12.

Теперь рассмотрим делителей чисел M и N. Сделаем это на нашем примере. Число M = 140 имеет 12 делителей: 1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70 и 140. Число N = 12 имеет 6 делителей: 1, 2, 3, 4, 6 и 12. Видим, что среди делителей чисел M и N есть общие: 1, 2 и 4. Наибольший среди них – это 4.

Теория чисел утверждает, что совокупность общих делителей чисел M и N совпадает с совокупностью общих делителей чисел N и r1. В частности, наибольший общий делитель чисел M и N равен наибольшему общему делителю чисел N и r1. Иначе и быть не может. Действительно, если числа M и N имеют некоторый общий делитель D, то M делится на D без остатка, и выражение N  q1 также делится на D без остатка. Следовательно, должно делиться на D без остатка также и r1, иначе равенство M = N  q1 + r1 невозможно.

Для нашего примера 140 = 12  11 + 8 это значит, что совокупность общих делителей для чисел N = 12 и r1 = 8 должна остаться прежней, то есть 1, 2 и 4. Это действительно так, поскольку число r1 = 8 имеет 4 делителя: 1, 2, 4 и 8.  

Евклид сделал вывод, что в поисках наибольшего общего делителя чисел M и N вместо них проще рассматривать числа N и r1. Пару чисел N и r1, из которых, как уже указывалось выше, r1 < N, можно, в свою очередь, представить в виде N = r1  q2 + r2, где 0 < r2 < r1, и далее рассматривать пару r1 и r2. Продолжая евклидовский процесс представления, получим:

r1 = r2  q3 + r3 где 0 < r3 < r2,

r2 = r3  q4 + r4 где 0 < r4 < r3,

. . . . . . . . . . . . . . . . . . . . . . . . . .

rk-1 = rk  q k+1 + rk+1 где rk+1 = 0.

Мы видим, что этот процесс заканчивается, когда некоторый очередной остаток от деления оказывается равным нулю: rk+1 = 0. Достижение последнего равенства неизбежно, так как убывающая последовательность целых чисел N, r1, r2, r3, ... не может содержать более чем N положительных.

Например, при M = 140 и N = 12 евклидовский процесс представления получается достаточно коротким:

140 = 12  11 + 8,

12 = 8  1 + 4,

8 = 4  2 + 0. 

Рассматривая последовательность представлений сверху вниз, можно сделать вывод, что общие делители чисел M и N одинаковы с общими делителями чисел N и r1, далее одинаковы с общими делителями чисел r1 и r2, затем чисел r2 и r3, ..., и наконец, с общими делителями чисел rk-1 и rk.

Замечаем, что последнее представление rk-1 = rk  q k+1 + rk+1, где rk+1 = 0, по сути представляет собой фиксацию того факта, что rk-1 кратно rk, то есть, что число rk само является делителем числа rk-1. Из этого немедленно следует, что число rk (последний не равный нулю остаток от деления) является наибольшим общим делителем всех образованных в процессе представления пар, в том числе и исходной пары чисел M и N.

Задача C.2.5. “Наибольший общий делитель”. Построить подпрограмму вычисления наибольшего общего делителя двух натуральных чисел M и N.

   Function NOD ( M,N: LongInt ): LongInt;
      Var C: LongInt;
   Begin
      Repeat
         C := M Mod N; M := N; N := C
      Until N = 0;
      NOD := M
   End;

Евклидовская последовательность представлений позволяет установить следующие особенности подпрограммы NOD, вычисляющей наибольший общий делитель двух натуральных чисел M и N.

1). Результат подпрограммы, то есть значение наибольшего общего делителя, имеет смысл при целых положительных значениях исходных данных, то есть при M > 0 и N > 0.

2). Порядок следования чисел в исходной паре M и N не имеет значения. Если оказалось, что M < N, то последовательность операторов C := M Mod N; M := N; N := C меняет порядок их следования на обратный. Например, при M = 5 и N = 9 получаем C = 5 Mod 9 = 5, после чего M = 9, а N = 5.

3). При дальнейшем продолжения цикла получения остатков от деления число M всегда оказывается большим числа N. И это тоже обеспечивается последовательностью тех же операторов C := M Mod N; M := N; N := C. 

4). Значения чисел в паре M и N можно заменить значениями чисел новой пары N и C,  где C равно остатку от деления большего числа M на меньшее число N. Их наибольший общий делитель от этого не изменяется. 

5). Вышеописанный процесс замены значений пары чисел M и N имеет циклический характер и должен продолжаться до момента, когда меньшее из чисел N становится равным нулю.

6). Большее из чисел M, которое нулю не равно, представляет собой искомый наибольший общий делитель.

7). В случае равенства чисел M и N последовательность операторов C := M Mod N; M := N; N := C сразу даёт нужный результат, равный M, поскольку оказывается, что C = 0, а следовательно, и N = 0.

На следующем занятии, уважаемые подписчики, мы рассмотрим простые числа.

Уважаемые подписчики! При необходимости задать вопрос, проконсультироваться, уточнить или обсудить что-либо обращайтесь через Гостевую книгу моего персонального сайта http://a-morgun.narod.ru. При этом настоятельно рекомендую пользоваться браузером Internet Explorer.

С уважением, Александр.

 
В избранное