Содержание

Главная >> Информатика 11 класс. Босова

§ 5. Основные сведения об алгоритмах

Понятие алгоритма. Свойства алгоритма

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

Пример 1. Решение задачи «Закрыть входную дверь ключом» предполагает выполнение следующих шагов.

1. Вставить ключ в замочную скважину.

2. Повернуть ключ несколько раз на 180 градусов против(по) часовой стрелки(е).

3. Вынуть ключ из замочной скважины.

Последовательность шагов, приведённая в примере 1, является алгоритмом решения задачи «Закрыть входную дверь ключом». Исполнитель этого алгоритма — человек. Объекты этого алгоритма — ключ, дверь.

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

Из курса информатики основной школы вам известны понятия алгоритма и исполнителя.

Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.

Исполнители бывают двух типов: формальные и неформальные. Далее мы будем говорить преимущественно о формальных или «неразмышляющих» исполнителях. Формальный исполнитель не размышляет над выполняемыми командами, а строго следует пошаговым инструкциям алгоритма. Одну и ту же команду формальный исполнитель всегда выполняет одинаково. За действия формального исполнителя отвечает управляющий им объект.

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

Приведённое определение не является определением в строгом смысле этого слова, это — описание понятия алгоритма, раскрывающее его сущность. Оно не является формальным, потому что в нём используются такие неуточняемые понятия, как «система предписаний», «действия исполнителя», «объект».

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

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

Пример 2. Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число (рис. 2.1).

Метод нахождения простых чисел в интервале [2; n] предложил греческий математик Эратосфен (275-194 гг. до н. э.). По одной из версий, он выписал все числа от 2 до 10 000 на папирусе, натянутом на рамку, и прокалывал составные числа. Папирус стал подобен решету, которое «просеивало» составные числа, а простые оставляло. Поэтому метод Эратосфена называют ещё Эратосфено- вым решетом.

Во все времена люди хотели найти как можно большее простое число.

Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр.

В 2013 г. открыто простое число, запись которого в десятичной системе счисления состоит из 17 425 170 знаков. На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, США.

Для нахождения всех простых чисел не больше заданного числа я, следуя методу Эратосфена, нужно выполнить следующие шаги:

1) выписать подряд все целые числа от 2 до n (2, 3, 4, ..., n);

2) присвоить переменной р значение 2 (2 — первое простое число);

3) зачеркнуть в списке числа, кратные р: 2р, 3р, 4р, ...;

4) найти первое незачёркнутое число в списке, большее чем р, и присвоить переменной р соответствующее значение;

5) повторять шаги 3 и 4, пока возможно.

Числа, остающиеся незачёркнутыми после завершения работы алгоритма, и есть все простые числа от 2 до n.

На практике, алгоритм можно улучшить следующим образом. На шаге 3 числа можно зачёркивать начиная сразу с числа р² (р • р), потому что все составные числа меньше него к этому времени уже будут зачёркнуты. И соответственно, останавливать алгоритм можно, когда р² станет больше, чем n.

Любой алгоритм существует не сам по себе, он всегда предназначен для определённого исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют гак называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.

Значение слова «алгоритм» очень похоже по значению на слова «рецепт», «метод», «способ». Но, в отличие от рецепта или способа, любой алгоритм обязательно обладает следующими свойствами.

1. Дискретность. Выполнение алгоритма разбивается на последовательность законченных действий-шагов. Только выполнив одно действие, можно приступать к выполнению следующего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма, называемое командой.

Окончание >>>