Способы представления алгоритма ответы

Различают следующие виды алгоритмов :

линейный – список команд (указаний), выполняемых последовательно друг за другом;

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

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

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

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

1. определить температуру воздуха

2. если температура ниже 0, то надеть шубу, иначе надеть куртку

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

Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.

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

Источник

Алгоритмы

Алгоритмы. Способы записи алгоритмов

Выделяют три наиболее распространенные на практике способа записи алгоритмов:

словесный (запись на естественном языке);
графический (запись с использованием графических символов);
программный (тексты на языках программирования).

Словесный способ записи алгоритмов

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

В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника

где S – площадь прямоугольника; а, b – длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

Словестный способ записи алгоритма выглядит так:

Начало алгоритма.
Задать численное значение стороны a.
Задать численное значение стороны b.
Вычислить площадь S прямоугольника по формуле S=a*b.
Вывести результат вычислений.
Конец алгоритма.

Графический способ описания алгоритмов

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

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

Название символа	Обозначение и пример заполнения	Пояснения
Пуск-останов		Начало, завершение алгоритма или подпрограммы
Ввод-вывод данных		Ввод исходных данных или вывод результатов
Процесс		Внутри прямоугольника записывается действие, например, расчетная формула
Решение	b» width=»219″ height=»65″/>	Проверка условия, в зависимости от которого меняется направление выполнения алгоритма
Модификация		Организация цикла
Предопределенный процесс		Использование ранее созданных подпрограмм
Комментарий		Пояснения

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

блок Решение обозначает проверку условия

Если условие выполняется, то есть a>b, то следующим выполняется действие по стрелке «Да». Если условие не выполняется, то осуществляется переход по стрелке «Нет».

блок Модификация используется для организации циклических (повторяющихся) действий.

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

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


устройство ввода или вывода	дисплей	магнитный диск

В качестве примера графического способа описания алгоритмов с помощью блок-схем запишем алгоритм нахождения площади прямоугольника:

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

Последовательность выполнения сверху вниз и слева направо принята за основную.

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

Программный способ записи алгоритмов

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

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

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

Запись алгоритма на языке программирования называется компьютерной программой.

Источник

2 Методы разработки и способы представления алгоритмов

2.2 Методы разработки и способы представления алгоритмов

1. Основные принципы методов ветвей и границ, понятия сложности и сводимости задач.

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

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

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

Перечислим основные этапы решения задачи методом МВГ.

1) Трансформация задачи (ТЗ). Исходную задачу заменяют другой задачей так, что множество решений исходной задачи содержится в множестве решений трансформированной задачи. Найти оптимальное решение трансформированной задачи значительно проще, чем решение исходной задачи.

2) Построение дерева решений. Множество решений ТЗ разбивают на подзадачи. Затем каждую подзадачу в свою очередь разбивают на подзадачи. В результате получается дерево решений. Процесс разбиения прекращается, если подзадача содержит не более одного решения исходной задачи, такая задача называется концевой. Если в результате работы МВГ будет построено полное дерево решений, то МВГ будет эквивалентен полному перебору, чем лучше работает МВГ, тем он дальше от полного перебора.

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

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

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

5) Отсечения. Если для подзадачи нижняя оценка получилась больше или равна верхней оценке, то эта подзадача заведомо не содержит решения лучше одного из уже найденных решений. Поэтому дальнейшее ее исследование не имеет смысла. Идущий от нее фрагмент дерева отсекается. Чем больше ветвей дерева отсекается, тем быстрее работает МВГ. А отсечения зависят как от качества нижних оценок, так и от качества верхней оценки (исходного размещения).

6) Ветвление. Чаще всего используется следующий способ ветвления:

— для подзадач верхнего уровня получают оценки снизу;

— подзадача с лучшей оценкой разбивается на подзадачи следующего уровня, и для них определяются оценки снизу;

— эти подзадачи добавляются к тем подзадачам, от которых еще не производилось ветвление, из них выбирается для разбиения подзадача с лучшей нижней оценкой;

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

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

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

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

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

Вычислить Af чисел в последовательности Фибоначчи: 1,1,2,3,5,8. где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.

Самый очевидный способ «решения» задачи состоит в написании рекурсивной функции примерно следующего вида:

function F(X: integer): longint; begin

if (X = 1) or (X = 2) then F := 1

else F := F(X-l) + F(X-2) end;

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

Для вычисления, например, F (40) вначале вычисляется F (39) и F (38). Причем F (3 8) вычисляется заново, без использования значения, которое было вычислено, когда считалось F (39), т. е. значение функции при одном и том же значении аргумента считается много раз. Если исключить повторный счет, то функция станет заметно эффективней. Для этого приходится завести массив, в котором хранятся значения нашей функции:

var D: array[1..100] of longint;

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

Функция принимает следующий вид:

function F(X: integer): longint; begin

if (X=l) or (X=2) then D[X] := 1

else D[X] := F(X-l) + F(X-2); F := D[X]; end;

Этот подход динамического программирования называется подходом «сверху вниз». Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

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

D[12] := 1; D[2] := 1; For i := 3 to N do

Здесь использован подход «снизу вверх». Чаще всего, такой способ раза в три быстрее. Однако в ряде случаев такой метод приводит к необходимости решать большее количество подзадач, чем при рекурсии.

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

Таким образом, если алгоритм превышает отведенное ему время на тестах большого объема, то необходимо осуществлять доработку этого алгоритма.

Способы представления алгоритмов

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

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

Таким образом, алгоритм — это точное и понятное предписание исполнителю совершить последовательность действий для достижения поставленной цели за конечное число шагов.

Основные свойства алгоритмов:

1. Понятность для исполнителя.

2. Дискpетность (прерывность, раздельность) — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).

3. Опpеделенность — каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола.

4. Pезультативность — это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.

5. Массовость. Алгоpитм pешения задачи pазpабатывается в общем виде.

Разрабатывать алгоритмы может только человек.

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

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

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

— словесная (записи на естественном языке);

— графическая (изображения из графических символов);

— псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке);

— программная (тексты на языках программирования).

1. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел. Алгоритм может быть следующим:

1. задать два числа;

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

3. определить большее из чисел;

4. заменить большее из чисел разностью большего и меньшего из чисел;

5. повторить алгоритм с шага 2.

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

— такие описания строго не формализуемы;

— страдают многословностью записей;

— допускают неоднозначность толкования отдельных предписаний.

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

В таблице приведены наиболее часто употребляемые символы

Обозначение и пример заполнения

Вычислительное действие или последовательность действий

Вычисления по подпрограмм-ме, стандартной подпрог-рамме

Ввод-вывод в общем виде

Начало, конец алгоритма, вход и выход в подпрограмму

Блок «процесс» — выполнение одной или нескольких операций, обработка данных любого вида. Внутри фигуры записывают непосредственно сами операции.

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

Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.

Отображает решение или функцию переключательного типа с одним входом и двумя или более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых и нижней). В программировании данный блок соответствует условному оператору if (два выхода: true, false) и case (множество выходов).

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

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

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

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

3. Программная форма. При записи алгоритма в словесной и в графической форме допускается определенный произвол при изображении команд. Вместе с тем такая запись точна на столько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма — программной, т.е. программная форма записи алгоритма — это запись на языке программирования.

Рассмотрим примеры использования данных форм записи алгоритмов, используя следующее задание: написать алгоритм «Одеться по погоде». Если на улице температура ниже 0, то необходимо надеть шубу, иначе — куртку.

1) Словесная форма:

2. определить температуру воздуха

3. если температура ниже 0, то надеть шубу, иначе надеть куртку

Источник