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

Алгоритмы

Изучив эту тему, вы узнаете:

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

12.7. Вспомогательный алгоритм

Вспомните рассмотренный ранее алгоритм «Приготовление гречневой каши». Он начинался с пункта «Обратитесь к алгоритму „Разжигание костра"».

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

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

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

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

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

Алгоритм «Набор текста песни»

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

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

Рассмотрим, что представляет собой алгоритм копирования, который является вспомогательным по отношению к основному алгоритму «Набор текста песни». Назовем такой вспомогательный алгоритм «Скопировать (объект копирования)».

Алгоритм «Скопировать (объект копирования)»

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

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

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

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

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

- алгоритм Дуга (радиус, направление);
- алгоритм Лепесток (радиус, направление);
- алгоритм Группа (радиус, направление).

Рис. 12.12. Этапы создания сложной графической композиции

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

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

12.8. Стадии создания алгоритма

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

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

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

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

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

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

Таким образом, в общем случае алгоритм претерпевает изменения по стадиям:
♦ первая стадия — алгоритм должен быть представлен в форме, понятной человеку, который его разрабатывает;
♦ вторая стадия — алгоритм должен быть представлен в форме, понятной тому объекту (в том числе и человеку), который будет выполнять описанные в алгоритме действия. В том случае, если эти действия станет выполнять сам разработчик алгоритма, вторая стадия будет отсутствовать.

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

1. Достать карту местности.
2. Оговорить продолжительность путешествия.
3. Проложить предстоящий маршрут. 

Это первая стадия разработки алгоритма. На этом этапе вы обдумываете план и намечаете для себя промежуточные цели.

В дальнейшем, исследуя карту, вы обнаруживаете, что наиболее привлекательным местом является берег речки, расположенный довольно далеко. Ваша цель меняется. Теперь вы мечтаете совершить путешествие именно к этому месту. Поэтому вы вынуждены откорректировать намеченный план действий:
4. Подготовить перечень необходимых продуктов, которые вы возьмете с собой.
5. Подготовить велосипед к длительному пути — смазать маслом, накачать шины и т. д.
6. Собрать необходимые вещи — купальные принадлежности, удочку и т. д.

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

Это вторая стадия разработки алгоритма, когда необходимо ориентироваться на тот объект, который будет этот алгоритм исполнять. На этом этапе выбираются среда и инструменты — объекты, которые могут осуществить ваш план.

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

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

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

Рассмотрим другой пример. Вы хотите поздравить друзей с Новым годом. Для этого вы наметили подготовить красочные открытки. На первой стадии вы разрабатываете алгоритм для себя:

1. Придумать сюжет.
2. Нарисовать картинку по сюжету.
3. Написать стихи до сюжету.
4. Подготовить открытки с адресами.
5. На каждую открытку поместить рисунок и текст.

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

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

Запомните правила разработки любого алгоритма.

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

Вторая стадия — детализация алгоритма с учетом специфики среды и других объектов:
- выбрать среду и объекты, посредством которых алгоритм будет реализован;
- детализировать алгоритм с учетом особенностей выбранной среды.

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

1. Дайте определение алгоритма и приведите примеры.
2. Что такое алгоритмизация?
3. Приведите пример математического выражения и составьте алгоритм его вычисления.
4. Поясните на примерах свойства алгоритма.
5. Как вы понимаете свойство конечности алгоритма? Приведите примеры.
6. Как вы понимаете свойство массовости алгоритма? Приведите примеры.
7. Что такое линейный алгоритм? Приведите примеры.
8. Что такое циклический алгоритм? Приведите примеры.
9. Напишите циклический алгоритм и укажите в нем тело цикла.
10. Как происходит окончание циклического алгоритма?
11. Что такое разветвляющийся алгоритм? Приведите примеры.
12. Как в алгоритме записывается условие?
13. Как записывается полная форма разветвляющегося алгоритма? Приведите примеры.
14. Как записывается неполная форма разветвляющегося алгоритма? Приведите примеры.
15. Что такое вспомогательный алгоритм? Приведите примеры.
16. Зачем нужна блок-схема алгоритма?
17. Придумайте пример алгоритма и представьте его в виде блок-схемы.
18. Какие стадии разработки алгоритма вы знаете и в чем их суть?
19. Приведите пример разработки алгоритма по стадиям в виде двух блок-схем.

Тест по теме: “Основные понятия алгоритма”

1. Свойство алгоритма, заключающееся в том, что каждое действие и алгоритм в целом должны иметь возможность завершения...
а) дискретность;
б) детерминированность;
в) конечность;
г) массовость.

2. Алгоритм называется циклическим:
а) если он начинается с конца;
б) если серия команд повторяется многократно, в зависимости от условия задачи;
в) если в программе упорядочены действия;
г) всё выше перечисленное верно.

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

4. Алгоритмом является:
а) прайс лист;
б) инструкция по получению денег в банкомате;
в) расписание уроков;
г) список класса.

5. Алгоритм это:
а) правила выполнения определённых действий;
б) ориентированный граф, указывающий порядок выполнения некоторого набора команд;
в) описание последовательности действий, строгое исполнение которых приводит к решению поставленной задачи за конечное число шагов;
г) набор команд ля компьютера.

---

Практикум

---

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

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

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

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

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

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