Типы алгоритмов

Ознакомившись с различными формами записи алгоритмов и их свойствами, вы сможете распознать отдельные команды. Для примера рассмотрим расписание уроков.
Расписание на сегодня, по свойствам и понятием алгоритма, мы можем трактовать как алгоритм, в котором команды следуют друг за другом в определенной последовательности, причем команды в этой последовательности нельзя произвольно переставлять - это приведет к «ломки» расписания по школе (если в классе нет разделения учащихся на подгруппы по отдельным предметам).

Поэтому под словом «расписание уроков» мы понимаем расписание конкретного ученика. Наблюдаем структуру последовательного расположения команд.
Расписание на неделю - другая структура, которая зависит от условия «какой сегодня день», ведь расписание на понедельник отличается (для большинства учеников) от расписания на пятницу или какой другой день. Итак, наблюдаем структуру, в которой выбор перечня уроков зависит от условия «день».

Расписание на семестр характерен тем, что в нем повторяется расписание на неделю в первом семестре 16 раз, во втором - 18. Если бы не посмотрели на расписание, вы можете уверенно сказать, в каком кабинете вы учились на третьем уроке в третью среду сентября, и в этом же кабинете вы проведете третий урок в первую среду декабря.

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

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

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

Линейным элементом алгоритма называется операция, которая определяет один элементарный шаг обработки или отображения информации.

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

К линейным элементам относятся: команда изменения значения величины, ввод значения аргументов и вывода значений результатов, информации и т.п.

Если алгоритм состоит только из линейных элементов, то его называют линейным (как на рисунке).

Рассмотрим пример. Задача. Вычислите площадь треугольника. Размышления и решения

1) Площадь треугольника мы можем вычислить по известным из геометрии формулам. их несколько, а у нас в хозяйстве только одна линейка, поэтому оптимальным способом является вычисление по формуле Герона.

2) Измерили стороны, оказалось, что они равны 13 см, 14 см и 15 см. Вычисляем периметр треугольника: 13 + 14 + 15 = 42 см, пол периметра - 21 см. Тогда площадь этого треугольника по формуле Герона равна: 5 => / 21 876 => / 7056 = 84 (см2).

3) Обобщим наши действия и запишем алгоритм решения этой прикладной задачи в общем виде.
Поскольку процесс решения конкретной задачи мы записали в словесной форме, обобщенный алгоритм запишем учебной алгоритмическом языке. Алгоритм назовем «Герон». Очевидно, что аргументами нашего алгоритма является стороны треугольника, обозначим их как а, Ь, с. Результатом - площадь треугольника, мы ее уже обозначали переменной 5. Кроме того, в процессе вычислений мы пользовались такой величиной, как периметр треугольника и пивпериметр треугольника. Обозначим их соответственно Р и р - промежуточные величины будущего алгоритма.

При записи алгоритмов НАМ академика Ершова, языком программирования Разсаи нужно (таковы правила) указывать тип переменной, используется, - числовая или буквенная или какая: если числовая - то натуральная, целая, рациональная, действительна т.д. Итак,
а + 6 + с
Дано: а, Ь, с. Нужно: 8
Связь: 8 = у] р (р а) (р Ь) (р с), где р =

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

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

1. Ввели значение его аргументов (стороны треугольника).
2. Вычислили периметр (по формуле).
3. Вычислили периметр (по формуле).
4. Вычислили площадь (по формуле).
5. Вывели значение результата.

Алгоритм состоит из последовательности элементарных операций, которые следуют одна за другой

Вывод. Алгоритм вычисления площади треугольника по формуле Геро на - линейный.
Процесс измерения сторон треугольника дискретный. Сначала измерили одну сторону треугольника, записали результат измерений в собственную память, затем - на бумаге. Измерили длину другой стороны, записали значения; аналогично - с третьей стороной. Как видите, блок ввода аргументов алгоритма (значений сторон треугольника) в свою очередь состоит из трех простых команд: «ввести обозначения одной стороны», «ввести значение второй стороны», «ввести значение третьей стороны».

