программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент

• Название: Учебное пособие Томск Эль Контент
• Анкор: программирование тусур
• Дата: 17.08.2022
• Размер: 0.93 Mb.
• Имя файла: Программирование учебное пособие.pdf
• Тип: Учебное пособие; #647947
• страница: 9 из 16

Глава 4. Технология программирования
Миф о тестировании путей
Выполнение всех путей не гарантирует соответствия программы со специфи- кациями, потому что:
• сделана правильная программа, но для других целей;
• отсутствуют необходимые пути (например, нет контроля входных данных);
• программа чувствительна к данным (например, для проверки на равенство
A, B и C используется соотношение (A+B+C)
/3=A).
В соответствии с проектированием возможно восходящее и нисходящее тести- рование.
10 аксиом тестирования
1. Хорош тот тест, для которого высока вероятность обнаружения ошибки,
а не тот, что демонстрирует правильную работу программы.
2. Одна из самых сложных проблем при тестировании — решить, когда нужно закончить.
3. Невозможно тестировать свою собственную программу.
4. Необходимая часть всякого теста — описание выходных данных или резуль- татов.
5. Избегайте невоспроизводимых тестов, не тестируйте «с лету».
6. Готовьте тесты как для правильных, так и для неправильных входных данных.
7. Детально изучайте результаты каждого теста.
8. По мере того, как число ошибок, обнаруженных в программе, увеличи- вается, растет также и относительная вероятность существования в ней необнаруженных ошибок.
9. Поручайте тестирование самым способным программистам.
10. Никогда не изменяйте программу, чтобы облегчить ее тестирование.
Процесс разработки тестов:
1. Исходя из спецификаций (описания программы как «черного ящика») под- готовьте тест для каждой ситуации допустимых и недопустимых входных данных.
2. Проверьте текст программы, чтобы убедиться, что все условные перехо- ды будут выполнены в каждом направлении. Если необходимо, добавьте соответствующие тесты.
3. Убедитесь по тексту, что тесты охватывают достаточно много возможных путей. Например, каждый цикл должен быть выполнен 0, 1 и максимальное число раз.
4. Проверьте по тексту программы ее чувствительность к отдельным особым значениям входных данных.

4.6 Тестирование и отладка
89
Пример
Набор тестов для программы, решающей квадратное уравнение
ax
2
+ bx + c = 0:
• a
= 0, b = 0, c = 0 (уравнение 0 = 0 не может быть разрешено относительно
x);
• a
= 0, b = 0, c = 10 (уравнение 0 = 10 — тест на ошибочные входные данные);
• a
= 0, b = 5, c = 17 (5 x + 17 = 0 — не квадратное уравнение, может быть деление на 0);
• a
= 6, b = 1, c = −2 («нормальный» тест);
• a
= 3, b = 7, c = 0 («нормальный» тест, один из корней равен 0);
• a
= 3, b = 2, c = 5 (комплексные корни);
• a
= 7, b = 0, c = 0 (может ли извлекаться корень из 0?).
4.6.2 Отладка
Отладка — деятельность, направленная на установление точной природы из- вестной ошибки, а затем на исправление этой ошибки.
Результаты тестирования являются исходными данными для отладки. После- довательность событий:
симптом (ошибки)
→ причина (ошибки) → исправление (ошибки).
Как искать ошибку?
1. Поймите ошибку. Какие данные правильные, какие —
неправильные?
2. Постройте гипотезу о причине ошибки.
3. Проверьте гипотезу (для этого пропустите новый тест).
4. При подтверждении гипотезы следует исправление, а по- том повторите все тесты (не внесли ли Вы новую ошибку —
вероятность этого от 0.2 до 0.5).
Наилучший способ отладки — просто читать программу и изо всех сил стараться вникнуть в алгоритм, хотя это и требует усердия и собранности.

