Как составить алгоритм повторения чисел

План урока:

Циклы, их виды

Повторение в программировании

Сравнение цикличных структур 

С повторяющимися действиями мы сталкиваемся и в обычной жизни и при решении задач. Проход стрелок часов каждую минуту, секунду, час, смена дня и ночи, ежедневные сборы в школу, еженедельная смена уроков, ежегодные поездки на море – примеров циклов повторения миллиарды. Несмотря на разнообразие происходящих процессов, большинство из них можно описать простыми конструкциями. Делая что-то раз за разом, мы не задумываемся, что ученые уже написали алгоритмы с повторением или циклы универсальными способами.

Циклы, их виды

Многие операции, действия выполняются однотипно много раз. Этот процесс повторения называют циклом, а повторяемая последовательность – телом цикла. Процедуру с повторяющимися этапами называют циклической.

Каждое повторение действий в алгоритмах – итерация.

 

Выделяют 3 основных вида повторяющихся структур:

• с условием выполнения цикла (предусловием);
• с критерием завершения (постусловием);
• с указанным числом повторений цикла.

Описывать подобные процессы удобно схематично или при помощи команд.

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

Данную конструкцию еще встречается как «цикл-пока», потому что пока выполняется условием, программа/исполнитель будет проходить шаги снова и снова.Описанный критерий, логическое сравнение – причина начала прохождения повторяемых шагов/команд.

Описание цикла с условием двумя способами:

Порядок выполнения:

• Проверка критерия/логического сравнения.
• Пока результат «Да», «проигрывать по кругу» однотипные операции.
• Если ответ на условие отрицательный, закончить процедуру.

Особенность этой конструкции – существуют такие условия, когда команды не будут выполнены ни разу.

Циклический алгоритм, примеры:

• Написать алгоритм постройки забора из кирпичей высотой 2 м.

алг забор

нач

нц пока есть кирпичи и раствор цемента

если высота забора < 2,0 м

то намазать слой цемента

положить слой кирпичей

иначе сделать сверху декоративный слой

все

кц

кон

• Нарисовать шуточный (но действующий) алгоритм покраски забора «от начала и до обеда.

 

• Написать алгоритм вычисления частного и остатка от числа, не используя операции деления. В программе используются целые числа.

Заменим деление вычитанием, будем выполнять отнимание, пока остаток не будет меньше вычитаемого – условие выполнения. Число вычитаний и будет частному от деления, это счетчик цикла, а разность, выполненная в последний раз – остаток от деления.

Обозначим x – делимое, y – делитель, q – частное от деления, r – остаток.

Особенности цикла-Пока:

• Если условие ни разу не выполняется, то команды из тела не будут выполнены ни разу. Это нормально, это один из вариантов – нет необходимости в выполнении команд.
• Если же условие всегда истинно, тело операции будут выполняться бесконечное число раз. Такое положение называется зацикливанием. Фактически программа «зависает» и не сможет завершиться сама. Рекомендуется предусмотреть этот вариант.

Циклический алгоритм с постусловием

Такую конструкцию называют «цикл-До». Здесь условие является основанием окончания выполнения команд из тела, то есть, они выполнятся хотя бы раз, даже если условие ложно.

Порядок выполнения цикла с заданным условием:

• Выполнение команд из тела.
• Проверка условия (сравнения определенной величины с заданной).
• Пока ответ на условие «Нет», повторять описанные в теле операции/шаги.
• Если ответ на условие положительный, закончить процедуру.

Описание структуры с постусловием языком блок-схем и на алгоритмическом языке:

Особенности циклов с заданным условием окончания работы:

• Будет хотя бы одно выполнение процедуры;
• Условие описывает завершение повторяемых действий.

Пример: написать программу покраски забора.

Блок схема циклического алгоритма.

Цикл с параметром

Используется для задач, в которых известно количество повторений однотипных шагов, то есть заранее известно, сколько раз нужно выполнить действия. Параметр в этой процедуре– количество повторений цикла(счетчик повторов).

Особенность алгоритмической конструкции повторение с параметром – не бывает зацикливаний, ведь после выполнений указанного числа повторов процесс остановится.

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

Пример: написать алгоритм разгрузки и переноса 15 мониторов из авто в компьютерный класс.

Повторение в программировании

