Основные требования к алгоритмам кратко

Обновлено: 04.07.2024

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

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

2. Детерминированность - определенность (операция на каждом шаге должна понимать однозначно).

3. Результативность - получение результата за конечное число шагов.

4. Массовость - возможность использования данного алгоритма для решения целого класса задач при различных исходных данных.

5. Понятность - понятная запись для исполнителя.

6. Эффективность. Алгоритм должен приводить к результату за как можно короткое время и использовать минимум ресурсов ЭВМ (памяти).

7. Требование конечности процесса реализации. Алгоритм д. заканчиваться.

-словесный (неформальные записи на предварительном этапе);

- запись в виде программы, на одном из языков программирования.

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

3 осн. типа моделей:

1-Машины Тьюринга. В 1936 задачу уточнения понятия алг-ма и далее с его помощью опр-ть класс вычислимых ф-ий решили независимо др от др Пост и Тьюринг. Их осн идеей явл идея сущест-я некот машины, кот могла бы реализ-ть любой алгоритмич процесс. МТ состоит из следующих элементов:

2-Рекурсия – способ задания ф-ции, при к-м знач-е определяемой ф-ции для произвольных значений аргумента выражается через знач-е определяемой ф-ции для меньших аргументов (ф-я задается через обращение к самой себе). Рекурсивные ф-ции – арифм. или целочисл. ф-ции. Совок-ть таких ф-ций наз-ся множ-м рекурс-х ф-й. Ф-я, при к-й часть обл. опред-я соотносится с частью обл. знач-я назыв-ся частично-определенной ф-й. Гипотеза Клини: все частично-опред. ф-ции, вычисляемые посредством алгоритмов, явл-ся частично-рекурс-ми.

3-алгоритмы Маркова. Нормальные алгоритмы Маркова (НАМ) – это алгоритмическая система, основанная на соответствие между словами в абстрактном алфавите и включает элементарные операторы (ЭО) и распознаватели (ЭР).

ЭО – это преобразование с помощью последующего выполнения который реализует алгоритм.

ЭР – это оператор для распознавания тех или иных свойств перерабатываемой алгоритмом информации.

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

-структурное кодирование (собственно программирование)

Пример: Рекомендуют разбить сложную задачу на подзадачи и проектировать алгоритм в несколько этапах.

На 1ом этапе представить задачу в виде одного блока или словесно в виде одного предложения.

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

3.Типы и структуры данных, ср-ва для работы с ними в АЯП, примеры.

Данные – это об-ты, обраб-мые алг-мами.

Тип данных – мн-во значений, кот. может принимать переменная. (Напр. Boolean 0|1).

Структуры данных – набор перем-х, возможно, различных типов данных, объединённых определ-м образом.

1) Простые = скалярные [порядковые (цел, логич, символьн, перечисляем, интервальн) и веществ] 2) Структурир. (массивы, мн-ва, записи, файлы, строки, стек, оч-дь, деревья, графы) 3) указатели

Простые хар-ся в каждый момент вр-ни одним зн-ем, и они упорядоченные. Структурир. д. – это сов-сть данных, о кот. известно, какие элементы входят в эти структуры и каковы между ними связи. Д. простых данных: одна величина – 1 зн-е, д. структ-х одна величина – мн-во зн-ий.

