Теория:
Алгоритм – это последовательность команд, выполнение которых приводит к решению поставленной задачи. Простым языком: это определенные действия, с указанной последовательностью, которые приводят нас к результату.
Свойства алгоритмов
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
- Дискретность – алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно. Кому интересно, то пробейте в гугле: Дискретная математика.
- Детерминированность (или определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит формальный характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
- Понятность – алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд. Короче говоря, алгоритм должен быть понятным!
- Результативность (или конечность). Это свойство состоит в том, что при корректно заданных исходных данных алгоритм должен завершать работу (приводить к решению задачи) и выдавать результат за конечное число шагов.
- Массовость – универсальность. Это означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применения алгоритма. Но это правило не всегда действует, в основном разрабатывается один или несколько алгоритмов для решения одной задачи . Например можно решить задачу с помощью if-then-else или с использованием switch-case.
for(i=0; i<100; i++) a=i;//Мы хотим, что бы цикл for выводил 100 интераций, не смотря на то, что массив из десяти элементов,
//он может привести к краху вашей ОС'и и возможно перезапишит важную информацию в памяти. [/CPP] И компилятор не выдаст ошибку, потому что С++ предназначен для профи программистов, и его задача - предоставить им возможность создать максимально эффективный код, любая проверка средствами С++ существенно замедлит выполнение программы. Если вы кодите на ассемблере и пишете неправильный код, то беды не миновать, ну кроме того, что вас остановит компилятор.
Каждое действие можно представить , как алгоритм. Следует, что алгоритмы нас окружат во всех сферах деятельности: учеба, работа, производство металов, ect.
Типы алгоритмов:
Решение любых задач состоит, как правило, из двух этапов: первый – составление алгоритма решения задачи, второй – исполнение алгоритма.
В алгоритме команды записаны одна за другой в определенном порядке. Исполняются они не обязательно в том же порядке. В зависимости от того, каков порядок исполнения команд, можно выделить три типа алгоритмов: линейные алгоритмы, разветвляющиеся алгоритмы и алгоритмы с повторениями.
Линейные алгоритмы
Алгоритм решения задачи называется линейным, если исполнитель все команды алгоритма исполняет одну за другой в порядке их записи. Например рассмотрим алгоритм с чайником.
Разветвляющиеся алгоритмы
В ходе решения задач часто возникают различные ситуации, которые исполнителю приходится учитывать. От того, какая складывается ситуация, может зависеть дальнейший ход решения задачи.
Например, любые вычисления прекращаются, если выясняется, что нужно делить на нуль. При нахождении корней квадратного уравнения ход решения зависит от знака дискриминанта. Зонтик раскрывают, если идет дождь или светит жаркое солнце. Возможные ситуации учитываются при составлении алгоритма.
Ситуации оцениваются при помощи условий. Условие понимается как вопрос, на который исполнитель дает один из двух ответов – условие выполняется (условие истинно, true - T) или условие не выполняется (условие ложно, false - F).
Пример. На стоянке при въезде в гараж находится легковая или грузовая машина с работающим двигателем. Если машина легковая, то исполнитель Загонщик должен загнать её в бокс А и выключить двигатель. Если машина грузовая, то ёё нужно загнать в бокс С и выключить двигатель. Составим алгоритм действий исполнителя Загонщик.
Сначала исполнитель должен определить, какая машина находится на стоянке. Это можно сделать проверкой условия – «машина легковая». Если на стоянке находится легковая машина, то ответ будет «*да» – условие выполняется (условие истинно). Если на стоянке находится грузовая машине, то ответ будет «*нет» – условие не выполняется (условие ложно).
Используя условие «машина» легковая», запишем алгоритм.
В зависимости от ситуации исполняется одна из двух разных последовательностей команд. Рассмотрим возможные ситуации.
Ситуация 1: на стоянке легковая машина. Исполняются команды 1, 2, 4.
Ситуация 2: на стоянке грузовая машина. Исполняются команды 1, 3, 4.
Действительно, после проверки условия в команде 1 в разных ситуациях исполняются разные наборы команд. Их называют ветвями алгоритма. Исполнение алгоритма всегда идет только по одной ветви. Здесь можно провести аналог с разветвлением дороги: после разветвления одна машина может ехать только по одной дороге.
Алгоритм называется разветвляющимся, если после проверки условия в разных ситуациях исполняется один из двух разных наборов команд.
Запись алгоритма мало меняется, если для проверки ситуации выбирается противоположное условие. В алгоритме Заезд, например, можно использовать условие «машина грузовая». В этом случае изменится только команда 1, и алгоритм будет иметь вид:
Алгоритмы с повторениями
При анализе алгоритмов, рассмотренных в примерах 1 и 2, можно заметить одно общее свойство: при их исполнении каждая команда исполняется один раз или не исполняется ни разу. Но часто встречаются задачи, при решении которых одно и то же действие (или набор действий) нужно исполнить несколько раз подряд. Например, наполнить бочку водой из ведер (переливать воду в бочку из ведер, пока бочка не заполнится до краев); покрасить забор (красить дощечки забора, пока есть незакрашенные); до упора завернуть гайку (закручивать гайку, пока не завернешь её до упора). Для описания алгоритмов решения таких задач используется способ организации команд, который называют повторением. Повторение – это набор команд, который исполняется до тех пор, пока выполняется некоторое условие. При исполнении алгоритма этот набор команд может исполниться несколько раз или не исполниться ни разу. Алгоритмы, которые содержат команду повторения, называют алгоритмами с повторением.
Пример. Имеется пустое ведро. Исполнитель имеет бочку с водой и кружку. Составим алгоритм наполнения ведра водой из бочки.
Команда 1 называется командой повторения или командой цикла. Команда 2 составляет тело цикла. После того, как ведро наполнится водой, команда 2 (тело цикла) больше не исполняется. Исполнитель переходит к команде, следующей за телом цикла.
В записи алгоритма «Наполнение» команда «Налить в ведро кружку воды» встречается один раз. При исполнении алгоритма она будет исполняться до тех пор, пока ведро не наполнится водой.
В других алгоритмах тело цикла может состоять из нескольких команд. В командах повторения могут содержаться команды ветвления; в ветвях алгоритма – команды повторения.
Способы представления алгоритмов:
1. Словесная форма представления алгоритмов.Можно назвать техническим языком.
2. Блок-схемы.
3. Языки программирования.Самый основной.
Блок-схемы. Общий вид и назначение элементов блок-схем
Словесная форма достаточно удобна для записи небольших алгоритмов. Если алгоритм содержит десятки команд, то в такой форме довольно трудно проследить всевозможные разветвления. Поэтому на практике иногда используют другую форму записи алгоритмов – графическую. Графическая форма записи алгоритма называется блок-схемой.
Блок-схемы алгоритмов состоят из блоков, которые дополнены элементами словесной формы записи. Приведем графические изображения основных блоков:
http://i60.fastpic.ru/big/2013/0921/dc/ ... 9ab6dc.jpg
Внутри блока дается описание команд или условий. В блок действий записывают команду, не содержащую условий. В блок проверки условия записывают условие.
Все блоки, кроме блока Начало и блока Конец, можно нумеровать. Блоки на схемах соединяют стрелками, которые показывают последовательность исполнения алгоритма.
Материал из икипедии
Сам не против от создания такого раздела.