Не нужно недооценивать изучение простейших алгоритмических конструкций. Следование, ветвление, повторение – важные конструкции, операторы, используемые в программировании.

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

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

 

Цикл начала работы в программировании

Так, описанная выше команда в программировании обозначается словом While. Этот оператор обозначает многократное прохождение участка кода. Это очень востребованная операция.

“While” обозначает на английском “пока”. Но не как прощание, а как то, что «делается пока, что-то происходит/выполняется». Этот оператор используется во всех языках программирования, использующих структурный подход (Pascal, Python). Обобщено его записывают так:

Как видим, это очень похоже на запись на алгоритмическом языке – написанное просто, структурировано и понятно.

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

 

Цикл окончания работы в программировании

Для записи такой повторяемой конструкции в языках программирования используется оператор repeat. После него следуют команды (тело), после – оператор until, обозначающий условие окончание процесса.

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

Источник

Цикл со счетчиком в программировании

Для описания цикла с заданным повторением применяют оператор for.

Общий вид блока на языке программирования:

Программа проходит команды из тела и значение счетчика (параметра) становится больше на 1. Чтобы выйти из цикла с фиксированным числом повторений, нужно достичь максимума параметра, который указан в условии задачи.

Сравнение цикличных структур

Блок-схемы повторяющихся алгоритмов позволяют оценить подобие всех 3 видов:

• обязательное наличие условия (для оператора с параметром – это число повторений);
• серия однотипных команд/шагов.

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

Хотя все алгоритмы циклической структуры описывают повторяющиеся шаги, у них много отличий.

Цель: изучение алгоритмической структуры циклы, создание моделей и алгоритмов для решения практических задач.

Ход урока

I. Актуализация знаний

• Повторить понятие алгоритма, основные конструкции алгоритмического языка.
• Уметь разрабатывать математическую модель, алгоритм и блок схему решения задачи.
• Иметь понятие о языках программирования и их назначении.
• Уметь работать в среде программирования.
• Знать структуры программы.
• Уметь записывать выражения, содержащие числовые и символьные величины.
• Знать структуры операторов и особенности их работы.
• Уметь применять операторы при написании программ с линейными и ветвящимися структурами.
• Уметь на компьютере создавать и запускать программы на отладку.

II. Теоретический материал урока

Большинство практических задач требует многократного повторения одних и тех же действий, т. е. повторного использования одного или нескольких операторов. (Презентация)

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

Другой пример. Чтобы найти фамилию человека в списке, надо проверить первую фамилию списка, затем вторую, третью и т.д. до тех пор, пока не будет найдена нужная или не будет достигнут конец списка. Преодолеть подобные трудности можно с помощью циклов.

Циклом называется многократно исполняемый участок алгоритма (программы). Соответственно циклический алгоритм — это алгоритм, содержащий циклы.

Различают два типа циклов: с известным числом повторений и с неизвестным числом повторений. При этом в обоих случаях имеется в виду число повторений на стадии разработки алгоритма.

Существует 3 типа циклических структур:

• Цикл с предусловием;
• Цикл с послеусловием;
• Цикл с параметром;

Иначе данные структуры называют циклами типа «Пока», «До», «Для».

Графическая форма записи данных алгоритмических структур:

Цикл с предусловием (иначе цикл пока) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Пока (условие) нц серия команд кц		while условие do begin             серия команд; end;

где

условие – выражение логического типа.

Цикл может не выполняться ни разу, если значение логического выражения сразу же оказывается ложь.

Серия команд, находящихся между begin и end, выполняются до тех пор, пока условие истинно.

Для того чтобы цикл завершился, необходимо, чтобы последовательность инструкций между BEGIN и END изменяла значение переменных, входящих в условие.

Цикл с постусловием (иначе цикл до) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
В алгоритмическом языке нет команды которая могла бы описать данную структуру, но ее можно выразить с помощью других команд (Например, ветвления).		repeat серия команд until условие

где

условие – выражение логического типа.

Обратите внимание:

Последовательность инструкций между repeat и until всегда будет выполнено хотя бы один раз;

Для того чтобы цикл завершился, необходимо, чтобы последовательность операторов между repeat и until изменяла значения переменных, входящих в выражение условие.

Инструкция repeat, как и инструкция while, используется в программе, если надо провести некоторые повторяющиеся вычисления (цикл), однако число повторов заранее не известно и определяется самим ходом вычисления.

