Основы безошибочного программирования

Основной недостаток традиционной практики составления про­грамм для ЭВМ заключается в том, что при таком подходе никто не может гарантировать отсутствие в них ошибок. Особенностью традиционной практики является поиск ошибок в программах при их отладке на ЭВМ.

Однако, так как число ошибок в программах заранее неизвестно, то неизвестна заранее и продолжительность отладки программ на ЭВМ. Более того даже после «завершения» отладки никто не может гарантировать отсутствие ошибок. Естественно, что использование таких программ, приводит к возникновению отказов, сбоев и полу­чению неверных результатов.

Структурный подход снижает количество ошибок в алгоритмах и программах. Однако и при этом подходе число ошибок также зара­нее неизвестно. Хотя структурная форма записи и упрощает поиск и исправление ошибок в текстах программ, гарантии отсутствия ошибок структурный подход не дает.

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

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

Более того, при систематическомиспользовании спецификаций возможен не только анализ правильности алгоритмов и программ, но и становится возможным составление программ с одновремен­ным доказательством правильности.

Безошибочное программирование - это составление алгоритмов и программ с гарантиями отсутствия в них ошибок. А составление алгоритмов и программ с одновременным доказательством правиль­ности называется доказательным программированием. И в том и другом подходе необходимо составление спецификаций.

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

Сценарий «Галерея картинок»

Список картинок:

1. треугольник

2. прямоугольник

3. кольцо

номер = ? <N>

n =1 n = 2 n = 3

В соответствии с этими четырьмя картинками построим три вспо­могательных алгоритма рисования отдельных картинок из «Галереи» и общий алгоритм выбора картинок в соответствии с принятым сценарием:

Алг «Галерея картинок»

нач алг «рисуиок_треугольника»

вывод («Список картинок:») нач

вывод («1. треугольник») линия(150,50)-(100,100)

вывод («2. прямоугольник») линия(150,50)-(200,100)

вывод («3. кольцо») линия(100,100)-(200,100)

запрос («номер=», п) кон

графический_экран

если п = 1 то алг «рисунок_прямоугольника»

рисунок_треугольника нач

инес п = 2 то рамка(50,50)-(150,100)

рисунок_прямоугольника кон

инес п = 3 то

рисунок_кольиа алг «рисунок_кольца»

иначе нач

вывод («нет такого рисунка») окружность( 100,100),20

все окружность(100,100),50

кон кон

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

Данный подход к составлению алгоритмов и программ с исполь­зованием спецификаций - позволяет реализовать основную идею безошибочного программирования - создание алгоритмов и про­грамм,правильных по построению. Такой подход может применяться к составлению алгоритмов и программ для любых современных языков программирования - Паскаль, Си, Ада, Модула, Бейсик и т. д.

Приведем примеры составления сложных алгоритмов и программ с циклами с использованием спецификаций. Первый пример - построение алгоритма и программы изображения на экране картинки «Звездное небо» из n случайных точек:

В приводимом ниже алгоритме для формирования и вывода по­следовательности случайных точек на экране используется цикл со счетчиком и датчик случайных чисел для генерации координат «звезд».

Алгоритм Программа

алг «звездное небо» ' звездное небо

нач сls

запрос(«звезд=», п) input «звезд=», n

графический_экран screen 2,0

от k = 1 до п цикл for k = 1 to n

x: = случайное [0:200] х = rnd*200

у: = случайное [0:200] у = rnd*200

точка (х,у) pset (x,y),3

кцикл next k

кон end

Второй пример - составление с использованием спецификаций алгоритма и программы игры «Угадай-ка». В этой игре ЭВМ «зага­дывает» число от 0 до 100, а человек должен его отгадать, вводя пробные числа с клавиатуры. Для составления алгоритма и програм­мы примем следующий сценарий:

Сценарий«Угадай-ка»

Угадай число от 0 до 100
число = ? < х>	*
мало
много
молодец, умница

Для реализации этого сценария воспользуемся циклом с выхо­дом, в котором задается вопросчисло=? и проверяются числа, вво­димые человеком. Выход из цикла происходит после совпадения ответа с числом, задуманным ЭВМ:

