Урок 7
§5. Основные сведения об алгоритмах
|
|
5.1. Понятие алгоритма. |
 |
|
|
|
 |
5.1. Свойства алгоритма. |
|
5.1. Понятие алгоритма.
Предположим, перед вами поставлена задача, для решения которой необходимо написать программу. Из курса информатики основной школы вам известно, что решение задачи имеет определённые этапы.
1. Постановка задачи. Необходимо определить исходные данные (что подаётся «на вход») и требуемые результаты (что следует получить «на выходе»), указать связи между исходными данными и результатами.
2. Формализация. На этом этапе определяется класс, к которому принадлежит задача, связи между исходными данными и результатами записываются с помощью математических соотношений.
3. Выбор метода решения и разработка алгоритма. Это один из важнейших этапов решения задачи; от правильности выбора метода зависит эффективность алгоритма, определяющая быстродействие программы и размер необходимой для её выполнения памяти.
4. Составление программы (запись алгоритма на языке программирования) и её ввод в память компьютера. Сейчас этот этап принято называть кодированием.
5. Отладка программы. Созданная программа может содержать ошибки, допущенные как в процессе кодирования, так и на любом из предыдущих этапов. Ошибки могут быть выявлены в процессе тестирования — выполнения программы с заранее подготовленными наборами исходных данных, для которых известен результат.
6. Вычисление и обработка результатов.
Задачи, которые мы будем рассматривать в данной главе, достаточно чётко поставлены и формализованы. Основное внимание при их решении мы будем уделять этапам 3-6.
Понятие алгоритма
Каждый из нас ежедневно решает задачи различной сложности: как быстрее добраться в школу или на работу в условиях недостатка времени, в каком порядке выполнить дела, намеченные на текущий день, и т. д. Некоторые задачи настолько сложны, что требуют длительных размышлений для нахождения решения (которое иногда так и не удаётся найти). Другие задачи мы решаем автоматически, т. к. выполняем их ежедневно на протяжении многих лет (выключить звенящий будильник; почистить утром зубы; вскипятить воду в чайнике; позвонить другу по телефону; открыть или закрыть входную дверь ключом). В большинстве случаев в решении каждой задачи можно выделить отдельные шаги.
Пример 1. Решение задачи «Закрыть входную дверь ключом» предполагает выполнение следующих шагов.
1. Вставить ключ в замочную скважину.
2. Повернуть ключ несколько раз на 180 градусов против(по) часовой стрелки(е).
3. Вынуть ключ из замочной скважины.
Последовательность шагов, приведённая в примере 1, является алгоритмом решения задачи «Закрыть входную дверь ключом». Исполнитель этого алгоритма — человек. Объекты этого алгоритма — ключ, дверь.
Для решения любой задачи надо знать, что дано и что следует получить, т. е. у задачи есть исходные данные (объекты) и искомый результат. Для получения результатов необходимо знать способ решения задачи — располагать алгоритмом.
Из курса информатики основной школы вам известны понятия алгоритма и исполнителя.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
Исполнители бывают двух типов: формальные и неформальные. Далее мы будем говорить преимущественно о формальных или «неразмышляющих» исполнителях. Формальный исполнитель не размышляет над выполняемыми командами, а строго следует пошаговым инструкциям алгоритма. Одну и ту же команду формальный исполнитель всегда выполняет одинаково. За действия формального исполнителя отвечает управляющий им объект.
Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения (после конечного числа шагов) искомого результата.
Приведённое определение не является определением в строгом смысле этого слова, это — описание понятия алгоритма, раскрывающее его сущность. Оно не является формальным, потому что в нём используются такие неуточняемые понятия, как «система предписаний», «действия исполнителя», «объект».
Понятие алгоритма, являющееся фундаментальным понятием математики и информатики, возникло задолго до появления вычислительных машин.
Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.
Пример 2.
Простые числа — это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число (рис. 2.1).
Рис. 2.1. Примеры простых чисел (иллюстрация Н. П. Антокольской)
Метод нахождения простых чисел в интервале [2; n] предложил греческий математик Эратосфен (275-194 гг. до н. э.). По одной из версий, он выписал все числа от 2 до 10 ООО на папирусе, натянутом на рамку, и прокалывал составные числа. Папирус стал подобен решету, которое «просеивало» составные числа, а простые оставляло. Поэтому метод Эратосфена называют ещё Эратосфеновым решетом.
Во все времена люди хотели найти как можно большее простое число.
Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр.
В 2013 г. открыто простое число, запись которого в десятичной системе счисления состоит из 17 425 170 знаков. На проверку простоты нового числа ушло 39 дней работы персонального компьютера в Университете Центрального Миссури, США.
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
1) выписать подряд все целые числа от 2 до n (2, 3, 4, ..., n);
2) присвоить переменной р значение 2 (2 — первое простое число);
3) зачеркнуть в списке числа, кратные р: 2р, 3р, 4р, ...;
4) найти первое незачёркнутое число в списке, большее чем р, и присвоить переменной р соответствующее значение;
5) повторять шаги 3 и 4, пока возможно.
Числа, остающиеся незачёркнутыми после завершения работы алгоритма, и есть все простые числа от 2 до n.
На практике, алгоритм можно улучшить следующим образом. На шаге 3 числа можно зачёркивать начиная сразу с числа р2 (р • р), потому что все составные числа меньше него к этому времени уже будут зачёркнуты. И соответственно, останавливать алгоритм можно, когда р2 станет больше, чем n.
Любой алгоритм существует не сам по себе, он всегда предназначен для определённого исполнителя. Алгоритм описывается в командах исполнителя, который этот алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют так называемую среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.
Cкачать материалы урока
