И технологии программирования 1 страница

6.1. Понятие алгоритма и его свойства

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

Алгоритм — описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи. Понятие алгоритма, являющееся фундамен­тальным в математике и информатике, возникло задолго до появле­ния средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами вы­полнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» — человек из города Хорезми; в настоящее время го­род Хива в Хорезмской области Узбекистана). Слово алгоритм — есть результат европейского произношения слов аль-Хорезми. Первона­чально под алгоритмом понимали способ выполнения арифметичес­ких действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности дей­ствий, приводящей к решению поставленной задачи.

Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя (человека, робота, компьютера, языка программирования и т.д.). Свойством, характеризующим любого ис­полнителя, является то, что он умеет выполнять некоторые коман­ды. Совокупность команд, которые данный исполнитель умеет вы­полнять, называется системой команд исполнителя. Алгоритм описывается в командах исполнителя, который будет его реализовы вать. Объекты, над которыми исполнитель может совершать дей­ствия, образуют так называемую среду исполнителя. Исходные дан­ные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.

Значение слова «алгоритм» очень схоже со значениями слов «ре­цепт», «метод», «процесс». Однако, в отличие от рецепта или про­цесса, алгоритм характеризуется следующими свойствами: дискрет­ностью, массовостью, определенностью, результативностью, формальностью.

Дискретность (разрывность — противоположно непрерывности)— это свойство алгоритма, характеризующее его структуру: каждый ал­горитм состоит из отдельных законченных действий, говорят: «Де­лится на шаги».

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

Определенность (детерминированность, точность) — свойство ал­горитма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. По­мните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Пря­мо пойдешь - голову потеряешь, направо пойдешь - жену найдешь, налево пойдешь — разбогатеешь». Стоит Иван и думает, что дальше делать», Таких инструкций 'алгоритм содержать не может.

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

Формальность — это свойство указывает на то, что любой испол­нитель, способный воспринимать и выполнять инструкции алгорит­ма, действует формально, т.е. отвлекается от содержания поставлен­ной задачи и лишь строго выполняет инструкции. Рассуждать «что, как и почему?» должен разработчик алгоритма, а исполнитель формально (не думая) поочередно исполняет предложенные команды, и получает необходимый результат.

6.2. Способы описания алгоритмов

Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

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

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

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

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

Рассмотрим некоторые основные конструкции, использующие­ся для построения блок-схем.

Блок, характеризующий нача­ло/конец алгоритма (для¹ под­программ — вызов/возврат):

Блок - процесс, предназначен­ный для описания отдельных дей­ствий:

Блок — предопределенный про­цесс, предназначенный для обраще­ния к вспомогательным алгоритмам (подпрограммам):

Блок — ввода/вывода с неопре­деленного носителя:

Блок — ввод с клавиатуры

Блок — вывод на монитор:

Блок — вывод на печатающее устройство:

Блок — решение (проверка усло­вия или условный блок):

Блок, описывающий цикл с па­раметром:

Блок — границы цикла, описыва­ющий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»:

Соединительные блоки

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

Программа — описание структуры алгоритма на языке алгорит­мического программирования. С другой стороны, понятие «програм­ма» нельзя трактовать только таким образом, как уже говорилось в главе 5 (п. 5.5.2), программа на языке декларативного программиро­вания представляет собой совокупность описанных знаний и не со­держит явного алгоритма исполнения.

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

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

6.3.1. Линейная алгоритмическая конструкция

Линейной называют алгоритмичес­кую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i-го действия (шага) выполняется (i-1)-е действие (шаг), если /-е дей­ствие - не конец алгоритма.

Пример 6.1.

Опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схе­мы (рис. 6.1).

Псевдокод:

1. Ввод двух чисел а, Ь.

2. Вычисляем сумму S — а + b.

3. Вывод S.

4. Конец.

Рис. 6.1. Блок-схема к примеру 6.1

6.3,2, Разветвляющееся алгоритмическая конструкция

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

Рис. 6.2. Полное ветвление

на одной ветви (то), вторая ветвь отсутствует, т.е. для одного из ре­зультатов проверки никаких действий выполнять не надо, управле­ние сразу переходит к точке слияния (рис. 6.3).

Пример 6.2.

Вывести значение наибольшего из двух чисел. Псевдокод:

1. Ввод двух чисел а, Ь.

2. ЕСЛИ а > Ь, ТО «выводим а»,

ИНАЧЕ «выводим Ь».

3. Конец.

Рис. 6.3. Неполное ветвление

Рис. 6.4. Блок-схема к примеру 6.2

В данном примере реализовано полное ветвление. ЕСЛИ значе­ния входных данных таковы, что а >Ь, ТО выполняется линейный алгоритм:

1. Ввод двух чисел а, Ь.