АлгоритмПрограмма

алг «угадай-ка» ' угадай-ка

нач сls

вывод («Угадай число») print «Угадай число»

вывод («от 1 до 100») print «от 1 до 100»

z: = случайное [0:100] z = int (rnd* 100)

цикл do

запрос( «число=», х) input «число=», х

при х = z вых if х = z then exit do

если х < z то if х < z then

вывод («мало») print «мало»

инеc х > z то elseif х > z then

вывод («много») print «много»

все end if

кцикл loop

вывод («молодец, умница») print «молодец, умница»

кон end

Сравнение алгоритма со сценарием показывает их полное соот­ветствие друг другу.

В о п р о с ы

1. Сколько ошибок содержится в программах?

2. Как долго длится отладка программ?

3. Что такое спецификации программ?

4. Зачем нужны спецификации?

5. Можно ли гарантировать отсутствие ошибок в программах?

6. Что такое систематический подход к алгоритмизации?

З а д а ч и

1. Составьте сценарий и алгоритм диалога «Распорядок дня», с по­мощью которого можно узнать, что запланировано на заданный час дня.

2. Составьте сценарий и алгоритм диалога с выбором по меню;

а) национальных флагов;

б) каталога строительных блоков;

в) набора рисунков;

г) каталога строений.

3. Предложите сценарии и алгоритмы рисования на экране абстракт­ных рисунков:

а) из случайных разноцветных точек;

б) из случайных разноцветных отрезков;

в) из случайных разноцветных рамок;

г) из случайных разноцветных окружностей;

д) из случайных разноцветных кругов;

е) из случайных разноцветных окошек.

4. Составьте сценарий и алгоритм, моделирующий на экране бро­уновское движение частиц.

Средства обработки данных

Автоматизированная обработка данных - одна из основных массовых проблем, решаемых с помощью ЭВМ. На персональных компьютерах IBM PC базовым средством обработки данных является язык программирования Basic. В операционной системе Windows это язык считается основным языком разработки программ для компьютеров IBM PC.

Основной особенностью языков структурного и графического программирования Бейсика как языка обработки данных являются операторы данных data, позволяющие описывать данные непосредст­венно в текстах программ. Пример и реализация алгоритма обработки данных:

алг «день рождения» ' день рождения

нач cls

вывод («день рождения») print «день рождения:»

чтение пт$, dn, ms, gd read nm$, dn, ins, gd

вывод nm$; dn; ms; gd print nm$; dn; ms; gd

кон end

дано: Саша, 18, 10, 1980 data «Саша», 18,10,1980

Выполнение программы на компьютере приведет к появлению на экране следующих строк:

день рождения:

Саша 18 10 1980

Для решения этой задачи для других данных необходимо внести изменения в оператор данных dataи вновь запустить программу на выполнение. Пример изменения данных:

дано: Оля, 1, 12, 1974 data «Оля», 1,12,1974

В традиционных версиях языка Бейсик с нумерацией строк опе­раторы dataвыделяются в отдельные группы и нумеруются обычно с числа 1000. Это позволяет четко отделить в программах описание данных от операторов их обработки:

алг «дни рождения» 10 ' дни рождения

нач 20 cls

вывод («день рождения:») 30 print «день рождения:»

чтение nт$, dn, ms, gd 40 read nm$, dn, ms, gd

вывод nm$; dn; ms; gd 50 print nm$; dn; ms; gd

кон 60 end

дано: Иванов, Саша, 18,10,1980 1000 data «Саша», 18,10,1980

При размещении нескольких таблиц или других групп данных в программах на Бейсике полезным средством являются операторы restore (операторы чтения данных с заданного номера или метки):

1) оператор чтения данных после метки test:

restore test - чтение данных после метки test;

2) оператор чтения данных с оператора 1000:

restore 1000 - чтение данных, начиная с 1000-го оператора;

3) оператор чтения данных с самого начала:

restore- чтение данных сначала.

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

Символьные данные - это последовательности символов. В текстах программ на Бейсике символьные данные заключаются в двойные кавычки. Примеры: «мама», «корень=», «2 + 1» и т.д. Во входных данных символьные данные записываются в соответствии с входными спецификациями.

