Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Алгоритмом называется четкое описание последовательности действий, которые необходимо выполнить для решения задачи. Любая задача требует получения результата по заданным исходным данным, т.е. алгоритм описывает последовательный процесс преобразования исходных данных в результат.
Разработать алгоритм решения задачи означает разбить задачу на последовательно выполняемые шаги (этапы), причем результаты выполнения предыдущих этапов могут использоваться при выполнении последующих. При этом должны быть четко указаны как содержание каждого этапа, так и порядок выполнения этапов. Отдельный этап (шаг) алгоритма представляет собой либо другую, более простую задачу, алгоритм решения которой разработан ранее, либо должен быть достаточно простым и понятным без пояснений. После разработки алгоритма его можно реализовать практически на любом языке программирования.
На практике используются следующие формы представления алгоритмов:
Словесный способ представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например: записать алгоритм определения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида). Алгоритм может быть следующим:
Данный способ плохо формализуем и практически применяется редко.
Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими направление потоков данных.
Основные элементы блок-схемы алгоритма. Правила выполнения схем и обозначения для отдельных операций процесса обработки данных регламентирует Государственный стандарт (ГОСТ 19.701-90 «Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения»).
Алгоритмические языки близки к естественному языку, поэтому для них характерны: алфавит, операции – слова, операторы – предложения, синтаксис – правила написания.
Правила построения конструкций в алгоритмическом языке более «жесткие». Это означает, что алгоритмические языки допускают меньше разнообразия для описания действий алгоритма, чем естественный язык и привычная математическая символика, и машина однозначно понимает любую конструкцию языка. Например, для умножения двух переменных a и b общепринятая математическая символика допускает несколько возможных форм записи:
ab ab ab a*b.
На алгоритмическом же языке эту операцию можно записать только единственным образом как a*b. Алгоритмический язык занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в алгоритмическом языке используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
Примером алгоритмического языка является псевдокод, приведенный в таблице:
|
алг (алгоритм) |
сим (символьный) |
дано |
для |
да |
|
арг (аргумент) |
лит (литерный) |
надо |
от |
нет |
|
рез (результат) |
лог (логический) |
если |
до |
при |
|
нач (начало) |
таб (таблица) |
то |
знач |
выбор |
|
кон (конец) |
нц (начало цикла) |
иначе |
и |
ввод |
|
цел (целый) |
кц (конец цикла) |
все |
или |
вывод |
|
вещ (вещественный) |
длин (длина) |
пока |
не |
утв |
Общий вид алгоритма:
алг название алгоритма (аргументы и результаты)
нач описание промежуточных величин
| последовательность команд (тело алгоритма)
кон
Часть алгоритма от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон – телом алгоритма.
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное граничными парами по каждому индексу элементов массива.
Примеры предложений алг:
алг объем_и_площадь_цилиндра (арг вещ R, H, рез вещ V, S)
алг диагональ (арг цел N, арг цел таб A[1:N, 1:N], рез лит otvet)
Пример записи на алгоритмическом языке:
алг произведение (арг цел n, m, рез цел s)
нач цел i
| ввод n, m
| s:=0
| i:=0
| нц пока i<n
| | s:=s+m
| | i:=i+1
| кц
| вывод s
кон
На самом деле изложение структурного стиля не может уместиться в рамки одной лекции. Но данный стиль программирования (вернее, его вариант, основанный на циклах и массивах, слегка пополненный рекурсивными процедурами) описывается и навязывается как единственно возможный во всех ныне предлагаемых учебных пособиях по программированию на традиционных языках. В связи с этим мы имеем право предположить, что обучающийся знаком с ним (более того, знаком только с ним, и мы надеемся, что он еще не потерял способность воспринимать другие стили). И хотя Вы считаете, что с этим вариантом структурного стиля уже освоились, особенности, опускаемые в традиционных изложениях, могут полностью изменить Ваш взгляд на данный стиль.
Начнем с того, что обратимся к истории.
В теории схем программ было замечено, что некоторые случаи блок-схем легче поддаются анализу. Поэтому естественно было выделить такой класс блок-схем, что и сделали итальянские ученые С. Бем и К. Джакопини в 1966 г. Они доказали, что любую блок-схему можно привести к структурированному виду, использовав несколько дополнительных булевых переменных. Э. Дейкстра подчеркнул, что программы в таком виде, как правило, являются легче понимаемыми и модифицируемыми, так как каждый блок имеет один вход и один выход.
В качестве методики структурного программирования Э. Дейкстра предложил пользоваться лишь конструкциями цикла и условного оператора, изгоняя go to как концептуально противоречащее этому стилю2).
Структурное программирование основано главным образом на теоретическом аппарате теории рекурсивных функций. Программа рассматривается как частично-рекурсивный оператор над библиотечными подпрограммами и исходными операциями. Структурное программирование базируется также на теории доказательств, прежде всего на естественном выводе. Структура программы соответствует структуре простейшего математического рассуждения, не использующего сложных лемм и абстрактных понятий).
Средства структурного программирования в первую очередь включаются во все языки программирования традиционного типа и во многие нетрадиционные языки.
При структурном программировании присваивания и локальные действия становятся органичной частью программы. Достаточно лишь внимательно следить, чтобы каждая переменная в модуле использовалась для одной конкретной цели, и не допускать "экономии", при которой ненужная в данном месте переменная временно используется под совсем другое значение. Такая "экономия" запутывает структуру информационных зависимостей, которая при данном стиле должна быть хорошо согласована со структурой программы.
Структурное программирование естественно возникает во многих классах задач, прежде всего в таких, где задача естественно расщепляется на подзадачи, а информация - на достаточно независимые структуры данных. Основной его инвариант: действия и условия локальны.
Необходимой чертой хорошей реализации структурного стиля программирования является соблюдение согласованности, а в идеале и единства, следующих компонентов программы:
Для структурного стиля программирования требуется следующее. Задача разбивается на подзадачи, и таким образом выстраивается дерево вложенности подзадач. Информационное пространство структурируется в точном соответствии с деревом вложенности: для каждой подзадачи оно состоит из ее локальных объектов, определяемых вместе с подзадачей и для нее, и так называемых глобальных объектов, определяемых как информационное пространство непосредственно объемлющей подзадачи. Таким образом, информационное пространство всей задачи (подзадачи самого верхнего уровня) расширяется по мере перехода к подзадачам за счет их локальных объектов. Для различных дочерних подзадач одной подзадачи оно имеет общую часть - информационное пространство родительской подзадачи4).
Внимание!
Этой альтернативы Вы не встретите в традиционных изложениях структурного программирования. Концептуальное противоречие между циклами и рекурсиями намного мягче, чем между операторами структурного программирования и структурными переходами, и оно отмечается лишь в виде изредка встречающихся прагматических указаний (благих пожеланий) не смешивать их произвольно.
Первым обратил внимание на необходимость введения призраков для логического и концептуального анализа программ Г. С. Цейтин в 1971 г. В Америке это "независимо" открыли заново в 1979 г., хотя упомянутая статья Цейтина была опубликована на английском языке в общедоступном издании. Даже название сущностям было дано то же самое... Этому важнейшему и традиционно игнорируемому понятию посвящена отдельная лекция в курсе "Основания программирования".
Подпорки противоположны призракам. На самом деле они являются той формой, в которой материя проникает в программу, и в этом качестве противостоят всей совокупности идеальных сущностей, порождающих структуру программы: как реальных, так и призрачных, - и порою грубо ее искажают. Но без подпорок программа просто не будет работать или будет работать неэффективно.
Для структурного программирования весьма важно требование:
Все структуры подчиняются структуре информационного пространства.
Это общее требование конкретизируется в следующие.
Структурное программирование лучше всего описано теоретически, но частные описания не сведены в единую систему.
Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (основных) элементов. Базовые структуры алгоритмов – это набор символов (блоков) и стандартных способов их соединений для выполнения типичных последовательностей действий.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
Образуется последовательностью действий, следующих одно за другим:
Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Разветвляющаяся структура существует в следующих вариантах:
Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Структура цикл существует в следующих вариантах:
Словесное описание …
Словесное описание …
Сортировку массива осуществим с помощью метода «пузырька». Метод заключается в том, что попарно сравниваются элементы массива, начиная с первых двух. Если последующий элемент меньше предыдущего, то они меняются местами. После этого аналогично сравнивается третий элемент и больший из двух предыдущих, затем четвертый и больший из двух предыдущих и т.д. до конца массива. После этого вся описанная процедура повторяется заново для полученного на предыдущем этапе массива и т.д. до тех пор, пока больше не будет происходить перестановок элементов массива. Таким образом, максимальный элемент массива как будто бы «всплывает» как пузырек к концу массива, за ним – следующий по значению и т.д.
Псевдокод:
Данный алгоритм, как это видно из его описания, содержит в себе вложенный цикл (цикл со счетчиком – цикл «для» внутри цикла с предусловием – цикла «пока»).
Развёрнутая схема алгоритма (самостоятельно):
Схема с альтернативными обозначениями циклов (самостоятельно):
Когда одни и те же вычисления должны выполняться в различных участках программы, собственно расчетные операции выделяют в подпрограмму.
Разрабатывая схему алгоритма, мы должны всегда доводить ее до уровня типовых приемов программирования. Для каждого из типовых приемов программирования на схеме алгоритма имеется один вход и один выход. Это означает, что на укрупненной схеме алгоритма соответствующие участки выглядят как линейные. Поэтому и удается на укрупненной схеме избегать ненужных подробностей, детализируя их по мере необходимости, при раскрытии структуры отдельных блоков.
Пример использования подпрограмм:
алг Alg(арг вещ X, Y, Z, рез вещ D) алг F1(арг вещ Arg, рез вещ Res)
нач нач
| ввод X, Y, Z | Res:=Arg*Arg
| A:=F1(X) кон
| B:=F2(Y,Z)
| C:=F2(A,B) алг F2(арг вещ Arg1, Arg2, рез вещ Res)
| D:=A+B+C нач
| вывод D | Res:=Arg1*Arg2
кон кон
Схема алгоритма:
Рекурсивным называется алгоритм (или функция), содержащий в себе вызов самого себя (обращение к самому себе). Простой рекурсией является использование операции присваивания в следующем виде:
a:=a+1.
Классическим примером рекурсивного алгоритма является функция вычисление факториала целого числа N! = 1·2·3·…·N, N ≥ 0, 0! = 1.
алг Факториал(арг цел N, рез цел F)
нач
| если N=0
| | то F:=1
| | иначе F:=Факториал(N-1)*N
| все
кон
Результатом работы следующего алгоритма:
алг
нач
| A:=Факториал(5)
| вывод A
кон
является значение A=120=5!.
Из рекурсивной функции необходимо предусмотреть выход, иначе вызов такой функции может привести к «зависанию» алгоритма. В рассмотренном примере условием выхода из рекурсии является проверка условия N=0, при выполнении которого функция возвращает 1. Однако данное условие неработоспособно, если будет введено отрицательное значение (N<0) аргумента функции. В этом случае функция F будет бесконечно вызывать саму себя, поэтому для предотвращения бесконечной рекурсии здесь необходимо предусмотреть и проверку условия N<0, при выполнении которого должно выдаваться сообщение об ошибке ввода.
Рекурсия бывает прямой и косвенной:
PAGE 5
a:=b/c
Процесс – обработка данных любого вида.
Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок.
Решение – решение или функция переключательного типа, имеющая один вход и ряд альтернативных выходов, один и только один из которых может быть активизирован после вычисления условий, определенных внутри этого символа.
Терминатор – выход во внешнюю среду и выход из внешней среды, начало или конец схемы программы.
a>b
да
нет
Начало
Данные – символ отображает данные, носитель данных не определен.
Ввод
a, b, c
Предопределённый процесс – предопределенный процесс, состоящий из одной или нескольких операций или шагов программы, которые определены в другом месте.
Расчёт параметров
Комментарий – комментарии к алгоритму.
Блок «комментарий» применяется добавления описательных комментариев или пояснительных записей в целях объяснения или примечаний. Пунктирные линии связаны с соответствующим символом или могут обводить группу символов.
екст
комментария
A
Соединитель – обрыв линий, выход в часть схемы и вход из другой части этой схемы.
B
Ввод
a, b, c
Конец F1
B:=F2(Y,Z)
Начало F1
C:=F2(A,B)
Вывод
D
D:=A+B+C
Введите
a, b, c
A:=F1(X)
Дисплей – данные, представленные в человекочитаемой форме на носителе в виде отображающего устройства (экран, индикатор).
Ручной ввод – ввод данных вручную во время обработки с устройств любого типа (клавиатура, переключатели, кнопки, полоски со штриховым кодом).
Процесс или группа процессов
Граница цикла – вычисление в цикле.
имости от расположения операции, проверяющей условие.
Цикл 1
i:=0; i<n;
i:=i+1
Цикл 1
Линия – поток данных.
Символ отображает поток данных. При необходимости или повышения удобочитаемости могут быть добавлены стрелки-указатели.
алг
нач
| ……………
| действие 1
| действие 2
| ……………
| действие n
| ……………
кон
действие 1
Схема алгоритма
Алгоритмический язык
действие 2
действие n
Ввод
Arg
Б
Множественный выбор
нет
условие
алг сумма (арг вещ a, b, рез вещ s)
нач
| ввод a, b
| s:=a+b
| вывод s
кон
Ввод
a, b
тело цикла
s:=a+b
имя цикла
условие
Конец
Начало
тело цикла
да
Алгоритмический язык
Схема алгоритма
алг
нач
| ……………
| если условие
| | то действия
| все
| ……………
кон
действия
Ветвление (если-то-иначе)
нет
да
условие
алг
нач
| ……………
| если условие
| | то действия 1
| | иначе действия 2
| все
| ……………
кон
действия 1
действия 2
A
A
M[1]:=X[N]
Ввод
N, X[1:N]
Б
i:=i+1
i>i2
нет
да
Альтернативное обозначение
Б
b:=M[i]
M[i]:=M[i-1]
M[i-1]:=b
k:=1
i:=i+1
Алгоритмический язык
альтернатива n
A
альтернатива 1
Вывод
s
действия n
да
нет
min:=X[2]
num:=2
нет
тело цикла
i
действия 1
алг
нач
| ……………
| выбор i
| | при альтернатива 1: действия 1
| | ……………
| | при альтернатива n: действия n
| | иначе действия n+1
| все
| ……………
кон
действия 3
имя цикла,
i = i1,i2
да
нет
нет
да
Развёрнутая схема алгоритма
M[i-1]>M[i]
условие 2
действия 2
да
нет
условие 1
действия 1
да
алг
нач
| ……………
| если условие 1
| | то действия 1
| | иначе если условие 2
| | | то действия 2
| | | иначе действия 3
| | все
| все
| ……………
кон
i>N
имя цикла
действия n+1
иначе
имя цикла,
условие завершения
начальные присваивания
1. Цикл с предусловием
алг
нач
| ……………
| начальные
| присваивания
| нц пока условие
| | тело цикла
| | (действия)
| кц
| ……………
кон
тело цикла
i:=i1
3. Цикл со счётчиком
алг
нач
| ……………
| нц для i от i1 до i2
| | тело цикла
| | (действия)
| кц
| ……………
кон
имя цикла
тело цикла
имя цикла,
условие завершения
условие
да
нет
тело цикла
начальные присваивания
2. Цикл с постусловием
алг
нач
| ……………
| начальные
| присваивания
| нц
| | тело цикла
| | (действия)
| кц пока условие
| ……………
кон
k:=0
i:=2
M[1:N]:=X[1:N]
k:=1
A
A
k=1
нет
да
min:=X[3]
num:=3
да
нет
X[3]<min
min:=X[1]
num:=1
Ввод
X[1:3]
Вывод
min
Конец
Начало
алг мин (арг вещ таб X[1:3], рез вещ min, рез цел num)
нач
| ввод X
| если X[2]<X[1]
| | то min:=X[2], num:=2
| | иначе min:=X[1], num:=1
| все
| если X[3]<min
| | то min:=X[3], num:=3
| все
| вывод min, num
кон
нет
да
X[2]<X[1]
A
Вывод
M
i>N
M[i]:=X[i-1]
i:=i+1
Конец
A
Цикл 1
A
A
M:=X[N]
i:=2
Цикл 1
i=2,N
нет
да
Ввод
N, X[1:N]
Вывод
M
Конец
Ввод
N, X[1:N]
Вывод
M
Начало
алг сдвиг (арг цел N, арг таб вещ X[1:N], рез таб вещ M[1:N])
нач цел i
| ввод N, X
| M[1]:=X[N]
| нц для i от 2 до N
| | M[i]:=X[i-1]
| кц
| вывод M
кон
M[i]:=X[i-1]
Конец
Начало
Начало
Цикл 1
b:=M[i]
M[i]:=M[i-1]
M[i-1]:=b
k:=1
нет
да
M[i-1]>M[i]
Цикл 2
i=2,N
Цикл 2
Цикл 1
k=1
Б
Б
А
k:=0
M[1:N]:=X[1:N]
k:=1
A
Ввод
N, X[1:N]
Вывод
M
Конец
Начало
алг сорт (арг таб цел N, арг таб вещ X[1:N], рез таб вещ M[1:N])
нач цел i, k
| ввод N, X[1:N]
| M[1:N]:=X[1:N]
| k:=1
| нц пока k=1
| | k:=0
| | нц для i от 2 до N
| | | если M[i-1]>M[i]
| | | | то b:=M[i]
| | | | M[i]:=M[i-1]
| | | | M[i-1]:=b
| | | | k:=1
| | | все
| | кц
| кц
| вывод M
кон
1
Alg
1
Вывод
Res
Res:=Arg1*Arg2
Ввод
Arg1, Arg2
Конец F2
Начало F2
Ввод
X, Y, Z
Res:=Arg*Arg
Вывод
Res