90
Глава 4. Технология программирования
Можно пользоваться автоматизированными средствами отладки: в интегриро- ванной среде Паскаля имеется отладчик debug, который предлагает средства отсле- живания и трассировки программы (в том числе, печать переменных, счетчиков,
критических значений). Эффективность отладчика новичками часто переоценивается.
Парадоксы программной ошибки:
• ошибка — не всегда результат недостатков;
• ошибка не всегда может быть выявлена;
• выявленная ошибка не всегда может быть описана;
• описанная ошибка не всегда может быть понята;
• понятая ошибка не всегда может быть исправлена;
• исправленная ошибка не всегда может улучшить качество программы.
Известна некоторая статистика о программных ошибках.
• Язык C++ дает на 25% больше ошибок, чем традиционные Си или Паскаль.
• Исправление ошибок в объектно-ориентированных программах на C++ тре- бует в 2–3 раза большего времени. Наследование порождает в 6 раз больше ошибок, чем без него.
• 33% всех ошибок случается реже, чем 1 раз за 5000 лет работы системы.
• Каждый Кбайт кода содержит 0.5–2 ошибки.
Контрольные вопросы по главе 4 1. Почему оператор перехода является лишним оператором в языке высокого уровня?
2. Почему блок-схемы имеют ограниченное применение при разработке про- грамм?
3. Почему программист должен придерживаться хорошего стиля программи- рования?
4. Какие преимущества у нисходящего проектирования перед восходящим?
5. Выскажите свое мнение о том, когда следует прекратить тестирование про- граммы. Обоснуйте его.

Рекомендуемая литература к главе 4
91
Рекомендуемая литература к главе 4
[1]
Йодан Э. Структурное программирование и конструирование программ.
М. : Мир, 1979.
[2]
Майерс Г. Надежность программного обеспечения — М. : Мир, 1980. —
360 с.
[3]
Майерс Г. Искусство тестирования программ. М. : Финансы и статистика,
1982.
[4]
Bohm, Corrado; and Giuseppe Jacopini. Flow Diagrams, Turing Machines and
Languages with Only Two Formation Rules. // Communications of the ACM 9
(5): 366–371.
[5]
Dijkstra, Edsger. «Go To Statement Considered Harmful». // Communications
of the ACM 11 (3): 147–148.

Глава 5
МАССИВЫ И СТРОКИ
5.1 Регулярные типы данных (массивы)
Рассмотренные простые типы определяют различные множества атомарных
(неразделимых) значений. Составные типы задают множества «сложных» значе- ний; каждое значение из такого множества образует некоторую структуру (сово- купность) нескольких значений другого типа.
5.1.1 Определение регулярного типа
Мы вводим вычислительную структуру, использующую абстрактное понятие
«конечная последовательность».
Каждое значение регулярного типа (массива) состоит из фик-
сированного числа элементов одного и того же базового типа
(т. е. значение содержит фиксированное число однотипных ком-
понент).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Способ образования позволяет обозначать значения этих типов одним груп- повым именем, а доступ к отдельным элементам массивов посредством указания этого группового имени и порядкового номера (индекса) необходимого элемента.
Для корректного определения регулярного типа необходимо задать две харак- теристики:
• тип элементов массива,
• количество и «способ нумерации» элементов.
Программист сам должен определить тип массива в разделе type.
type
<тип массива> = array[<тип индекса>] of <тип элементов>;