Символьные переменные - это переменные, значениями которых являются символьные данные. В программах на Бейсике символь­ными явлются те переменные, к имени которых справа приписан знак $. Примеры символьных переменных: s$, p$, sl$, pr$.

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

n%, m%, nl%, m3% - целочисленные

х, у, xl, y5 - вещественные

а#, b#, al#, b8# - вещественные двойной точности

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

Дни рождения:

Мама
Папа
Сережа
Оля

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

Дни рождения:

Мама
Папа
Сережа
Оля

Dni: ' дни рождения

Data «мама», 26, 6, 1949

Data «папа», 22,5, 1946

Data «Сережа», 25, 10, 1973

Data «Оля», 1, 12, 1974

Data «», 0, 0, 0

Обратите внимание!

1. Каждый операторdata здесь отвечает одной строке таблицы.

2. Последний операторdata содержит пустую «запись» - пустое имя «» и три нуля, означающие конец данных.

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

Рассмотрим алгоритм и программу вывода списка дней рождения в семье, составленные в соответствии с выбранным представлением данных:

алг «дни рождения» ' дни рождения

нач сls

вывод («дни рождения») print «дни рождения»

чтение таблицы dni restore dni

цикл do

чтение (пп, d, т, g) read nn$, d, m, g

при пп = «» вых if nn$ = «» exit then do

вывод (пп, d, m, g) print nn$, d, m, g

кцикл loop

кон end

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

Использование массивов в программах на Бейсике требует опи­сания их с помощьюоператоров dim. В операторахdim для каждого массива указывается его имя и размеры. Массивы в программах могут быть одномерными, двумерными, трехмерными и т. д.

Примеры описаний массивов:

одномерные массивы из 20 элементов -

dim nm$(20), d(20), m(20)

двумерные массивы из 2х10 и 10х10 элементов –

dim fm$(2,10), tb(10,10)

Обращения к элементам массивов записываются в зависимости от размерности, указанной в их описаниях. Примеры обращений к одномерным и двумерным массивам:

nm$(4) = «Костя»

d(4) = 10

fm$(l,10) = «Петров»

tb(3,4) = 3*4

В программах на Бейсике операторыdim являются выполняемы­ми. Результатом их выполнения является выделение участков памя­ти для хранения соответствующих массивов. По этой причине в ка­честве размеров массивов могут указываться переменные, которые должны получить конкретные положительные значения до выпол­нения оператораdim.

Описание двумерного массива с переменной n в качестве его раз­меров:

n = 5 ' n = 5

dim tb(n,n) , ' массив tb[1:n, 1:n]

В качестве примера использования массивов с переменными раз­мерами приведем алгоритм и программу формирования «Таблицы умножения n´n».

Таблица умножения

1 2 3 4 5

2 4 6 8 10

3 6 9 12 15

4 8 12 16 20

5 10 15 20 25

В приведенных ниже алгоритме и программе расчета и вывода таблицы умножения для ее размещения используется двумерный массив tb(n, n) c n = 5:

алг «таблица умножения» ' таблица умножения

п=5 n=5

массив tb[1:n, 1:n] dim tb(n,n)

нач сls

от k = 1 до п цикл for k = 1 to n

от 1 = 1 до п цикл for l = 1 to п

tb[k,l]: = k*l tb(k,l) = k*l

вывод tb[k,l] print tb(k,l);

кцикл next 1

нов_строка print

кцикл next k

кон end

Запуск этой программы на ЭВМ приведет к получению приве­денной выше картинки с таблицей умножения размера 5х5. Для получения таблицы умножения размера 8х8 или 10 х 10 достаточно изменить в программе значение n =5 на n = 8 или n = 10.

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

По способу использования при решении задач различаются сле­дующие данные:

исходные;

результирующие.

Исходные данные - конкретные данные решаемых задач, отвеча­ющие принятой постановке. Исходные данные могут оказаться как допустимыми, так и недопустимыми по постановке решаемых задач.

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

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

· входные;

· выходные;

