Построение и анализ алгоритмов

УРОК 2

Построение и анализ алгоритмов

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

На практике наиболее распространены следующие формы представления алгоритмов:

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

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

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

Рассмотрим словесный способ записи еще на одном простом примере. Пусть требуется найти модуль величины X (то есть значение │X│) и присвоить это зна­чение переменной Y. При построении алгоритма воспользуемся определением модуля: │х│ = х при х ≥0 и │х│= - х при х<0. Алгоритм можно записать сле­дующим образом.

1.  Начало.

2.  Ввести числовое значение величины X.

3.  Если Х ≥ 0, то Y присвоить значение X, иначе Y присвоить значение - X.

4.  Вывести значение Y.

5.  Конец.

Словесная запись чаще всего применяется на начальном этапе изучения алгоритмов и предназначается для использования алгоритма человеком. Од­нако эта форма записи алгоритма не имеет широкого распространения, так как обладает существенными недостат­ками:

строго не формализуемы; недостаточно наглядны; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний: трудно непо­средственно переложить на язык программы.

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

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

Например, запись алгоритма начинается и заканчивается сле­дующими блоками:

Эти элементы называются блоками начала и конца алгоритма. Стрелки обозна­чают направление выполнения алгоритма. Блок Начало имеет одну выхо­дящую стрелку, а блок Конец - одну входящую стрелку.

В алгоритмах часто встречаются команды ввода и вывода значений. Этим командам отвечают блоки ввода-вывода:

Здесь левый блок обозначает ввод величины X, а правый блок - вывод Y. С помощью приведенных выше блоков вы можете составить простейший алгоритм ввода величины X:

Согласно этому алгоритму в программу вводится значение величины X. Однако программа, состоящая только из операции ввода, вряд ли имела бы смысл.

Обычно над введенной величиной выполняются определенные действия, которые обозначаются прямоугольными (операторными) блоками вида:

Внутри прямоугольников записаны выражения, выполняемые над величинами. Левый блок обозначает присваивание переменной X значения суммы Х + 1. Правый блок отвечает нахождению разности X-Y и присваиванию значения разности переменной Z. Операторные блоки могут иметь несколько входов и только один выход. Запишем простейший алгоритм вычисления квадрата некоторого числа:

Согласно этому алгоритму выполняется ввод величины X, затем вычисляется квадрат этой величины (произведение Х*Х) и выводится полученное значение.

Все приведенные выше блоки позволяют организовать последовательное выполнение инструкций алгоритма. Однако на практике часто возникают ситуации, когда в зависимости от выполнения какого-либо условия требуется изменить последовательный ход вычислений. Примером такого условия является неравенство Х>0 в алгоритме нахождения модуля числа X. В схему алгоритма логическое условие вводится с помощью условного блока. Этот блок принято изображать в виде ромба с одним входом и двумя выходами:

Если условие, указанное на изображении блока, выполняется (условие имеет значение Истина), то происходит переход по стрелке Да, если не выполняется (значение Ложь) - по стрелке Нет. Благодаря условному блоку вычислительный процесс как бы разветвляется, то есть условный блок используется для организации ветвления.

Приведем как пример алгоритм вычисления модуля числа. Запись этого алгоритма ограничивают блоки начала и конца алгоритма. За блоком начала алгоритма следует блок ввода значений X, а за ним - условный блок. В условном блоке выполняется проверка условия Х>0 и в результате проверки осуществляется переход по одной из ветвей Да или Нет. На каждой из ветвей находится операторный блок присваивания значений переменной Y. После операции присваивания ветви алгоритма сходятся, и следующая инструкция алгоритма содержится в блоке вывода полученного значения Y.

В таблице приведены наиболее часто употребляемые символы.  

Название символа	Обозначение и пример заполнения	Пояснение
Процесс, присваивание		Вычислительное действие или последовательность действий (обрабатывает данные и размещает результаты в ячейки памяти с указанным именем)
Блок проверка условия		Проверка условий
Блок цикла с параметром		Начало цикла
Предопределенный процесс (блок обращения к подпрограмме)		Вычисления по подпрограмме, стандартной подпрограмме
Ввод-вывод		Ввод-вывод в общем виде
Пуск-остановка		Начало, конец алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов на печать

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

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

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

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

Основные понятия, использующиеся в алгоритмических языках

Каждое понятие алгоритмического языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных.

Основными понятиями в алгоритмических языках обычно являются следующие:

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

2.  Операции. Типы операций:

операция присваивания. С помощью присваивания переменные получают новые значения:

А: =13

