Практикум

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

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

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

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

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

В цикле с предусловием сначала проверяется выполнение условия продолжения цикла. Если условие истинно (да, 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. Чем различаются ветвления на блок-схеме и в примерах программ?