· сохраняемые.

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

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

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

В качестве примера рассмотрим задачу поиска номеров телефо­нов по телефонному справочнику. Исходной информацией в этой задаче является «Телефонный справочник», который можно пред­ставить следующей таблицей:

Телефонный справочник

Вова	125-14-70
Саша	222-01-02
Маша	102-99-00

Результирующая информация - номера телефонов и сообщения об отсутствии таких сведений. Информация о результатах поиска информации может выводиться на экран ЭВМ. Диалог с компьюте­ром может проходить по следующему сценарию, в котором отража­ются исходные и выходные данные:

Сценарий:

поиск номера телефона имя = ? <имя>

телефон: <номер>

нет такого

Для хранения таблицы «Телефонного справочника» в программе можно воспользоваться следующими операторами data:

tel: 'номера телефонов:

Data «Вова», «125-14-80»

Data «Саша», «222-01 -02»

Data «Маша», «102-99-00»

Data «», «»

При выбранных представлении данных и сценарии диалога решением могут служить следующие алгоритм и программа:

АлгоритмПрограмма

алг «Телефонный справочник» ' Телефонный справочник

нач сls

вывод («поиск номера телефона») print «поиск номера телефона»

запрос(«имя=», NN) input «имя=», NN$

чтение-таблицы tel restore tel

цикл do

чтение (имя, пот) read im$, nm$

если имя = NN то if im$ = NN$ then

вывод («номер:»,пот) print «номер:»,nm$

выход [из цикла] exit do

инес имя = «» то elseif im$ = «» then

вывод («нет такого») print «нет такого»

выход [из цикла] exit do

все end if

кцикл loop

кон end

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

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

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

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

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

фамилия	имя	рост
Иванов	Саша
Петров	Вова
Сидоров	Миша

Примем, что запросы на поиск друзей по росту и результаты по­иска будут выводиться на экран по следующему сценарию:

Сценарий «Поиск друзей»

выбор друзей по росту мин_рост = ? <min> макс_рост = ? <max>

<фамилия> <имя>

нет таких

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

Dan: 'данные о друзьях

Data «Иванов», «Саша», 180

Data «Петров», «Вова», 160

Data «Сидоров», «Миша», 190

Data «», «», 0

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

АлгоритмПрограмма

алг «выбор друзей» ' выбор друзей

нач сls

вывод («выбор друзей по росту») print «выбор друзей по росту»

запрос («мин_рост =>», min) input «мин_рост =>», mn

запрос («макс_рост =<», тах) input «макс_рост =<», mх

чтение-таблицы dan restore dan

n: = 0 n = 0

цикл do

чтение (фам, имя, r) read fm$,im$,r

при фам = «» вых if fm$ = «» then exit do

если min £ r и r £ max то if mn<= r and r <= mx then

вывод (фам, имя) print fm$, im$

n: = n+1 n = n+1

все end if

кцикл loop

если n = 0 то if n = 0 then

вывод «нет таких» print «нет таких»

кон end

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

В о п р о с ы

1. Что такое исходные и результирующие данные?

2. Что такое входные, выходные и сохраняемые данные?

3. Что такое представление данных?

4. Как описываются массивы в программах на Бейсике?

5. Какие типы переменных есть в программах на Бейсике?

6. Как описываются данные в программах на Бейсике?

А д а ч и

1. Составьте сценарий, алгоритм и программу поиска номера теле­фона по фамилии с представлением сведений в последовательности операторов data.

2. Составьте сценарий, алгоритм и программу поиска по имени дней рождения родных: мамы, папы, сестер и братьев, используя операторы data.

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

а) о росте друзей;

б) о весе друзей;

в) о цвете глаз.

4. Составьте сценарий, алгоритм и программу поиска сведений о расписании занятий по дням недели, используя операторы data.

5. Составьте сценарий, алгоритм и программу поиска сведений о расписании занятий, используя операторы data:

а) по названию предмета;

б) по дням недели;

в) по номеру урока.

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

7. Составьте алгоритм и программу вывода изображений ткани из цветных кругов по данным об их центрах и радиусах, записанных в последовательности операторов data.