D1:=C

X:=Х+1

В левой части инструкции ставится идентификатор величины, а в правой части - обычная форма алгебраического выражения. В операторах присваивания используется либо привычный знак равенства, либо сочетание двоеточия и знака равенства Поскольку знак присваивания - это не знак равенства, возможны записи вида: Х:=Х+1 или А:=А-В. Нужно учитывать, что оператор, присваивания будет выполняться только в том случае, если значения всех переменных в правой части уже определены.

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

арифметические операции   +   ,   —   ,   *   ,   /   и дp. ; логические операции   и   ,   или   ,   не  ;

Логические операции выполняются над величинами логического (булевского) типа. К наиболее употребляемым логическим операциям относятся: логическое отрицание (not), логическое И (and), логическое ИЛИ (or) и исключающее ИЛИ (xor). Эти операции проще всего описать с помощью приведенных ниже таблиц, в которых операндами являются переменные А и В.

Смысл всех логических операций очевиден. Отрицание обращает значение логического операнда. Логическое И дает истинное значение лишь в случае, когда оба операнда имеют значение True. Напротив, для истинного значения логического ИЛИ достаточно, чтобы хотя бы один из операндов был True. Операция исключающего ИЛИ отличается от логического ИЛИ тем, что она истинна, когда только один операнд принимает значение True.

операции отношения   <   ,   >   ,   <=   ,   >=   ,   =   ,   <>   ;

Результатом этих операций являются значения True или False. Например, выражение А=В принимает значение True, если А равно В, и False - в противном случае.

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

Приоритет операций

Очередность выполнения операций в выражениях называется приори­тетом. Так в выражении А+В*С сначала будет выполнено умножение, а затем сложение, поскольку операция * имеет более высокий приоритет, чем +. Пере­числим порядок выполнения операций согласно их приоритету:

1.  Операция not - логическое отрицание.

2.  Операции типа умножения: *, /, div, mod, and.

3.  Операции типа сложения: +, –, or, хог.

4.  Операции отношения: =, <> (не равно), <, >, <=, >=.

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

3.  Данные — величины, обрабатываемые программой. Имеется три основных вида данных: константы, переменные и массивы.

Каждая величина имеет имя, значение и тип. Имя величины (например: «а», «х1», «ср23», «date1») служит для обозначения величины в алгоритме. Во время выполнения алгоритма в каждый конкретный момент величина имеет какое-то значение либо не определена. Если значением величины может быть только целое число, то величина называется целой или целочисленной, если любое вещественное число – то вещественной. Эта характеристика величины называется типом величины. Для того, чтобы запомнить или изменить значение величины, в алгоритмическом языке есть специальная команда – команда присваивания, которая записывается в виде: имя величины := выражение. При выполнении команды присваивания ПК сначала вычисляет записанное в правой части выражение (заменяя имена величин на их значения), а потом полученное значение выражения записывает в память.

Константы — это данные, которые зафиксированы в тексте программы и не изменяются в процессе ее выполнения.

Примеры констант:

o  числовые   7.5, 12;

логические   да (истина),   нет   (ложь); символьные (содержат ровно один символ)   "А"   ,   "+"   ; литерные (содержат произвольное количество символов) "a0",  "Мир",  ""  (пустая строка).
Переменные обозначаются именами и могут изменять свои значения в ходе выполнения пpогpаммы. Переменные бывают целые, вещественные, логические, символьные и литерные. Массивы — последовательности однотипных элементов, число которых фиксировано и которым присвоено одно имя. Положение элемента в массиве однозначно определяется его индексами (одним, в случае одномерного массива, или несколькими, если массив многомерный). Иногда массивы называют таблицами.

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

Различают унарные и бинарные операции. В унарной операции участвует один операнд, а в бинарной - два операнда. Примером унарной операции явля­ется взятие обратного знака величины: - А. К бинарным операциям относятся арифметические операции сложения, умножения и т. д.

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

Различают выражения арифметические, логические и строковые.

•  Арифметические выражения служат для определения одного числового значения.  Например,  (1+sin(x))/2. Значение этого выражения при x=0 равно 0.5,  а при x=p/2 — единице.

•  Логические выражения описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Таким образом, логическое выражение может принимать только два значения —  "истина"  или  "ложь"  (да  или  нет). Рассмотрим в качестве примера логическое выражение  x*x + y*y < r*r,  определяющее принадлежность точки с координатами  (x, y)  внутренней области круга радиусом  r  c центром в начале координат.  При  x=1,  y=1,  r=2 значение этого выражения —  "истина", а при  x=2,  y=2,  r=1  — "ложь".