5.1 Регулярные типы данных (массивы)
93
Типом индекса может быть ограниченный тип, символьный тип, перечислимый тип (о нем речь пойдет дальше). Тип элементов массива может быть любой.
Пример const n=20;
type vector = array[
−100..100] of real;
masChar = array[char] of boolean;
matrix=array[1..n] of array[1..n] of integer;
var v: vector;
SymTab: masChar;
arr1,arr2: matrix;
s: array[
'a'..'z'] of boolean;
Значением переменной v будет массив из 201 вещественного числа, элементы массива нумеруются целыми числами от
−100 до 100.
Значением переменной masChar будет массив из 256 булевских значений,
и элементы массива нумеруются символами с кодами ASCII от 0 до 255.
Значениями переменных arr1, arr2 будут массивы из 20 элементов с нумера- цией целыми числами от 1 до 20. Элементы в данном случае будут снова массивами,
состоящими из 20 целых чисел, пронумерованными также целыми числами от 1
до 20.
Переменная s принадлежит типу массив, но для этого типа не введено имя.
Этот массив состоит из 26 булевских значений, которые нумеруются строчными буквами латинского алфавита.
Мы можем «нумеровать» элементы массива не только целыми числами, но и значениями произвольного дискретного типа (типа, на котором действуют функ- ции ord, succ, pred).
В том случае, когда определен тип массива, элементами которого являются сно- ва массивы, можно использовать эквивалентное определение двухмерного массива.
Следующие два определения эквивалентны:
v:array[1..10] of array[1..20] of integer;
v:array[1..10,1..20] of integer;
В этом примере размерность массива (число индексов) не ограничена. В общем случае количество индексов может быть любое.
Синтаксис:
<регулярный тип> ::= array[<тип индекса> {,<тип индекса}] of <тип>
Единственное возможное действие над массивом в целом — это присваивание
(слева и справа должны быть переменные одного типа):
arr1:= arr2;
Доступ к элементам массива осуществляется следующим образом:
<идентификатор массива>[<индекс>]
или

94
Глава 5. Массивы и строки
<идентификатор массива>[<список индексов через запятую>]
В качестве индексов выступают произвольные выражения, тип которых должен совпадать с типом индекса.
Пример v[1]
v[(i+2)*6]
Пример
Пусть v2:array[1..10] of array[5..20] of integer
— двухмерный массив, тогда v2[k] — k-ый массив в группе из 10 массивов целых чисел, v2[k][5] — 5-ый элемент этого массива, этот же элемент получаем и так v[k,5]
Элемент массива считается переменной:
• он может получать значения (например, в операторе присваивания);
• он может участвовать в выражениях там, где может присутствовать пере- менная данного типа.
Ассортимент операций над элементами массива полностью опре- деляется типом этих элементов.
Пример v2[i,j]:=v2[i,j
−1]+1;
SymTab[
'z']:=not SymTab['a'];

5.1 Регулярные типы данных (массивы)
95
Одна из ошибок в работе с массивами вызывается выходом индекса за допустимые пределы var v:array[0..10] of real;i:integer;
Ошибка в следующем операторе присваивания будет обнаружена при трансляции.
v[11]:=0.5;
Но в такой ситуации i:=11; v[i]:=0.5;
ошибка может быть обнаружена только во время исполнения и то,
если осуществляется контроль диапазона (специальная включен- ная опция при трансляции), иначе это может привести к непред- сказуемым последствиям.
Замечание об символьных массивах.
Символьные массивы — одномерные массивы, состоящие из элементов сим- вольного типа, и индекс принадлежит ограниченному целому типу. Для работы с символьными массивами имеются дополнительные средства: изображение кон- кретного значения символьного массива в виде строки.
Пример var s:array[1..26] of char;
s:=
'Пример символьного массива';
Это изображение может использоваться в операторах присваивания, в описа- ниях констант и в процедуре write.
5.1.2 Примеры программ для работы с массивами
Приведем несколько типичных программ, использующих массивы.
Задача 1. Ввести последовательность из n чисел и распечатать ее с конца.
var i:integer;
s:array[1..100] of integer;
begin writeln(
'Введите количество чисел'); readln(n);
writeln(
'Введите ',n,'чисел');
for i:=1 to n do

