АЛГОРИТМ И ЕГО СВОЙСТВА

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

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

1) определенности (детерминированности);

2) массовости;

3) конечности.

Прежде всего, определение подчеркивает то, что алгоритм носит дискретный характер (последовательность действий). Свойство детерминированности состоит в понятности каждого действия алгоритма его исполнителю. Если это не так, то при исполнении алгоритма возникает АВОСТ (аварийная остановка), потому что исполнитель не может или не умеет исполнять непонятное действие.

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

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

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

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

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

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

Пример. Алгоритм покраски забора:

1. Взять краску и кисть.

2. Подойти к первой доске забора.

3. Пока забор не закончился, повторять:

3.1. Покрасить доску.

3.2. Подойти к следующей доске.

4. Убрать на место краску и кисть.

5. Вымыть руки.

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

Упражнение.

1. Приведите пример алгоритма. Покажите его свойства.

2. Приведите пример не алгоритма. Укажите, какие свойства в нем нарушены.

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

* на естественном языке;

* в виде блок-схемы;

* на алгоритмическом языке.

Пример. Описать алгоритм решения задачи: полторы кошки за полтора часа съедают полторы мышки. Сколько мышек съедят M кошек за N часов?

1. Алгоритм на естественном языке будет выглядеть следующим образом:

1. Ввести количество кошек М и часов N.

2. Одна кошка за полтора часа съест одну мышку, а за один час - 1/1,5 мышек.

3. Общее количество съеденных мышек определится по формуле: 1/1,5 * M * N.

2. Блок-схема алгоритма:

3. Программа на Паскале

program task1;

var M, N: integer;

K: real;

begin

write(‘Введите количество мышек и количество часов’);

readln (M, N);

K:= 1/1.5 * M * N;

writeln (‘будет съедено’, K:10:3, ‘мышек’);

end.

В зависимости от последовательности выполнения шагов алгоритма выделяют три типа вычислительных процессов:

* линейные;

* ветвящиеся;

* циклические.

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

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

Пример 2. Если кошка прячет нос, то будет холодно, иначе - тепло.

Пример 3. Если температура ниже -25°, то физкультура будет в зале, иначе - на улице.

program task2;

var t: integer;

begin

write (‘ Какая сегодня температура?’);

readln (t);

if t <= - 25 then writeln (‘физкультура будет в зале’)

else writeln(‘физкультура будет на улице’);

end.

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

Существуют циклы, для которых заранее известно количество раз выполнения тела. Такие циклические алгоритмы называют арифметическими или циклами с параметром (счетчиком).

Пример 4. Алгоритм покраски забора.

От первой доски до десятой повторять:

1. покрасить доску;

2. сделать шаг вправо, перейти к следующей доске.

Это арифметический цикл с положительным шагом (номера досок увеличиваются).

Пример 5. Алгоритм покраски забора.

От десятой доски до первой повторять:

1. покрасить доску;

2. сделать шаг влево, перейти к следующей доске.

Это арифметический цикл с отрицательным шагом (номера досок уменьшаются).

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

Пока забор не закончился, повторять шаги 1 и 2.

Или

Повторять шаги 1 и 2 до тех пор, пока забор не закончился.

Такие циклы называют итерационные, в первом случае - с предусловием, во втором - с постусловием. Для таких циклов заранее не известно количество раз выполнения тела, но существует только одна причина окончания.

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

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

Такой цикл называют цикл поисковым. Он может быть завершен по двум причинам: 1) найдена покрашенная доска; 2) забор кончился, покрашенная доска не была найдена.

Упражнения.

1. Какие формы представления алгоритмов существуют? Приведите пример алгоритма во всех его формах.

2. В чем преимущества алгоритмического языка перед естественным для записи алгоритмов?

3. Приведите примеры

* цикла, для которого заранее известно количество повторений тела цикла;

* цикла, для которого неизвестно количество повторений тела цикла;

* цикл, который может завершиться по трем причинам.

4. Приведите пример алгоритма, содержащего цикл и ветвление во всех формах.

5. В чем сходство и различие алгоритма и программы? Приведите примеры не менее трех сходств и различий.

6. Представьте в виде алгоритмов решения задач:

* Имеется 12 литров жидкости. Нужно разделить ее поровну с помощью двух пустых сосудов емкостью 8 и 5 литров.

* Имеются две линейки. На одной отмечен отрезок длиной 7 см, на другой - 5 см. Как, пользуясь для измерений только данными линейками, нанести на них сантиметровые деления?

* Есть двое песочных часов: на 3 минуты и на 8 минут. Как с их помощью отмерить ровно 7 минут?

* Как, имея два сосуда, емкостью 5 и 9 литров, набрать из водоема ровно 3 л воды?

* Имеется 9 кг крупы и гири в 50 г и 200 г. Как отмерить в три приема на чашечных весах 2 кг крупы? Как называется такой алгоритм?

* Имеются три сосуда, емкостью 8, 5 и 3 литра. Первый из них наполнен водой. Как разлить воду в два из этих сосудов так, чтобы в каждом было по 4 литра?

* К владельцу бакалейного магазина пришли 10 покупателей, каждый из которых хотел купить двухфунтовый пакет сахара. Утром в магазин привезли двадцатифунтовый мешок сахара. Но бакалейщик еще не успел расфасовать его, потому что у него были только пяти- и девятифунтовые гирьки. Один из покупателей, потеряв терпение, показал бакалейщику самый быстрый способ расфасовки сахара с помощью этих 2 гирь. Как он это сделал?

* Идея устроить в замке костюмированный бал казалась очень романтичной - до тех пор, пока не был поднят мост и 11 дам и 2 кавалера не остались по ту сторону рва, заполненного водой и окружающего замок. Все остальные уже ушли, и некому было им помочь. Потом им удалось найти маленькую лодку, но она могла перевезти за 1 раз только 1 даму (а дамы были в пышных кринолинах) или 2 кавалеров. Как же им всем удалось пересечь ров и не промокнуть?

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

* Для этой головоломки нужно 80 мелких предметов, например орешки. Вы с товарищем по очереди берете орешки. Выигрывает тот, кто берет последний орешек. За один раз вы можете взять любое количество орехов (от 1 до 9 включительно), причем это количество может меняться по вашему усмотрению. У этой головоломки есть такое решение, которое поможет вам всегда выиграть. Так какое же это решение?

Поиск по сайту: