Уроки 20 - 24
Основы алгоритмизации

Практикум

---

Циклические алгоритмы

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

Выполнив задания этой темы, вы научитесь:

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

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

В цикле с предусловием сначала проверяется выполнение условия продолжения цикла. Если условие истинно (да, true), то выполняется тело цикла, а иначе (нет, False) цикл завершается. Особенностью этого цикла является то, что если при 1-й проверке условие ложно, то тело цикла не выполнится ни разу.

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

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

Блок-схемы алгоритмов, содержащих циклы, легко узнаваемы, так как содержат возврат на предыдущие блоки («петлю»). Во всех языках программирования есть специальные операторы, реализующие этот цикл.

Задание 8.7

Существуют простые правила определения делимости чисел на числа 3, 4, 5:

♦ на 3 без остатка делятся числа, сумма цифр которых делится на 3; 
♦ на 4 без остатка делятся числа, у которых две последние цифры составляют число, делящееся на 4;
♦ на 5 без остатка делятся числа, заканчивающиеся на цифры 5 и 0.

Впервые эти правила были сформулированы в знаменитой «Книге Абака» итальянского математика Леонардо Фибоначчи (XII век). Требуется проверить делимость введенных чисел на 3 по первому из перечисленных правил.

Словесный алгоритм

Начало алгоритма
1. Введите число.
2. Пока цифры числа не закончатся:
а) выделите очередную цифру как остаток от деления на 10;
б) прибавьте эту цифру к общей сумме;
в) удалите обработанную цифру из числа, получив новое число в виде частного от деления на 10.
3. Проверьте, делится ли полученная сумма на 3 без остатка:
• если делится, то сообщите, что исходное число делится на 3;
• иначе сообщите, что исходное число не делится на 3. Конец алгоритма
Конец алгоритма

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

На рис. 8.9 приведена блок-схема, составленная по словесному алгоритму.

Рис. 8.9. Блок-схема алгоритма (к заданию 8.7)

Алгоритм в виде программы

В табл. 8.13 приведена программа к заданию на алгоритмическом языке Кумир. В табл. 8.14 приведены тексты программ на языках Паскаль и Visual Basic. 

Таблица 8.13. Программа на Кумире с пояснениями (к заданию 8.7)

Таблица 8.14. Примеры программ на Паскале и Visual Basic (к заданию 8.7)

Задание 8.8

Леонардо из Пизы, известный как Фибоначчи, был первым из великих математиков Европы позднего Средневековья. Числовой ряд, носящий в наше время имя Фибоначчи, вырос из проблемы с кроликами, которую Фибоначчи изложил в своей «Книге Абака», написанной в 1202 году. Он выглядит так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,...

В этом ряду каждое следующее число, начиная с третьего, равно сумме двух предыдущих (рис. 8.10). Требуется составить алгоритм проверки принадлежности введенного числа ряду чисел Фибоначчи.

Словесный алгоритм

Начало алгоритма
1. Введите число.
2. Установите значение первых трех чисел Фибоначчи: 1,1,1 + 1 (сумма двух предыдущих чисел).
3. Пока введенное число больше очередного числа Фибоначчи, возьмите два последних числа и получите из них новое число Фибоначчи. 
4. Если число Фибоначчи, полученное по выходу из цикла, равно введенному (n) или было введено число п = 1, то сообщите «Да» (введено число Фибоначчи), в противном случае — сообщите «Нет» (введенное число не является числом Фибоначчи)
Конец алгоритма

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

На рис. 8.11 приведена блок-схема, составленная по словесному алгоритму.

Алгоритм в виде программы

В табл. 8.15 приведена программа на алгоритмическом языке Кумир.

Таблица 8.15. Программа на Кумире с пояснениями (к заданию 8.8)

В табл. 8.16 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.16. Примеры программ на Паскале и Visual Basic (к заданию 8.8)

Задание 8.9

В телевизионном эфире в США проводится марафон, цель которого — сбор средств для поддержки незащищенных слоев населения. Во время эфира слушатели отправляют на адрес студии телеграммы с указанием суммы пожертвования и цели, на реализацию которой пойдет эта сумма, например: «Посылаю 521$ в фонд помощи безработным. Смит».

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

