Алгоритм Евклида
Вычисление НОД.
Число а называется общим делителем чисел b1, b2,…, bn, если оно является делителем каждого из чисел b1, b2,…, bn.
Наибольшим общим делителем целых чисел a1,…,an , называется такой их общий делитель, который делится на любой общий делитель этих чисел: обозначается НОД (a1,…,an).
Каноническое разложение
Если
a=
и
b=
суть канонического разложения целых
положительных чисел a
и b,
то d=НОД(a,b),
где d=
Простой способ
a= 24 b=6
24-6=18
18-6=12
12-6=6 < НОД
6-6=0
Теорема Евклида.
Теорема Евклида
Пусть a и b – два целых числа, b ≠ 0 и a = bq + r (0 ≤ r < |b|). Тогда НОД (a,b) = НОД (b,r).
Алгоритм Евклида, сравнение алгоритмов.
Для нахождения НОД двух целых чисел применяется способ «последовательного деления», называемый алгоритмом Евклида.
Сущность алгоритма Евклида состоит в том, что в силу теоремы Евклида задача нахождения НОД (a,b) сводится к более простой задаче нахождения НОД (b,r), 0 ≤ r < |b|. Если r = 0, то НОД (a,b) = b. Если же r ≠ 0, то получаем цепочку неравенств
a = bq0 + r1, 0 ≤ r < |b|,
b = r1q1 + r2, 0 ≤ r2 < r1,
……………………
rn-2 – rn-1qn-1 + rn, 0≤ rn < rn-1,
rn-1 = rnqn + rn+1.
Приходим к выводу: если к целым числам a,b, где b ≠ 0, применить алгоритм Евклида, то последний ненулевой остаток в этом алгоритме и есть НОД (a,b).
Пример: a=86, b=32
a = b*q + p1
86 = 32*2 + 22
32 = 22*1 + 10
22 = 10*2 +2
10 = 2*5 + 0
Ответ: НОД (86, 32) = 2
Сравнение алгоритмов
Сравним «простой» алгоритм и алгоритм Евклида. Для малых чисел ни один из них не дает преимущества в вычислениях, но для больших параметров эффективней применять алгоритм Евклида.
Соотношение Безу.
(Целые числа называют взаимно простыми, если любой их общий делитель равен +1 или -1.)
Теорема. Если целые числа a и b взаимно простые, то существуют целые числа u и v такие, что au+bv=1.
Пример. Пусть a = 5 и b = 7, тогда u = -4 и v = 3, т.е. 5*(-4) + 7*3 = 1.
Расширенный алгоритм Евклида.
Алгоритм, примененный к паре чисел a,b порождает последовательность такую, что
ri-1=riqi+ri+1 для 1≤i≤n, где r0=a, r1=b, rn+1=0.
Из этих формул легко получается рекуррентная последовательность:
из которой теперь следует классический результат
rn=НОД(a,b)=una+vnb.
Этапы развития технологии программирования
1 Этап: методологии программирования нет.
Программирование считается искусством.
Архитектура программы имеет следующий вид:
Проблемы, возникшие на данном этапе:
Данные общедоступны, а следовательно велика вероятность их ошибочного изменения (например, одновременное использование одной и той же переменной для различных целей)
В больших программах без структурирования очень сложно разобраться.
2 Этап: структурное программирование.
Методология - структурный подход.
Архитектура программы имеет следующий вид:
Проблемы, возникшие на данном этапе:
Проблема общей незащищенной области данных решена не полностью, но все же появилась возможность использования локальных переменных в подпрограммах.
При достаточно большом размере программ структурирование действий с помощью подпрограмм не уменьшает растущей сложности, что так же не полностью решает данную проблему.
Разработчики объединяются в группы, что предполагает дальнейшее развитие методологии программирования. Появилась необходимость в методологии, позволяющей программистам эффективно использовать совместно разработанный код программы.
Проблемы, решенные на данном этапе:
Появился метод проектирования программ – метод пошаговой детализации.
Выделены три основных алгоритмических конструкции (следование, ветвление и цикл), достаточных для построения любого алгоритма.