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

12.4. Линейный алгоритм

В основе линейных алгоритмов лежит структура «последовательность». Покажем это на примерах.

Пример 12.6

В своей книге «Арифметика» Леонтий Филиппович Магницкий привел следующий способ отгадывания задуманного двузначного числа: «Если кто задумает двузначное число, то ты скажи ему, чтобы он увеличил число десятков задуманного числа в 2 раза, к произведению прибавил бы 5 единиц, полученную сумму увеличил в 5 раз и к новому произведению прибавил сумму 10 единиц и числа единиц задуманного числа, а результат произведенных действий сообщил бы тебе. Если ты из указанного тебе результата вычтешь 35, то узнаешь задуманное число».

Представим предлагаемые JI. Ф. Магницким действия в виде алгоритма в словесной форме. В предлагаемом процессе должны участвовать два человека: загадывающий число и отгадывающий его. Поэтому алгоритмов тоже будет два.

Алгоритм для загадывающего число

Алгоритм для отгадывающего число

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

Пример 12.7

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

Для исходных данных алгоритма будем использовать следующие обозначения:
п — норма расхода продукта на человека в сутки;
k — количество участников похода;
d — количество дней.

Результат работы алгоритма (рассчитанный вес продукта) будет занесен в переменную m (рисунок 12.6).

Рис. 12.6. Алгоритм решения задачи «Вес продукта» в двух формах представления: в виде блок-схемы и в виде программы на школьном алгоритмическом языке

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

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

12.5. Разветвляющийся алгоритм

Вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Пойдешь направо — коня потеряешь, налево — сам пропадешь...»

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

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

Условие может принимать значение «истина», когда оно выполнено, или «ложь», когда оно не выполнено. От значения условия зависит наше дальнейшее поведение. Например, в предложении «Если закат красный, то 'жди ветреной погоды» условие «закат красный» может быть или истинным, или ложным. Если условие истинно, то следует ждать ветреной погоды, иначе (если условие ложно) ничего о погоде сказать нельзя.

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

Рассмотрим примеры алгоритмов, содержащих анализ условия.

Пример 12.8

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

Алгоритм проверки можно записать так:

Если гриб съедобный, то положить его в котелок для варки, иначе — выбросить в костер.

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

Рис. 12.7. Алгоритм проверки грибов, в котором использована полная форма ветвления

Пример 12.9

Вы идете в гости и вам необходимо перевязать коробку с подарком красивой лентой, длина которой d. Но хватит ли этой ленты?

Представим решение этой задачи на школьном алгоритмическом языке. Исходными данными для решения этой задачи являются размеры коробки и длина ленточки. Примем для них следующие обозначения: а, b, с — соответственно длина, ширина и высота коробки; d — длина ленточки.

алг Подарок
нач вещ a,b,c,d
вывод "Введите размеры коробки" ввод а,b,с
вывод "Введите размеры ленты" ввод d
если (a+b+2*c)*2 <= d то
вывод "Ленты хватит" иначе
вывод "Ленты не хватит" все кон

В примерах 12.8 и 12.9 при описании алгоритмов в виде блок- схемы и программы на школьном алгоритмическом языке использовалась конструкция «ветвление».

Различают полную и неполную форму ветвления.

При полной форме ветвления действия выполняются в обоих случаях: и при истинности, и при ложности условия. Вспомните кота из сказки А. С. Пушкина: «идет направо — песнь заводит, налево — сказку говорит ». В рассмотренных выше примерах использовалась полная форма ветвления, которой соответствует выражение
если <условие>, то <действие 1>9 иначе <действие 2>.

Неполной форме ветвления соответствует выражение
если <условие>9 то <действия>

Неполная форма предполагает отсутствие действий в случае невыполнения условия. Например: среднесуточная температура воздуха ниже +8 °С, приступить к протапливанию помещений.

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

Рис. 12.8. Алгоритм тушения костра, в котором используется неполная форма ветвления

Пример 12.10

Известно, что в аэропорту существуют ограничения на бесплатный провоз багажа. Если вес багажа превышает норму, то за каждый килограмм сверх нормы необходимо доплачивать. Исходными данными для решения задачи являются: v — вес багажа; vn — разрешенная норма провоза багажа; st — стоимость килограмма сверх нормы. Результат будем записывать в переменную s — сумму выплат сверх нормы.

Алгоритм «Доплата за багаж» представим на школьном алгоритмическом языке.

