Программирование (кодирование) или программная реализация алгоритмов

Словесную или графическую запись алгоритма обычно нельзя сразу ввести в ЭВМ, поэтому необходимо записать алгоритм на каком-либо языке программирования (ЯП). В результате получается программа на ЯП, которая вводится на ЭВМ и поступает на обработку в системную программу – транслятор (переводчик). Транслятор проверяет программу и выдаёт пользователю сообщение об ошибках.

Если в программе ошибок нет, то транслятор переводит программу с ЯП на внутренний машинный язык ЭВМ. В результате получается машинная программа, которая управляет работой ЭВМ в процессе решения прикладной задачи. Переход от алгоритма к программе на ЯП называется кодированием алгоритма. Для каждого алгоритма можно построить несколько вариантов программы, поэтому при кодировании алгоритма нужно оптимизировать программу по лёгкости понимания, быстродействию и объёму памяти.

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

Алгоритмический язык (АЯ) – это специальный искусственный язык, с помощью которого можно достаточно просто и удобно записать любой алгоритм. В настоящее время существуют сотни алгоритмических языков, например, наиболее известны следующие языки программирования: Фортран – язык для научно-технических расчётов; ПЛ/1, Кобол – языки для экономических расчётов; Бейсик – язык начального обучения; Паскаль – универсальный язык для обучения и программирования; Си – язык прикладного и системного программирования; Модула-2 и Ада – универсальные языки программирования; Лисп, Пролог – языки функционального и логического программирования; С++, Java, Object Pascal – языки объектно-ориентированного программирования. Часто вместо термина алгоритмический язык используется термин – язык программирования высокого уровня.

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

Таблица 3.

Правила кодирования алгоритмов

Язык Си Язык Паскаль
Блок начало
main(){ PROGRAM Name;BEGIN
Блок конец
} END.
Операция присваивания: переменой x присвоить значение Z: x
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 BEGINA;ENDELSE BEGINB;END;
Условие с одним вариантом действий
if (Условие){ A;} IF (Условие) THEN BEGINA;END;
Цикл с предусловием
while (Условие){ A; } WHILE (Условие) DO BEGINA;END
Цикл с постусловием
do {A;} while (Условие) ; REPEATA;UNTIL (Условие ) ;
Описание данных
main(){int i, j,…; // целые данныеdouble x,y,z,…; // вещественныеchar c,p,…; // символьныеchar str[50]; // строковые… PROGRAM FIRST;VARi, j,… : INTEGER ; {целые данные}x,y,z,…: REAL ; {вещественные }c,p,… : CHAR; {символьные }str : STRING; {строковые}BEGIN…
Подключение библиотек и модулей
//ОБЯЗАТЕЛЬНО!#include #include #include main(){… {В случае необходимости}UNIT имямодуля-библиотеки;PROGRAM Name2;…
Комментарий
// текст в одной строкеили/* многострочный текст*/ { текст комментария в одну или несколько строк } или(* текст в одну или несколько строк *)или// текст в одной строке

Машинно-ориентированный язык (МОЯ) – это язык машинных команд, записанных в символическом виде. Для обозначения таких языков применяются термины: язык ассемблера, автокод, мнемокод, язык символического кодирования и т.п. Программирование на машинно-ориентированном языке менее наглядно и более трудоёмко, чем программирование на АЯ. Однако в процессе работы с машинно-ориентированным языком можно учесть все особенности системы команд конкретной ЭВМ.

Программа, составленная хорошим программистом на машинно-ориентированном языке, имеет лучшие характеристики по быстродействию и памяти, чем программа, полученная после трансляции с АЯ. Поэтому МОЯ применяются либо в системном, либо в высокоэффективном прикладном программировании.

Пример 5. Используя таблицу, закодируем на языках Си и Паскаль (рис.8) структурные алгоритмы решения задачи табулирования функции на основе цикла с постусловием (на языке Си) и цикла с предусловием (на языке Паскаль).

#include #include #include 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;VARa,b,h,x,f: REAL;BEGINREADLN (a, b, h);x := A;WHILE ( x

Рис.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
Конец цикла, Конец работы алгоритма

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

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

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

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

Можно выделить следующие виды тестирования:

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

Рандомно подобранные статьи с сайта:

Алгоритм Хаффмана C++


Похожие статьи:

admin