96
Глава 5. Массивы и строки
read(s[i]); {ввод потоком}
writeln;
writeln(
'Вывод:');
for i:=n downto 1 do write(s[i],
' ')
end.
Задача 2. Вести матрицу построчно.
const n=4; m=5;
var s:array[1..n,1..m] of integer;
i,j:integer;
writeln(
'введите матрицу ',n,' — строк', m,' — столбцов);
for i:=1 to n do begin for j:=1 to m do read(s[i,j]); {Ввод потоком}
writeln end;
Задача 3. Напечатать матрицу построчно.
for i:=1 to n do begin for j:=1 to m do write(s[i,j],
' ');
writeln end;
Задача 4. Вычислить максимальный элемент матрицы и его индексы.
const n=4;m=5;
type matrix=array[1..n,1..m] of real;
var a:matrix;
max:real; in,jm:integer;
i,j:integer;
in:=1;jm:=1;max:=a[1,1];
for i:=1 to n do for j:=1 to m do if a[i,j]>max then begin max:=a[i,j];
in:=i;
jm:=j;
end;
Задача 5. В матрице a изменить порядок строк на противоположный.
const n=4;m=5;
type stroka=array[1..m] of real;
matrix=array[1..n] of stroka;
var a:matrix;

5.1 Регулярные типы данных (массивы)
97
i:1..n;
x:stroka;
for i:=1 to n div 2 do begin x:=a[i];
a[i]:=a[n+1
−i];
a[n+1-i]:=x end;
Задача 6. Коэффициенты многочлена лежат в массиве a: array[0.. n] of integer
(n — натуральное число, степень многочлена). Вычислить значение этого многочле- на в точке x, т. е. найти a
n
x
n
+ . . . + a
1
x + a
0
Решение. (Описываемый алгоритм называется схемой Горнера.)
k:=0; y:=a[n];
{инвариант: 0<=k<=n, y = a[n] x
∧
k+ a[n-1] x
∧
(k
−1)+ . . .+
a[n
−k] x
∧
0}
while k <>n do begin k:=k+1;
y:=y*x+a[n
−k]
end;
Задача 7. Произведение многочленов. Даны три массива a: array[0..k] of integer;
b: array[0..n] of integer;
c: array[0..m] of integer;
В массивах a, b хранятся коэффициенты двух многочленов степеней k и n. По- местить в массив c коэффициенты их произведения. (Числа k, n, m — натуральные,
m = n + k; элемент массива с индексом i содержит коэффициент при степени i.)
Решение. Воспользуемся математическим свойством c
t
= ∑
i
+j=t
a
i
b
j
for i:=0 to m do c[i]:=0;
for i:=0 to k do for j:=0 to n do c[i+j]:=c[i+j]+a[i]*b[j];
Задача 8. Двоичный поиск. Дана последовательность x
1
⩽ x
2
⩽ . . . ⩽ x
n
и число a.
Выяснить, содержится ли a в этой последовательности, т. е. существует ли такое i,
1
⩽ i ⩽ n, что x
i
= a. (Количество действий должно быть порядка log n.)
left:=1; right:=n+1;
{right>left, если a есть вообще, т. е. и среди x[left]..x[right
−1]}
while right
−1eft <> 1 do begin m:=left+(right
−left) div 2;
{left < m < right}
if x[m]<=a then left:=m

98
Глава 5. Массивы и строки
else right:=m;
end;
(Обратите внимание, что и в случае x[m] = a, инвариант не нарушается.) Каждый раз right
− left уменьшается приблизительно вдвое, откуда и вытекает требуемая оценка числа действий.
Замечание: left + (right
− left) div 2 = (right + left) div 2.
5.2 Строковый тип
5.2.1 Определение строкового типа
Строковый тип обобщает понятие символьных массивов, позволяя динамиче- ски менять длину строки.
Строковый тип данных определяет множество символьных це-
почек произвольной длины от нуля символов до заданного их числа.
<описание строкового типа>::=
string
| string[<максимальная длина строки>]
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Максимальная длина строки, если не указана, то подразумевается равной 255,
иначе может быть любое целое от 0 до 255.
Пример type line=string[80];
var myLine:line;
myLineShort:string[10];
Описание
Var St: string[80];
резервирует 81 байт памяти для St. Если учесть, что на каждый символ отводится один байт, возникает естественный вопрос, а откуда взялся еще один байт, 81-й,
а точнее нулевой байт? Дело в том, что после того, как переменной St присвоено какое-то значение, нулевой байт содержит фактическую длину строки St. Длина строки в байтах при этом равна значению кода символа, находящегося в St[0].
Присваивание
St := ‘abcdefgh’;
дает такой результат:
St[0] = Chr(8).

5.2 Строковый тип
99
St[1] = ‘a’.
St[8] = ‘h’.
Фактическая длина строковой переменной St равна Ord(St[0]). Значение
255 для верхнего предела длины строки объясняется тем, что одиночный байт может принимать 256 различных значений, от 0 до 255.
Изображение строки, такое же, как для символьных массивов, может исполь- зоваться:
• в операторах присваивания,
• как фактические параметры,
• в описании констант.
Символьный массив в отличие от строки может быть очень большим!
5.2.2 Строковые операции
Операция конкатенация (сцепление) применяется для соединения (сцепления)
нескольких строк в одну результирующую строку. Эта операция является бинарной ассоциативной операцией и обозначается знаком +. Например, выражение 'Т'+ 'у'+
+ 'р'+ 'бо'+ 'паскаль' дает 'Турбо паскаль'.
Длина результирующей строки не должна превышать 255.
Пример myLine:=
'Короткая строка';
{длина 15}
myLine:=MyLine+
' стала длинее';
{длина 28}
myLine:=
'';
{длина 0}
Операции сравнения =, <>, >, <, >=, <=.
При сравнении строк используется лексикографический порядок:
а) сравнение строк производится с первых символов (слева направо) до пер- вого несовпадающего символа, и та строка считается больше, в которой первый несовпадающий символ больше;
б) если строки имеют различную длину и одна строка полностью входит во вторую, то более короткая строка меньше, чем более длинная.