Несколько простых линейных элементов объединяются в составленную линейную структуру. Так, фильм объединяет некоторую последовательность отдельных эпизодов, учебник состоит из отдельных тем (разделов), тема - из отдельных подразделений, ваше творение по литературе или реферат по истории состоит из введения, главной (основной) части и выводов. В процессе изучения отдельных предметов вы наверняка заметили, что есть темы, которые независимы друг от друга, поэтому отдельные темы в учебнике можно переставить, а можно изменить порядок следования отдельных фрагментов или эпизодов в фильме, составные части вашего произведения, например вступление и выводы?

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

Разветвленный элемент алгоритма (алгоритм в целом) - операция (алгоритм), где есть выбор одной из двух возможных действий в зависимости от предварительно сформулированной условия.

Разветвленный элемент (алгоритм) может быть записанным в полной или сокращенной форме, что на блок-схемах выглядит так:

Сокращенная форма ветвления в случае невыполнения условия не предусматривает никаких действий, и алгоритм переходит к выполнению следующего базового элемента, поэтому блок «Действие 2» отсутствует.


Вдумайтесь в примеры:
1) Вспомните определение модуля действительного числа. Формулой его описывают так: | а | =
а, если а> 0,
а, если а <0.

Результат вычисления модуля числа а обозначим через т, тогда в словесной форме алгоритм вычисления модуля числа а может звучать так:
«Если число а неотъемлемое, то его модуль - число т, равна а, иначе число т равно числу а, противоположном числа а».
«Математизуемо» последнее предложение: «Если а> 0, тот: = а, иначе гп: = а».
Имеем полную форму разветвленного алгоритма.

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

Рассмотрим примеры.
1. Вычислите значение квадратного трехчлена 2х2 + Зл: 4якщо х = 5. Решения. Как вы выполняли такую задачу? Значение переменной х подставляли в выражение и выполняли действия февраля 1952 +354 в такой последовательности: 52 = 25, 2 25 = 50, 3 5 = 15, 50 + 15 = 65, 654 = 61.
А можно было бы сделать так: сгруппировать первые два слагаемые и вынести множитель х за скобки, тогда 2х2 + Зх4 = (2х + 3) х4 Если * = 5, то (2х +3) д: 4 = (25 +3) 54 = (10 + 3) 54 = 13 54 = 61.

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

Вся наша жизнь, как и окружающей среды, характерно тем, что в нем есть большое количество явлений и процессов, которые периодически повторяются. Да, мы уверены, что после светлой поры суток - день, наступит ночь, ночь сменит день, а потом снова ночь, снова день т.п. Времена года образуют годовой цикл, связанный с периодом обращения Земли вокруг Солнца. Четыре такта работы двигателя внутреннего сгорания образуют рабочий цикл двигателя (вспомните по физике «циклы Карно»). Когда я говорю, что частота моего пульса 72 удара в минуту, то не всегда задумываюсь над тем, что это мое сердце выполняет 72 сокращения в течение минуты, а тем более, что рабочий период моего сердца в этот момент составляет - минуты.

А теперь вспомните известный вам по физике связь между частотой и периодом. Частота - это количество повторов некоторого процесса в единицу времени, а период - продолжительность одного повтора за единицу времени.

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

Большое количество алгоритмов содержит последовательности многократно повторяющихся команд (указаний, действий) (вспомните алгоритм Евклида). Для их описания используют составленную команду «повторение» или так называемую циклическую конструкцию.
Циклическим элементом алгоритма называется такая алгоритмическая конструкция, с помощью которой согласно сформулированной условия осуществляются повторение одного или нескольких действий.

В первом случае сначала проверяется условие, и если она выполняется, то указанное действие очередной раз повторяется, и если условие не выполняется, то повторение действия прекращается и алгоритм переходит к выполнению следующей после цикла команды. Цикл с предусловием называют еще «цикл ПОКА» (выполняется условие - выполнять действия).

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

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

Рассмотрим несколько примеров.
1. Вспомните совет «Пока идет дождь, держи зонтик открытой». Проанализируем ее. Сначала сформулирована условие «идет дождь», за ней указание «держи зонтик открытой», так проверили условие «идет дождь», выполняем указание; проверили условие, она выполняется, выполняем указание, и так до тех пор, пока условие не исполнилась - дождь уже не идет, то и нет необходимости держать зонтик открытой, т.е. неопределенный цикл завершился и можно выполнять следующие указания.