Словесный алгоритм

Начало алгоритма
1. Запросите текст телеграммы.
2. Поместите текст в строку st.
3. Определите длину строки n.
4. Пока не закончатся все символы в строке или пока не встретится знак $,
рассмотрите три ситуации:
а) если символ — цифра, то получите цифровой эквивалент символа;
добавьте полученную цифру в следующую позицию числа,
из которого будет сформирована сумма пожертвования,
и перейдите к следующему символу, увеличив счетчик символов: i = i + 1;
б) если символ — «$», то установите признак окончания цифр d,
который будет признаком досрочного выхода из цикла;
в) если это другой символ (буква, знак препинания и т. п.), то перейдите
к следующему символу, увеличив счетчик символов: i = i + 1.
5. Проанализируйте признак окончания цифр d. Если он равен 1,
то сообщите сумму пожертвования, если нет — сообщите,
что указания о сумме пожертвования в телеграмме нет.
Конец алгоритма

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

На рис. 8.12 приведена блок-схема, составленная по словесному алгоритму.

Алгоритм в виде программы

В табл. 8.17 приведена программа на алгоритмическом языке Кумир.

Таблица 8.17. Программа на Кумире (к заданию 8.9)

В табл. 8.18 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.18. Примеры программ на Паскале и Visual Basic (к заданию 8.9)

Контрольные вопросы и задания

К заданию 8.7

1. Для чего нужны начальные установки в алгоритме?
2. Пройдите алгоритм по блок-схеме для числа 521 (см. рис. 8.9). Какое значение будет в переменных nl и Sum перед выходом из цикла?
3. Добавьте в любую из программ оператор вывода переменных cifra и Sum. Какое значение и сколько раз будет выведено для числа 222?
4. Что произойдет, если пользователь введет число п равным нулю?
5. Напишите комментарий к п. 9 программы на Кумире (см. табл. 8.13).

К заданию 8.8

1. Какие действия выполняются в блоке 6 (см. рис. 8.11) и соответствующем фрагменте программы на Кумире (см. табл. 8.15)?
2. Какое условие проверяется в данном алгоритме при входе в цикл с предусловием?
3. Запишите в тетради тело цикла с предусловием, используемое в данном алгоритме. 
4. Придумайте и запишите пример ситуации, когда тело цикла не выполняется ни одного раза.
5. В блоке 3 алгоритма (см. рис. 8.11) было введено число 5. Сколько раз выполнится тело цикла?
6. Напишите пояснение к строкам 2 и 3 программы на Кумире (см. табл. 8.15).
7*. В блоке 6 программы на Кумире (см. табл. 8.15) производится переприсваивание содержимого ячеек (предпредыдущей, предыдущей и текущей). Можно ли поменять местами операторы присваивания? Ответ обоснуйте.
8*. Можно ли в данном алгоритме обойтись только двумя переменными ƒ1 и ƒ2?

К заданию 8.9

1. В блоке 4 блок-схемы (см. рис. 8.12) определяется длина строки n. Для чего это делается? Где далее используется эта переменная?
2. В алгоритме используется цикл с предусловием. Может ли возникнуть такая ситуация, что тело цикла не исполнится ни разу? Придумайте и запишите в тетради пример телеграммы, текст которой приведет к такой ситуации.
3. Что произойдет в алгоритме, если в адрес телемарафона придет телеграмма из России: «Я пенсионерка, но хочу пожертвовать 3 доллара в фонд помощи бездомным животным. Татьяна». Предложите вариант алгоритма, учитывающего подобную ситуацию.
4. Добавится ли к сумме число, указанное в телеграмме: «Я родился в 1900 году, средств не имею, но считаю, что нужно помогать старикам. Джон»?
5*. Если вы отлаживаете программы на Паскале или на Visual Basic, упростите поиск упоминания доллара (знак или текст).
6. Что означает сложное условие sim >= "0" и sim <= "9" (см. п. 8 табл. 8.17)?
7. Чем различаются ветвления на блок-схеме и в примерах программ?

Циклические алгоритмы

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

Выполнив задания этой темы, вы научитесь:

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