1. Целый Значения: цел + - в некот диапазоне Операции: арифм. опер-ии с цел числами +-*/ mod div > 9 Операции: +-/* > > 0,123456*10 3 3-порядок мантиссы, мантисса – разряды после запятой.

3. Логич Значения: true false Операции: AND OR NOT = ≠ Внутр представление: 1 бит: 1 true, 0 false ) логический – для представления логич инфы. В яз pascal дан тип наз-ся булевым , false – 0, True – 1. в памяти данный тип занимает 4 байта.

4. Симв Значения:  символы компьют алфавита g+$7 Операции: оп-ции отношений, конкатенация Внутр представление: код таб-цы символьной кодировки. 1 симв=1байт

5. Перечисл. type FAM=(Ivanov, Petrov, Sidorov) Var student: FAM

6. Отрезковый строится на основе простых типов, кроме веществ. путем огран-я диап-на Var ind: [1..10]; (или = Type t=1..10 Var ind: t;)

В кажд. языке прогр-я свой набор типов данных. Basic – числов и симв.

Данные: Константы, переменные, выражения, ф-ции. Типы констант опр-ся по ее записи, а типы перем-х устан-ся в описании перем-х. Символьные const – это строка разрешенных символов, заключенных в кавычки. Тип перем-й задается програмером или приним-ся по умолчанию.

Средства для работы с данными – операции, выражения и команды. Операция – простейшее законченное дей-е над данными. Выр-е – запись в алг-ме (прог-ме), опред-щая послед-сть операций д. вычисления некоторой величины. Команда – входящее в запись алгоритма типовое предписание исполнителю выполнить некоторое законченное действие. Команды :=, вв/выв наз-ся простыми. Команды цикла и ветвления – составными, структурными.

Ф-ции бывают стандартные или нестанд. К станд. обращаются по имени с указанием аргумента. Существуют числовые и символьные функции. Round, trunc

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

Массивы – это упоряд. совок-ть данных одного типа, имеющих одно и то же имя. Хар-ся типом компонентов структуры и взаимосвязью между компонентами стр-ры. Эл-ты массива им. номера. Одномерн м-в – линейная таб-ца, или вектор. Двум. м-в прямоуг. таб-ца, или матрица. М-в хар-ся именем (=идентификатор), размером (к-во эл-тов м-ва), разм-стью (форма компоновки м-ва).

A: array[1..10] of Integer;

Очередь – стр-ра данных, представленная в виде списка Эл-тов, доступ к которым д. чтения возможен только в начале списка, а для записи – только с конца. Начало списка front, конец rear. Число эл-тов, хран-ся в очереди, определяет ее длину: length=rear-front+1. Оч-дь является одной из самых часто используемых стр-р данных ВТ. С ее помощью реализуется многозадачность в ОС Windows и Linux. Микропроцессор обраб-ет приложения в соотв-ии с очередью. Также организуется печать док-тов. Используется в быстрых алгоритмах сортировки эл-тов мн-ва и прохождении деревьев.

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

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

3) строковый - для хранения символьной инф-ции. В pascal исп-ся сл типы: короткие строки, длинные, широкие, указательные. Наиб часто использ-м типом явл string . В яз pascal 7.0 этот тип соответ-т типу коротк строки, в более поздних версиях длинным.

5) Структуриров-е типы данных – массив(array), запись (record ), файл (file).

Массив – объед-е однотипных элем-в в памяти.

A: array[1..10] of Integer;

Запись – объед разнотипн эл-в в памяти

Файл – объед разнотипн или однотипн эл-в на внеш носителе инф-ции. (опис-ся сл образом: : FILE of ;

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

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

Но, греческая версия происхождения этого слова была не единственной. Мифический АлГор (Algor) именовался то королём Кастилии (Rex quodam Castelliae), то индийским королём, то арабским мудрецом (philosophus Algus nomine Arabicus), то египетским божеством. Соответственно АлГорРитм — это ритм (порядок) бога Гора (АлГора).

Основная версия

Около 825 года аль-Хорезми написал сочинение, где впервые описал придуманную в Индии позиционную десятичную систему счисления. Оригинал книги, к сожалению, не сохранился, и ее оригинально название неизвестно. Аль-Хорезми сформулировал правила вычислений в новой системе и, возможно, впервые использовал цифру 0, чтобы обозначать пропущенную позицию в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как цифра и шифр). Примерно в тоже время индийские числа начали использовать и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу.

Современное понятие алгоритма

Понятие

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

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

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

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

Третье свойство результативность (конечность) – алгоритм должен приводить к решению задачи за определенное число шагов.

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

Такая трактовка понятия “алгоритм” является не совсем полной и не совсем точной.

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

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

Виды алгоритмов

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

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

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);

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

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

Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не определено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя.

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

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

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

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

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

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

Требования, предъявляемые к алгоритму

Первое требование – при построении алгоритма, прежде всего, нужно задать множество объектов, с которыми будет работать алгоритм. Формализованное (т.е. закодированное) представление этих объектов носит название данных. Алгоритм начинает работать с некоторым набором данных, название которых входные, и в результате этой работы выдает данные, название которых выходные. В итоге, алгоритм преобразует входные данные в выходные. Это правило дает возможность сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

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

Третье требование – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.

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

математический алгоритм число уравнение

Введение

Основная версия

Современное понятие алгоритма

Понятие

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

Такая трактовка понятия “алгоритм” является не совсем полной и не совсем точной.

Виды алгоритмов

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

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

Требования, предъявляемые к алгоритму

1. Каждый алгоритм имеет дело с Данными — входными, промежуточными, выходными. Для того чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т. п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора в языке программирования может выглядеть следующим образом: идентификатор — это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах — наиболее обычный тип алгоритмических данных, а число символов в слове — естественная мера объема данных. Другой случай алгоритмических объектов — формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний. В этом случае не каждое слово в алфавите будет формулой.

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

3. Алгоритм состоит из отдельных Элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов — система команд ЭВМ.

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

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

6. Алгоритм предполагает наличие Механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.

Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ЭВМ, требование 2 — памяти ЭВМ, требование 3 — программе машины, требование 4 — ее логической природе, требования 5, 6 — вычислительному устройству и его возможностям.

7. Следует ли фиксировать конечную границу для размера входных данных?

8. Следует ли фиксировать конечную границу для числа элементарных шагов?

9. Следует ли фиксировать конечную границу для размера памяти?

10. Следует ли ограничить число шагов вычисления?

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

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

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

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

Теория алгоритмов оказала существенное влияние на развитие ЭВМ и практику программирования. В теории алгоритмов были предугаданы основные концепции, заложенные в аппаратуру и языки программирования ЭВМ. Упоминаемые выше главные алгоритмические модели математически эквивалентны, но на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, и породили разные направления в программировании. Так, микропрограммирование строится на идеях машин Тьюринга; структурное программирование заимствовало свои конструкции из теории рекурсивных функций; языки символьной обработки информации (РЕФАЛ, ПРОЛОГ) берут начало от нормальных алгоритмов Маркова и систем Поста.

Конспект по информатике "Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки" для подготовки к контрольным, экзаменам и ГИА.

Алгоритм. Свойства алгоритмов.
Блок-схемы. Алгоритмические языки

Код ОГЭ: 1.3.1. Алгоритм, свойства алгоритмов, способы записи алгоритмов.
Блок-схемы. Представление о программировании

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

■ Алгоритм — строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.

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

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

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

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

Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:

Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

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

словесная запись (на естественном языке). Алгоритм записывается в виде последовательности пронумерованных команд, каждая из которых представляет собой произвольное изложение действия;
блок–схема (графическое изображение). Алгоритм представляется с помощью специальных значков (геометрических фигур) — блоков;
формальные алгоритмические языки. Для записи алгоритма используется специальная система обозначений (искусственный язык, называемый алгоритмическим);
псевдокод. Запись алгоритма на основе синтеза алгоритмического и обычного языков. Базовые структуры алгоритма записываются строго с помощью элементов некоторого базового алгоритмического языка.

Словесная запись алгоритма

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

■ Пример 1. Записать в словесной форме правило деления обыкновенных дробей.

Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.

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

Формальные исполнители алгоритма

Формальный исполнитель — это исполнитель, который выполняет все команды алгоритма строго в предписанной последовательности, не вникая в его смысл, не внося ничего в алгоритм и ничего не отбрасывая. Обычно под формальным исполнителем понимают технические устройства, автоматы, роботов и т. п. Компьютер можно считать формальным исполнителем.

Исполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). Среда исполнителя — это совокупность объектов, над которыми он может выполнять определенные действия (команды), и связей между этими объектами. Алгоритмы в этой среде выполняются исполнителем по шагам.

■ Пример 2. Исполнитель Крот имеет следующую систему команд:

вперед k — продвижение на указанное число шагов вперед;
поворот s — поворот на s градусов по часовой стрелке;
повторить m [команда1 … командаN] — повторить m раз серию указанных команд.

Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?

Повторить 5 [вперед 10 поворот 72]

Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.

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

■ Пример 3. В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).

Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).

Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

Блок–схема

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

Основные элементы блок–схемы алгоритма:

Общий вид блок–схемы алгоритма:

■ Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.

Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.

Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 Алгоритмические языки

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

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

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

Псевдокод

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

Служебные слова учебного алгоритмического языка:

Стандартная структура алгоритма

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

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

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

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

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

Примеры заголовков алгоритмов:

В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.

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

На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.

Описание величин и действия над ними

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

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

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

В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.

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

Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).

Значение — то, чему равна переменная в конкретный момент. Значение переменной можно задать двумя способами: присваиванием и с помощью процедуры ввода.

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

Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10 -2 и –7,123456*10 2 ).

Над числовыми данными можно выполнять арифметические операции и операции сравнения.

Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.

Учебный алгоритмический язык использует следующие команды для реализации алгоритма:

ОПЕРАЦИЯ ПРИСВАИВАНИЯ

Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).

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

ВВОД И ВЫВОД ДАННЫХ

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

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

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

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

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

Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:

Путь 200 м

Тот же результат был бы получен, если бы изменить строку вывода на

Читайте также: