Лекция по "Информатике"

Информатика. Тема 5

Тема  5. Алгоритмизация

1. Интуитивное  определение алгоритма

Слово "алгоритм" является производным  от имени среднеазиатского ученого аль-Хорезми, уроженца Хивы, жившего в IX веке нашей эры. На основании его трудов в средние века были сформулированы основные правила арифметики. Первоначально слово «алгоритм» использовалось для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Неточное (интуитивное) определение  алгоритма следующее:

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

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

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

Свойства алгоритма:

1. Детерминированность (определенность) - каждое действие должно быть понятно исполнителю (для каждого алгоритма предполагается конкретный исполнитель) и содержать операции над известными данными;
2. Дискретность - каждый алгоритм должен быть разбит на конечное число законченных действий;
3. Результативность - каждый алгоритм направлен на решение конкретной задачи, а следовательно на получение определенного результата;
4. Массовость - алгоритм необходимо составить так, чтобы с его помощью можно было решать класс подобных задач.

2. Формы представления  алгоритма

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

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

Виды символьной записи

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

Пример 2.  Алгоритм Евклида нахождения наибольшего общего делителя:

1. Если два числа равны, то наибольший общий делитель – их значение. Идти к пункту 4
2. Большее число заменить на разность большего и меньшего
3. Вернуться к пункту 1
4. Конец алгоритма

Задание. Составьте алгоритмы решения следующих задач: 1) «Из 9 монет одна фальшивая (легче других). Как определить фальшивую монету с помощью весов без гирь за 2 взвешивания?»;  2) «Из 12 монет одна фальшивая (отличается по массе). Как определить фальшивую монету с помощью весов без гирь за 3 взвешивания?»

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

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

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

Язык программирования – искусственный формализованный язык, предназначенный для записи алгоритма, ориентированного на исполнителя «компьютер».

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

3. Организация потока управления действиями алгоритма

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

1. Линейный – несколько функциональных блоков выполняются последовательно, кроме того, каждый блок обязательно выполняется и не более одного раза. (Пример алгоритма привести самостоятельно).
2. Ветвление – организует выполнение одного из двух функциональных блоков в зависимости  от значения проверяемого условия. Ветвление может быть полным и неполным.

Команда «ветвление» имеет две  формы: полную и сокращенную. Полная команда ветвления в записи псевдокодом и синтаксической диаграммой имеет вид:

 

если условие

то

    серия 1

иначе

    серия 2

конец-если

 

 

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

Команда выполняется следующим образом: сначала проверяется, соблюдается ли условие. Если оно соблюдается, то выполняется серия 1, работа команды завершается, и осуществляется переход к команде, стоящей после ключевого слова «конец-если». Если же условие не соблюдается, то выполняется серия 2, и работа команды завершается – осуществляется переход к команде, стоящей после ключевого слова «конец-если». Команды серий реализуются подряд, каждая по своим правилам.

Сокращенная команда «ветвление»  имеет вид:

 

 

если условие

то

    серия

конец-если

 

Выполнение команды: проверяется, соблюдается ли условие. Если оно соблюдается, то выполняются команды серии, и на этом работа команды завершается,  осуществляется переход к команде, стоящей после ключевого слова «конец-если». Если же условие не соблюдается, то серия игнорируется, и работа команды завершается – осуществляется переход к команде, стоящей после ключевого слова «конец-если». В языках программирования высокого уровня русские слова заменяются на английские: «если» – If; «то» – Then; «иначе» – Else.

Пример 3. Даны 2 числа, неравные друг другу. Построить псевдокод алгоритма нахождения наименьшего значения.

Решение.

алгоритм Меньшее из двух

     арг    цел а,b

   рез     цел min

начало

    ввести а, b

    если а<b

        то  min=a

        иначе min=b

    конец-если

  вывести «Меньшее из»,  а «и», b, « - » , min

 конец

3. Циклический – многократное повторение функционального блока, в зависимости от проверки логического условия.

Цикл с предусловием можно описать составной командой пока выполнять, которую можно представить псевдокодом и графически так:

 

пока условие выполнять

    серия

конец-цикл

 

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

Пример 4.  Даны 2 числа. Построить псевдокод алгоритма Евклида нахождения их наибольшего общего делителя (см. пример 2). Использовать цикл с предусловием.

Решение.

алгоритм Евклида

     арг    цел а,b

   рез     цел nod

начало

    ввести а, b

    пока а<>b выполнять

       если a>b

           то  a=a-b

           иначе b=b-a

       конец-если

    конец-цикл

  nod=a

  вывести «Наибольший общий делитель чисел »,  а, «и», b, « - » , nod

 конец

В языках программирования высокого уровня русские слова заменяются на английские: «пока» – While; «выполнять» – Do.

Цикл с постусловием можно описать командой – выполнять пока. В записи псевдокодом и синтаксической диаграммой команда будет иметь вид:

выполнять

    серия

пока условие

В этом цикле серия всегда выполнится один раз, каким бы ни было начальное значение условия, а затем повторяется до тех пор, пока условие остается верным. Цикл заканчивается, когда условие станет ложным.

Пример 5.  Даны 2 числа. Построить псевдокод алгоритма Евклида нахождения их наибольшего общего делителя (см. пример 2). Использовать цикл с постусловием.

Решение.

алгоритм Евклида

арг    цел а,b

рез     цел nod

начало

ввести а, b

если a=b

           то  nod=a

           иначе

                выполнять

                   если a>b

                       то  a=a-b

                        иначе b=b-a

                   конец-если

                 пока а<>b

               nod=a

конец-если                

вывести «Наибольший общий делитель чисел »,  а «и», b, « - » , nod

 конец

Цикл с параметром предназначен для циклов,  которые должны быть проделаны определенное число раз, пока переменная i будет изменяться от j₁ до j₂ с шагом изменения j₃.

Таким образом, серия выполняется, если соблюдается условие i £ j₂, и не выполняется, если i > j₂, или когда в процессе повторений значение i превзойдет j₂. Если фраза шаг j₃ пропущена, по умолчанию предполагается j₃ =1.

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

 

для i от j₁ до j₂ [шаг j₃] выполнять

    серия

конец-цикл

В языках программирования высокого уровня русские слова заменяются на английские: «для» – For; «до» – To; «выполнять» – Do.

Пример 6.  Дано целое число n. Построить псевдокод алгоритма вычисления значения факториала этого числа. Использовать цикл с параметром.

Решение.

алгоритм Факториал

арг    цел n

рез     цел factorial

всп    цел i

начало

вывести «Факториал числа n»       n=

ввести n

factorial =1

для i от 2 до n выполнять

    factorial = factorial · i

конец-цикл

вывести «Факториал числа»,  n, « = » , factorial

 конец