2. Вывод а.

ИНАЧЕ, когда а < Ь, выполняется линейный алгоритм:

1. Ввод двух чисел а, b.

2. Вывод b.

Вывод: алгоритм является разветвляющимся и состоит из двух

ветвей.

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

Пример 6.3.

Заданы три числа. Найти значение наименьшего из них.

Рис. 6.5. Алгоритм поиска наименьшего значения среди трех заданных

Заданные числа обозначим: а, Ь, с; результирующее наимень­шее - min. На рис. 6.5 представ­лена блок-схема алгоритма реше­ния данной задачи.

Команда «выбор»

Рис. 6.6. Команда «выбор»

Часто при выборе одного из возможных вариантов действий при­ходится проверять значение выражения на принадлежность заданно­му набору данных. Для этого существует команда «Выбор». При ее исполнении сначала вычисляется значение некоторого выражения 2. Затем последовательно проверяются условия VI, V2, ..., \п относи­тельно Z, начиная с первого, до тех пор, пока не встретится усло­вие, принимающее значение ИСТИНА. Далее выполняется соответ­ствующее этому условию действие (или серия действий), после чего команда выбора завершается. Если ни одно из условий не является истинным, то выполняется действие (или набор действий), идущее по ветви ЛОЖЬ для каждого из условий. На рис. 6.6 представлена блок-схема команды «Выбор» для п = 3.

6.3.3. Алгоритмическое конструкция «Цикл»

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

Правило изменения параметра i: i = N, К, h означает
1-й шаг цикла
2-й шаг цикла	/ = N + h
3-й шаг цикла и т.д.	/ - N + 2h
последний шаг

ся телом цикла. Любая цикли­ческая конструкция содержит в себе элементы ветвящейся алгоритмической конструк­ции.

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

Арифметический цикл

В арифметическом цикле число его шагов (повторений) одно­значно определяется правилом изменения параметра, которое зада­ется с помощью начального (N) и конечного (К) значений параметра и шагом (И) его изменения. Те., на первом шаге цикла значение па­раметра равно N, на втором - N + h, на третьем - N + 2п и т.д. На последнем шаге цикла значение параметра не больше К, но та­кое, что дальнейшее его изменение приведет к значению, большему, чем К.

Пример 6.4.

Вывести 10 раз слово «Привет!».

Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При / = 1 будет выведено первое слово, при / = 2 будет выведено второе слова и т.д. Так как требуется вывести 10 слов, то последнее значение параметра / = 10. В заданном примере требу­ется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, ис­пользуя арифметический цикл, в котором правило изменения параметра / — 1, 10, 1. Т.е. на­чальное значение параметра / — 1; конечное значение i = 10; шаг изменения h = 1. На рис. 6.7 представлена блок-схема алгоритма решения данной за­дачи.

Рис. 6.7. Блок-схема к примеру 6.4

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

б

Количество шагов цикла заранее не определено и зависит от входных данных задачи. В данной циклической структуре сначала проверяется значение условного выражения (условие) перед выпол­нением очередного шага цикла. Если значение условного выражения истинно, исполняется тело цикла. После чего управление вновь пе­редается проверке условия и т.д. Эти действия повторяются до тех пор, пока условное выражение не примет значение ЛОЖЬ. При пер­вом же несоблюдении условия цикл завершается.

Блок-схема данной конструкции представлена на рис. 6.8 двумя способами: с помощью условного блока а и с помощью блока гра­ницы цикла б.

Особенностью цикла с предусловием является то, что если из­начально условное выражение ложно, то тело цикла не выполнится ни разу.

Пример 6.5.

Одним из наиболее распространенных алгоритмов, встречаю­щихся в литературе по информатике, является алгоритм Евклида — алгоритм нахождения наибольшего общего делителя двух натураль­ных чисел т и п (рис.6.9).

Рис. 6.8. Блок-схема цикла с предусловием

Опишем его на псевдокоде:

1. Ввод натуральных чисел тип.

2. Пока делать.

2.1. Если т>п, то т=т — п,
иначе п =п — т .

2.2. Переход к шагу 2.

. 3. Вывод т (найденный наибольший общий делитель). 4. Конец.

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

Рис. 6.10. Блок-схема цикла с постусловием

Как и в цикле с предусловием, в циклической конструкции с постусловием заранее не определено число повторений тела цикла, оно зависит от входных данных задачи. В отличие от цикла с пред­условием, тело цикла с постусловием всегда будет выполнено хотя бы один раз, после чего проверяется условие. В этой конструкции тело цикла будет выполняться до тех пор, пока значение условного выражения ложно. Как только оно становится истинным, выполне­ние команды прекращается. Блок-схема данной конструкции пред­ставлена на рис. 6. L0 двумя способами: с помощью условного блока а и с помощью блока управления 6.

