Лекция №1 Понятие алгоритма



Скачать 493,53 Kb.
страница1/5
Дата21.10.2016
Размер493,53 Kb.
  1   2   3   4   5

Лекция №1



Понятие алгоритма. Понятие алгоритма является одним из ос­новных понятий современной математики и информатики. Термин алгоритм происходит от имени средневекового узбекского математика Аль-Хорезми, который еще в IX в. (825) дал правила вы­полнения четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий был назван алгоризмом.

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

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

Определение 1:

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

Первоначально для записи алгоритмов пользовались средствами обычного языка (словесное представление алгоритмов).

Уточним понятие словесного представления алгоритма на примере нахождения произведения n натуральных чисел — факториал числа п (с = n!), т.е. вычисления по формуле с = 1*2*3*4*...*n.



Этот процесс может быть записан в виде следующей системы по­следовательных указаний (пунктов):

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

  2. Полагаем i равным единице и переходим к следующему пункту.

  3. Полагаем с = i*с и переходим к следующему пункту.

  4. Проверяем, равно ли i числу n. Если i = п, то вычисления пре­кращаем. Если i < п, то увеличиваем i на единицу и переходим к пункту 3.

Рассмотрим еще один пример алгоритма — нахождение наимень­шего числа М в последовательности из n чисел а1, а2, ..., аn (n > 0). Прежде чем записать словесный алгоритм данного примера, детально рассмотрим сам процесс поиска наименьшего числа. Будем считать, что процесс поиска осуществляется следующим образом. Первоначально в качестве числа М принимается аи т. е. полагаем М = а,, после чего М сравниваем с последующими числами последовательности, начиная с аъ Если М"Ща2, то М сравнивается с д3, если M~S{ д3, то М сравнивается с а4, и так до тех пор, пока найдется число а, < М. Тогда полагаем М = а, и продолжаем сравнение с М последующих чисел из последовательности, начиная с а,+1> и так до тех пор, пока не будут просмотрены все п чисел. В результате просмотра всех чисел М будет иметь значение, равное наименьшему числу из последовательности (/— текущий номер числа). Этот процесс может быть записан в виде следующей системы последо­вательных указаний:

    1. Полагаем i = 1 и переходим к следующему пункту.

    2. Полагаем М = аi, и переходим к следующему пункту.

    3. Сравниваем i с п; если i < п, переходим к 4 пункту, если i = п, процесс поиска останавливаем.

    4. Увеличиваем i на 1 и переходим к следующему пункту.

    5. Сравниваем а, с М. Если M < аi, то переходим к пункту 3, иначе (М> аi ) переходим к пункту 2.

Алгоритмы, в соответствии с которыми решение поставленных задач сводится к арифметическим действиям, называются численны­ми алгоритмами.

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

Определение 2:

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

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

2) Дискретность алгоритма. Поочередное выполнение команд алгоритма за конечное число ша­гов приводит к решению задачи. Разделение вы­полнения решения задачи на отдельные операции (выполняемые испол­нителем по определенным командам) — важное свойство алгоритмов, называемое дискретностью.

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

4) Исполнитель действует формально, т.е. от­влекается от содержания поставленной задачи и только строго выполня­ет некоторые правила, инструкции. Выполняя алгоритм, исполнитель может не вникать в смысл того, что он делает, и вместе с тем получать нужный результат.

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

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

5) Определенностью (или точностью) алгоритма. Каждая команда алгоритма должна опреде­лять однозначно действие исполнителя. Всякий алгоритм составляется в расчете на конкретного исполни­теля с учетом его возможностей. Совокупность ко­манд, которые могут быть выполнены исполнителем, называется сис­темой команд исполнителя.

6) понятность алгоритма. Алгоритм, составленный для конкретного исполнителя, должен включать только те команды, которые входят в его систему команд. Алгоритм не должен быть рассчитан на принятие каких-либо самостоятельных решений ис­полнителем, не предусмотренных составленным алгоритмом.

7) ре­зультативность (или конечность) алгоритма. Испол­нение алгоритма должно закончиться за конечное число шагов.

Разработка алгоритмов — процесс творческий, требующий умст­венных усилий и затрат времени. Поэтому предпочтительно разрабаты­вать алгоритмы, обеспечивающие решения всего класса задач данного типа. Например, если составляется алгоритм решения кубического уравнения ахъ +bx2 +cx + d = 0, то он должен быть вариативен, т.е. обеспечивать возможность решения для любых допустимых исходных значений коэффициентов а, b, с, d. Про такой алгоритм говорят, что он удовлетворяет требованию массовости. Свойство массовости не явля­ется необходимым свойством алгоритма. Оно скорее определяет качест­во алгоритма; в то же время свойства дискретности, точности, понятно­сти и конечности являются необходимыми (иначе это не алгоритм).

