Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. A Описание клавиш
  2. I. Описание установки.
  3. I. Описание установки.
  4. I.Описание установки.
  5. Receiver specifications (описание приемника)
  6. Transmitter specifications (описание передатчика)
  7. VIII.Техническое описание прохождения группой маршрута.

В» класс. Изучить методический материал, разработать алгоритм Евклида в виде блок-схемы и реализовать его в Паскаль. Выполнить задания. (мет. рек. в Приложении 1).

11 класс. Создать презентацию с анимациями на произвольную тему.

 


 

Приложение1.

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

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

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

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

НОД(12, 18) = 6.

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

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

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

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

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

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

Легко доказать это свойство. Пусть К - общий делитель М u N (M> 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, что верно.

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

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

Рис. 3.12. Блок-схема алгоритма Евклида

 

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

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

Шаг Операция M N Условие
  ввод М      
  ввод N      
  M ¹ N     32 ¹ 24, да
  M>N     32>24, да
  M:=M-N      
  M ¹ N     8 ¹ 24, да
  M>N     8>24, нет
  N:=N-M      
  M ¹ N     8 ¹ 16, да
  M>N     8>16, нет
  N:=N-M      
  M ¹ N     8 ¹ 8, нет
  вывод M      
  конец      

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


Дата добавления: 2015-10-29; просмотров: 152 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
F Неподеленная пара| How the city hurts your brain

mybiblioteka.su - 2015-2024 год. (0.005 сек.)