•  Строковые (литерные) выражения, значениями которых являются тексты. В строковые выражения могут входить литерные и строковые константы, литерные и строковые переменные, литерные функции, разделенные знаками операции сцепки. Например, А + В означает присоединение строки  В  к концу строки  А . Если   А = "куст ",   а   В = "зеленый",   то значение выражения   А + В   есть   "куст зеленый".

5.  Операторы (команды). Действия, выполняемые над величинами, обозначаются операторами. Оператор - это законченное выражение, которое трактуется однозначным образом. Оператор – это наиболее крупное и содержательное понятие языка: каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных.

В состав операторов входят:

ключевые слова; данные; выражения и т. д.

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

Базовые структуры

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

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

Особенности базовых структур:

1.  Каждая базовая структура имеет один вход и один выход. При конструировании выход каждой базовой структуры присоединяется к входу другой.

2.  Полнота – из основных базовых структур можно собрать алгоритм любой степени сложности

3.  Однозначность – выполнение разными исполнителями приводит к одинаковому результату.

Схема следования

Схема следования состоит из двух блоков S1 и S2, каждый из которых в простейшем случае может быть арифметическим оператором. Эта структура означает, что два блока алгоритма могут быть размещены друг за другом. Схема следования отвечает двум последовательно выполняемым дейст­виям, к примеру:

сум:=0

n:=100

Схема ветвления

Схема ветвления в общем случае отвечает условному оператору и состоит из условия Р и блоков S1 и S2. Если один из блоков отсутствует, то приходим к неполному условному оператору. Она обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах:

Если – то; Если – то – иначе; выбор; выбор – иначе.

Школьный алгоритмический язык	Язык блок-схем
1. если—то
если условие   то действия все
2. если—то—иначе
если условие   то действия 1   иначе действия 2 все
3. выбор
выбор   при условие 1: действия 1   при условие 2: действия 2     при условие N: действия N все
4. выбор—иначе
выбор   при условие 1: действия 1   при условие 2: действия 2     при условие N: действия N   иначе действия N+1 все

Примеры структуры ветвление

Школьный алгоритмический язык	Язык блок-схем
если x > 0   то y := sin(x) все
если a > b то a := 2*a; b := 1 иначе b := 2*b все
выбор   при n = 1: y := sin(x)   при n = 2: y := cos(x)   при n = 3: y := 0 все
выбор при a > 5: i := i+1 при a = 0: j := j+1 иначе i := 10; j:=0 все

 

Схема цикла

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

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

Основные разновидности циклов представлены в таблице:

Школьный алгоритмический язык	Язык блок-схем
Цикл типа N раз. Предписывает выполнить некоторую последовательность команд N раз подряд
нц N раз тело цикла (последовательность действий, команд) кц
Цикл типа пока. Предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова пока.
нц пока условие   тело цикла   (последовательность действий) кц
Если условие цикла ПОКА не соблюдается с самого начала, то тело цикла не выполниться ни разу. Выполнение цикла ПОКА может и не завершиться, если условие все время будет соблюдаться (эту операцию называют зацикливанием). Чтобы не запутываться необходимо продумывать цикл по частям: 1.  Понять, когда цикл должен закончиться, т. е. сформировать условие окончание цикла. Записать после пока противоположное условие – условие продолжения цикла. 2.  Выяснить, что и как будет меняться в цикле, описать промежуточные состояния после нескольких повторений цикла. 3.  Описать, что происходить при однократном выполнении цикла (за один шаг цикла), т. е. записать тело цикла. 4.  Проверить, что рано или поздно цикл закончиться, а не будет повторяться вечно.
Цикл типа для. Предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
нц для i от i1 до i2   тело цикла   (последовательность действий) кц

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

Примеры структуры цикл

Школьный алгоритмический язык	Язык блок-схем
нц пока i <= 5   S := S+A[i]   i := i+1 кц
нц для i от 1 до 5   X[i] := i*i*i   Y[i] := X[i]/2 кц

СРАВНЕНИЕ КОМАНД ЦИКЛА (повторения)

1.  Каждая из команд цикла содержит серию повторяемых команд, называемую телом цикла. В каждой из них в той или иной форме дается указание на число повторений.

2.  Команды N РАЗ и ДЛЯ имеют одно общее свойство – количество повторений цикла известно в момент начала его исполнения.

