§ 20. Программирование циклических алгоритмов | Алгоритм Евклида

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень)


Уроки 35 - 41
§ 20. Программирование циклических алгоритмов




Содержание урока

Как организовать цикл?

Циклы с предусловием

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

Циклы в других языках программирования

Обработка потока данных

Циклы с постусловием

Циклы по переменной

Циклы по переменной в других языках программирования

Выводы. Интеллект-карта

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

Практическая работа № 15 «Циклы с условием»

Практическая работа № 16 «Алгоритм Евклида»

Практическая работа № 17 «Обработка потока данных»

Практическая работа № 18 «Циклы с постусловием»

Практическая работа № 19 «Циклы по переменной»


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


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

Алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на их разность до тех пор, пока они не станут равны. Полученное число и есть их НОД.

Этот вариант алгоритма работает довольно медленно, если одно из чисел значительно меньше другого, например для пары чисел 2 и 2014. Значительно быстрее выполняется улучшенный (модифицированный) алгоритм Евклида.

Модифицированный алгоритм Евклида для натуральных чисел: заменять большее из двух заданных чисел на остаток от деления большего на меньшее, пока этот остаток не станет равен нулю. Тогда второе число и есть их НОД.

Мы видим, что здесь тоже нужно выполнять некоторые операции несколько раз, причём сколько раз — заранее неизвестно. Но нас выручит цикл с условием, ведь мы знаем, когда нужно остановиться — когда какое-нибудь из двух чисел станет равно нулю.

Запишите условие, которое означает «одно из значений переменных а или b равно нулю». После этого запишите обратное условие.

Теперь мы готовы записать цикл:

Обратите внимание, что цикл содержит только один условный оператор, поэтому слова begin и end, ограничивающие тело цикла в программе на Паскале, можно не писать.

Остаётся вывести результат — ненулевое значение переменной а или b.

Запишите условный оператор, который выводит результат, проверяя одну из переменных на равенство нулю.

Из двух переменных, а и b, одна равна нулю, а вторая — не ноль. Запишите арифметическое выражение, которое всегда равно второй (ненулевой) переменной.

Количество шагов такого цикла заранее неизвестно и зависит от исходных данных. Дополним программу так, чтобы она считала ещё и количество сделанных шагов цикла. Для этого нужно ввести переменную-счётчик целого типа. Перед началом цикла счётчик обнуляется (в него записывается ноль), и на каждом шаге цикла значение счётчика увеличивается на единицу:

Вместо многоточия нужно вставить условный оператор, как и в предыдущем варианте программы. В цикле теперь находятся два оператора, поэтому в программе на Паскале нужно использовать составной оператор, ограниченный служебными словами begin и end.

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



Cкачать материалы урока








Наверх