Для реализации циклического алгоритма с известным числом повторений в блок-схемах используется специальный блок (см. блок 3 на рис. 8.13). Для программной реализации цикла с известным числом повторений используются специальные операторы.

Задание 8.10

Часто требуется обработать оценки, полученные учащимися или студентами в результате каких-либо испытаний (контрольной работы, экзамена). Обработка, как правило, сводится к подсчету количества хороших (или плохих) оценок, среднего балла, и к нахождению максимального показателя. Требуется смоделировать процесс ввода оценок с клавиатуры с одновременным набором статистики.

Словесный алгоритм

Начало алгоритма
1. Для каждого из учащихся проделайте следующие действия:
а) введите его оценку;
б) приплюсуйте ее к сумме оценок (для дальнейшего подсчета средней оценки);
в) сравните оценку с текущим максимумом: если они равны, то увеличьте счетчик
максимальных оценок; иначе, если оценка больше текущего максимума,
замените текущий максимум новой оценкой,
а счет лучших оценок начните заново.
2. Сообщите данные по накопленной статистике.
Конец алгоритма

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

 

Алгоритм в виде программы

В табл. 8.19 приведена программа на алгоритмическом языке Кумир.

Таблица 8.19. Программа на Кумире с пояснениями (к заданию 8.10)

В табл. 8.20 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.20. Примеры программ на Паскале и Visual Basic (к заданию 8.10)

Задание 8.11

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

Словесный алгоритм

Начало алгоритма
1. Введите текущую дату: день, месяц и год.
2. Для каждого месяца, начиная с текущего, проанализируйте, сколько в нем дней. Добавьте полученное число к общей сумме дней.
3. Вычтите из полученной суммы число дней, которые уже прошли в текущем месяце.
4. Сообщите количество дней до Нового года.
Конец алгоритма

    Иногда применение вложенных блоков принятия решения делает схему громоздкой. Здесь в блок-схему введен блок выбора по индексам месяцев. Этот блок применяется, когда вариантов выбора по условию больше двух. Он соответствует оператору Выбор (Case).

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

На рис. 8.14 приведена блок-схема, составленная по словесному алгоритму.

 

Алгоритм в виде программы

В табл. 8.21 приведена программа на алгоритмическом языке Кумир.  

Таблица 8.21. Программа на Кумире с пояснениями (к заданию 8.11)

В табл. 8.22 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.22. Примеры программ на Паскале и Visual Basic (к заданию 8.11)

Задание 8.12

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

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

Словесный алгоритм

Начало алгоритма
1. Запросите и введите строку, состоящую из цифр и знаков «+» и «—».
2. Определите длину строки.
3. Занесите числовой эквивалент первого символа (цифры) в сумму.
4. Для каждого символа строки проделайте следующее:
а) прочтите символ;
б) рассмотрите три ситуации:
если это символ «+», установите признак знака равным 1;
если это символ «—», то установите признак знака равным -1;
иначе (остается только символ-цифра) определите вес цифры и приплюсуйте ее к сумме с соответствующим знаком.
5. Выведите результат.
Конец алгоритма

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

На рис. 8.15 приведена блок-схема, составленная по словесному алгоритму. 

Рис. 8.15. Блок-схема алгоритма (к заданию 8.12)

Алгоритм в виде программы

В табл. 8.23 приведена программа на алгоритмическом языке Кумир. В табл. 8.24 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.23. Программа на Кумире с пояснениями (к заданию 8.12)

Контрольные вопросы и задания

К заданию 8.10

1. Определите по блок-схеме (см. рис. 8.13), сколько учеников участвовало в контроле знаний?
2. Что означает запись i = 1, 15, 1 в блоке, обозначающем цикл?
3. Что означает левая и правая части оператора присвоения sum = sum + otc? Что и чему будет присваиваться?
4. Почему в начальных установках переменной max присваивается значение 1, несмотря на то что оценка 1 не ставится за контрольные работы и экзамены?
5. Изобразите в тетради фрагмент блок-схемы цикла Для, который будет суммировать числа от 1 до 100.
6. Изобразите в тетради блок-схему алгоритма, вычисляющего произведение всех нечетных чисел от 1 до 29.
7. Останутся ли оценки, которые были введены в алгоритме, после его завершения?

К заданию 8.11

