Алгоритм
<<  Алгоритм и его исполнение Алгоритм – модель деятельности исполнителя алгоритмов  >>
Тема: «Применение алгоритма Евклида при решении задач »
Тема: «Применение алгоритма Евклида при решении задач »
Например, имеется прямоугольник 9
Например, имеется прямоугольник 9
Максимальный размер квадрата, который мы можем врезать из
Максимальный размер квадрата, который мы можем врезать из
На следующем шаге мы отрежем квадрат размером 4
На следующем шаге мы отрежем квадрат размером 4
?
?
Вперед 2 Назад 2
Вперед 2 Назад 2
Картинки из презентации «Тема: «Применение алгоритма Евклида при решении задач »» к уроку информатики на тему «Алгоритм»

Автор: pozdnyakov. Чтобы познакомиться с картинкой полного размера, нажмите на её эскиз. Чтобы можно было использовать все картинки для урока информатики, скачайте бесплатно презентацию «Тема: «Применение алгоритма Евклида при решении задач ».ppt» со всеми картинками в zip-архиве размером 245 КБ.

Тема: «Применение алгоритма Евклида при решении задач »

содержание презентации «Тема: «Применение алгоритма Евклида при решении задач ».ppt»
Сл Текст Сл Текст
1Тема: «Применение алгоритма Евклида 20на псевдокоде: Procedure
при решении задач ». Налить_до_краев_А; Begin while not (А
2Задача №1. На какое число квадратов полный) do Begin Налить_В;
можно разделить прямоугольник m?n, если Перелить_из_В_в_А; End; End;
каждый раз отрезать от него квадрат 21Тогда основная программа будет иметь
максимального размера? следующую структуру: BEGIN While
3Например, имеется прямоугольник 9?5. (B<>требуемое) and
4Максимальный размер квадрата, который A<>требуемое) do begin
мы можем врезать из прямоугольника 9?5 Налить_до_краев_А; Вылить_из_ А;
равен 5?5, так, как минимальная сторона Перелить_из_В_в_А; end; END.
прямоугольника равна 5. После того, как мы 22Заметим, что нам потребовалось три
отрежем один квадрат останется раза налить 5 – литровый сосуд и два раза
прямоугольник 4?5. опорожнить 7-литровый, что соответствует
5На следующем шаге мы отрежем квадрат равенству: 1=5*3-7*2. Эта формула по сути
размером 4?4, так как минимальная сторона является способом представить наибольший
оставшегося прямоугольника равна 4. После общий делитель (НОД) двух чисел (5 и 7) в
этого останется прямоугольник 4?1. Из виде разности чисел. Как известно из
которого мы можем вырезать 4 квадрата математики, для НОД такое представление
размером 1?1. Т. о. прямоугольник 9?5 мы существует всегда. Мало того, если
разрезали на шесть квадратов. требуемое число литров не является кратным
6На какое же число квадратов можно НОД емкостей исходных сосудов, тол такое
разделить прямоугольник m?n, если каждый представление невозможно в принципе!
раз отрезать от него квадрат максимального 23Можно ли отмерить 3 литра с помощью
размера? сосудов емкостью 4 и 8 литров? Можно ли
7Для того, чтобы узнать какой квадрат отмерить 2 литра с помощью сосудов
максимального размера можно вырезать из емкостью 4 и 8 литров? Можно ли отмерить 4
того или иного прямоугольника, необходимо литра с помощью сосудов емкостью 4 и 8
сравнить значения его сторон. Найти литров? Можно ли отмерить 3 литра с
значение наименьшей стороны, и вырезать из помощью сосудов емкостью 21 и 6 литров?
прямоугольника квадрат со стороной равной Можно ли отмерить 1 литр с помощью сосудов
данной. При этом длина наибольшей стороны емкостью 15 и 5 литров?
прямоугольника уменьшается на величину 24Оказывается, что всегда можно отмерить
минимальной из сторон. количество литров, кратное НОД(А,В) и не
8На языке программирования TurboPascal, превышающее емкость большего сосуда.
это запишется следующим образом: If 25Рассмотрим случай, когда А=7л, а В=5
(m>n) then m:=(m-n) else n:=(n-m); л, требуется получить 2 литра.
Подобную операцию нам необходимо будет Вышеприведенная схема позволяет получить
произвести не один раз! До каких же пор мы результат за 18 переливаний (2=5*6-7*4).
будем делить прямоугольник на квадраты Действие. А=7л. B=5л. Налить B. 0. 5.
максимального размера? Перелить из B в A. 5. 0. Налить B. 5. 5.
9? Перелить из B в A. 7. 3. Вылить из A. 0.
10Прямоугольник m?n мы будем делить до 3. Перелить из B в A. 3. 0. Налить B. 3.
тех пор, пока m не станет равна n! While 5. Перелить из B в A. 7. 1. Вылить из A.
(m<>n) do begin If (m>n) then 0. 1. Перелить из B в A. 1. 0. Налить B.
m:=(m-n) else n:=(n-m); end; Как же 1. 5. Перелить из B в A. 6. 0. Налить B.
посчитать количество квадратов, на которые 6. 5. Перелить из B в A. 7. 4. Вылить из
мы разрежем таким образом прямоугольник? A. 0. 4. Перелить из B в A. 4. 0. Налить
11i:=1; while (m<>n) do begin if B. 4. 5. Перелить из B в A. 7. 2.
(m>n) then m:=(m-n) else n:=(n-m); 26Действие. А=5л. B=7л. Налить B. 0. 7.
i:=i+1; end; Перелить из B в A. 5. 2. Для этого
12Задача №2 «Кузнечик». Кузнечик может достаточно поменять сосуды местами. Хотя в
выполнять следующие команды: Вперед 2 данном случае можно обойтись всего двумя
Назад 2. Какие значения может принимать переливаниями (2=7*1-5*1).
координата кузнечика? 27Таким образом, для выявления более
13Вперед 2 Назад 2. Нод(2,2)=2. экономичного представления необходимо
Координата кузнечика может быть равна: … сравнить число переливаний в случае, когда
-6 -4 -2 0 2 4 6 … с помощью меньшего сосуда наполняют
14Вперед 3 Назад 3. Нод(3,3)=3. больший, с числом переливаний в противном
Координата кузнечика может быть равна: … случае и выбрать наилучшее решение.
-9 -6 -3 0 3 6 9 … 28Существует быстрый алгоритм нахождения
15Вперед 6 Назад 3. Нод(3,6)=3. наибольшего общего делителя, который
Координата кузнечика может быть равна: … благодаря своим особенностям , допускает
-9 -6 -3 0 3 6 9 … более эффективную реализацию на
16Вперед 7 Назад 5. Нод(7,5)=1. компьютере, нежели рассмотренные ранее
Координата кузнечика может быть равна: …-4 алгоритмы. D:=1; while оба числа a и b
-3 -2 -1 0 1 2 3 4 … Демонстрация четные do begin a:=a div 2; b:=b div 2;
«кузнечик». end; while оба числа a и b отличны от нуля
17Задача № 3 «Водолей! Имеются два do begin if одно из a,b отличны от нуля do
сосуда емкостью A и B литров каждый и begin if одно из a, b четное then поделить
неограниченный источник воды. его на 2 else заменить большее из а,b их
Первоначально оба сосуда пусты. Требуется разностью end; nod:=(ненулевое из a, b)*d
набирая воду в эти сосуды и переливая из end;
одного в другой, получить в каком-либо из 29d:=1; While a<>0 and b<>0
них требуемое количество воды за do begin If not odd(a) and odd(b) then
наименьшее число переливаний. При этом begin a:=a div 2; b:=b div 2; end else if
сосуды разрешается опорожнять только not odd(a) and odd(b) then a:=a div 2 else
полностью! if odd(a) and not odd(b) then b:=b div 2
18Пусть, например, сосуды имеют емкости else if (odd(a) and odd(b) and (a>=b)
5 и 7 литров соответственно, а получить then a:=a-b else if odd(a) and odd(b) and
требуется один литр. Как это сделать? (a<=b) then b:=b-a; end; If (a=0) then
Демонстрация «Водолей». NOD1:=d*b else NOD:=d*a;
19Действие. A=7л. B=5л. Налить В. 0. 5. 30Домашнее задание. Какое минимальное
Перелить из В в А. 5. 0. Налить в. 5. 5. число (k>0) прямолинейных разрезов
Перелить из В в А. 7. 3. Вылить из А. 0. нужно произвести, чтобы разрезать
3. Перелить из В в А. 3. 0. Налить В. 3. прямоугольник m?n на равновеликие квадраты
5. Перелить из В в А. 7. 1. максимальной площади?
20Определим процедуру Налить_до_краев_А
Тема: «Применение алгоритма Евклида при решении задач ».ppt
http://900igr.net/kartinka/informatika/tema-primenenie-algoritma-evklida-pri-reshenii-zadach-78169.html
cсылка на страницу

Тема: «Применение алгоритма Евклида при решении задач »

другие презентации на тему «Тема: «Применение алгоритма Евклида при решении задач »»

«Пятый постулат Евклида» - Исследования Януша Больяй. Неприступная "крепость" пятого постулата осталась непокоренной. Гаусс обратился к теории параллельных в 1792 г. Какой геометрией описывается наш мир? Исследования Саккери. Исследования Гаусса. В каком мире мы живем? Результаты Яноша Больяя были сжато изложены в 1832 г.

«Типы алгоритмов» - Линейные алгоритмы. Каждая переменная имеет имя, значение и тип. Основные типы алгоритмов. Какое расстояние прошел автомобиль? № 2. В магазине купили 2 кг яблок и 1,5 кг апельсинов. Если значением переменной является только целое число, то переменная называется целочисленной. Сколько заплатили за всю покупку?

«Решение алгоритмов» - 1984 – полиномиальный МВТ (Кармаркар). Алгоритмы центрального пути. Параметры управления алгоритмом. Вариант приближенного метода. 1947 – симплекс-метод (Данциг). Аффинно-масштабирующие алгоритмы. Пара взаимно-двойственных задач линейного программирования. Методы решения вспомогательной задачи. Метод сопряженных направлений.

«Геометрия Евклида» - Аксиоматика. Гиппократ Хиосский. Над входом в платоновскую Академию - надпись: «Да не войдёт сюда не знающий геометрии». Биография. Основное сочинение Евклида «Начала». Неевклидова геометрия. Февдий. "Евклид". Статуя Платона в Дельфах. Древнегреческий математик. Некоторые книги предваряются списком определений.

«Алгоритм уроки» - Например, распорядок дня. В жизни мы постоянно выполняем разные алгоритмы. Разветвляющийся. Понятие алгоритма – одно из фундаментальных в информатике. Физкультминутка. Проверка условия. В алгоритме встречаются повторяющиеся действия. Словами. Алгоритмическим языком – то есть учебным языком. Откройте графический редактор.

«Алгоритм задачи» - Составить действия мальчика в виде блок-схемы. Разветвляющийся алгоритм. ЗАДАЧА: составить графический алгоритм наполнения ведра водой из бочки. Алгоритм с повторением (циклический). Нужно ли соблюдать порядок в алгоритме? Из каких компонентов состоит? Воспроизвести по памяти. Надеть ведро на третий шар.

Алгоритм

31 презентация об алгоритме
Урок

Информатика

130 тем
Картинки
900igr.net > Презентации по информатике > Алгоритм > Тема: «Применение алгоритма Евклида при решении задач »