Программирование (кодирование) или программная реализация алгоритмов
Словесную или графическую запись алгоритма обычно нельзя сразу ввести в ЭВМ, поэтому необходимо записать алгоритм на каком-либо языке программирования (ЯП). В результате получается программа на ЯП, которая вводится на ЭВМ и поступает на обработку в системную программу – транслятор (переводчик). Транслятор проверяет программу и выдаёт пользователю сообщение об ошибках. Если в программе ошибок нет, то транслятор переводит программу с ЯП на внутренний машинный язык ЭВМ. В результате получается машинная программа, которая управляет работой ЭВМ в процессе решения прикладной задачи. Переход от алгоритма к программе на ЯП называется кодированием алгоритма. Для каждого алгоритма можно построить несколько вариантов программы, поэтому при кодировании алгоритма нужно оптимизировать программу по лёгкости понимания, быстродействию и объёму памяти. Языки программирования можно разделить на 2 большие группы: алгоритмические и машинно-ориентированные.
Алгоритмический язык (АЯ) – это специальный искусственный язык, с помощью которого можно достаточно просто и удобно записать любой алгоритм. В настоящее время существуют сотни алгоритмических языков, например, наиболее известны следующие языки программирования: Фортран – язык для научно-технических расчётов; ПЛ/1, Кобол – языки для экономических расчётов; Бейсик – язык начального обучения; Паскаль – универсальный язык для обучения и программирования; Си – язык прикладного и системного программирования; Модула-2 и Ада – универсальные языки программирования; Лисп, Пролог – языки функционального и логического программирования; С++, Java, Object Pascal – языки объектно-ориентированного программирования. Часто вместо термина алгоритмический язык используется термин – язык программирования высокого уровня.
С технической точки зрения процесс кодирования алгоритма заключается в записи основных алгоритмических конструкций на языке программирования. Очень просто это можно представить в виде таблицы (табл.3), в которой сводятся основные алгоритмические конструкции и соответствующие им конструкции языка программирования.
Таблица 3.
Правила кодирования алгоритмов
| № | Язык Си | Язык Паскаль | ||
| Блок начало | ||||
| main() { | PROGRAM Name; BEGIN | |||
| Блок конец | ||||
| } | END. | |||
| Операция присваивания: переменой x присвоить значение Z: x←Z | ||||
| x = Z ; | x := Z; | |||
| Разделение команд (операторов). Символ разделитель | ||||
| ; | ; | |||
| Ввод данных | ||||
| scanf ( &перем1, &перем2,…) [1]; | READ ( перем1, перем2,…); или READLN ( перем1, перем2,…); | |||
| Вывод данных | ||||
| printf ( перем1, перем2,…) 1; | WRITE ( перем1, перем2,…); или WRITELN ( перем1, перем2,…); | |||
| Условие с двумя вариантами действий | ||||
| if (Условие) { A;} else {B;} | IF (Условие) THEN BEGIN A; END ELSE BEGIN B; END; | |||
| Условие с одним вариантом действий | ||||
| if (Условие) { A;} | IF (Условие) THEN BEGIN A; END; | |||
| Цикл с предусловием | ||||
| while (Условие) { A; } | WHILE (Условие) DO BEGIN A; END | |||
| Цикл с постусловием | ||||
| do { A; } while (Условие) ; | REPEAT A; UNTIL (Условие ) ; | |||
| Описание данных | ||||
| main() { int i, j,…; // целые данные double x,y,z,…; // вещественные char c,p,…; // символьные char str[50]; // строковые … | PROGRAM FIRST; VAR i, j,… : INTEGER ; {целые данные} x,y,z,…: REAL ; {вещественные } c,p,… : CHAR; {символьные } str : STRING; {строковые} BEGIN … | |||
| Подключение библиотек и модулей | ||||
| //ОБЯЗАТЕЛЬНО! #include <stdio.h> #include <stdlib.h> #include <math.h> main() { … | {В случае необходимости} UNIT имямодуля-библиотеки; PROGRAM Name2; … | |||
| Комментарий | ||||
| // текст в одной строке или /* многострочный текст */ | { текст комментария в одну или несколько строк } или (* текст в одну или несколько строк *) или // текст в одной строке | |||
Машинно-ориентированный язык (МОЯ) – это язык машинных команд, записанных в символическом виде. Для обозначения таких языков применяются термины: язык ассемблера, автокод, мнемокод, язык символического кодирования и т.п. Программирование на машинно-ориентированном языке менее наглядно и более трудоёмко, чем программирование на АЯ. Однако в процессе работы с машинно-ориентированным языком можно учесть все особенности системы команд конкретной ЭВМ. Программа, составленная хорошим программистом на машинно-ориентированном языке, имеет лучшие характеристики по быстродействию и памяти, чем программа, полученная после трансляции с АЯ. Поэтому МОЯ применяются либо в системном, либо в высокоэффективном прикладном программировании.
Пример 5. Используя таблицу, закодируем на языках Си и Паскаль (рис.8) структурные алгоритмы решения задачи табулирования функции на основе цикла с постусловием (на языке Си) и цикла с предусловием (на языке Паскаль).
| #include <stdio.h> #include <stdlib.h> #include <math.h> main() { double a,b,h,x,f ; scanf (&a, &b, &h); x = a; do { f = sin(x*x) - x; printf(x, f); x = x+h; } while ( x>b ); } | PROGRAM TABUL1; VAR a,b,h,x,f: REAL; BEGIN READLN (a, b, h); x := A; WHILE ( x<= B ) DO BEGIN f:=sin(x*x) - x; WRITELN(x, f); x:=x+h; END END. |
Рис.8. Реализация алгоритмов на языке Си и Паскаль
Примечание. На языке Си функции ввода-вывода scanf и printf имеют более сложный синтаксис, поэтому полученная в примере программа требует небольшой доработки. Программа на языке Паскаль получилась полностью работоспособной.
Тестирование и отладка
Тестирование – процесс поиска ошибок работы программы, посредством проверки правильности результатов ее функционирования на наборах данных, характерных для рабочего состояния программы. Как правило, при тестировании известны исходные данные и правильный результат, который должна выдавать программа. Такие данные часто называются тестовыми последовательностями или просто тестами. Цель тестирования – подготовить как можно больше тестовых последовательностей и проверить работоспособность программы на них.
Отладка – точное определение местоположения ошибок в программе, причин и условий их возникновения, с целью последующего их устранения.
Трассировка (раскрутка) алгоритма – это процесс пошагового выполнения алгоритма с записью в таблицу значений переменных, значений условий, номеров последующего шага (блока) для выполнения и комментариев по выполнению. Трассировка позволяет в ручном режиме, на бумаге проверить работу алгоритма и при необходимости найти ошибки. Фактически трассировка в таком виде заменяет стандартного исполнителя алгоритма – ЭВМ на исполнителя-человека. Важно, чтобы исполнитель действовал исключительно по инструкциям алгоритма, а не «фантазировал», что-то придумывал или изменял по ходу выполнения алгоритма.
Пример 6.Проведем трассировку структурного алгоритма на основе цикла с постусловием, приведенного в примере 4 (табл.4).
Таблица 4.
Трассировка(раскрутка) алгоритма
| № п/п | № шага | a | b | h | x | f | x>b | Примечание |
| Начало | ||||||||
| 0,2 | Ввели в ячейки данные для a, b, h | |||||||
| Записываем в ячейку x := a=1 | ||||||||
| 3, 3.1 | –0,159 | Начало цикла, вычисляем f:=sin 1 – 1 | ||||||
| 3.2 | На экран выводzтся ячейки x = 1 и f = –0,159 | |||||||
| 3.3 | 1,2 | x := x + h=1+0,2=1,2 | ||||||
| 3.4 | Нет | Проверка условия окончания цикла 1,2>2 | ||||||
| 3.1 | –0.209 | Вычисляем f:=sin (1,2) – 1,2= –0,209 | ||||||
| 3.2 | На экран выводится 1,2 и –0,209 | |||||||
| 3.3 | 1,4 | x := x + h=1,2+0,2=1,4 | ||||||
| 3.4 | Нет | Проверка условия окончания цикла 1,4>2 | ||||||
| 3.1 | –0.475 | Вычисляем f | ||||||
| 3.2 | На экран выводится 1,4 и –0,475 | |||||||
| 3.3 | 1,6 | x := x + h=1,4+0,2=1,6 | ||||||
| 3.4 | Нет | Проверка условия окончания цикла 1,6>2 | ||||||
| 3.1 | –1.051 | Вычисляем f | ||||||
| 3.2 | На экран выводится 1,6 и –1,051 | |||||||
| 3.3 | 1,8 | x := x + h=1,6+0,2=1,8 | ||||||
| 3.4 | Нет | Проверка условия окончания цикла 1,8>2 | ||||||
| 3.1 | –1.898 | Вычисляем f | ||||||
| 3.2 | На экран выводится 1,8 и –1,898 | |||||||
| 3.3 | 2,0 | x := x + h=1,8+0,2=2,0 | ||||||
| 3.4 | Нет | Проверка условия окончания цикла 2,0>2 | ||||||
| 3.1 | –2.757 | Вычисляем f | ||||||
| 3.2 | На экран выводится 2,0 и –2,757 | |||||||
| 3.3 | 2,2 | x := x + h=2,0+0,2=2,2 | ||||||
| 3.4 | Да | Проверка условия окончания цикла 2.2>2 | ||||||
| Конец цикла, Конец работы алгоритма |
Верификация – доказательство правильности программы. Проблема верификации программ все еще является открытой, и в настоящее время существуют методы, позволяющие доказывать правильность лишь небольших и однотипных алгоритмов. Для сложных и больших алгоритмов методов верификации, к сожалению, пока не придумано. Более того, существует такая аксиома: любая сложная программа содержит хотя бы одну ошибку. Такое утверждение основывается на том факте, что в любой сложной программе с наличием циклов и ветвлений существует бесконечное (или очень большое) количество путей, и проверить работоспособность каждого пути, как правило, не представляется возможным, а значит вероятность того, что на одном из таких путей возникнет ошибка, достаточно велика. Фактически большинство методов верификации программ пытаются строго математически обойти все пути алгоритма и доказать, что ни на одном из них нет ошибок. При отладке программы, программист делает то же самое, – он пытается пройти все возможные пути и проверить на них работоспособность программы, но только не теоретическими методами, а практическим способом, выбирая различные тестовые последовательности, что бы охватить как можно большее количество путей в программе. Ошибки возникают именно на том пути, где программист не проверил работоспособность алгоритма.
Поэтому, для более тщательного тестирования и отладки программы, план проведения испытаний работы программы должен быть составлен заранее и тестовые данные должны подбираться для проверки функций программы, а не разработанных алгоритмов. Т.е. тестовые примеры создаются на этапе проектирования программной системы, а не на этапе кодирования.
Можно выделить следующие виды тестирования:
· автономное (тестирование модулей программистами);
· комплексное (тестирование общих функций системы программистами);
· системное (оценочное) – тестирование, как правило, с участием заказчика.