Читайте также:
|
7. Сопровождение программы:
• доработка программы для решения конкретных задач;
• составление документации к решенной задаче, к математической модели, к алгоритму, к программе, к набору тестов, к использованию.
Алгоритм - точное предписание исполнителю совеpшить определенную последовательность действий для достижения поставленной цели за конечное число шагов.
Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850) выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем алгоритмом стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных.
Алгоритм может быть предназначен для выполнения его человеком или автоматическим устройством. Создание алгоритма, пусть даже самого простого, - процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел. Именно эти правила в то время называли алгоритмами.
Данное выше определение алгоритма нельзя считать строгим – не вполне ясно, что такое «точное предписание» или «последовательность действий, обеспечивающая получение требуемого результата».
Поэтому обычно формулируют несколько общих свойств алгоритмов, позволяющих отличать алгоритмы от других инструкций.
Такими свойствами являются:
• Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов. Каждое действие, предусмотренное алгоритмом, исполняется только после того, как закончилось исполнение предыдущего.
• Определенность – каждое правило алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
• Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.
• Массовость – алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
На основании этих свойств иногда дается определение алгоритма, например: “Алгоритм – это последовательность математических, логических или вместе взятых операций, отличающихся детерменированностью, массовостью, направленностью и приводящая к решению всех задач данного класса за конечное число шагов”.
Такая трактовка понятия “алгоритм” является неполной и неточной.
Во-первых, неверно связывать алгоритм с решением какой-либо задачи. Алгоритм вообще может не решать никакой задачи.
Во-вторых, понятие “массовость” относится не к алгоритмам как к таковым, а к математическим методам в целом. Решение поставленных практикой задач математическими методами основано на абстрагировании – мы выделяем ряд существенных признаков, характерных для некоторого круга явлений, и строим на основании этих признаков математическую модель, отбрасывая несущественные признаки каждого конкретного явления. В этом смысле любая математическая модель обладает свойством массовости. Если в рамках построенной модели мы решаем задачу и решение представляем в виде алгоритма, то решение будет “массовым” благодаря природе математических методов, а не благодаря “массовости” алгоритма.
Виды алгоритмов
Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей ее решения, определения действий исполнителя подразделяются следующим образом:
• Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т.п.);
• Гибкие алгоритмы, например стохастические, т.е. вероятностные и эвристические. Механический алгоритм задает определенные действия, обозначая их в единственной и достоверной последовательности, обеспечивая тем самым однозначный требуемый или искомый результат, если выполняются те условия процесса, задачи, для которых разработан алгоритм.
• Вероятностный (стохастический) алгоритм дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
• Эвристический алгоритм (от греческого слова “эврика”) – это такой алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К эвристическим алгоритмам относят, например, инструкции и предписания. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений, основанные на аналогиях, ассоциациях и прошлом опыте решения схожих задач.
• Линейный алгоритм – набор команд (указаний), выполняемых последовательно во времени друг за другом.
• Разветвляющийся алгоритм – алгоритм, содержащий хотя бы одно условие, в результате проверки которого ЭВМ обеспечивает переход на один из двух возможных шагов.
• Циклический алгоритм – алгоритм, предусматривающий многократное повторение одного и того же действия (одних и тех же операций) над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов.
Цикл программы – последовательность команд (серия, тело цикла), которая может выполняться многократно (для новых исходных данных) до удовлетворения некоторого условия.
Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях при наличии одинаковых последовательностей указаний (команд) для различных данных с целью сокращения записи также выделяют вспомогательный алгоритм.
На всех этапах подготовки к алгоритмизации задачи широко используется структурное представление алгоритма.
Структурная (блок-, граф-) схема алгоритма – графическое изображение алгоритма в виде схемы связанных между собой с помощью стрелок (линий перехода) блоков – графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.
Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, т.к. зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.
Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой схему – набор прямоугольников и других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации “. Здесь форма представления алгоритма смешивается с самим алгоритмом.
Требования, предъявляемые к алгоритму
Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти. В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил.
В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки. Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Алфавит языка Турбо-Паскаль (набор используемых символов) включает буквы латинского алфавита: от a до z и от A до Z, арабские цифры: от 0 до 9, специальные символы: _ + - * / =,.:; < > () [ ] { } ^ @ $ #, пробел "_" и управляющие символы с кодами от #0 до #31.
Используются также служебные (зарезервированные) слова, например: absolute, and, array, begin, case, const, constructor, destructor, div, do, downto, else, end, external, file, for, forward, function, goto, if, implementation, in, inline, interface, interrupt, label, mod, nil, not, object, of, or, packed, procedure, program, record, repeat, set, shl, shr, string, then, to, type, unit, until, uses, var, vertual, while, with, xor и другие.
При написании программы применяются:
константы - данные, значения которых не изменяются в программе;
переменные - данные, могущие изменяться при выполнении программы;
выражения - константы, переменные и обращения к функциям, соединенные знаками операций;
операторы - специальные символы и слова, выполняющие действия;
функции, процедуры и модули - отдельные программные блоки, имеющие имена и подключаемые к основной программе.
Для обозначения имен констант, переменных, функций, процедур и модулей используются буквы и цифры, входящие в алфавит языка, и знак подчеркивания "_". Имена начинаются с буквы или знака подчеркивания "_" и содержат до 63 значащих символов. Символ пробела в имени не допускается. Эти имена принято называть идентификаторами. Различие прописных и строчных букв в идентификаторах компилятором Турбо-Паскаля не учитывается.
Идентификаторы отделяются друг от друга пробелами и специальными знаками. Примеры записи идентификаторов: Alfa, C, X_max, Y_min, Sin, Cos, _10_A
К@ро: линейный - самый простой. Выполняет задачи в одно действие или несколько простых последовательных действий.
21:46:14
К@ро: разветвляющийся - имеет условие. Условные операторы: if-do-else или упрощённый вариант if-do. Также оператор while-do
21:47:38
К@ро: цикличный - выполняет действие пока действительно (или недействительно) условие. Операторы: for-to-do
Заголовок программы содержит ключевое слово PROGRAM, за которым следует имя программы. Имя программы должно отражать главную функцию программы и не м.б. использовано внутри программы. В ТР заголовок игнорируется компилятором и является декоративной частью программы. Программу можно писать строчными или прописными буквами либо используя их комбинацию.
Блок (тело) программы содержит разделы описаний (декларативная часть) и раздел операторов (исполняемую часть).
Раздел описаний может включать:
раздел описания меток;
раздел описания констант;
раздел описания типов;
раздел описания переменных;
раздел описания процедур;
раздел описания функций.
Стандарт языка Паскаль регламентирует вышеперечисленный прядок следования разделов описаний, в Турбо Паскале порядок следования разделов и число одинаковых разделов не их количество регламентировано. Исходя из соображений хорошего стиля программирования, целесообразно соблюдать требования стандарта
Описание констант позволяет использовать имена как синонимы констант, их необходимо определить в разделе описания констант:
const K= 1024; MAX= 16384;
В разделе описания переменных необходимо указать все переменные, используемые в программе, и определить их тип:
var P,Q,R: Integer;
A,B: Char;
F1,F2: Boolean;
Описание типов, процедур и функций будет рассмотрено ниже. Отдельные разделы описаний могут отсутствовать, но следует помнить, что в Паскаль - программе должны быть обязательно описаны все компоненты программы.
Раздел операторов представляет собой составной оператор, который содержит между служебными словами
begin.......end
последовательность операторов. Операторы отделяются друг от друга символом;. Текст программы заканчивается символом точка.
Кроме описаний и операторов Паскаль - программа может содержать комментарии, которые представляют собой произвольную последовательность символов, расположенную между открывающей скобкой комментариев { и закрывающей скобкой комментариев }.
Пример 1
program Primer; {вычисление суммы двух чисел}
var
x,y,s: integer;
begin
WriteLn('Введите через пробел два числа ');
ReadLn(x,y);
s:= x + y;
WriteLn('Сумма чисел равна ',s);
end.
Данная программа запрашивает с клавиатуры два числа, находит их сумму и выводит ответ. Теперь сделаем так, чтобы программа сначала очищала экран, выполняла свои действия, а в конце работы позволяла пользователю посмотреть результат, ожидая его нажатия клавиши.
Пример 2
program Primer; {вычисление суммы двух чисел}
uses Crt; {подключение модуля, необходимого для процедур
очистки экрана и задержки}
var
x,y,s: integer;
begin
ClrScr; {очистка экрана}
WriteLn('Введите через пробел два числа ');
ReadLn(x,y);
s:= x + y;
WriteLn('Сумма чисел равна ',s);
ReadKey; {ожидание нажатия клавиши}
end.
Подробности..
Текст Паскаль - программы может содержать ключи компиляции, которые позволяют управлять режимом компиляции. Синтаксически ключи компиляции записываются как комментарии. Ключ компиляции содержит символ $ и букву-ключ с последующим знаком + (включить режим) или - (выключить режим). Например:
{$E+} - эмулировать математический сопроцессор;
{$F+} - формировать дальний тип вызова процедур и функций;
{$N+} - использовать математический сопроцессор;
{$R+} - проверять выход за границы диапазонов.
Некоторые ключи компиляции могут содержать параметр, например:
{$I имя файла} - включить в текст компилируемой программы названный файл.
Выражения
Выражение задает правило вычисления некоторого значения. Выражение состоит из констант, переменных, указателей функций, знаков операций и скобок.
Математические операции
В таблице приведены основные математические операции Турбо Паскаль.
| Символ операции | Название операции | Пример |
| * | умножение | 2*3 (результат: 6) |
| / | деление | 30/2 (результат: 1.5E+01) |
| + | сложение | 2+3 (результат: 5) |
| - | вычитание | 5-3 (результат: 2) |
| div | целочисленное деление | 5 div 2 (результат: 2) |
| mod | остаток от деления | 5 mod 2 (результат: 1) |
Логические операции
Над логическими аргументами в Турбо Паскаль определены следующие операции:
NOT - логическое отрицание ("НЕ")
AND - логическое умножение ("И")
OR - логическое сложение ("ИЛИ")
XOR - логическое "Исключающее ИЛИ"
Результаты выполнения этих операций над переменными А и В логического типа приведены в таблице истинности.
| A | B | not A | A and B | A or B | A xor B |
| true | true | false | true | true | false |
| true | false | false | true | true | |
| false | true | true | false | true | true |
| false | false | false | false | false |
Операции отношения
К операциям отношения в Турбо Паскаль относятся такие операции, как:
> - больше
< - меньше
= - равно
<> - не равно
>= - больше или равно
<= - меньше или равно
В операциях отношения могут принимать участие не только числа, но и символы, строки, множества и указатели.
Приоритет операций
Порядок вычисления выражения определяется старшинством (приоритетом) содержащихся в нем операций. В языке Паскаль принят следующий приоритет операций:
унарная операция not, унарный минус -, взятие адреса @
операции типа умножения: * / div mod and
операции типа сложения: + - or xor
операции отношения: = <> < > <= >= in
Порядок выполнения операций переопределить можно с помощью скобок. Например 2*5+10 равно 20, но 2*(5+10) равно 30.
Основные математические функции
В этом разделе приведены основные математические функции, встроенные в системную библиотеку Турбо Паскаль.
Abs(X)
Возвращает абсолютное значение числа X.
Cos(X), Sin(X)
Возвращает косинус (синус) числа X, где X - угол в радианах.
Функций тангенс и котангенс в Турбо Паскале нет. Для их вычисления используйте выражение sin(x)/cos(x) (или cos(x)/sin(x) для котангенса).
ArcTan(X)
Возвращает арктангенc числа X.
Exp(X)
Возвращает число, равное e в степени X.
Ln(x)
Возвращает число, равное натуральному логарифму от числа X.
Pi
Число Пи.
Sqr(X)
Возвращает число, равное квадрату числа X.
Функции возведения в произвольную степень в Турбо Паскале нет. Используйте многократное умножение для возведения в целочисленную степень, либо функции Exp и Ln для возведения в вещественную степень.
Sqrt(X)
Возвращает число, равное квадратному корню из числа X.
Trunc(X)
Возвращает число, равное целой части числа X. (Происходит отбрасывание дробной части числа X. Результат выполнения имеет тип Longint).
Frac(X)
Возвращает число, равное дробной части числа X.
Int(X)
Возвращает число, равное целой части числа X. Результат выполнения функции - real.
Round(X)
Функция округляет число X. Возвращаемое значение имеет тип Longint.
Random(X)
Возвращает случайное целое число в диапазоне 0..X. Если аргумент опущен (Random), то возвращается случайное вещественное число от 0 до 1.
Перед использованием random в программах рекомендуется сначала инициализировать генератор псевдослучайных чисел процедурой Randomize. В противном случае при каждом запуске программы будет генерироваться одна и та же последовательность случайных чисел.
Пример. Вывод на экран 5 случайных чисел в диапазоне -10..10.
var i: integer;
begin
randomize;
for i:=1 to 5 do writeln(random(21)-10);
end.
Inc(X,Y)
Увеличивает значение числа X на Y. Если число Y не указано, то увеличение происходит на 1.
Dec(X,Y)
Уменьшает значение числа X на Y. Если число Y не указано, то уменьшение происходит на 1.
Дата добавления: 2015-12-08; просмотров: 215 | Нарушение авторских прав