Алгоритмы
Исключительно важно использовать язык блок-схем при разработке алгоритма решения задачи. Решение одной и той же задачи может быть реализовано с помощью различных алгоритмов, отличающихся друг от друга как по времени счета и объему вычислений, так и по своей сложности. Запись этих алгоритмов с помощью блок-схем позволяет сравнивать их, выбирать наилучший алгоритм, упрощать, находить и устранять ошибки.
Отказ от языка блок-схем при разработке алгоритма и разработка алгоритма сразу на языке программирования приводит к значительным потерям времени, к выбору неоптимального алгоритма. Поэтому необходимо изначально разработать алгоритм решения задачи на языке блок-схем, после чего алгоритм перевести на язык программирования.
При разработке алгоритма сложной задачи используется метод пошаговой детализации. На первом шаге продумывается общая структура алгоритма без детальной проработки отдельных его частей. Блоки, требующие детализации, обводятся пунктирной линией и на последующих шагах разработки алгоритма продумываются и детализируются.
В процессе разработки алгоритма решения задачи можно выделить следующие этапы:
- Этап 1 . Математическое описание решения задачи.
- Этап 2 . Определение входных и выходных данных.
- Этап 3 . Разработка алгоритма решения задачи.
Основные сведения об алгоритмах
Работа по решению любой задачи с использованием компьютера делится на следующие этапы:
Часто эту последовательность называют технологической цепочкой решения задачи на компьютере. Непосредственно к программированию в этом списке относятся пункты 3, 4, 5.
На этапе постановки задачи должно быть четко определено, что дано и что требуется найти. Здесь очень важно определить полный набор исходных данных, необходимый для решения задачи.
Второй этап — формализация задачи. Здесь чаще всего задача переводится на язык математических формул, уравнений, отношений. Если решение задачи требует математического описания какого-то реального объекта, явления или процесса, то формализация равносильна получению соответствующейматематической модели.
Третий этап — построение алгоритма. Опытные программисты часто сразу пишут программы на языках программирования, не прибегая к каким-либо специальным способам описания алгоритмов (блок-схемам, псевдокодам). Однако в учебных целях полезно использовать эти средства, а затем переводить полученный алгоритм на язык программирования.
Первые три этапа — это работа без компьютера. Дальше следует собственно программирование на определенном языке в определенной системе программирования. Последний (шестой) этап — это уже использование разработанной программы в практических целях. Выполнение учебных заданий на программирование обычно заканчивается пятым этапом, т. е. доказательством правильности составленной программы.
Таким образом, программист должен обладать следующими знаниями и навыками:
• уметь строить алгоритмы;
• знать языки программирования;
• уметь работать в соответствующей системе программирования.
Основой программистской грамотности является развитое алгоритмическое мышление.
9.2. Вспомогательный алгоритм
Пример 1. Применим метод «сверху вниз» для разработки алгоритма нахождения периметра треугольника, заданного координатами своих вершин.
Пусть ХА, ХВ, YA, YB, ХС, YC — координаты вершин треугольника ABC. Его периметр — сумма длин отрезков АВ, ВС и АС.
Из курса геометрии вам известна формула для вычисления длины отрезка АВ по координатам его концов (рис. 2.11):
Действия по вычислению длины отрезка представляют собой логически целостный фрагмент, который целесообразно оформить в виде вспомогательного алгоритма.
Рис. 2.11. Отрезок АВ
Вспомогательный алгоритм — это алгоритм, целиком используемый в составе другого алгоритма.
На рисунке 2.12 представлены:
1) блок-схема алгоритма вычисления периметра треугольника, предполагающая вызов вспомогательного алгоритма Отрезок;
2) блок-схема вспомогательного алгоритма Отрезок.
При вызове вспомогательного алгоритма указываются его параметры (входные данные и результаты). Параметрами вспомогательного алгоритма Отрезок являются величины XI, Y1, Х2, Y2, D. Это формальные параметры, они используются при описании алгоритма. При конкретном обращении к вспомогательному алгоритму формальные параметры заменяются фактическими параметрами, т. е. именно теми величинами, для которых будет исполнен вспомогательный алгоритм. Типы, количество и порядок следования формальных и фактических параметров должны совпадать.
Рис. 2.12. Алгоритм вычисления периметра треугольника и вспомогательный алгоритм Отрезок
Команда вызова вспомогательного алгоритма исполняется следующим образом:
1) формальные входные данные вспомогательного алгоритма заменяются значениями фактических входных данных, указанных в команде вызова вспомогательного алгоритма;
2) для заданных входных данных исполняются команды вспомогательного алгоритма;
3) полученные результаты присваиваются переменным с именами фактических результатов;
4) осуществляется переход к следующей команде основного алгоритма.
Каким будет результат работы алгоритма при следующих исходных данных: ХА = 1, ХВ = 2, ХС = 3, YA = 1, YВ = 3, YC = 1.
Структура алгоритмов
Базовые алгоритмические структуры
В 1969 году известным голландским ученым — программистом Э. В. Дейкстрой было доказано, что алгоритм для решения любой логической задачи можно составить только из структур следование, ветвление, цикл. Их называют базовыми алгоритмическими структурами. Методика программирования, основанная на этой теореме, называется структурным программированием.
С базовыми алгоритмическими структурами вы познакомились, изучая информатику в 9 классе. Там же для описания структур алгоритмов были использованы два способа: блок-схемы и учебный Алгоритмический язык (АЯ). Еще раз покажем, как изображаются базовые структуры в схемах алгоритмов и как они описываются на АЯ.
Следование — это линейная последовательность действий (рис. 3.3).
В программе на Паскале серия — это либо один отдельный оператор, либо составной оператор: последовательность операторов, заключенная в операторные скобки. Например, в языке Паскаль операторными скобками являются служебные слова Begin и End.
Ветвление — алгоритмическая альтернатива. Управление передается одному из двух блоков в зависимости от истинности или ложности условия. Затем происходит выход на общее продолжение. Вот как изображается ветвление на блок-схеме и АЯ (рис. 3.4).
Условие представляет собой утверждение, которое может быть либо истинным, либо ложным. Такое утверждение называется логическим выражением.
Неполная форма ветвления имеет место, когда на ветви «нет» пусто (рис. 3.5).
Цикл — повторение некоторой группы действий по условию. Различают два типа цикла. Первый — цикл с предусловием: цикл-пока (рис. 3.6).
Пока условие истинно, выполняется серия, образующая тело цикла.
Второй тип циклической структуры — цикл с постусловием: цикл-до (рис. 3.7).
Здесь тело цикла предшествует условию цикла. Тело цикла повторяет свое выполнение, если условие ложно. Повторение прекращается, когда условие становится истинным.
Теоретически необходимым и достаточным является лишь первый тип цикла — цикл с предусловием. Любой циклический алгоритм можно построить с его помощью. Это более общий вариант цикла, чем цикл-до. В самом деле, тело цикла-до хотя бы один раз обязательно выполнится, так как проверка условия происходит после завершения его выполнения. А для цикла-пока возможен такой вариант, когда тело цикла не выполнится ни разу. Поэтому в любом языке программирования можно было бы ограничиться только циклом-пока. Однако в ряде случаев применение цикла-до оказывается более удобным, и поэтому он используется.
Иногда в литературе структурное программирование называют программированием без GOTO — оператора безусловного перехода. Действительно, при таком подходе нет места безусловному переходу. Неоправданное использование в программе оператора GOTO лишает ее структурности, а значит, всех связанных с этим положительных свойств: прозрачности и надежности алгоритма. Хотя во всех процедурных языках программирования этот оператор присутствует, однако, с точки зрения структурного подхода, его употребления следует избегать.
Комбинации базовых структур
Сложный алгоритм состоит из соединенных между собой базовых структур. Соединяться эти структуры могут двумя способами: последовательным и вложенным.
Если блок, составляющий тело цикла, сам является циклической структурой, то имеют место вложенные циклы. В свою очередь, внутренний цикл может иметь внутри себя еще один цикл и т. д. В связи с этим вводится представление о глубине вложенности циклов. Точно так же и ветвления могут быть вложенными друг в друга.
Структурный подход требует соблюдения стандарта в изображении блок-схем алгоритмов. Чертить их нужно так, как это делалось во всех приведенных примерах. Каждая базовая структура должна иметь один вход и один выход. Нестандартно изображенная блок-схема плохо читается, теряется наглядность алгоритма. Несколько примеров структурных блок-схем алгоритмов приведены на рис. 3.8 (вместо «да», «нет» здесь использованы знаки « + » и «-», У — , С — ).
Такие блок-схемы легко читаются. Их структура хорошо воспринимается визуально. Структуре каждого алгоритма можно дать название. Приведенные блок-схемы можно охарактеризовать следующим образом (в порядке номеров).
1. Вложенные ветвления. Глубина вложенности равна единице.
2. Цикл с вложенным ветвлением.
3. Вложенные циклы-пока. Глубина вложенности — 1.
4. Ветвление с вложенной последовательностью ветвлений на положительной ветви и с вложенным циклом-пока на отрицательной ветви.
5. Следование ветвления и цикла-до.
6. Вложенные циклы. Внешний — цикл-пока, внутренний — цикл-до.
Наглядность структуре описания алгоритма на АЯ придает структуризация внешнего вида текста.
Основной используемый для этого прием — сдвиги строк, которые должны подчиняться следующим правилам:
• конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);
• вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.
Для приведенных на рис. 3.8 блок-схем структура текста на АЯ должна быть следующей:
Такой же способ структуризации используется и в текстах программ (например, на Паскале).
Структурное программирование — это не только форма описания алгоритма и программы, но это еще и способ мышления программиста. Размышляя над алгоритмом, нужно стремиться составлять его из стандартных структур. Если использовать строительную аналогию, то структурная методика построения алгоритма подобна сборке здания из стандартных секций, в отличие от складывания по кирпичику.
Вопросы и задания
1. Перечислите основные базовые алгоритмические структуры и покажите способы их отображения на блок-схемах и в АЯ.
2. Какой алгоритм называется структурным?
3. Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из двух числовых величин наибольшее значение. Первый вариант — с полным ветвлением, второй вариант — с неполным ветвлением.
4. Нарисуйте блок-схемы и напишите на АЯ два варианта алгоритма решения задачи: выбрать из трех числовых величин наименьшее значение. Первый вариант — с вложенными ветвлениями, второй вариант — с последовательными ветвлениями.
5. Для данного натурального числа N требуется вычислить сумму: 1 + 1/2 + 1/3 + . + 1/N. Постройте блок-схемы и напишите на АЯ два варианта алгоритма: с циклом-до и с циклом-пока.
6. Какую структуру будет иметь алгоритм решения следующей задачи? Дано целое положительное число N. Если N — четное, то вычислить N! = 1 • 2 • . • N. Если N — нечетное, то вычислить сумму: 1 + 2 + . + N.
Составьте блок-схему алгоритма решения и опишите его на АЯ.
Средствами почтовой программы создать фильтр для автоматического распределения входящих писем по почтовым папкам в зависимости от темы письма
Рассмотрим решение поставленной задачи в двух разных почтовых клиентах.
Для того чтобы такое распределение было возможно, необходимо существование тех папок, по которым предполагается «раскладывать» письма (или нужно создать такие папки в процессе формирования правила сортировки почты).
Необходимо выбрать меню Сообщение -> Создать правило из сообщения.
Далее в диалоговом окне Создать правило для почты (см. рис.) указать, что сортировка почты осуществляется по полю Тема , в качестве действия указать Переместить в заданную папку , далее описать правило.
Описание правила включает:
1) ввод ключевых слов
2) выбор папки, куда будут помещаться указанные сообщения
Последнее задание названия для правила (либо можно согласиться с предлагаемым по умолчанию).
Таким образом, почтовый клиент будет автоматически сортировать часть почты. Аналогично можно сортировать почту по отправителю и т.д.
В персональных настройках можно установить фильтры.
Выбрать Добавить фильтр в список фильтров . Настроить фильтр
3. Задание на подсчет полного набора символов (мощности алфавита), используемого при кодировании информации
Пример. Перед въездом в город стоят пять флагштоков. На флагштоках можно поднимать флаги желтого, зеленого и красного цвета. Какое количество различных сигналов можно подать при помощи этих флагштоков при условии, что не обязательно поднимать флаг на каждом из флагштоков?
Решение. При условии, что не обязательно поднимать флаг на каждом из флагштоков, для каждого флагштока есть 4 возможности: нет флага, желтый флаг, зеленый флаг, красный флаг. Тогда общее количество комбинаций получается следующим: 4×4×4×4×4=1024.
Преобразуйте псевдокод в нормальный код и отладьте его
Когда ваш псевдокод будет готов, преобразуйте каждую строку в реальный код на вашем языке. Здесь мы воспользуемся JavaScript.
Если вы писали на бумаге, то перенесите всё в редактор в виде комментариев, а затем замените каждую строку.
Теперь вызовите функцию и дайте ей некоторые из ранее использованных наборов данных. Так можно проверить, возвращает ли код нужный результат. Также можете написать тесты для проверки соответствия выходных данных ожидаемому результату.
После каждой переменной или строки можно использовать console.log() . Это поможет проверить, ведут ли себя значения и код так, как ожидается, прежде чем двигаться дальше. Таким образом вы выловите любые проблемы, не зайдя слишком далеко. Вот пример того, какие значения можно проверить при начале работы.
Ниже приведён код, полученный после обработки каждой строки псевдокода. Символы // обозначают строки из псевдокода. Жирным выделен реальный код на JavaScript.
Уберём псевдокод, чтобы не путаться.
Иногда разработчики-новички настолько увлекаются синтаксисом, что им трудно идти дальше. Помните, что со временем вам будет проще соблюдать синтаксис, и нет ничего стыдного в том, чтобы потом при написании кода обращаться к справочным материалам для корректного соблюдения синтаксиса.
Модульное программирование
Модульное программирование является естественным следствием проектирования сверху вниз и заключается в том, что программа разбивается на части – модули, разрабатываемые по отдельности.
В программировании под модулем понимается отдельная подпрограмма, а подпрограммы часто называются процедурами или процедурами-функциями. Поэтому модульное программирование еще называется процедурным.
Модуль должен обладать следующими свойствами:
- один вход и один выход – на входе программный модуль получает определенный набор исходных данных, выполняет содержательную обработку и возвращает один набор результатных данных, т.е. реализуется стандартный принцип IPO (Input — Process — Output — вход-процесс-выход);
- функциональная завершенность – модуль выполняет перечень регламентированных операций для реализации каждой отдельной функции в полном составе, достаточных для завершения начатой обработки;
- логическая независимость – результат работы программного модуля зависит только от исходных данных, но не зависит от работы других модулей;
- слабые информационные связи с другими программными модулями – обмен информацией между модулями должен быть по возможности минимизирован;
- обозримый по размеру и сложности программный код.
Модули содержат определение доступных для обработки данных, операции обработки данных, схемы взаимосвязи с другими модулями.
Каждый модуль состоит из спецификации и тела. Спецификации определяют правила использования модуля, а тело – способ реализации процесса обработки.
Принципы модульного программирования программных продуктов во многом сходны с принципами нисходящего проектирования: сначала определяются состав и подчиненность функций, а затем — набор программных модулей, реализующих эти функции.
Паскаль – язык структурного программирования.
Возникновение и назначение Паскаля
После того как построен алгоритм решения задачи, составляется программа на определенном языке программирования.
Среди современных языков программирования одним из самых популярных является язык Паскаль. Этот язык разработан в 1971 году и назван в честь Блеза Паскаля — французского ученого, изобретателя механической вычислительной машины. Автор языка Паскаль — швейцарский профессор Никлаус Вирт.
Паскаль — это универсальный язык программирования, позволяющий решать самые разнообразные задачи обработки информации.
Команду алгоритма, записанную на языке программирования, принято называть оператором.
Программа на Паскале близка по своему виду к описанию алгоритма на Алгоритмическом языке. Сравните алгоритм решения уже знакомой вам задачи — деления простых дробей с соответствующей программой на Паскале:
Структура программы на Паскале
Даже не заглядывая в учебник по Паскалю, в этой программе можно все понять (особенно помогает знание английского языка).
Заголовок программы начинается со слова Рrogram (программа), за которым следует произвольное имя, придуманное программистом:
Раздел описания переменных начинается со слова Var (variables — переменные), за которым идет список имен переменных через запятую. Тип указывается после двоеточия. В стандарте языка Паскаль существуют два числовых типа величин: вещественный и целый. Слово integer обозначает целый тип (является идентификатором целого типа). Вещественный тип обозначается словом геаl. Например, раздел описания переменных может быть таким:
var а, b : integer; с, d : real;
Идентификаторы переменных составляются из латинских букв и цифр; первым символом обязательно должна быть буква.
Раздел операторов — основная часть программы. Начало и конец раздела операторов программы отмечаются служебными словами begin (начало) и end (конец). В самом конце программы ставится точка:
Операторы ввода, вывода, присваивания
Ввод исходных данных с клавиатуры происходит по оператору геаd (гead — читать) или геаdln (геad line — читать строку):
При выполнении команды ввода компьютер ожидает действий пользователя. Пользователь набирает на клавиатуре значения переменных в том порядке, в каком они указаны в списке, отделяя их друг от друга пробелами. Одновременно с набором данных на клавиатуре они появляются на экране. В конце нажимается клавиша (). Разница в выполнении операторов геаdln и геаd состоит в том, что после выполнения ввода по оператору геаdln экранный курсор перемещается в начало новой строки, а по оператору геаd этого не происходит.
Вывод результатов происходит по оператору write (write — писать) или writeln (write line — писать в строку):
Результаты выводятся на экранкомпьютера в порядке их перечисления в списке. Элементами списка вывода могут быть константы, переменные, выражения.
Разница в выполнении операторов writeln и write состоит в том, что после выполнения вывода по оператору writeln экранный курсор перемещается в начало новой строки, а по оператору write этого не происходит.
Арифметический оператор присваивания на Паскале имеет следующий формат:
Арифметическое выражение может содержать числовые константы и переменные, знаки арифметических операций, круглые скобки. Кроме того, в арифметических выражениях могут присутствовать функции.
Знаки основных арифметических операций записываются так:
+ сложение,
— вычитание,
* умножение,
/ деление.
Правила записи арифметических выражений
Запись арифметических выражений на Паскале похожа на обычную математическую запись. В отличие от математики, где часто пропускается знак умножения (например, пишут 2А), в Паскале этот знак пишется обязательно: 2*А. Например, математическое выражение
на Паскале записывается так:
Это же выражение можно записать иначе:
SQR (А) + SQR (В) — 12*С
Здесь использована функция возведения в квадрат — Аргументы функций всегда пишутся в круглых скобках.
Последовательность выполнения операций определяется по их приоритетам (старшинству). К старшим операциям относятся умножение (*) и деление (/). Операции сложения и вычитания — младшие. В первую очередь выполняются старшие операции. Несколько операций одинакового старшинства, записанные подряд, выполняются в порядке их записи слева направо. Приведенное выше арифметическое выражение будет вычисляться в следующем порядке (порядок вычислений указан цифрами сверху):
1 4 2 5 3
А * А + В * В — 12 * С
Круглые скобки в арифметических выражениях влияют на порядок выполнения операций. Как и в математике, в первую очередь выполняются операции в скобках. Если имеются несколько пар вложенных скобок, то сначала выполняются операции в самых внутренних скобках. Например:
6 1 3 2 4 5
А + ( (С — D) / (2 + К) — 1) *B
Пунктуация Паскаля
Необходимо строгое соблюдение правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации.
Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, является разделителем операторов. Перед словом end точку с запятой можно не ставить.
Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.
Строгий синтаксис в языке программирования необходим потому, что компьютер является формальным исполнителем программы. Если, допустим, разделителем в списке переменных должна быть запятая, то любой другой знак будет восприниматься как ошибка. Если точка с запятой является разделителем операторов, то в качестве оператора компьютер воспринимает всю часть текста программы от одной точки с запятой до другой. Если программист забыл поставить «;» между какими-то двумя операторами, то компьютер будет принимать их за один с неизбежной ошибкой.
В программу на Паскале можно вставлять комментарии. Комментарий — это пояснение к программе, которое записывается в фигурных скобках. В комментариях можно использовать русские буквы. На исполнение программы комментарий никак не влияет.
Заметим, что в Паскале нет различия между строчными и прописными буквами. Например, для Паскаля тождественны следующие варианты записи: begin, Веgin, ВЕGIN, ВеGIN. Использование строчных или прописных букв — дело вкуса программиста.
Коротко о главном
Паскаль — универсальный язык программирования.
Программа на Паскале состоит из заголовка, описаний и операторов.
Формат заголовка программы:
Формат описания переменных:
Операторы ввода данных с клавиатуры:
Операторы вывода на экран:
Арифметический оператор присваивания:
Арифметическое выражение может содержать любое количество арифметических операций и функций.
Последовательность выполнения операций определяется расстановкой скобок и старшинством операций (приоритетами). Старшие операции: *, /; младшие операции: +, — .
Точка с запятой ставится в конце заголовка программы, в конце описаний, а также является разделителем операторов. Текст всей программы заканчивается точкой.
Вопросы и задания
1. Когда появился язык Паскаль и кто его автор?
2. Как записывается заголовок программы на Паскале?
3. Как записывается раздел описания переменных?
4. С какими типами числовых величин работает Паскаль?
5. Как записываются операторы ввода и вывода в Паскале?
6. Что такое оператор присваивания?
7. Как записываются арифметические выражения?
8. По каким правилам определяется порядок выполнения операций в арифметическом выражении?
9. Какая задача решается по следующей программе?
Program Test;
var A, B, C: integer;
begin
readln(A, B) ;
C:=(A+B) * (B-A)
writeln(C)
end.
Какой результат будет получен, если в качестве исходных значений А и В ввести соответственно 7 и 8?
10. Составьте программы на Паскале для решения задач № 6-9 из заданий к § 34. При этом отмените ограничения на количество операций в арифметическом выражении, сформулированные в условиях задач.
