Гипермаркет знаний>>Информатика>>Информатика 9 класс>>Информатика: Алгоритм Евклида

§ 40. Алгоритм Евклида

Основные темы параграфа:

♦ наибольший общий делитель;
♦ идея алгоритма Евклида;
♦ описание алгоритма Евклида блок-схемой;
♦ программа на AЯ и на Паскале.

Наибольший общий делитель

Рассмотрим следующую задачу: требуется составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Вспомним математику. Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся нацело. Например, у чисел 12 и 18 имеются общие делители: 2, 3, 6. Наибольшим общим делителем является число 6. Это записывается так:

НOД(12, 18) = 6.

Обозначим исходные данные как М и N. Постановка задачи выглядит следующим образом:

Дано: М, N
Найти: НОД(M, N).

В данном случае какой-то дополнительной математической формализации не требуется. Сама постановка задачи носит формальный математический характер. Не существует формулы для вычисления НОД(М, N) по значениям М и N. Но зато достаточно давно, задолго до появления ЭВМ, был известен алгоритмический способ решения этой задачи. Называется он алгоритмом Евклида.

Идея алгоритма Евклида

Идея этого алгоритма основана на том свойстве, что если М>N, то

НОД(М, N) = НОД(М – N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности (модуля их разности) и меньшего числа.

Легко доказать это свойство. Пусть К — общий делитель М и N (М > N). Это значит, что М = mК, N = nК, где m,n — натуральные числа, причем m > n. Тогда М - N = К(m - n), откуда следует, что К — делитель числа М - N. Значит, все общие делители чисел М и N являются делителями их разности М - N в том числе и наибольший общий делитель.

Второе очевидное свойство:

НОД(М, М) = М.

Для «ручного» счета алгоритм Евклида выглядит так:

1) если числа равны, то взять любое из них в качестве ответа, в противном случае продолжить выполнение алгоритма;
2) затенить большее число разностью большего и меньшего из чисел;
3) вернуться к выполнению п. 1.

Рассмотрим этот алгоритм на примере М=32, N=24:

Получили: НОД(32, 24) = НОД(8, 8) = 8, что верно.

Описание алгоритма Евклида блок-схемой

На рис. 6.8 приведена блок-схема алгоритма Евклида.

Структура алгоритма — цикл-пока с вложенным ветвлением. Цикл повторяется, пока значения М и N не равны друг другу. В ветвлении большее из двух значений заменяется на их разность.

А теперь посмотрите на трассировочную таблицу алгоритма для исходных значений М = 32, N = 24.

В итоге получился верный результат.

Программа на АЯ и на Паскале

Запишем алгоритм на АЯ и программу на Паскале.

Коротко о главном

Алгоритм Евклида предназначен для получения наибольшего общего делителя двух натуральных чисел. Структура алгоритма Евклида — цикл с вложенным ветвлением.

Ручная трассировка может использоваться для проверки правильности лишь сравнительно простых алгоритмов. Правильность программ проверяется путем тестирования на компьютере.

Вопросы и задания

1. Выполните на компьютере программу Еvklid. Протестируйте ее на значениях М= 32, N = 24; М = 696, N = 234.
2. Составьте программу нахождения наибольшего общего делителя трех чисел, используя следующую формулу:
НОД(А, B, С) = НОД(НОД(A, В), С).
3. Составьте программу нахождения наименьшего общего кратного (НОК) двух чисел, используя формулу:
А·В = НОД(А, В)·HOK(А, В).

И. Семакин, Л. Залогова, С. Русаков, Л. Шестакова, Информатика, 9 класс
Отослано читателями из интернет-сайтов

_{Вся информатика онлайн, список тем по предметам, сборник конспектов по информатике, домашняя работа, вопросы и ответы, рефераты по информатике 9 класс, планы уроков}

Содержание урока
 конспект урока                       
 опорный каркас  
 презентация урока
 акселеративные методы 
 интерактивные технологии 

Практика
 задачи и упражнения 
 самопроверка
 практикумы, тренинги, кейсы, квесты
 домашние задания
 дискуссионные вопросы
 риторические вопросы от учеников

Иллюстрации
 аудио-, видеоклипы и мультимедиа 
 фотографии, картинки 
 графики, таблицы, схемы
 юмор, анекдоты, приколы, комиксы
 притчи, поговорки, кроссворды, цитаты

Дополнения
 рефераты
 статьи 
 фишки для любознательных 
 шпаргалки 
 учебники основные и дополнительные
 словарь терминов                          
 прочие 

Совершенствование учебников и уроков
 исправление ошибок в учебнике
 обновление фрагмента в учебнике 
 элементы новаторства на уроке 
 замена устаревших знаний новыми 

Только для учителей
 идеальные уроки 
 календарный план на год  
 методические рекомендации  
 программы
 обсуждения


Интегрированные уроки

Если у вас есть исправления или предложения к данному уроку, напишите нам.

Если вы хотите увидеть другие корректировки и пожелания к урокам, смотрите здесь - Образовательный форум.