1. Для чего нужны начальные установки в алгоритме?
2. Где в программе на Кумире учитывается, что определенное количество дней в текущем месяце уже прошло и не должно учитываться в сумме? 
3. Когда в программах используется оператор выбора? Можно ли заменить его операторами Если?
4. Выпишите в тетрадь, как выглядит оператор выбора на разных языках.
5. Значение какой переменной в программах влияет на выбор той или иной ветки? Что реально означает эта переменная?
6. Найдите в программе на Кумире место, где определяется, является ли год в XXI веке високосным.

К заданию 8.12

1. Определите по блок-схеме (см. рис. 8.15), почему цикл Для начинается со второго символа, а не с первого?
2. На блок-схеме условные блоки 8 и 10 обеспечивают выбор из трех возможных вариантов: символ « + », символ «-» и символ-цифра. Найдите в примерах программ фрагменты, соответствующие этому множественному выбору.
3. При помощи каких функций определяется длина введенной строки в разных языках? Выпишите их в тетрадь.
4. Определите по примерам программ, какой тип у переменной st?
5. В третьем блоке блок-схемы (см. рис. 8.15) была введена следующая строка: 6+3-2-4+5. Определите по программе на Кумире:
• длину строки n;
• какие значения примут переменные s i m и к после первого прохода цикла;
• какие значения будут находиться в переменных sim, к, sum и ch после завершения цикла.

Циклические алгоритмы

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

Выполнив задания этой темы, вы научитесь:

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

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

В цикле с постусловием условие окончания цикла проверяется в конце оператора цикла. Если условие ложно (нет, False), то тело цикла повторяется, а иначе (если истинно — да, True) цикл завершается. Особенностью этого цикла является то, что тело цикла выполняется хотя бы один раз. Специального блока для реализации цикла с постусловием в блок-схемах нет, но во всех языках программирования есть специальные операторы, реализующие этот цикл.

Задание 8.13

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

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

Словесный алгоритм

Начало алгоритма
1. Задайте радиус окружности.
2. Вычислите для него длину окружности. 
3. Последовательно удваивайте число сторон n-угольника, рассчитывайте его периметр и сравнивайте с длиной окружности, пока не добьетесь требуемой точности.
4. Сообщите результаты.
Конец алгоритма

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

Рис. 8.16. Блок-схема алгоритма (к заданию 8.13)

Алгоритм в виде программы

В табл. 8.25 приведена программа на алгоритмическом языке Кумир. В табл. 8.26 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.25. Программа на Кумире с пояснениями (к заданию 8.13)

Таблица 8.26. Примеры программ на Паскале и Visual Basic (к заданию 8.13)

Задание 8.14

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

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

Словесный алгоритм

Начало алгоритма
1. Введите фамилию.
2. Сравнивайте ее с очередным элементом массива, пока не найдете такую же или пока не закончится список.
3. Если фамилия найдена, сообщите ее номер в списке, если нет — сообщите о том, что фамилия не найдена.
Конец алгоритма

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

Рис. 8.17. Блок-схема алгоритма (к заданию 8.14)

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

Алгоритм в виде программы

В табл. 8.27 приведена программа на алгоритмическом языке Кумир. В табл. 8.28 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.27. Программа на Кумире с пояснениями (к заданию 8.14)

Таблица 8.28. Примеры программ на Паскале и Visual Basic (к заданию 8.14)

Задание 8.15^*

Слышали ли вы о «золотом» прямоугольнике? Если от него отсечь квадрат, то остается прямоугольник с такими же пропорциями (отношением сторон), то есть полученный прямоугольник тоже будет «золотым». Этот процесс можно продолжать до бесконечности. На этой же пропорции базируются все «золотые» геометрические фигуры. Отрезки «золотой» пропорции выражаются бесконечными дробями 1,618 или 0,618. 

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

Требуется определить по введенным сторонам, является ли прямоугольник «золотым». Принять допущение: считать прямоугольник «золотым», если одно и то же соотношение с заданной точностью (абсолютная погрешность — 0,01) повторилось 5 раз. Вывести «золотое» соотношение.

Рис. 8.18. К заданию 8.15

Словесный алгоритм