Цикл с параметром (иначе цикл для) имеет вид:

Форматы записи операторов алгоритма	Блок-схема	Форматы записи операторов на Паскале
Для i от а до b шаг h делай       Нц            Серия команд       кц		h = +1 for i:= a to b do      begin        серия команд      end; h = -1 for i:= b downto a do      begin        Cерия команд;      end;

где

i – параметр цикла;
a – начальное значение цикла;
b – конечное значение цикла;
h – шаг изменения параметра.

Структура данного цикла иначе называют циклом i раз.

Эта команда выполняется таким образом: параметру i присваивается начальное значение а, сравнивается с конечным значением b и, если оно меньше или равно конечному значению b, выполняется серия команд. Параметру присваивается значение предыдущего, увеличенного на величину h – шага изменения параметра и вновь сравнивается с конечным значением b.

На языке программирования Паскаль шаг изменения параметра может быть равным одному или минус одному.

Если между begin и end находится только один оператор, то операторные скобки можно не писать. Это правило работает для цикла типа «Пока» и «Для».

Рассмотрим пример решения задач с использованием данных структур

Пример.

Вычислить произведение чисел от 1 до 5 используя различные варианты цикла

Математическая модель:

Р= 1· 2· 3· 4· 5=120

Составим алгоритм в виде блок-схемы.

Для проверки правильности алгоритма заполним трассировочную таблицу.

Шаг	Операция	Р	i	Проверка условия
1	P:=1	1
2	i:=1;	1	1
3	i<=5 P:=P*I i:=i+1	1	1	1<=5, да (истина)
4	i<=5 P:=P*I i:=i+1	2	2	2<=5, да (истина)
5	i<=5 P:=P*I i:=i+1	6	3	3<=5, да (истина)
6	i<=5 P:=P*I i:=i+1	24	4	4<=5, да (истина)
7	i<=5 P:=P*I i:=i+1	120	5	5<=5, да (истина)
8	i<=5 P:=P*I i:=i+1			6<=5, нет (ложь)

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

Шаг первый: Р присваивается значение один.

Шаг второй: i присваивается значение один.

Шаг третий: при i равном единице проверяем условие один меньше или равен пяти, да, условие истинно, значит Р присваивается значение один умноженное на один, будет два. Для i: один плюс один, будет два.

Шаг четвертый: при i равном двум проверяем условие два меньше или равен пяти, да, условие истинно, значит Р присваивается значение 2 умноженное на один, будет 2. Для i: два плюс один, будет три.

Шаг пятый: при i равном трем проверяем условие три меньше или равен пяти, да, условие истинно, значит Р присваивается значение два умноженное на три, будет шесть. Для i: три плюс один, будет четыре.

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

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

Шаг восьмой: при i равном шести проверяем условие шесть меньше или равен пяти, нет, условие ложно, тогда мы выходим из цикла, а в результате получаем последнее значение равное сто двадцати.

Program Pr1;
Var i: integer;
Begin
P:=1;
i:=1;
While i<=5 do
       begin
           P:=P*i;
           i:=i+1;
       end;
Write (‘P=’, P);
end.

Для цикла с постусловием построим блок-схему и трассировочную таблицу. (слайд16)

В результате получаем последнее значение равное сто двадцати на седьмом шаге

И для Цикла с параметром построим блок-схему и трассировочную таблицу. (слайд17)

В результате получаем последнее значение равное сто двадцати на шестом шаге

Задача:

Вывести на экран числа от 1 до 5 в:

1. прямом порядке;
2. обратном порядке.

Математическая модель:

1. 1 2 3 4 5;
2. 5 4 3 2 1.

Блок-схема и программа решения задачи представлена для чисел в прямом порядке и обратном порядке.

(слайд 21)

Запишем рассмотренные алгоритмы на языке программирования Паскаль.

(слайд 22)

III. Подведение итогов урока

И так мы рассмотрели следующие вопросы:

1. Алгоритмическая структура цикл;
2. Виды алгоритмических структур:
   1. Цикл с предусловием;
   2. Цикл с послеусловием;
   3. Цикл с параметром;
3. Рассмотрели способы записи данных структур;
4. Разобрали примеры решения задач с помощью этих структур.

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

