КуМир

В 1983 году человечество широко отметило 1200-летие со дня рождения одного из величайших ученых Средней Азии и средневекового Востока Мухамада ибн Мусы аль-Хорезми.

Аль-Хорезми написал книгу «Арифметика индусскими цифрами». Из неё европейцы научились индийскому счету с помощью десяти цифр и узнали правила арифметических действий над ними. Она произвела в те времена такое огромное впечатление на математиков, что само имя ученого аль-Хорезми, указывающее на его происхождение из среднеазиатского государства Хорезм, в их устах превратилось в Algorithmus, первоначально обозначавшее десятичную систему исчисления и правила арифметических действий в этой системе.

Отсюда возник и современный научный термин «алгоритм». Сейчас под алгоритмом понимают точное предписание, определяющее путь к достижению поставленной цели. Алгоритм может представлять собою некоторую последовательность вычислений, а может – последовательность действий нематематического характера. Но, в любом случае, должны быть четко определены начальные условия и то, что предстоит получить. Сам алгоритм можно облечь в форму приказов, которые нужно выполнять точно и беспрекословно.

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

В качестве примера приведем рецепт приготовления молочно-малинового коктейля с мороженым:

1. Взять мороженое – 50 г, малиновый сироп – 20 мл, молоко – 150 мл, свежую или консервированную малину – 50 г.
2. Молоко и сироп взбить.
3. Вылить содержимое в бокал.
4. Положить в него шарик мороженого и малину.

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

1. Описываем окружность с центром в точке A радиусом AB.
2. Описываем окружность с центром в точке B радиусом BA.
3. Соединяем точки пересечения построенных окружностей отрезком прямой. Точка пересечения этого отрезка с отрезком АВ является серединой последнего.

Известному математику Л.Эйлеру принадлежит следующая задача: обойти конем все клетки шахматной доски, побывав в каждой клетке только один раз. В 1823 году некто Варнсдорф издал брошюру «Простейшее и наиболее общее решение задачи о ходе коня», в которой даётся алгоритм решения задачи Эйлера.

Предположим, что клетки доски пронумерованы, например, как показано на рисунке 1. Клетки, на которых конь уже побывал, будем перечеркивать.

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

В III веке до нашей эры греческий математик Эратосфен дал алгоритм для нахождения всех простых чисел, меньших заданного. Этот алгоритм, известный под названием «решето Эратосфена» можно сформулировать так:

1. Выпиши все натуральные числа от 1 до n.
2. Зачеркни число 1.
3. Подчеркни наименьшее из не зачёркнутых чисел.
4. Вычеркни все кратные подчеркнутому на предыдущем шаге числу.
5. Проверь, имеются ли ещё неподчёркнутые числа. Если таких чисел нет, то подчеркнутые числа – это все простые числа между 1 и n, задача решена. Если же имеются ещё неподчёркнутые числа, то перейди к указанию 3.

Исполнитель алгоритма — это человек или автомат (в частности, компьютер), умеющий выполнять предписания алгоритма.

Алгоритм может быть записан в различных формах: на естественном языке, как в рассмотренных примерах; в виде графических схем; на специальном алгоритмическом языке, пример которого является известная «нотация» Бэкуса-Наура. В школе на уроках информатики для записи алгоритмов мы используем так называемый «школьный алгоритмический язык». Необходимо, чтобы исполнитель получил его в той форме, которая ему понятна. Если исполнитель — компьютер, то алгоритм для него записывается в виде программы на языке программирование

В алгоритмическом языке можно выделить три основные конструкции:

1. Образование последовательности из нескольких операторов;
2. Выбора одного из двух операторов;
3. Повторения оператора, пока выполняется некоторое условие.

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

В этой книге в качестве практического алгоритмического языка программирования мы будем использовать школьный алгоритмический язык КуМир.