100
Глава 5. Массивы и строки
Пример
Следующие неравенства истинны:
'abcd'>='abc'
'abcde'>'aacde'>'aacdd'
Элементы строки нумеруются целыми числами, начиная с 1. Элемент строки принадлежит типу char. Доступ к отдельным элементам строки осуществляется с помощью указания индекса в квадратных скобках
<строка>[<выражения типа 1..255>]
Выражения строкового типа — выражения, в которых операндами служат строковые данные:
• строковые константы,
• строковые переменные,
• функции со строковым значением,
• литерные выражения.
Строковые выражения могут использоваться там, где используется строковый тип.
В операторах присваивания, если значение переменной после вы- полнения присваивания превышает по длине максимально до- пустимую величину, то все лишние символы отбрасываются!
(табл. 5.1).
Таблица 5.1 – Присваивание строковым переменным
Описание строки
Присваивание
Значение переменной
a:string[6]
a:=
'группа 1';
'группа'
a:string[8]
a:=
'группа 1';
'группа 1'
a:string[2]
a:=
'группа 1';
'гр'
Стандартная функция Length(<выражение строкового типа>)
Значение функции есть текущая длина строки — фактического параметра.
Пример var myLine:string; i:integer;
for i:=1 to Length(myLine) do myLine[i]:=chr(ord(myline[i])+1);

5.2 Строковый тип
101
Нет полной идентичности между строковыми типами и символь- ными массивами, поэтому возможна ошибка при работе с элемен- тами строки без учета ее текущей длины.
Пример var str:string[26];
i:integer;
begin str:=
'A';
for i:=1 to 26 do str[i]:=chr(ord(
'A')+i
−1);
writeln(str)
end.
Предполагается, что данная программа сформирует строку из 26 букв латинско- го алфавита, но печать writeln(str) дает просто A! Объяснение: присваивание значений элементам строки не влияет на ее текущую длину (здесь текущая дли- на = 1).
Правильная программа:
var str:string[26];
i:integer;
begin str:=
'';
for i:=1 to 26 do str:=str+chr(ord(
'A')+i
−1);
writeln(str
)
end.
5.2.3 Стандартные процедуры и функции
Опишем основные стандартные процедуры и функции для работы со строко- выми типами.
Процедура delete(var St:string;Poz:integer;N:integer)
производит удаление N символов строки St, начиная с позиции Poz. Если Poz > 255,
то осуществляется программное прерывание.
Пример
St:=
'abcdef';
delete(St,4,2);

102