Как описать алгоритм программы

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

Алгоритм — это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

Алгоритмы и способы их описания

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

• результативностью или конечностью;
• определенностью;
• массовостью.

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

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

К основным способам описания алгоритмов можно отнести следующие:

• словесно-формульный;
• структурный или блок-схемный;
• с помощью граф-схем;
• с помощью сетей Петри.

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

Удобно использовать программное описание алгоритмов функционирования сложных систем. Так, для описания принципов функционирования ОС использовался Алголоподобный высокоуровневый язык программирования. При словесно-формульном способеалгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий. Пусть, например, необходимо найти значение следующего выражения: у = 2а – (х+6). Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:

1. Ввести значения а и х.
2. Сложить х и 6.
3. Умножить a на 2.
4. Вычесть из 2а сумму (х+6).
5. Вывести у как результат вычисления выражения.

При блок-схемномописании алгоритм изображается геометрическими фигурами (блоками), связанными по управлению линиями (направлениями потока) со стрелками. В блоках записывается последовательность действий. Данный способ по сравнению с другими способами записи алгоритма имеет ряд преимуществ. Он наиболее нагляден: каждая операция вычислительного процесса изображается специальной геометрической фигурой. Кроме того, графическое изображение алгоритма наглядно показывает разветвления путей решения задачи в зависимости от различных условий, повторение отдельных этапов вычислительного процесса и другие детали. Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД). Операции обработки данных и носители информации изображаются на схеме соответствующими блоками.Большая часть блоков по построению условно вписана в прямоугольник со сторонами а и b. Минимальное значение а= 10 мм, увеличение а производится на число, кратное 5 мм. Размер b=1,5a. Для отдельных блоков допускается соотношение между а и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в табл. 1. Таблица 1. Условные обозначения блоков схем алгоритмов

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

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

Моделирование бизнес процессов: гайд от начала до конца

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

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

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

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

Источник: studfile.net

Информатика

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

Примеры: правила сложения, умножения, решения алгебраических уравнений и т.п.

1.Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.

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

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

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

5.Выполнимость (эффективность) — результата алгоритма достигается за конечное число шагов.

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

7.Последовательность – порядок исполнения команд должен быть понятен исполнителю и не должен допускать неоднозначности.

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

2. информационные алгоритмы , представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

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

Для задания алгоритма необходимо описать следующие его элементы:

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

3.правило непосредственной переработки информации (описание последовательности действий);

5.правило извлечения результатов.

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

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

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

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

Правила создания блок – схем:

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

2.Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз.

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

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

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

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

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

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

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

1.«да» — условие выполнено.

2.«нет» — условие не выполнено.

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

Источник: psk68.ru

Урок 15
§ 2.2. Способы записи алгоритмов

Существуют различные способы записи алгоритмов. Основными среди них являются:

• словесные;
• графические;
• на алгоритмических языках.

Теоретические исследования нашего соотечественника Андрея Андреевича Маркова (младшего) (1903-1979), выполненные в середине прошлого века, показали, что в общем случае алгоритмы должны содержать предписания двух видов:

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

Именно эти операторы положены в основу большинства способов записи алгоритмов.

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

Словесное описание. Самой простой является запись алгоритма в виде набора высказываний на обычном разговорном языке. Словесное описание имеет минимум ограничений и является наименее формализованным. Однако все разговорные языки обладают неоднозначностью, поэтому могут возникнуть различные толкования текста алгоритма, заданного таким образом. Алгоритм в словесной форме может оказаться очень объёмным и трудным для восприятия.

Пример 1. Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары натуральных чисел (алгоритм Евклида).

Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и У. Запишите первое из заданных чисел в столбец X, а второе — в столбец У. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего. Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца X считайте искомым результатом.

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

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

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

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

1. Обозначить первое из заданных чисел X, второе обозначить Y.

2. Если X = Y, то перейти к п. 8.

3. Если X > Y, то перейти к п. 4, иначе перейти к п. 6.

4. Заменить X на X — Y.

5. Перейти к п. 2.

6. Заменить Y на Y — X.

7. Перейти к п. 2.

8. Считать X искомым результатом.

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

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

2.2.2. Блок-схемы

Наилучшей наглядностью обладают графические способы записи алгоритмов; самый распространённый среди них — блок-схема.

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

Рассмотрим некоторые условные обозначения, применяемые в блок-схемах.

Выполнение алгоритма всегда начинается с блока начала и оканчивается при переходе на блок конца (рис. 2.2, а). Из начального блока выходит одна линия связи; в конечный блок входит одна линия связи.

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

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

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

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

Рис. 2.2. Обозначения на блок-схемах

Пример 3. Запись алгоритма Евклида с помощью блок-схемы (рис. 2.3).

Рис. 2.3. Запись алгоритма Евклида с помощью блок-схемы

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

2.2.3. Алгоритмические языки

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

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

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

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

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

алг

нач

кон

Пример 4. Алгоритм, позволяющий из полного сосуда ёмкостью 12 л отлить половину, пользуясь двумя пустыми сосудами ёмкостью 8 и 5 л.

алг переливания

нач

наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

наполнить сосуд ёмкостью 5 л из сосуда ёмкостью 8 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

вылить всё из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л

наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л

долить из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л

вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л

кон

По ссылке http://www.niisi.ru/kumir/ вы можете скачать систему КуМир (Комплект учебных Миров) или скачать архив программы с сайта, в которой используется школьный алгоритмический язык, со встроенными исполнителями Робот, Чертёжник, Водолей и др. Кумир работает в операционных системах Windows и Linux.

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

САМОЕ ГЛАВНОЕ

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

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

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

2. Каковы основные способы записи алгоритмов?

3. Чем вызвано существование многих способов записи алгоритмов?

4. Дайте словесное описание алгоритма сложения двух обыкновенных дробей а/b и c/d.

5. Представьте в виде построчной записи алгоритм решения следующей задачи: «Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить их по возрастанию веса?».

6. Представьте с помощью блок-схемы алгоритм решения следующей задачи: «Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?».

7. Запишите на алгоритмическом языке алгоритм построения окружности заданного радиуса r, проходящей через заданные точки А и В.

8. В среде КуМир запишите и выполните алгоритм переливаний (пример 4) для исполнителя Водолей.

9. Подготовьте краткую биографическую справку о Маркове А. А. (младшем).

Электронное приложение к уроку

Файлы

Материалы урока

Ресурсы ЭОР

Cкачать материалы урока

Источник: xn—-7sbbfb7a7aej.xn--p1ai