Основные алгоритмические конструкции

АЛГОРИТМИЧЕСКАЯ КОНСТРУКЦИЯ ПОВТОРЕНИЕ

ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

Ключевые слова

• повторение
• циклические алгоритмы
• тело цикла
• цикл

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

Повторение

Повторение - последовательность действий, выполняемых многократно.

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

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

Типы циклов

Могут быть

Заданы условия

продолжения работы

Заданы условия

окончания работы

Пока есть кирпич

Пока не наступит ночь

Задано число

повторений

Ровно 100 кирпичей

Цикл с заданным условием продолжения работы

(цикл-ПОКА, цикл с предусловием)

нц пока

кц

нет

Условие

да

Тело цикла

Погрузка кирпичей

алг погрузка

нач

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

взять один кирпич

если кирпич целый

то положить кирпич в машину

иначе отложить кирпич в сторону

все

кц

кон

Робот в коридоре

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

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

вправо

закрась

кц

= y да r:= r - y q:= q +1 q, r Конец " width="640"

Частное и остаток

Начало

Список данных

x, y, r, q - цел

x, y

r:=x

q:=0

нет

r = y

да

r:= r - y

q:= q +1

q, r

Конец

= y q := 0 5 r =y 6 r := r – y 7 q := q +1 8 r =y 9 r := r – y 10 q := q +1 11 r =y 12 r := r – y 13 q := q +1 17 r =y 18 Вывод r 19 Вывод q 17 5 17 17 5 17 5 17 0 17 17 5 (Да) 0 17 5 12 12 1 5 17 12 5 (Да) 5 7 17 1 5 7 17 2 7 5 (Да) 5 2 2 17 5 3 2 17 2 5 (Нет) 2 3 " width="640"

Таблица значений переменных

Шаг алгоритма

Операция

1

Переменная

Ввод x

x

2

y

Ввод y

3

r

r := x

4

q

Условие

r = y

q := 0

5

r =y

6

r := r – y

7

q := q +1

8

r =y

9

r := r – y

10

q := q +1

11

r =y

12

r := r – y

13

q := q +1

17

r =y

18

Вывод r

19

Вывод q

17

5

17

17

5

17

5

17

0

17

17 5 (Да)

0

17

5

12

12

1

5

17

12 5 (Да)

5

7

17

1

5

7

17

2

7 5 (Да)

5

2

2

17

5

3

2

17

2 5 (Нет)

2

3

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

(цикл-ДО, цикл с постусловием)

Тело цикла

Условие

нет

да

Запись на алгоритмическом языке:

нц

кц при

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

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

алг четверостишие

нач

нц

прочитать четверостишие по книге 1 раз

прочитать четверостишие наизусть

кц при не сделал ошибку

кон

Вычисление значения переменной b

Начало

Список данных

a, b - цел

a := 1

b := 1

a := a *2

b := b + a

a = 8

да

b

нет

Конец

Таблица значений переменных

Шаг алгоритма

Операция

Переменные

1

a := 1

a

2

3

b := 1

b

Условие

a = 8

a := a * 2

4

b := b+a

5

a = 8

6

a := a * 2

7

b := b+a

8

9

a = 8

10

a := a * 2

b := b+a

11

a = 8

1

1

1

2

1

2

3

2 = 8 (Нет)

4

3

4

7

4 = 8 (Нет)

8

7

8

15

8 = 8 (Да)

= 25 да i нет Конец " width="640"

Задача о тренировках

План тренировок:

В 1-й день пробежать 10 км.

Каждый следующий день увеличивать расстояние на 10% от результата предыдущего дня.

Как только дневной пробег достигнет или превысит 25 км, прекратить увеличение и пробегать 25 км ежедневно.

Начиная с какого дня спортсмен будет пробегать 25 км?

Начало

Список данных

i – цел

x – вещ

i := 1

x := 10

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

i := i +1

x := x +0.1* x

x = 25

да

i

нет

Конец

Цикл с заданным числом повторений

(цикл-ДЛЯ, цикл с параметром)

i = i 1 , i 2

Тело цикла

Запись на алгоритмическом языке:

нц для i от i1 до i2 шаг R

кц

Цикл с заданным числом повторений

алг переправа

нач

нц для i от 1 до 5

два мальчика переправляются на противоположный берег.

один мальчик высаживается на берег

другой мальчик плывёт обратно

солдат переправляется через реку

мальчик возвращается на исходную позицию

кц

кон

Вычисление степени

Начало

y=a n

Список данных

i, n – цел

a, y - вещ

a, n

y := 1

i = 1 , n

y

y := y * a

Конец

Таблица значений переменных

Шаг алгоритма

Операция

1

Переменная

a

Ввод a, n

2

n

y := 1

3

y

i := 1

4

Условие

i = n

i

i

5

y := y * a

6

i := i + 1

7

i

8

y := y * a

9

10

i := i + 1

i

11

y := y * a

12

i := i + 1

13

i

3

4

4

3

1

1

4

1

3

1

4

1

4

3

4

3

4

2

2

3

4

2

16

16

3

3

4

3

64

3

4

3

4

4

64

3

4

Повторение

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

нц раз

кц

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

алг

нач

нц 5 раз

вправо; закрасить

кц

кон

Самое главное

Для записи любого алгоритма достаточно трёх основных алгоритмических конструкций (структур): следования, ветвления, повторения.

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

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

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

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

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

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

3) цикл с заданным числом повторений.

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

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

Размеры области неизвестны.

Определите значения переменных n и m после

выполнения фрагмента алгоритма

Объявлен набор в школьную баскетбольную команду. Известен рост каждого из N учеников, желающих попасть в эту команду.

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

Запас рыбы в пруду оценён в А тонн. Ежегодный прирост рыбы составляет 15%. Ежегодный план отлова - В тонн. Наименьший запас рыбы составляет С тонн. (Запас ниже С тонн уже не восстанавливается.) Составьте блок-схему алгоритма для подсчёта количества лет, в течение которых можно выдерживать заданный план.

Население города Н увеличивается на 5%ежегодно. В текущем году оно составляет 40 000 человек.

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

Одноклеточная амёба каждые три часа делится на 2 клетки. Составьте алгоритм вычисления времени, через которое будет Х амёб.

Сумма 10 000 рублей положена в сберегательный банк, при этом прирост составляет 5%годовых. Составьте алгоритм, определяющий, через какой промежуток времени первоначальная сумма увеличится в два раза.

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

а) из повседневной жизни;

б) из литературного произведения;

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

Каждая бактерия делится на две в течение 1 минуты. В начальный момент имеется одна бактерия.

Составьте блок-схему алгоритма вычисления количества бактерий через 10 минут.

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

Составьте алгоритм нахождения произведения z двух

натуральных чисел x и y без использования

операции умножения.

Дана последовательность 5, 9, 13, 17, ... .

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

Составьте алгоритм для определения количества цифр в

записи произвольного натурального числа.

Начало

*

n,m

m := m -2

n := n *2

Да

Нет

m

n,m

Конец

Опорный конспект

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

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

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

Тип цикла

С заданным

условием

продолжения

работы

С заданным

условием

окончания

работы

С заданным

числом

повторений

Цикл - ПОКА

Цикл - ДО

Цикл - ДЛЯ