Пример 6.6.

Составим алгоритм игры «Угадай число». Первый игрок вводит задуманное число от 1 до 50. Второй (угадывающий) вводит другое число и получает один из ответов: «Ваше число меньше», «Ваше чис­ло больше» или «Вы угадали». Игра продолжается до тех пор, пока второй игрок не угадает задуманное число.

Составляя алгоритм игры, обозначим х — число, задуманное пер­вым игроком, у — число, вводимое на очередном шаге вторым игро­ком. Блок-схема алгоритма приведена на рис. 6.11.

Рис. 6.11. Блок-схема игры «Угадай число» (пример 6.6)

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

Суммирование.

Пример 6.7.

Для заданного натурального числа N вычислить сумму

Подсчет суммы осуществляется следующим образом. Сначала счи­таем, что сумма S есть первое слагаемое (S = 1). Далее к первому сла-

■ Но

гаемому прибавляем второе, получаем новую сумму

на предыдущем шаге S = 1, поэтому можно записать К сум­ме двух первых слагаемых прибавляем третье . Но на

предыдущем шагу , поэтому можно записать и т.д.

Запишем i-й шаг, опираясь на два предыдущих:

Получили следующую последовательность шагов: I) S = 1.

Выясним правило изменения номера шага i. В описанной по­следовательности г = 1, 2, 3 и т.д. В сумме N слагаемых, поэтому по­следним значением i будет N. Отсюда нашли правило изменения i = 1, N, 1.

Сверяя инструкции каждого шага, находим, что выражение на первом шаге отличается от других (однотипных). Чтобы оно стало таким как все, в сумму надо добавить S, т.е. записать: S = S + 1 (учи­тываем, что ). Отсюда для S возникает необходимость задания

начального значения, но такого, чтобы S + 1 = 1 (таким должно быть выражение для / — 1), этим числом является нуль, при сложении с нулем сумма не меняется.

Так как известно число шагов цикла, то для построения алго­ритма используем цикл с параметром /.

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

1.Ввод N.

2. S = 0.

3. Для i = 1, N, 1 повторить:

4. Вывод S.

5. Конец.

Блок-схема алгоритма приведена на рис. 6.12.

Сформулируем правило суммирования:

• начальное значение суммы S = 0;

• в теле некоторой циклической конструкции
выполнить команду:

S = S + <слагаемое>.

Упражнения для самостоятельной работы:

Для заданного натурального числа N вычислите суммы N-сла-гаемых:

Рис. 6.12. Алгоритм вычисления суммы

^Подсчет количества элементов. Произведем счет: 1, 2, 3, 4, 5 и т.д., этот процесс является циклическим, так как каждый раз мы со­вершаем одно и то же действие: предыдущее натуральное число уве­личиваем на единицу. Обозначив через К — счетчик искомых эле­ментов, легко получить правило счетчика: К = К + 1 (на очередном шаге цикла). Но при первом подсчете должны получить значение К, равное единице, а до начала счета счетчик должен быть пуст, следо­вательно, начальное значение счетчика равно нулю.

Правило счетчика:

• начальное значение счетчика К = 0;

• в.теле некоторой циклической конструкции
выполнить команду:

К = К+ 1.

Пример 6.8

Задано 20 чисел. Сколько среди них чисел, больших 10? Псевдокод:

1. К = 0 {Счетчик чисел, больших 10}.

2. Повторить 20 раз (для / = 1, 20, 1).

2.1. Ввод числа х.

2.2. Если х > 10, то К = К+ 1.

3. Вывод К.

4. Конец.

Рис. 6.13. Алгоритм примера 6.8

Блок-схема алгоритма приведена на рис. 6.13. Замечание: в фигурных скобках {....} принято помещать ком­ментарии к алгоритму.

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

Рис. 6.14. Расположение циклов

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

6.3,4. Рекурсивный алгоритм

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

6,4. Простые типы данных: переменные и константы

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

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

задает:

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

• необходимый объем памяти для ее хранения.

Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимо­го диапазона значений данного типа. Например, тип «байт» может принимать значения от 0 до 255, что в двоичном коде (255 ₁₀₎ = = 11111111 ₂) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

В описанных выше алгоритмах (примеры 6.1 - 6.8) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чи­сел а, Ь» означает введение пользователем значений двух перемен­ных, а инструкция «К=К+1» означает увеличение значения перемен­ной К на единицу.

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

Все остальные данные в программе, значения которых не изме­няются на протяжении ее работы, называют константами или посто­янными. Константы, как и переменные, имеют тип. Их можно ука­зывать явно, например, в инструкции «К = К + 1» 1 есть константа, или для удобства обозначать идентификаторами: pi = 3,1415926536. Только значение pi нельзя изменить, так как это константа, а не пе­ременная.