|
Решение задач на компьютере основано на понятии алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от начальных данных к исходному результату. Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Алгоритмизация – это процесс построения алгоритма для решения задач на компьютере. Свойства алгоритмов: 1.Универсальность (массовость) – алгоритм может применяться к различным наборам исходных данных. 2. Дискретность - процесс решения задачи по алгоритму разбит на отдельные простые действия. 3. Однозначность - правила и порядок выполнения действий алгоритма должны пониматься однозначно. 4. Конечность - каждое из действий и весь алгоритм в целом обязательно завершаются. 5. Результативность - по завершении выполнения алгоритма обязательно получается верный результат. Это только некоторые, самые основные из свойств алгоритма. На самом деле их можно рассмотреть больше. Алгоритмы могут быть представлены разными способами: v словесно-формульное описание; v блок-схема (схема из графических символов); v алгоритмические языки; v операторные схемы; v псевдокод. Для записи алгоритма существуют общие правила. Каждый алгоритм должен иметь имя, которое поясняет его смысл. Начало и конец алгоритма должны быть четко указаны. Входные и выходные данные (что дано и что надо получить) нужно указать перед началом записи алгоритма. В теле указывают команды, которые позволяют выполнять определенные действия над данными. Общий вид алгоритма: vназвание алгоритма; vописание данных; vначало; vкоманды (тело алгоритма); vконец. Поясним на примерах способы записи алгоритмов. Словесно-формульный способ записи отличается тем, что описание осуществляется с помощью слов и формул. Т. е. человек записывает алгоритм словами с использованием профессиональных терминов, знаков и формул вычислений. Например: «Вывод X». X – целое число.
Графический способ описания алгоритма (блок - схема) получил самое широкое распространение. Для описания используются блоки, которые соединяются между собой линиями связи. Каждый шаг алгоритма представляется геометрическими фигурами (блоками). Они делятся на вычислительные (прямоугольник), логические условия (ромб) и блоки ввода-вывода данных (параллелограмм). Примеры блоков языка блок-схем указаны в таблице 2. Таблица 2. Элементы языка блок-схем
Порядок выполнения этапов указывается стрелками, соединяющими блоки. Чтобы изобразить цикл, рисуют стрелку от конечного блока к началу цикла. В начале или в конце цикла обязательно должен быть блок «Условие». Геометрические фигуры размещаются сверху вниз и слева направо. Нумерация блоков производится в порядке их размещения в схеме (рис. 100). Алгоритмические языки - это специальное средство, предназначенное для записи алгоритмов. Алгоритмические языки близки к математическим выражениям и к естественным языкам. Каждый алгоритмический язык имеет свой словарь. Алгоритм, записанный на алгоритмическом языке, выполняется по строгим правилам этого конкретного языка (рис. 101). Использование операторных схем алгоритмов заключается в том, что каждый оператор обозначается буквой (например, А – арифметический оператор, Р – логический оператор и т.д.). Операторы записываются слева направо в последовательности их выполнения, причем, каждый оператор имеет индекс, указывающий порядковый номер оператора. Алгоритм записывается в одну строку в виде последовательности операторов (рис. 99). Рис. 99 Пример операторной схемы
Псевдокод – система команд абстрактной машины. Этот способ записи алгоритма с помощью операторов, близких к алгоритмическим языкам (рис. 102).
Рис. 102 Пример псевдокода Языки программирования – это искусственные языки записи алгоритмов для исполнения их на компьютере. Программирование – это процесс составления программы по заданному алгоритму. По структуре выполнения алгоритмы делятся на три вида: v линейные; v ветвления; v циклические. Линейный алгоритм (линейная структура) – это такой алгоритм, в котором все действия выполняются последовательно друг за другом и только один раз. Схема представляет собой последовательность блоков, которые располагаются сверху вниз в порядке их выполнения. Пример записи линейного алгоритма на языке программирования NXT-G (рис. 103).
Рис. 103 Пример записи линейного алгоритма Но на практике часто встречаются задачи, в которых необходимо при различных условиях действовать по-разному. Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. Выбор направления продвижения по схеме алгоритма осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором Условие или Переключатель. Пример записи алгоритма с ветвлением на языке программирования NXT-G (рис. 104).
Рис. 104 Пример записи алгоритма с ветвлением Для решения многих задач нужно многократное повторение отдельных участков вычислений. Для решения таких задач применяются алгоритмы циклической структуры (циклические алгоритмы). Цикл – последовательность команд, которая повторяется до тех пор, пока не будет выполнено заданное условие. Циклическое описание многократно повторяемых процессов значительно снижает сложность написания программ. Пример записи циклического алгоритма на языке программирования NXT-G (рис. 105).
Рис. 105 Пример записи алгоритма с циклом Существуют циклы с известным и с неизвестным числом повторений. В цикле с неизвестным числом повторений выход из тела цикла, как правило, происходит при выполнении записанного условия. Составлять алгоритмы можно множеством различных способов: разложение задачи в последовательность разнородных подзадач, разложение задачи в последовательность однородных подзадач (итерация), сведение задачи к самой себе (рекурсия), метод последовательных приближений, решение обратной задачи (метод полного перебора), эвристические методы разработки алгоритмов, динамическое программирование, метод балансировки, метод Лагранжевых релаксаций. Но наиболее простой и удобный для начинающего программиста – метод пошаговой детализации, который заключается в сведении задачи к подзадачам. При составлении алгоритма этим методом общая задача разбивается на несколько более простых подзадач. Затем каждая из подзадач точно так же разбивается на более мелкие. Весь процесс повторяется до тех пор, пока разбиение не детализируется до отдельных операторов или элементарных задач. Таким способом составлять программы гораздо проще, чем сразу пытаться решить глобальную задачу.
Рис. 106 Иерархия задач Различные методы разработки алгоритмов отличаются тем, на какие подзадачи производится разбиение и как эти подзадачи соотносятся между собой. |
Поделиться с друзьями: