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

 

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

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

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

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

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

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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

инес п = 3 то

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

иначе нач

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

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

кон кон

 

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

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

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

 

 

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

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

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

нач cls

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

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

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

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

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

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

кцикл next k

кон end

 

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

 

 

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

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

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

нач cls

вывод («Угадай число») 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, позволяющие описывать данные непосредственно в текстах программ. Пример и реализация алгоритма обработки данных:

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

нач сls

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

чтение пт$, dn, ms, gd read nm$, dn, ms, 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 сls

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

чтение пт$, 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#, a1#, 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, а добавление или удаление строк в таблице отображается добавлением или удалением соответствующих операторов в программе.

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

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

нач cls

вывод («дни рождения») 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 в качестве его размеров:

п = 5 ' n = 5

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

 

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

 

 

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

 

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

п = 5 n = 5

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

нач сls

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

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

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

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

кцикл next l

нов_строка print

кцикл next k

кон end

 

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

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

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

исходные;

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

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

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

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

• входные;

• выходные;

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

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

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

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

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

 

 

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

 

 

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

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

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

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

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

Data «», «»

 

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

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

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

нач cls

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

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

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

цикл do

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

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

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

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

инеc имя = «» то elseif ini$ = «» then

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

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

все end if

кцикл loop

кон end

 

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

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

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

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

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

 

 

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

 

 

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

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

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

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

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

Data «», «», 0

 

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

 

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

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

нач cls

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

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

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

чтение-таблицы 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.