10 алгоритмы способы записи типы алгоритмов алгоритмизация этапы решения задач на компьютерах
Чтобы написать еще более сложную программу, необходим новый подход к программированию - технология объектно-ориентированного программирования.
OOП включает лучшие идеи, воплощённые как в структурном программировании, так и в модульном. «Является еще более структурным программированием, еще более модульным» (Джеф Дантеманн?).
И, кроме того, ООП сочетает старые принципы с мощными новыми концепциями, которые позволяют оптимально организовывать программы.
Объектно-ориентированное программирование позволяет разложить проблему на составные части. Каждая составляющая становится самостоятельным объектом, содержащим свои собственные коды и данные, которые относятся к этому объекту. В этом случае программирование в целом упрощается, и программист получает возможность оперировать гораздо большими по объёму программами.
Таким образом, ООП – «это методология, основанная на представлении программы в виде совокупности объектов, каждый из которых является реализацией собственного класса» (А.Д. Александровский).
Основным понятием ООП является понятие класса.
Класс – множество объектов, связанных общностью структуры и поведения (класс содержит описание структуры и поведение всех объектов, связанных отношением общности). Любой объект является экземпляром класса.
procedure Init (Xinit, Yinit: byte);
function GetX : byte;
function GetY : byte;
Для разработки приложений в Delphi используются специальным образом оформленные классы – компоненты .
Компонент обладает набором свойств и методов . Свойства компонента изменяются либо на этапе сборки приложения (под воздействием системы), либо программно, в процессе работы приложения (под воздействием пользователя).
Особым видом свойства компонента является событие . Процедура обработки события – это реакция приложения на изменение свойства компонента под воздействием системы или пользователя (нажатие клавиши, перемещение курсора и т.п.)
В Object Pascal объекты существуют только в динамической памяти (т.е. переменная, являющаяся объектом, по сути является указателем на объект, и содержит адрес объекта).
Основные алгоритмические конструкции. Сложность алгоритмов.
Вопросы:
1. Линейный алгоритм
2. Разветвляющийся алгоритм
3. Циклический алгоритм
Несмотря на многообразие алгоритмов все они строятся из 3-х типов алгоритмических структур.
Линейным алгоритмом называется алгоритмом, в котором все указанные в последствии действия исполняются и притом только один раз.
Схема представляет собой последовательность блоков, которые располагаются сверху вниз в порядке их выполнения. Первичные и промежуточные данные не оказывают влияния на направление процесса вычисления. (действие 1 … действие N)
Разветвляющимся алгоритмом называется алгоритм, в котором выполняется одна из ветвей действий при заданных значениях параметра.
На практике часто встречаются задачи, в которых в зависимости от первоначальных условий или промежуточных результатов необходимо выполнить вычисления по одним или другим формулам.
Такие задачи можно описать с помощью алгоритмов разветвляющейся структуры. В таких алгоритмах выбор направления продолжения вычисления осуществляется по итогам проверки заданного условия. Ветвящиеся процессы описываются оператором IF (условие).
б) если – то иначе
условие 1: действие 1
условие N: действие N
Разветвляющийся алгоритм:
нет
да
Циклический алгоритм – алгоритм, в котором какая-то совокупность действий повторяется несколько раз при изменяющихся значениях параметра.
Для решения многих задач характерно многократное повторение отдельных участков вычислений. Для решения таких задач применяются алгоритмы циклической структуры (циклические алгоритмы). Цикл – последовательность команд, которая повторяется до тех пор, пока не будет выполнено заданное условие. Циклическое описание многократно повторяемых процессов значительно снижает трудоемкость написания программ.
Существуют две схемы циклических вычислительных процессов.
Особенностью первой схемы является то, что проверка условия выхода из цикла проводится до выполнения тела цикла. В том случае, если условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.
Особенностью второй схемы является то, что цикл выполняется хотя бы один раз, так как первая проверка условия выхода из цикла осуществляется после того, как тело цикла выполнено.
Существуют циклы с известным числом повторений и итерационные циклы. При итерационном цикле выход из тела цикла, как правило, происходит при достижении заданной точности вычисления.
Алгоритм любой сложности может быть представлен комбинацией трех базовых структур:
- ветвление (в полной и сокращенной форме);
- цикл (с предусловием или постусловием).
Характерной особенностью этих структур является наличие у них одного входа и одного выхода.
Циклический алгоритм:
да
нет
Процесс решения задач на компьютере – это совместная деятельность человека и ЭВМ. На долю человека приходятся этапы, связанные с творческой деятельностью – постановкой, алгоритмизацией, программированием задач и анализом результатов, а на долю персонального компьютера – обработка информации с разработанным алгоритмом.
Первый этап – постановка задачи.На этом этапе участвует человек, хорошо представляющий предметную область задачи. Он должен чётко определить цель задачи, дать словесное описание содержания задачи и предложить общий подход к её решению.
Второй этап – выбор метода решения (математическое или информационное моделирование). Цель данного этапа – создать такую математическую модель решаемой задачи, которая могла быть реализована в компьютере. Существует целый ряд задач, где математическая постановка сводится к простому перечислению формул и логических условий.
Этот этап тесно связан с первым этапом, и его можно отдельно не рассматривать. Однако возможно, что для полученной модели известны несколько методов решения и необходимо выбрать лучший.
Третий этап – алгоритмизация задачи.На основе математического описания необходимо разработать алгоритм решения.
Алгоритм –система точных и понятных предписаний о содержании и последовательности выполнения конечного числа действий, необходимых для решения любой задачи данного типа (класса).
Задача составления алгоритма не имеет смысла, если не известны или не учитываются возможности его исполнителя (ребёнок может прочесть, но не может решить сложную задачу).
Исполнителем может быть не только человек, но и автомат. Компьютер – лишь частный, но наиболее впечатляющий пример исполнителя, чьё поведение основано на реализации алгоритма. Более того, создание персонального компьютера оказало воздействие на развитие теории алгоритмов, одной из областей дискретной математики.
Эффективный метод построения алгоритма –метод пошаговой детализации(последовательного построения). При этом сложная задача разбивается на ряд более простых. Для каждой подзадачи – свой алгоритм. Универсальный эффективный метод построения алгоритма является основой структурного программирования (языки QBasic, Turbo Pascal и др.).
Если алгоритм разработан, то его можно вручить разным людям (пусть и не знакомым с сутью решаемой задачи), и они, следуя системе правил, будут действовать одинаково и получат (при безошибочных действиях) одинаковый результат.
Используются различные способы записи алгоритмов:
– словесный (запись рецептов в кулинарной книге, инструкции по использованию технических устройств и т. п.);
– графический – пример на рисунке;
– структурно-стилизованный (для записи используется язык псевдокода).
Свойства алгоритма.При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств.
Однозначностьалгоритма – единственность толкования исполнителем правил выполнения действий и порядка их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя (сложитьАиВ).
Конечностьалгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость алгоритма в целом. Представленный на рисунке алгоритм обладает этим свойством.
Результативностьалгоритма – предполагает, что выполнение алгоритма должно завершиться получением определённых результатов. У нас для целыхАиВвсегда будет вычислена сумма.
Массовость– возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. В нашем примере алгоритмом используется обозначение, а не конкретные числа, поэтому он может быть использован для сложения любых целых чисел.
Правильностьалгоритма – способность алгоритма давать правильные результаты решения поставленных задач.
Четвёртый этап – программирование.Программой называется план действий, подлежащих выполнению некоторым исполнителем, в качестве которого может выступать компьютер. Программа позволяет реализовать разработанный алгоритм. Именно этому этапу посвящена большая часть данного учебного пособия.
Пятый этап – ввод программы и исходных данных в ЭВМс клавиатуры с помощью редактора текстов и их запись на гибкий или жёсткий диск для постоянного хранения.
Шестой этап – тестирование и отладка программы. Исполнение алгоритма с помощью ЭВМ, поиск и исключение ошибок. При этом программисту приходится выполнять рутинную работу по проверке работы программы, поиску и исключению ошибок, и поэтому для сложных программ этот этап часто требует гораздо больше времени и сил, чем написание первоначального текста программы.
Отладка программы – сложный и нестандартный процесс, который заключается в том, чтобы протестировать программу на контрольных примерах.
Контрольные примеры стремятся выбрать так, чтобы при работе с ними программа прошла все основные пути блок-схем алгоритма, поскольку на каждом из путей могут быть свои ошибки, а детализация плана зависит от того, как поведёт себя программа на этих примерах. На одном она может «зациклиться», на другом дать бессмысленный результат. Сложные программы отлаживают отдельными фрагментами.
Для повышения качества выполнения этого этапа используются специальные программы – отладчики, которые позволяют исполнить программу «по шагам» с наблюдением за изменением значений переменных, выражений и других объектов программы, с отслеживанием выполнения операторов.
Седьмой этап – исполнение отлаженной программы и анализ результатов.На этом этапе программист запускает программу и задаёт исходные данные, требуемые по условию задачи.
Полученные результаты анализируются постановщиком задачи, и на основании этого анализа вырабатываются соответствующие решения, рекомендации, выводы. Например, если при решении задачи на ПК результат 2+3=4, то следует изменить алгоритм и программу.
Чтобы персональный компьютер (ПК) выполнил решение какой-либо задачи, ему необходимо получить от человека инструкции, как её решать. Набор таких инструкций для компьютера, направленный на решение конкретной задачи, называется компьютерной программой.
Современные компьютеры не настолько совершенны, чтобы понимать программы, написанные на каком-либо употребляемом человеком языке.
Команды, записанные для ЭВМ, необходимо представлять в понятной компьютеру форме. С этой целью применяютязыки программирования– искусственные языки, алфавит, словарный запас и структура которых удобны и понятны компьютеру.
В самом общем смыслеязыком программированияназывается фиксированная система обозначений и правил для описания алгоритмов и структур данных.
Язык программирования Турбо- Паскаль. Структура языка Turbo-Pascal, основные понятия. Запись и порядок выполнения операций в арифметическом выражении. Стандартные математические функции и процедуры Turbo-Pascal
Система программирования Turbo Pascal предназначена для выполнения этапов решения задачи на алгоритмическом языке Паскаль и включает в себя три главные компоненты: редактор текстов, компилятор, исполнительную систему.
С помощью встроенного в систему текстового редактора можно формировать в памяти любые тексты, не только программы на Паскале. В частности, это могут быть исходные данные решаемой задачи в текстовой форме. Текст программы, созданный редактором, можно сохранить на диске в виде файла с именем следующего формата .раs, где pas — это стандартное расширение имени файла, созданного системным редактором. Имя файла задается пользователем.
Выполнение программы остается под контролем исполнительной системы. Она, в частности, помогает обнаружить ошибку в программе, если при исполнении произошел сбой. Пользователю сообщается причина сбоя и указывается место, где он случился в Паскаль-программе, происходит автоматический возврат в режим редактирования.
Turbo Pascal позволяет редактировать, компилировать, компоновать и выполнять Паскаль-программы. При этом пользователю предоставляется высокая скорость компиляции, удобство работы с компьютером и мощная библиотека процедур и функций.
Программа на Паскале в общем случае состоит из нескольких файлов. Один из них содержит главную программу, а остальные – модули. Главная программа состоит из заголовка, блока и заканчивается точкой — признаком конца программы. В свою очередь, блок содержит разделы описаний и раздел операторов. В общем случае «скелет» программы можно представить следующим образом:
Program (заголовок программы);
Uses(раздел объявления модулей);
Label(раздел объявления меток);
Const(раздел объявления констант);
Type(раздел объявления типов);
Var(раздел объявления переменных);
Procedure(function)(раздел объявления подпрограмм: процедурили функций);
Begin
(раздел операторов, обязательная часть);
end.
Все указанные разделы отделяются друг от друга точкой с запятой.
Раздел операторов должен обязательно присутствовать в любой программе и является основным. Предшествующие разделы носят характер описаний и не обязательно содержаться в программе.
Заголовок программы состоит из зарезервированного словаprogramи имени программы (со списком параметров, заключенных в круглые скобки). Завершается заголовок точкой с запятой.
В Turbo Pascal имеются особенности в структуре программы. Так, заголовок программы необязателен и игнорируется компилятором. Порядок размещения разделов произвольный, можно создавать несколько одинаковых разделов. Единственное правило, которое необходимо выдерживать, - в любом месте программы можно использовать лишь элементы (метки, типы, константы, переменные, подпрограммы и т. д.), которые были определены ранее по тексту программы или являются предопределенными элементами языка. Исключением из этого правила может быть лишь определение типа-указателя через неопределенный до этого тип. Однако этот тип в дальнейшем должен быть обязательно определен.
Операторы в разделе операторов отделяются друг от друга точкой с запятой. Передendточка с запятой не ставится, однако ее наличие не является ошибкой, а лишь означает присутствие между последним исполняемым оператором и служебным словомendеще одного оператора - пустого оператора. Заканчивается программа словомend, после которого ставится точка.
В начале программы необходимо располагать ее спецификацию – комментарий в фигурных скобках, содержащий назначение программы, данные о программисте, дату создания программы.
Язык программирования Паскаль является языком структурного программирования. В нем есть все необходимые управляющие конструкции для структурного построения программы. Наглядность такому построению придает структуризация внешнего вида текста программы. Основной используемый для этого прием — сдвиги строк, которые должны подчиняться следующим правилам:
- конструкции одного уровня вложенности записываются на одном вертикальном уровне (начинаются с одной позиции в строке);
- вложенная конструкция записывается смещенной по строке на несколько позиций вправо относительно внешней для нее конструкции.
Знаки операций предназначены для обозначения тех или иных арифметических, логических или других действий. Они бывают двух типов: состоящие из небуквенных символов (например, +, -, * и т.д.) и буквенные операции (например, not, mod, div и т. д.), представляющие собой зарезервированные слова. Операции над данными делятся на унарные (применимые к одному операнду) и бинарные (применимые к двум операндам). Приведем примеры бинарных арифметических операций (в таблице буква I обозначает целые типы, R — вещественные типы):
Знак | Выражение | Типы операндов | Тип результата | Операция |
+ | А+В | R,R I,I I,R; R,I | R I R | Сложение |
- | А-В | R,R I,I I,R; R,I | R I R | Вычитание |
* | А*В | R,R I,I I,R; R,I | R I R | Умножение |
/ | А/В | R,R I,I I,R; R,I | R R R | Вещественное деление |
Div | A div B | I, I | I | Целое деление |
Mod | A mod B | I, I | I | Остаток от деления |
Арифметическое выражение задает порядок выполнения действий над числовыми величинами. Арифметические выражения содержат арифметические операции, функции, операнды, круглые скобки. Одна константа или одна переменная — простейшая форма арифметического выражения.
Порядок выполнения операций в арифметическом выражении подчиняется трем правилам:
1. Правилу скобок. Оно гласит, что первыми выполняются операции в скобках. Если имеется несколько пар вложенных скобок, вычисления начинаются с самых внутренних скобок.
2. Правилу учета приоритета операций: вначале вычисляются значения функций, затем выполняются операции умножения и деления и в последнюю очередь - операции сложения и вычитания.
3. Правилу следования: операции одинакового старшинства (приоритета) выполняются слева направо в порядке их следования.
В качестве операндов в выражении, кроме констант и переменных, можно использовать стандартные функции. Аргументы функций обязательно заключаются в круглые скобки. Приоритет выполнения функции выше, чем приоритет выполнения арифметических операций. Рассмотрим стандартные функции Турбо Паскаля (в таблице буква I обозначает целые типы, R — вещественные типы):
Обращение | Тип аргумента | Тип результата | Тип действия |
pi | - | R | Число π |
abs(x) | I,R | I,R | Модуль (абсолютная величина) числа х |
sqr(x) | I,R | I,R | Квадрат х |
sqrt(x) | I,R | R | Корень квадратный из х (х≥0) |
sin(x) | I,R | R | Синус х (х в радианах) |
cos(x) | I,R | R | Косинус х (х в радианах) |
arctan(x) | I,R | R | Арктангенс х (результат в радианах) |
exp(x) | I,R | R | Экспонента е в степени х (е≈2,71828) |
ln(x) | I,R | R | Натуральный логарифм х (x>0) |
trunc(x) | R | I | Целая часть х |
int(x) | I,R | R | Целая часть х |
round(x) | R | I | Округление х до ближайшего целого |
frac(x) | I,R | R | Дробная часть х |
random | - | I | Случайное число [0,1) |
random(x) | I | R | Случайное число [0,х) |
dec(x,[n]) | I | I | Уменьшение х на n, при отсутствии n – на 1 |
inc(x,[n]) | I | I | Увеличение х на n, при отсутствии n – на 1 |
odd(x) | Longint | Boolean | true, если значение x нечетное; false, если x четное |
ord(x) | любой порядковый | Longint | Порядковый номер значения х в его типе. Если х – символ, то функция возвращает код символа |
pred(x) | любой порядковый | тот же, что для x | Предыдущее относительно х значение в его типе |
succ(x) | любой порядковый | тот же, что для x | Следующее относительно х значение в его типе |
chr(x) | Byte | Char | Определяет символ с указанным кодом (х – число, определяющее код символа) |
Турбо Паскале не содержит некоторые часто используемые математические функции, поэтому при их вычислении используют эквивалентные математические формулы:
Функция | Эквивалентная математическая формула | Запись в программе |
ax | | exp(x*ln(a)) |
tg(x) | | sin(x)/cos(x) |
arcsin(x) | | arctan(x/sqrt(1-x*x)) |
arccos(x) | | arctan(sqrt(1-x*x)/x) |
logax | | ln(x)/ln(a) |
При возведении в небольшую целую степень вместо операции возведения в степень рекомендуется использовать операцию умножения, поскольку возведение в степень выполняется на несколько порядков дольше умножения и не позволяет обрабатывать отрицательные аргументы.
Структура процедуры имеет следующий вид:
Procedure (формальные параметры : их тип);
Процедура - стандартный алгоритм обработки информации, состоящий из имени (идентификатора), описания (перечня имен переменных и др.) и операторов, реализующих процедуру. Помимо стандартных процедур, могут быть использованы процедуры, подготовленные составителем программы. В исполняемой части программы указывается только имя процедуры. Процедура исполняется, если все упомянутые в ней пара метры приобретают соответствующие значения.
Процедура вызывается по имени:
Значение каждого фактического параметра при вызове процедуры передаётся формальному параметру. Временно управление передаётся процедуре. После завершения работы процедуры управление возвращается в основную программу.
Каждый формальный параметр указывается вместе со своим типом. Соответствующий ему фактический параметр указывается без типа. Между формальными и фактическими параметрами должно быть соответствие по количеству параметров, по их типу и порядку следования.
Заголовок процедуры может выглядеть так:
PROCEDURE GG(a,b,c:integer); вызыватьсятак: GG(3,n,m)
Здесь a,b,c-формальные параметры, а 3, n, m-фактические параметры
Таким образом в процедуру передаются значения: a=3, b=n, c=m
Переменные описанные в процедуре после слова Var, являются внутренними переменными процедуры или промежуточными, они не являются данными для операций внутри процедуры и не являются результатом её выполнения, а нужны лишь для промежуточных действий. Данные и результаты описываются в круглых скобках после имени процедуры. Перед описанием переменных-результатов пишут служебное слово var.
Первоначально ЭВМ были созданы для вычислений, но постепенно на ней стали решать задачи по физике, химии, биологии, управлению технологическими процессами, рисованию мультфильмов и т.д., т.е. для решения задач с математикой непосредственно не связанных. В общем случае выделяют несколько этапов в подготовке и решении задач на ЭВМ.
На первом этапе анализируется условие задачи, определяются исходные данные и результаты, устанавливается зависимость между величинами, рассматриваемыми в задаче. Некоторые задачи имеют множество способов решения, поэтому необходимо выбрать способ решения (сделать постановку задачи, составить модель задачи). Для этого необходимо определить математические соотношения между исходными данными и результатом. Выполнив перевод задачи на язык математики, получают математическую модель.
Второй этап заключается в составлении алгоритма решения задачи по выбранной модели.
На третьем этапе алгоритм записывается на языке программирования и полученная программа вводится в ЭВМ. Далее проводится отладка программы, т.е. поиск и ошибок. Различают логические и семантические ошибки. Семантические ошибки возникают, когда программист неправильно записывает конструкции языка программирования. Семантические ошибки отыскать легче, т. к. современные трансляторы языков программирования способны их выявить. Логические ошибки возникают, когда инструкции записаны правильно, но последовательность их выполнения дает неверный результат.
Далее проводится тестирование, которое заключается в запуске программы с использованием контрольных примеров - тестов. Тесты выбирают таким образом, чтобы при работе с ними программа прошла все возможные ветви алгоритма, поскольку на каждом из них могут быть свои ошибки.
После отладки и тестирования программа выполняется с реальными исходными данными и проводится анализ полученных результатов, т.е. сопоставление их с экспериментальными фактами, теоретическими воззрениями и другой информацией об изучаемом объекте. Если результаты работы программы не удовлетворяют пользователей по каким-либо параметрам, то производится уточнение модели. При уточнении модели правится алгоритм программы, снова проводятся отладка, тестирование, расчеты и анализ результатов. Так продолжается до тех пор, пока результаты работы программы не будут удовлетворять знаниям об изучаемом объекте.
В данном учебном элементе подробно рассказывается об алгоритме и его свойствах; о компьютере как автоматическом исполнителе алгоритма; об алгоритмических структурах и этапах решения задач на конкретном примере. В качестве практической части предложены задачи.
Понятие алгоритма. Свойства алгоритмов. Формы записей алгоритмов. Общие принципы построения.
Вопросы:
Решение задач на компьютере основано на понятии алгоритма. Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к исходному результату.
Происходит от имени узбекского ученого IX в. Аль-Хорезми, который в своем труде "Арифметический трактат", переведенном в XII в. с арабского на латынь, изложил правила арифметических действий над числами в позиционной десятичной системе счисления. Эти правила и называли алгоритмами.
Алгоритм означает точное описание некоторого процесса, инструкцию по его выполнению. Разработка алгоритма является сложным и трудоемким процессом. Алгоритмизация – это техника разработки (составления) алгоритма для решения задач на ЭВМ.
Составление алгоритмов и вопросы их существования являются предметом серьезных математических исследований. Алгоритм должен удовлетворять определенным требованиям.
Принято выделять следующие семь:
1. Наличие ввода исходных данных.
2. Наличие вывода результата выполнения.
3. Однозначность (компьютер «понимает» только однозначные инструкции).
4. Общность – алгоритм предназначен для решения некоторого класса задач.
5. Корректность – алгоритм должен давать правильное решение задачи.
6. Конечность – решение задачи должно быть получено за конечное число шагов.
7. Эффективность – для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объем оперативной памяти и т.д.).
Свойства алгоритмов.
Свойства алгоритма:
1. Массовость – алгоритм должен описывать круг однотипных задач, исходные данные которых могут изменяться в определенных пределах.
2. Детерминированность – это обусловленность всех шагов алгоритма потребностью решения данных задач. Свойство детерминированности выражается в том, что при заданных значениях параметров алгоритм выполняется формально, т.е. строго выполняется последовательность действий до появления результата.
3. Понятность – предписания алгоритма должны быть сформулированы так, чтобы они понимались одинаково разработчиком и исполнителем, т.е. они должны быть однозначно понятны.
4. Дискретность – четкое разделение всего пути решения задачи на отдельные этапы (шаги) так, чтобы ход выполнения алгоритма проходил поэтапно, вовремя корректируя действия исполнителя.
5. Результативность – точное выполнение предписаний алгоритма должно привести к результату за n шагов, если правильно разработана исходная модель и сам алгоритм.
Всякий человек при планировании деятельности обязательно выполняет две операции:
1. Оценивает исходные данные (создает исходную модель).
2. Прогнозирует результат (прогнозирует какую-то конечную модель).
Суть решения задачи в переходе от исходной модели к прогнозируемому результату, через конечное число действий.
Формы записей алгоритмов. Общие принципы построения
Этапы информационных технологий решения прикладных задач:
- общая формулировка задачи;
- математическая формулировка задачи;
- выбор математического метода решения;
- составление алгоритма решения;
- составление и отладка программы;
- решение поставленной задачи и представление результатов.
Для записи алгоритма существует общая методика:
- Каждый алгоритм должен иметь имя, которое раскрывает его смысл.
- Необходимо обозначить начало и конец алгоритма.
- Описать входные и выходные данные.
- Указать команды, которые позволяют выполнять определенные действия над выделенными данными
Общий вид алгоритма
Алгоритм: Название алгоритма
Для записи алгоритма решения задачи применяются следующие изобразительные способы их представления:
- Словесно- формульное описание
- Блок-схема (схема графических символов)(по ГОСТ 19.701-90 "Единая система программной документации"/ИСО 5807-85);
Формульно-словесный способ записи алгоритма характеризуется тем, что описание осуществляется с помощью слов и формул. Содержание последовательности этапов выполнения алгоритмов записывается на естественном профессиональном языке предметной области в произвольной форме.
Графический способ описания алгоритма (блок - схема) получил самое широкое распространение. Для графического описания алгоритмов используются схемы алгоритмов или блочные символы (блоки), которые соединяются между собой линиями связи.
Блок-схемой называется направленный граф, в узлах которого содержаться элементы (блоки), геометрическая конфигурация которых показывает, что делает этот блок.
Каждый этап вычислительного процесса представляется геометрическими фигурами (блоками). Они делятся на арифметические или вычислительные (прямоугольник), логические (ромб) и блоки ввода-вывода данных (параллелограмм).
Порядок выполнения этапов указывается стрелками, соединяющими блоки. Геометрические фигуры размещаются сверху вниз и слева на право. Нумерация блоков производится в порядке их размещения в схеме.
Алгоритмические языки - это специальное средство, предназначенное для записи алгоритмов в аналитическом виде. Алгоритмические языки близки к математическим выражениям и к естественным языкам. Каждый алгоритмический язык имеет свой словарь. Алгоритм, записанный на алгоритмическом языке, выполняется по строгим правилам этого конкретного языка.
Операторные схемы алгоритмов. Суть этого способа описания алгоритма заключается в том, что каждый оператор обозначается буквой (например, А – арифметический оператор, Р – логический оператор и т.д.).
Операторы записываются слева направо в последовательности их выполнения, причем, каждый оператор имеет индекс, указывающий порядковый номер оператора. Алгоритм записывается в одну строку в виде последовательности операторов.
Псевдокод – система команд абстрактной машины. Этот способ записи алгоритма с помощью операторов близких к алгоритмическим языкам.
Просмотр содержимого документа
«Алгоритмы и способы их описания, этапы решения задач»
У чебный элемент
Тема: «Алгоритмы и способы их описания. Этапы решения задач.» - 10 -
П редмет: «Информатика»
Изучив данный учебный элемент, Вы повторите и усвоите:
понятие алгоритма, свойства;
способы описания алгоритма;
виды алгоритмических конструкций;
этапы решения задач
Оборудование, материалы и вспомогательные средства:
Сопутствующие учебные элементы и пособия:
Учебник И.Г. Семакин и др. 10 класс
Слово «алгоритм» происходит от имени великого среднеазиатского ученого 8–9 вв. Аль-Хорезми.
Алгоритм – понятное и точное предписание исполнителю совершить определенную последовательность действий для достижения поставленной цели за конечное число команд.
Характеристики исполнителя
Сpеда — это «место обитания» исполнителя.
Система команд – некоторый строго заданный список команд.
После вызова команды исполнитель совеpшает соответствующее элементаpное действие.
Отказы исполнителя возникают, если команда вызывается пpи недопустимом для нее состоянии сpеды.
Свойства алгоритма
Понятность - исполнитель алгоритма должен знать, как его выполнять.
Дискpетность — алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых шагов.
Опpеделенность — каждое пpавило алгоpитма должно быть четким и однозначным.
Pезультативность - алгоpитм должен пpиводить к pешению задачи за конечное число шагов.
Массовость – алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными
Способы записи алгоритмов
словесный (запись на естественном языке);
графический (изображения из графических символов);
программный (тексты на языках программирования).
Блок-схема – это графическое изображение алгоритма в виде определенным образом связанных между собой нескольких типов блоков.
б лок начала (конца)
блок ввода (вывода)
Линейный алгоритм – это алгоритм, в котором команды выполняются последовательно одна за другой.
действие n
Разветвляющийся алгоритм – это алгоритм, в котором та или иная серия команд выполняется в зависимости от истинности условия.
Условия в разветвляющихся алгоритмах
Условие – это высказывание, которое может быть либо истинным, либо ложным.
Простое условие включает в себя одно предложение; два числа, две переменных или два арифметических выражения, которые сравниваются между собой
Сложное условие - последовательность простых условий, объединенных между собой знаками логических операций И (AND), ИЛИ (OR).
Например: (100) AND (89); (x=10) OR (x=0).
Алгоритмическая структура «выбор»
В ыбор - это такая алгоритмическая структура, в которой выполняется одна из нескольких последовательностей команд при истинности соответствующего условия.
Полный выбор:
при условии 1: действия 1
при условии 2: действия 2
при условии N: действия N
иначе действия N+1
Неполный выбор
при условие 1: действия 1
при условие 2: действия 2
при условие N: действия N
Алгоритмическая структура «цикл»
Цикл - это такая алгоритмическая структура, в которой серия команд (тело цикла) выполняется многократно.
Различают циклы с предусловием и с постусловием ( цикл «До» и цикл «Пока»)
Цикл со счетчиком предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне.
Словесный способ записи: для i от i1 до i2 тело цикла.
Этапы решения задачи на компьютере
Постановка задачи и формализация.
Анализ математической задачи.
Разработайте первые 3 этапа решения задачи: города А и Б находятся на одной междугородней магистрали. Из обоих городов на магистраль одновременно выехали два автомобиля. Каждый движется со своей постоянной скоростью, никуда не сворачивая. Нужно определить, через сколько времени они встретятся, на каком расстоянии от городов А и Б произойдет встреча и встретятся ли они вообще?
Вариант постановки задачи и математической модели решения
Дано: V1 , V2 – скалярные значения скоростей автомобилей,
S – расстояние между городами А и Б.
Требуется найти t – время, через которое автомобили встретятся.
Данная модель очень ограничена. Возможны другие варианты решения.
Автомобили выехали навстречу друг другу. Должны встретиться.
Автомобили выехали в одном направлении. Могут встретиться, могут не встретиться.
Автомобили выехали в одном направлении. Могут встретиться, могут не встретиться.
Автомобили выехали в разных направлениях. Они не встретятся.
Будем считать, что если V1 или V2 меньше 0, то автомобиль едет в сторону, противоположную положительному направлению.
Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.
Алгоритм — это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит от algoritmi, являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми. Благодаря латинскому переводу трактата аль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.
Применительно к ЭВМ алгоритм определяет вычислительный процесс, начинающийся с обработки некоторой совокупности возможных исходных данных и направленный на получение определенных этими исходными данными результатов. Термин вычислительный процесс распространяется и на обработку других видов информации, например, символьной, графической или звуковой.
Если вычислительный процесс заканчивается получением результатов, то говорят, что соответствующий алгоритм применим к рассматриваемой совокупности исходных данных. В противном случае говорят, что алгоритм неприменим к совокупности исходных данных. Любой применимый алгоритм обладает следующими основными свойствами:
Результативность означает возможность получения результата после выполнения конечного количества операций.
Определенность состоит в совпадении получаемых результатов независимо от пользователя и применяемых технических средств.
Массовость заключается в возможности применения алгоритма к целому классу однотипных задач, различающихся конкретными значениями исходных данных.
Для задания алгоритма необходимо описать следующие его элементы:
набор объектов, составляющих совокупность возможных исходных данных, промежуточных и конечных результатов;
правило непосредственной переработки информации (описание последовательности действий);
правило извлечения результатов.
Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.
Таким образом, можно дать следующее определение программы.
Программа для ЭВМ представляет собой описание алгоритма и данных на некотором языке программирования, предназначенное для последующего автоматического выполнения.
Способы описания алгоритмов
К основным способам описания алгоритмов можно отнести следующие:
структурный или блок-схемный;
с помощью граф-схем;
с помощью сетей Петри.
Перед составлением программ чаще всего используются словесно-формульный и блок-схемный способы. Иногда перед составлением программ на низкоуровневых языках программирования типа языка Ассемблера алгоритм программы записывают, пользуясь конструкциями некоторого высокоуровнего языка программирования. Удобно использовать программное описание алгоритмов функционирования сложных программных систем. Так, для описания принципов функционирования ОС использовался Алголоподобный высокоуровневый язык программирования.
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
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 а. Внутри парных окружностей указывается один и тот же идентификатор. В качестве идентификатора, как правило, используется порядковый номер блока, к которому направлена соединительная линия.
Если схема занимает более одного листа, то в случае разрыва линии вместо окружности используется межстраничный соединитель. Внутри каждого, соединителя указывается адрес — откуда и куда направлена соединительная линия. Адрес записывается в две строки: в первой указывается номер листа, во второй — порядковый номер блока.
Блок-схема должна содержать все разветвления, циклы и обращения к подпрограммам, содержащиеся в программе.
Читайте также: