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



Уроки 21 - 22
Цикл с условием. Цикл с переменной
§58. Циклические алгоритмы




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

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

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

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

Вложенные циклы

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

Задачи (1 - 16)

Задачи (17 - 32)


Вложенные циклы


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

Предположим, что нужно найти все простые числа в диапазоне от 2 до 1000. Простейший (но не самый быстрый) алгоритм решения такой задачи на псевдокоде выглядит так:

Как же определить, что число простое? Как известно, простое число делится только на 1 и само на себя. Если число n не имеет делителей в диапазоне от 2 до n-1, то оно простое, а если хотя бы один делитель в этом интервале найден, то составное.

Чтобы проверить делимость числа n на некоторое число k, нужно взять остаток от деления n на k. Если этот остаток равен нулю, то n делится на k. Таким образом, программу можно записать так (здесь n, k и count — целочисленные переменные, count обозначает счётчик делителей):

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

Чтобы ещё ускорить работу цикла, заметим, что когда найден хотя бы один делитель, число уже заведомо составное, и искать другие делители в данной задаче не требуется. Поэтому можно закончить цикл. Для этого в условие работы цикла добавляется условие count = 0, связанное с имеющимся условием с помощью операции «И»:

На первом шаге (при i = 1) переменная k принимает единственное значение

В любом вложенном цикле переменная внутреннего цикла изменяется быстрее, чем переменная внешнего цикла. Рассмотрим, например, такой вложенный цикл:

На первом шаге (при i = 1) переменная k принимает последовательно значение 1. Далее, при i = 2 переменная k принимает последовательно значения 1 и 2. На следующем шаге при i = 3 переменная k проходит значения 1, 2 и 3, и т. д.

Следующая страница Вопросы и задания



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







Наверх