В зависимости от способа организации повторений различают три типа циклов:

1) цикл с заданным условием продолжения работы;
2) цикл с заданным условием окончания работы;
3) цикл с заданным числом повторений.

Цикл с заданным условием продолжения работы (цикл-ПОКА, цикл с предусловием)

Логика работы этой конструкции описывается схемой, показанной на рис. 2.10.

На алгоритмическом языке эта конструкция записывается так:

нц пока <условие>
    <тело цикла (последовательность действий)>
кц

Выполняется цикл-ПОКА следующим образом: 1) проверяется условие (вычисляется значение логического выражения); 2) если условие удовлетворяется (Да), то выполняется тело цикла и снова осуществляется переход к проверке условия; если же условие не удовлетворяется, то выполнение цикла заканчивается. Возможны случаи, когда тело цикла не будет выполнено ни разу.

Пример 1

Алгоритм, по которому из всех имеющихся кирпичей отбираются целые кирпичи и складываются в машину.

алг отбор
нач
  нц пока есть кирпичи
    взять один кирпич
    если кирпич целый
      то положить кирпич в машину
    иначе отложить кирпич в сторону
    все
  кц кон

Пример 2

Правее Робота (клетка со звёздочкой) расположен коридор неизвестной длины. Необходимо, чтобы Робот закрасил все клетки этого коридора.

Пока будет выполняться условие справа свободно, Роботу следует выполнять команды:

вправо
закрась

Соответствующий алгоритм для Робота будет иметь вид:

нц пока справа свободно
  вправо
  закрась
кц

Пример 3 

Требуется, не пользуясь операцией деления, получить частное q и остаток r от деления натурального числа х на натуральное число у.

Представим операцию деления как последовательные вычитания делителя из делимого. Причём вычитать будем до тех пор, пока результат вычитания не станет меньше вычитаемого (делителя). В этом случае количество вычитаний будет равно частному от деления q, а последняя разность — остатку от деления r.

Исполним этот алгоритм для х = 23 и у = 5.

Цикл с заданным условием окончания работы (цикл-ДО, цикл с постусловием)

Логика работы этой конструкции описывается схемой, показанной на рис. 2.11.

На алгоритмическом языке эта конструкция записывается так:

нц
  <тело_цикла (последовательность действий)>
кц при <условие>

Выполняется цикл-ДО следующим образом: 1) выполняется тело цикла; 2) проверяется условие (вычисляется значение логического выражения); если условие не удовлетворяется («Нет»), то снова выполняется тело цикла и осуществляется переход к проверке условия; если же условие удовлетворяется, то выполнение цикла заканчивается. В любом случае тело цикла будет выполнено хотя бы один раз.

Пример 4

Алгоритм по выучиванию наизусть четверостишия.

алг четверостишие
нач
  нц
    прочитать четверостишие по книге 1 раз
    рассказать четверостишие
  кц при не сделал ошибку кон

Пример 5

Вычислим значение переменной b согласно следующему алгоритму:

Составим таблицу значений переменных, задействованных в алгоритме:

Ответ: b = 255.

Пример 6 

Спортсмен приступает к тренировкам по следующему графику: в первый день он должен пробежать 10 км; каждый следующий день следует увеличивать дистанцию на 10% от нормы предыдущего дня. Как только дневная норма достигнет или превысит 25 км, необходимо прекратить её увеличение и далее пробегать ежедневно ровно 25 км. Начиная с какого дня спортсмен будет пробегать 25 км?

Пусть х — количество километров, которое спортсмен пробежит в некоторый i-й день. Тогда в следующий (i + 1)-й день он пробежит х + 0,1х километров (0,1х — это 10% от х).

Цикл с заданным числом повторений (цикл-ДЛЯ, цикл с параметром)

Логика работы этой конструкции описывается схемой, показанной на рис. 2.12.

На алгоритмическом языке эта конструкция записывается так:

нц для i от i1 до i2 шаг R
  <тело цикла (последовательность действий)>
кц

В цикле-ДЛЯ всегда есть параметр цикла — величина целого типа, изменяющаяся в ходе выполнения цикла от своего начального значения il до конечного значения i2 с шагом R.