Формы записи алгоритмов. Алгоритмы можно записывать по- разному. Форма записи, состав и количество операций алгоритма зави­сят от того, кто будет исполнителем этого алгоритма. Если задача реша­ется с помощью ЭВМ, алгоритм решения задачи должен быть записан в понятной для машины форме, т. е. в виде программы. Всякий алгоритм может быть:


  • записан на естественном языке (примеры записи алгоритма на ес­тественном языке приведены при определении понятия алгоритма);

  • изображен в виде блок-схемы;

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

Запись алгоритмов в виде блок-схем. Схема алгоритма — графи­ческое представление алгоритма. Каждый пункт алгоритма отображает­ся на схеме некоторой геометрической фигурой — блоком — и допол­няется элементами словесной записи. Правила выполнения схем алго­ритмов регламентирует ГОСТ 19.002—80 (единая система программной документации, см. табл. 1.1)

Блоки на схемах соединяются линиями потоков информации. Ос­новное направление потока информации идет сверху вниз и слева на­право (стрелки могут не указываться), снизу вверх и справа налево — стрелка обязательна. Количество входящих линий для блока не ограни­чено. Выходящая линия должна быть одна (исключение составляет ло­гический блок).








Рис. 1.1. Блок-схема алгоритма нахождения минимума в последовательности чисел


Приведем запись алгоритма нахождения минимального числа М в последовательности из п чисел aj, а2, ..., а„ (п > 0) в виде блок-схемы (рис. 1.1).

Базовые структуры алгоритмов — это определенный набор бло­ков и стандартных способов их соединения для выполнения типичных последовательностей действий. К основным структурам относятся сле­дующие: линейные (рис. 1.2, а), разветвляющиеся (рис. 1.2, б), цикличе­ские (рис. 1.2, в, г).





Рнс. 1.2. Базовые структуры алгоритмов и программ

Линейными называются алгоритмы, в которых действия осуществ­ляются последовательно друг за другом. Стандартная блок-схема ли­нейного алгоритма приводится на рис. 1.3, а (вычисление произведения двух чисел — А и В).

Разветвляющимся называется алгоритм, в котором действие вы­полняется по одной из возможных ветвей решения задачи, в зависимо­сти от выполнения условий. В отличие от линейных алгоритмов, в кото­рых команды выполняются последовательно одна за другой, в разветв­ляющиеся алгоритмы входит условие, в зависимости от выполнения или невыполнения которого выполняется та или иная последовательность команд (действий).

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

Примером может являться разветвляющийся алгоритм, изображен­ный на рис. 1.3, б. Аргументами этого алгоритма являются числа А и В, а результатом — число X. Если условие А >= В истинно, то выполняет­ся операция умножения чисел (X = А * В), в противном случае выполня­ется операция сложения (X = А + В). В результате печатается то значе­ние X, которое получается в результате выполнения одного из действий.

Циклическим называется алгоритм, в котором некоторая часть опе­раций (тело цикла — последовательность команд) выполняется много­кратно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов.

Перед операцией цикла осуществляются операции присвоения начальных значений тем объектам, которые используются в теле цикла. В цикл входят в качестве базовых следующие структуры: блок проверки условия и блок, называемый телом цикла. Если тело цикла расположено после проверки условий (рис. 1.2, в — цикл с преду­словием), то может случиться, что при определенных условиях тело цикла не выполнится ни разу. Такой вариант организации цикла, управляемый предусловием, называется циклом типа пока (здесь условие — на продолжение цикла).

Возможен другой случай, когда тело цикла выполняется по крайней мере один раз и будет повторяться до тех пор, пока не ста­нет истинным условие. Такая организация цикла, когда его тело рас­положено перед проверкой условия, носит название цикла с пост­условием, или цикла типа до (рис. 1.2, г). Истинность условия в этом случае — условие окончания цикла. Отметим, что возможна ситуация с постусловием и при организации цикла-яока. Итак, цикл- до завершается, когда условие становится истинным, а цикл-мжа — когда условие становится ложным.

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

Рассмотрим циклический алгоритм типа пока (рис. 1.2, в) на при­мере алгоритма вычисления факториала. N— число, факториал которо­го вычисляется. Начальное значение^ принимается равным 1. К будет меняться от 1 до N и вначале также равно 1. Цикл будет выполняться, пока справедливо условие N <Ш К. Тело цикла состоит из двух операций N\=N] *КиК = К+ 1 (рис. 1.3, в).