алг Доплата за багаж
нач вещ v, vn, st, s
вывод "введите вес багажа, норму, стоимость кг"
ввод v, vn, st
если v>vn
то s:=(v-vn)*st
вывод "Доплата составляет", s
все
кон

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

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

    Разветвляющийся алгоритм — алгоритм, содержащий структуру ветвления.

12.6. Циклический алгоритм

Общее представление

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

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

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

Циклические алгоритмы могут содержать разные типы циклов. Классификация типов циклов представлена на рисунке 12.9 и подробно рассмотрена далее.

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

    Тело цикла — описание действий, повторяющихся в цикле.

Рис. 12.9. Типы циклов

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

Цикл с известным числом повторений часто называют «циклом ДЛЯ». Рассмотрим примеры циклических алгоритмов с известным числом повторений.

Пример 12.11

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

Алгоритм «Упражнение для глаз»

В этом примере заранее известно число повторений. Цикл закончится, когда действия пунктов а и b повторятся 10 раз. Действия а и Ь, повторяющиеся в цикле, определяют тело цикла.

Пример 12.12

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

Исходными данными для этой задачи являются:
b — балл теущего ученика;
n — количество учеников.

Расчетные данные:
s — сумма баллов;
sr — средний балл.

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

Таблица 12.3. Алгоритм «Итоги» на школьном алгоритмическом языке

Здесь нц, кц — служебные слова, обозначающие соответстенно начало и конец цикла.

В этом примере повторяются следующие операции:
♦ ввод оценки каждого ученика;
♦ добавление ее к общей сумме.

Эти операции составляют тело цикла. Число повторений в цикле равно количеству учащихся в классе.

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

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

Цикл с неизвестным числом повторений, в котором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ».

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

Пример 12.13

После соревнований по бегу рекомендуется измерить пульс. Измерение пульса можно описать следующим алгоритмом.

Алгоритм «Пульс»

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

Рис. 12.10. Блок-схема алгоритма «Пульс»

Пример 12.14

Требуется рассчитать время работы батарейки в часах с кукушкой, если известно, что заряда хватает примерно на 1000 звуковых сигналов «ку-ку». Однократный звуковой сигнал звучит, когда минутная стрелка показывает 30 минут. Начало каждого часа сопровождается повторением сигнала столько раз, сколько показывает часовая стрелка (от 1 до 12).

Расчетными данными для этой задачи являются:
t — обозначение текущего часа;
к — количество звуковых сигналов.

Алгоритм «Кукушка» представим на школьном алгоритмическом языке в таблице 12.4.

В этом алгоритме повторяются следующие действия:
♦ определение значения текущего часа;
♦ определение количества звуковых сигналов.

Эти действия составляют тело-цикла.

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

Таблица 12.4. Алгоритм «Кукушка» на школьном алгоритмическом языке

Из рассмотренных примеров 12.13 и 12.14 видно, что цикл с постусловием имеет следующие особенности:
♦ проверка условия осуществляется в конце цикла, поэтому тело цикла выполняется хотя бы один раз;
♦ цикл заканчивается по выполнению условия.

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

Рассмотрим другой тип цикла, в котором проверка условия осуществляется в начале цикла. Для организации циклической последовательности действий и выхода из нее к другому фрагменту алгоритма используется условие, которое ставится в начале тела цикла. Цикл с неизвестным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА».

Пример 12.15

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

Алгоритм «Бочка»

На блок-схеме (рис. 12.11) видно, что условие проверки стоит в самом начале цикла.

Рис. 12.11. Блок-схема алгоритма «Бочка»

Такой цикл получил название цикла с предусловием.

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

Пример 12.16

Требуется проверить число на симметричность (примеры симметричных чисел: 12321, 8668).

Исходными данными для этой задачи является введенное число n.

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

В алгоритме используются функции:
mod — вычисление остатка от деления на 10;
div — определение целой части числа.

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

Таблица 12.5. Алгоритм «Симметричное число» на школьном алгоритмическом языке

В этом алгоритме в цикле получается перевернутое число, которое затем сравнивается с введенным. Если они равны, то введенное число симметрично. Цикл выполняется до тех пор, пока nl при целочисленном делении на 10 не превратится в 0. Если введенное число равно 0, то цикл не выполнится ни разу, но будет выдан ответ «Число симметричное».

Из рассмотренных примеров 12.15 и 12.16 видно, что цикл с предусловием имеет следующие особенности.

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