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

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск

Тема работы

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

Состав группы

Ученики 9 класса

Руководитель проекта

Милованова Татьяна Павловна

Цель работы

Научится находить наибольший общий делитель с помощью алгоритма Евклида.

Основополагающий вопрос

В чём удобство применения алгоритма Евклида?

Проблемный вопрос

Что такое алгоритм Евклида?

Учебные вопросы

Что такое наибольший общий делитель (НОД)?

В чём заключается идея Алгоритма Евклида?

Как описать алгоритм Евклида блок-схемой?

План проведения проекта

Этап 1 Разработка проектного задания. Задачи этапа – определение темы, уточнение целей, выбор рабочих групп, определение источников информации, постановка задач

Этап 2. Разработка проекта. Задачи этапа – сбор и уточнение информации.

Этап 3. Оценка результатов Задачи этапа – анализ выполнения проектных заданий.

Этап 4.Защита проекта. Урок – презентация Задачи этапа – коллективная защита проекта

Найденная информация

Как мы помним из математики наибольший общий делитель двух натуральных чисел -это самое большое натуральное число на которое они делятся нацело.

Достаточно давно ,задолго до появления ЭВМ был известен алгоритмический способ решения этой задачи.Называется он алгоритмом Евклида.

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

Алгоритм Евклида описанный блок схемой выглядит так :

EvclidMI.jpg

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

Вывод

Научились: Решать задачи с помощью алгоритма Евклида.

Используемые источники информации

Kniigiiii.jpeg

Информатика и ИКТ Базовый курс_9 кл_Семакин и др_2005.

картинка

картинка

Полезные ссылки

Учебный проект Жизнь как алгоритм