Начало алгоритма
1. Введите параметры прямоугольника.
2. Определите, какая сторона является большей, какая — меньшей.
3. Найдите и сообщите первое отношение большей стороны к меньшей.
4. Пока не закончатся 5 экспериментов или не выявится неравенство последующих отношений, выполняйте следующие действия:
а) определите стороны нового прямоугольника после отсечения квадрата и найдите их соотношение;
б) если это соотношение не равно предыдущему с заданной точностью, то завершите эксперименты.
5. Если все 5 попыток прошли успешно, то выведите сообщение «прямоугольник золотой», иначе — «прямоугольник не золотой». Конец алгоритма

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

Рис. 8.19. Блок-схема алгоритма (к заданию 8.15)

На блок-схеме (рис. 8.19) пунктирной линией обведены блоки, которые будут многократно повторяться далее в цикле. Это означает, что данные блоки должны быть оформлены как вспомогательный алгоритм.

Алгоритм в виде программы

В табл. 8.29 приведена программа на алгоритмическом языке Кумир с пояснениями. В табл. 8.30 приведены тексты программы на языках программирования Паскаль и Visual Basic.

Таблица 8.29. Программа на Кумире с пояснениями (к заданию 8.15)

Таблица 8.30. Примеры программ на Паскале и Visual Basic (к заданию 8.15)

Контрольные вопросы и задания

К заданию 8.13

1. В примерах программ сторона многоугольника рассчитывается через синус центрального угла. В каких единицах измерения должен быть указан угол?
2. Условием окончания цикла является отношение (l - р) < е. Что оно означает?
3. Найдите на блок-схеме (см. рис. 8.16) и в примерах программ операторы, составляющие тело цикла с постусловием, и выпишите их в тетрадь.
4. Существуют ли такие ситуации, когда тело цикла в цикле с постусловием не будет выполнено ни разу?
5. Напишите пояснение к пп. 3 и 5 программы на Кумире.
6. Зачем при тестировании программы на Visual Basic (рис. 8.20) расчетные данные выводятся с такой точностью, если точность е = 0,1?

Рис. 8.20. Пример тестирования программы на Visual Basic (к заданию 8.13)

К заданию 8.14

1. В пп. 3 и б примеров программ (см. табл. 8.27 и 8.28) начинаются два разных цикла. Напишите в тетради их назначение и разновидности.
2. Сколько элементов в строке фамилий? Где можно узнать это число?
3. Определите по примерам программ тип переменной poisk. Какие значения может принимать эта переменная?
4. Условие окончания цикла выглядит так: poi sk или (i > 10). Что означает это сложное условие?
5*. Заполните таблицу истинности для указанного сложного условия.

6. Выпишите в тетрадь, как описана на разных языках строка фамилий?
7. Если искомая фамилия является последней в списке, по какому условию осуществился выход из цикла?

К заданию 8.15

1. Для чего нужны начальные установки в алгоритме?
2. При решении задачи принято допущение: считать прямоугольник «золотым», если одно и то же соотношение с заданной точностью (абсолютная погрешность — 0,01) повторилось 5 раз. Найдите места в примерах программ, где учитывается это соглашение.
3. Что надо изменить в блок-схеме и программах, чтобы пользователь сам указывал абсолютную погрешность?
4. После выхода из цикла анализируется переменная razn. Можно ли анализировать переменную ch? 
5*. Заполните таблицу истинности для сложного логического выражения (razn > 0.01) Or (ch = 5).

6. Напишите пояснения к пп. 10 и 11 программы на Кумире (см. табл. 8.29).
7*. Золотое соотношение обеспечивают стороны, длина которых соответствует числам Фибоначчи (чем больше числа, тем точнее пропорция). Это видно на первом тесте (рис. 8.21). Что нужно изменить в программе, чтобы рассматриваемое отношение сторон поменялось с 0,618 на 1,618?
8*.На рис. 8.21 изображено два теста. Какого теста не хватает для проверки всех ветвей алгоритма?

Рис. 8.21. Примеры тестирования программы на Visual Basic (к заданию 8.15)

9. Что нужно изменить (добавить) в блок-схеме, чтобы проверялось условие равенства сторон исходного прямоугольника? Что даст подобное изменение?