Циклические алгоритмы, в которых тело цикла выполняется задан­ное число раз, реализуются с помощью цикла со счетчиком. Цикл со счетчиком реализуется с помощью рекурсивного увеличения значения счетчика в теле цикла (К = К + 1 в алгоритме вычисления факториала).






Процесс решения сложной задачи довольно часто сводится к решению нескольких более простых подзадач. Соответственно процесс разработки сложного алгоритма может разбиваться на этапы составления отдельных алгоритмов, которые называются вспомогательными. Каждый такой вспо­могательный алгоритм описывает решение какой-либо подзадачи.

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

Примеры и решения

1. Рассмотрим следующую известную задачу: имеются два кув­шина емкостью 3 и 8 л. Необходимо составить алгоритм, с помощью которого, пользуясь только этими двумя кувшинами, можно набрать 7 л воды.

Можно предположить, что кувшин емкостью 3 л необходимо ис­пользовать для того, чтобы отлить в него 1 л из полного кувшина емко-

16

стью 8 л. Таким образом, решение задачи сводится к поиску возможно­сти поместить, например, 2 л воды в трехлитровый кувшин, затем на­полнить восьмилитровый и перелить из него воду в трехлитровый кувшин, в котором до полного заполнения не хватает ровно 1 л. Задача реализуется следующим линейным алгоритмом (А — количество воды в трехлитровом кувшине, В — количество воды в восьмилитровом кув­шине):







2. Рассмотрим задачу вычисления наибольшего общего делителя (НОД) двух натуральных чисел А и В с применением алгоритма Евкли­да. Основная идея алгоритма в том, что НОД А и В есть также и НОД (А - В), т.е. последовательное вычитание из большего числа меньшего до тех пор, пока числа не сравняются, должно привести к искомому значению НОД.

Приведем сначала запись алгоритма Евклида на естественном языке:


  1. Рассмотреть А как первое число, В как второе. Перейти к пункту 2.

  2. Сравнить первое и второе число. Если они равны, перейти к пункту 5. Если нет, перейти к пункту 3.

  3. Если первое число меньше второго, то поменять их местами. Перейти к пункту 4.

  4. Вычесть из первого числа второе и рассмотреть полученную разность как первое число. Перейти к пункту 2.

  5. Рассмотреть первое число как результат. Закончить выполнение алгоритма.

Представленный алгоритм имеет разветвляющуюся структуру и в виде блок-схемы изображается следующим образом:





3. Пусть необходимо вывести на печать все числа ряда Фибоначчи (1, 1, 2, 3, 5, 8,...) до заданного натурального N.

Очередной член ряда F; определяется как сумма двух предыдущих (Fj = F;.i + Fj.2). Первые два члена ряда равны 1.

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

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







Вопросы и задания

    1. Охарактеризуйте базовые структуры алгоритмов.

    2. Дано число X и последовательность действий:

  • умножить полученное число на 2;

  • сообщить результат;

  • разделить Хна 3;

  • вычесть из полученного числа 5;

  • прибавить к полученному числу 7.

Сколько и каких различных алгоритмов можно составить из этой последо­вательности действий? Какие функции от А" при этом вычисляются?

    1. Приведите примеры задач, для реализации которых применимы: а) линей­ные алгоритмы; б) разветвляющиеся алгоритмы; в) циклические алгоритмы.

    2. Охарактеризуйте разницу между циклом типа до и циклом типа пока.

    3. Приведите примеры задач, для реализации которых целесообразно приме­нять циклические структуры: а) с постусловием; б) с предусловием.

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

    5. Нарисуйте блок-схему алгоритма получения произведения п произвольных чисел (п = 15).

    6. Нарисуйте блок-схему алгоритма вычисления суммы квадратов первых п чисел натурального ряда.

    7. Модифицируйте алгоритм вычисления суммы квадратов первых п чисел натурального ряда для вычисления суммы квадратов: а) только четных чи­сел (до п)\ б) только нечетных чисел (до п).

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

Программа> Здравствуйте! Как Ваше имя? Пользователь^ Гаврик

Программа> Доброе утро, Гаврик! Как настроение?

Пользователь> так себе

Программа> У меня тоже так себе, Гаврик!




Поделитесь с Вашими друзьями:
  1   2   3   4   5


База данных защищена авторским правом ©grazit.ru 2017
обратиться к администрации

    Главная страница