2. Не так давно, когда вы еще были маленькие и не всегда послушны, особенно за столом, мама очень вас просила, например: «Съешь еще 5 ложек каши». Вы же, преодолев все обиды, черпали из тарелки, несли надоевшую ложку ко рту, глотали кашу, перемешанную со слезами, а мама считала: «Раз! Опять весь комплекс пыток повторялся, а мама считала:« Два! »И т.д. Но звучало долгожданное «Пять!» И ... Классифицируем описан алгоритм. Да, это определенный цикл с параметром, а мама была «счетчиком цикла» - параметром цикла «ДЛЯ с параметром мама».

3. А теперь запишем в виде алгоритма крылатое выражение, объединивший пространство и время: «Копать от ворот к обеду». Осуществим постановку задачи. Подразумевается копать канаву от ворот и до того времени, когда наступит обед, а не копать под руководителя учреждения - с момента, когда прошли ворота учреждения и к тому времени, когда прозвучит сигнал перерыва на обед. Указание и действие «копать» понимают все, даже дошкольники, а вот что делать с выражением «до обеда»? Придется исполнителю выдать часы. Уточним термин «обед». Пусть обед в вашем «заведении копания» в 14 час. Тогда алгоритм в словесной форме может иметь вид:
1) копнуть;
2) посмотреть на часы;
3) до 14.00.

Классифицируем его. Да, это циклическая алгоритмическая структура с Постусловия «цикл К». Запишите этот алгоритм в псевдокоде.

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

Попробуем решить несколько задач. 1. Вычислить сумму нескольких слагаемых.
Конкретизируем эту задачу. Пусть вам нужно найти сумму n слагаемых. Как вы будете считать? Прочитаете первое слагаемое и запишете его значение на бумаге или введете в регистр калькулятора. Такие же действия проводите со вторым слагаемым и еще выполняете добавление его к первому, если это на бумаге, либо нажимаете клавишу «+» на калькуляторе и т.д., пока не «расправитесь» с последним слагаемым. На калькуляторе нажать клавишу «=» (на бумаге поставили жирную точку) и получили значение суммы.

А обратили внимание, что каждый раз, начиная с третьего слагаемого, следующий слагаемое добавляли к сумме предыдущих? Если да, то вы внимательной и наблюдательным человеком. Тогда тест на внимание: вспомните, какое было первоначальное значение суммы на калькуляторе (на бумаге) в начале добавления (первое слагаемое - неправильный ответ). Конечно - на калькуляторе 0 (на бумаге чисто, поэтому будем считать, что первоначальное значение суммы на бумаге тоже 0). Итак, мы первое слагаемое добавляли в число 0, к этой сумй добавили второе слагаемое, затем к полученной сумме добавили третье слагаемое т.д., пока не выполнили добавления ПГО слагаемого.

В вашем воображении уже, наверное, сформировался вычислительный блок алгоритма вычисления суммы n слагаемых. Так, первоначальное значение суммы 5 примем за 0, т.е. переменной 5 присвоим ее первоначальное значение, записав команду 5: = 0.
К этому значению добавим значение первого слагаемого, а значение переменной 5 Замена значением суммы 0 + а, где а - числовое значение первого слагаемого, а 0 - предварительное значение суммы, т.е. выполним команду 5: = 5 + а. Поскольку значение первого слагаемого нас больше не интересует, то переменной а предоставим значение второго слагаемого, тогда, выполнив команду 5: = 5 + а, предоставим переменной 5 Значение суммы первого и второго слагаемых.

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

Так, признаком конца добавление является нулевое значение слагаемого. Следовательно, добавление вести до тех пор, пока какой плагин не будет равен 0. Другими словами: «Добавлять по схеме 5: = 5 + а до тех пор, пока какой плагин не будет равен 0». Алгоритм может иметь и такой вид:
5: = 0 Если вы зашли в магазин,
а: = 0 покрутились перед витринами и
ПЦ выставками, ничего не купили,
Введение а а потому ничего и не платили,
5: = 5 + а и вышли из него, то первичное зна
КЦ чение слагаемого а = 0 не изменит пер
до а = 0 виновного значение суммы 5 = 0, ведь
Вывод 8 0 + 0 = 0. Да?

Подведем итоги:

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

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

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

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

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