3.  В цикле N РАЗ при каждом повторении исполняется одно и та же серия команд, номер повторения при исполнении цикла неизвестен. В цикле ДЛЯ появляется дополнительная величина – параметр цикла. Таким образом серия команд может зависеть от номера повторения. Поэтому если повторяются одинаковые действия, можно применять цикл N РАЗ, если действия необходимо варьировать, нужен цикл ДЛЯ.

4.  Для команды ПОКА число повторений определяется в ходе выполнения этой команды. величины, для которых проверяется условие повторения, могут меняться более сложно, чем параметр цикла в команды ДЛЯ.

Команды повторения (цикла) N РАЗ и ДЛЯ взаимозаменяемы и обе могут быть заменены командой ПОКА, т. е. используя команду ПОКА, сравнительно несложно реализовать команды N РАЗ и ДЛЯ. Команда ПОКА в общем случае не может быть заменена командами циклов других типов.

Что такое вложенные циклы?

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

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

Пример вложенных циклов   для  

Вычислить сумму элементов заданной матрицы А(5,3).

Матрица А

S := 0; нц для i от 1 до 5   нц для j от 1 до 3   S:=S+A[i, j]   кц кц

Пример вложенных циклов   пока  

Вычислить произведение тех элементов заданной матрицы A(10,10), которые расположены на пересечении четных строк и четных столбцов.

i:=2; P:=1 нц пока i <= 10   j:=2 нц пока j <= 10   P:=P*A[i, j]   j:=j+2   кц   i:=i+2 кц

Комбинирование базовых структур

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

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

·  разработка алгоритма «сверху вниз»;

·  модульное построение алгоритма;

·  метод пошаговой детализации.

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

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

·  подсоединять одну структуру к другой, образуя последовательность структур;

·  заменять функциональные блоки S1 и S2 любой из базовых структур вло­женными в них структурами.

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

Еще одним преимуществом структурного подхода является его модуль­ность. Программу, построенную на основе структурного алгоритма, можно представить в виде отдельных модулей.

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

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

Метод пошаговой детализации

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

Рассмотрим метод пошаговой детализации на примере решения квадратного уравнения ах2 + bх + с = 0. На первом этапе решаются такие задачи:

1.  Ввод данных;

2.  Расчет детерминанта;

3.  Анализ существования корней уравнения и их вычисление;

4.  Вывод результата расчета;

5.  Завершение задачи.

На втором этапе производится детализация каждого из названных пунктов. Рассмотрим для примера пункт 1:

1.1.  Ввести коэффициент а;

1.2.  Если а = 0, сообщить, что уравнение является линейным и перейти к пункту 5;

1.3.  Ввести коэффициент b;

1.4.  Ввести коэффициент с;

1.5.  Получить у пользователя подтверждение, что значения коэффициентов вер­ны, если нет, то вернуться к пункту 5.

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

Writeln ( 'введите коэффициент а= ', а);

Readln (а);

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

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

Вспомогательные алгоритмы (подалгоритмы)

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

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

Если вспо­могательный алгоритм в процессе работы программы выполняется много­кратно, отличаясь только параметрами, то обычно прибегают к оформлению вспомогательного алгоритма в виде алгоритма-процедуры (или алгоритма-функции).

Практические задания

Задание:

найти соответствие между свойствами алгоритма и их словесным описанием:

Свойство алгоритма	Описание
Дискретность	Алгоритм состоит из последовательности отдельных элементарных действий - шагов. Только выполнив одно действие, исполнитель сможет приступить к выполнению следующего
Определенность	Каждая команда алгоритма определяет однозначное действие исполнителя.
Понятность	Все команды алгоритма должны входить с систему команд исполнителя.
Результативность	Исполнение алгоритма всегда приводит к решению задачи.
Конечность	Алгоритм будет завершен за конечное число шагов.
Массовость	С помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно.
Правильность	Выполнение алгоритма дает правильные результаты решения задачи.

Примеры алгоритмов:

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

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

•  задумать произвольное натуральное число

•  умножить это число на 5

•  к результату прибавить 8

•  сумму умножить на 2

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

Далее учитель предлагает составить алгоритм и на основе этого алгоритма сделать вывод: как учитель мгновенно называл задуманное число.

Ученик работает у доски, остальные учащиеся и учитель ему помогают.

алгоритм: (x*5+8)*2=a a - результат, известен

10*x+16=a
10*x=a-16 т. е. из результата надо вычесть 16 и отбросить крайнюю правую цифру.

3. Логическая старинная задача «Волк, коза и капуста»

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

–  перевезти козу

–  вернуться назад

–  перевезти волка

–  перевезти козу обратно

–  перевезти капусту

–  вернуться назад

–  перевезти козу