Алгоритмы, структуры алгоритмов, структурное программирование

Урок Дата

Тема: Алгоритмы, структуры алгоритмов, структурное программирование

Цель:

Учащиеся должны знать

- этапы решения задачи на компьютере:

- что такое исполнитель алгоритмов, система команд исполнителя

- какими возможностями обладает компьютер как исполнитель алгоритмов

- система команд компьютера

- классификация структур алгоритмов

- основные принципы структурного программирования

Ход урока

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

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

Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Существует

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

Алгоритм можно записывать различными способами (словесное описание, графическое описание – блок схема, программа на одном из языков программирования и т.д.). 

Программа – это алгоритм, записанный на языке программирования.

 Для создания алгоритма (программы) необходимо знать:

полный набор исходных данных задачи (начальное состояние объекта);

 цель создания алгоритма (конечное состояние объекта);

  систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

 Полученный алгоритм  (программа) должен обладать следующим набором свойств:

         дискретность (алгоритм разбит на отдельные шаги - команды);

         однозначность (каждая команда определяет единственно возможное действие исполнителя);

         понятность (все команды алгоритма входят в систему команд исполнителя);

         результативность (исполнитель должен решить задачу за конечное число шагов).

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

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

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

 Приведем пример описания алгоритма суммирования двух величин в виде блок-схемы:

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

 Типовые алгоритмические структуры.

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

Линейная структура (следование).

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

 Ветвление.

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

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

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

 Цикл (повторение).

Цикл позволяет организовать многократное повторение одной и той же последовательности команд - она называется телом цикла. В различных видах циклических алгоритмов количество повторений может зависеть от значения логического выражения (условия) или может быть жестко задано в самой структуре. Различают циклы : «до», «пока», циклы со счётчиком. В циклах «до» и «пока» логическое выражение (условие) может предшествовать телу цикла (цикл с предусловием) или завершать цикл (цикл с послеусловием).

  Циклы «до» - повторение тела цикла до выполнения условия:

 Циклы «пока» - повторение тела цикла пока условие выполняется (истинно):

Циклы со счётчиком (с параметром)  – повторение тела цикла заданное число раз:

Вспомогательный алгоритм (подпрограмма, процедура).

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

Методы разработки сложных алгоритмов.

Существует два метода разработки сложных алгоритмов:

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

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

 Алгоритмы и процессы управления.

Управление - целенаправленное взаимодействие объектов, одни из которых являются управляющими, другие - управляемыми.

В простейшем случае таких объектов два:

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

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

 Более подробно процессы управления изучаются рассматриваются кибернетикой. Эта наука утверждает, что самые разнообразные процессы  управления в обществе, природе и технике происходят сходным образом, подчиняются одним и тем же принципам.

Паскаль – язык структурного программирования.

Возникновение и назначение Паскаля

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

Среди современных языков программирования одним из самых популярных является язык Паскаль. Этот язык разработан в 1971 году и назван в честь Блеза Паскаля — французского ученого, изобретателя механической вычислительной машины. Автор языка Паскаль — швейцарский профессор Никлаус Вирт.

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

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

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

Структура программы на Паскале

Даже не заглядывая в учебник по Паскалю, в этой программе можно все понять (особенно помогает знание английского языка).

Заголовок программы начинается со слова Рrogram (программа), за которым следует произвольное имя, придуманное программистом:

Рrogram ;

Раздел описания переменных начинается со слова Var (variables — переменные), за которым идет список имен переменных через запятую. Тип указывается после двоеточия. В стандарте языка Паскаль существуют два числовых типа величин: вещественный и целый. Слово integer обозначает целый тип (является идентификатором целого типа). Вещественный тип обозначается словом геаl. Например, раздел описания переменных может быть таким:

var  а, b : integer; с, d : real;

Идентификаторы переменных составляются из латинских букв и цифр; первым символом обязательно должна быть буква.

Раздел операторов — основная часть программы. Начало и конец раздела операторов программы отмечаются служебными словами begin (начало) и end (конец). В самом конце программы ставится точка:

begin
     
end.

Операторы ввода, вывода, присваивания

Ввод исходных данных с клавиатуры происходит по оператору геаd (гead — читать) или геаdln (геad line — читать строку):

       геаd ();
или геаdln ();

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

Вывод результатов происходит по оператору write (write — писать) или writeln (write line — писать в строку):

       write (); 
или writeln ();

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

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

Арифметический оператор присваивания на Паскале имеет следующий формат:

 :=

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

Знаки основных арифметических операций записываются так:

+ сложение, 
- вычитание, 
* умножение, 
/ деление.

Правила записи арифметических выражений

Запись арифметических выражений на Паскале похожа на обычную математическую запись. В отличие от математики, где часто пропускается знак умножения (например, пишут 2А), в Паскале этот знак пишется обязательно: 2*А. Например, математическое выражение

А² + В² - 12С

на Паскале записывается так:

А*А + В*В - 12*С

Это же выражение можно записать иначе:

SQR (А) + SQR (В) - 12*С

Здесь использована функция возведения в квадрат — Аргументы функций всегда пишутся в круглых скобках.

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

   1    4    2   5      3
А * А + В * В - 12 * С

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

    6       1     3     2    4     5
А + ( (С - D) / (2 + К) - 1) *B

Пунктуация Паскаля

Необходимо строгое соблюдение правописания (синтаксиса) программы. В частности, в Паскале однозначно определено назначение знаков пунктуации.

Точка с запятой (;) ставится в конце заголовка программы, в конце раздела описания переменных, является разделителем операторов. Перед словом end точку с запятой можно не ставить.

Запятая (,) является разделителем элементов во всевозможных списках: списке переменных в разделе описания, списке вводимых и выводимых величин.

Строгий синтаксис в языке программирования необходим потому, что компьютер является формальным исполнителем программы. Если, допустим, разделителем в списке переменных должна быть запятая, то любой другой знак будет восприниматься как ошибка. Если точка с запятой является разделителем операторов, то в качестве оператора компьютер воспринимает всю часть текста программы от одной точки с запятой до другой. Если программист забыл поставить «;» между какими-то двумя операторами, то компьютер будет принимать их за один с неизбежной ошибкой.

В программу на Паскале можно вставлять комментарии. Комментарий — это пояснение к программе, которое записывается в фигурных скобках. В комментариях можно использовать русские буквы. На исполнение программы комментарий никак не влияет.

Заметим, что в Паскале нет различия между строчными и прописными буквами. Например, для Паскаля тождественны следующие варианты записи: begin, Веgin, ВЕGIN, ВеGIN. Использование строчных или прописных букв — дело вкуса программиста.

Коротко о главном

Паскаль — универсальный язык программирования.

Программа на Паскале состоит из заголовка, описаний и операторов.

Формат заголовка программы:

Рrogram ;

Формат описания переменных:

var  : ; …

Раздел операторов:

begin
          
end.

Операторы ввода данных с клавиатуры:

read (),    геаdln ().

Операторы вывода на экран:

write (,   writeln ().

Арифметический оператор присваивания:

: =

Арифметическое выражение может содержать любое количество арифметических операций и функций.

Последовательность выполнения операций определяется расстановкой скобок и старшинством операций (приоритетами). Старшие операции: *, /; младшие операции: +, - .

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

Домашняя работа: читать §12-14