Выполняется цикл-ДЛЯ следующим образом: 1) параметру цикла присваивается начальное значение; 2) параметр цикла сравнивается с конечным значением; если параметр цикла не превышает конечное значение, то выполняется тело цикла, увеличивается значение параметра цикла на шаг и снова осуществляется проверка параметра цикла; если же параметр цикла превышает конечное значение, то выполнение цикла заканчивается.

Если величина шага в цикле с параметром равна единице, то шаг не указывают. Мы ограничимся рассмотрением именно таких циклов.

В отличие от двух предыдущих конструкций (цикл-ПОКА, цикл-ДО) цикл-ДЛЯ имеет строго фиксированное число повторений, что позволяет избежать зацикливания, т. е. ситуации, когда тело цикла выполняется бесконечно.

Пример 7 

Алгоритм переправы через реку воинского отряда из пяти человек. Солдаты могут воспользоваться помощью двух мальчиков — хозяев небольшой лодки, в которой может переправиться или один солдат, или два мальчика.

алг переправа
нач
  нц для i от 1 до 5
    два мальчика переправляются на противоположный берег
    один мальчик высаживается на берег, другой плывёт обратно
    солдат переправляется через реку
    мальчик возвращается на исходную позицию
  кц
кон

Пример 8

Составим алгоритм вычисления степени с натуральным показателем n для любого вещественного числа а.

По определению:

При составлении алгоритма воспользуемся единой формулой, в которой число умножений равно показателю степени:

Исполним этот алгоритм для а = 4 и n = 3.

Пример 9

Для исполнителя Робот цикл с известным числом повторений реализуется с помощью следующей конструкции:

нц <число повторений> раз
  <тело цикла>
кц

Так, если правее Робота не встретится препятствий, то, выполнив приведённый ниже алгоритм, он переместится на пять клеток вправо и закрасит эти клетки:

алг
нач
  нц 5 раз
    вправо; закрасить
  кц
кон

Задание:

Приведите пример циклического алгоритма:

а) из повседневной жизни;
б) из литературного произведения;
в) из любой предметной области, изучаемой в школе.

Записать в тетрадь и отправить фото в VK

Практические задания будут на следующем уроке!

 На этом уроке ты познакомишься с циклическими алгоритмами, научишься их составлять. 
Вспомни

 Что такое алгоритм? (Алгоритм – это последовательность действий, которая приводит к определённому результату)

Какой алгоритм называют линейным? (Линейный алгоритм – это алгоритм, в котором действия выполняются последовательно в определённом порядке, друг за другом)

Что такое разветвляющийся алгоритм? (Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от поставленного условия выполняется та или иная последовательность команд (действий).

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

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

Таким образом, форма организации действий, при которой выполнение одной и той же последовательности команд повторяется, пока выполняется некоторое заранее установленное условие, называется циклом или повторением.

Алгоритм, содержащий циклы, называется циклическим алгоритмом, 

Алгоритм, содержащий циклы, называется циклическим алгоритмом, или алгоритмом с повторениями.

Ситуация, при которой выполнение цикла никогда не заканчивается, называется зацикливанием.

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

Обратите внимание!!! При составлении алгоритмов нельзя допускать зацикливания.

Рассмотрим ещё один пример алгоритма с повторениями.

Таню мама попросила собрать все красные помидоры. Таня взяла корзину и пошла в огород на грядку с помидорами.

Опишем последовательность действий Тани:

Сорвать красный помидор,

Положить помидор в корзинку,

Сорвать красный помидор,

Положить помидор в корзинку,

То есть Таня будет повторять действия «Сорвать красный помидор», и «Положить помидор в корзинку» пока не соберёт все красные помидоры.

Представим данный алгоритм с помощью блок-схемы:

Начало алгоритма;

Выполняемое действие (Подойти к грядке с помидорами);

Условие выполнения (Остались красные помидоры?)

Если да, то выполнять действия (сорвать красный помидор, положить помидор в корзинку). Если нет красных помидор, то пойти к маме.

Конец алгоритма.

То есть Таня действовала по алгоритму с повторениями. При его исполнении действия «Сорвать красный помидор» и «Положить помидор в корзинку» будут выполнены столько раз, сколько красных помидор на грядке.

Запомни: алгоритм с повторениями – это алгоритм, содержащий команды, которые повторяются, пока выполняется заданное условие.

Закрепи материал, выполнив задание. Обрати внимание при выполнении необходима регистрация (введи фамилию и имя)