Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Анкор: Окулов.Программирование.в.алгоритмах.pdf
• Дата: 26.04.2017
• Размер: 5.46 Mb.
• Имя файла: Окулов.Программирование.в.алгоритмах.pdf
• Тип: Документы; #5718
• страница: 24 из 26

|
+-+?
-+—+-+-|-+-?
9 14 10 15 11
?
-2,9
-3, 13
-7,5
-10,7
-5,8
Автор благодарит Александра Николаевича Семенова помощь в разборе данной задачи.

316
6. Избранные
задачи по программированию
№ 6
7 8
q
13 9
14
Р
5 5
5
Схема Евклида
3
Последовательность
-+-?
+++?
+++?
L
16 12 17
?
-7,
-11,3
-15,4
Первая строка —
Схема Евклида дает условный символ
(назовем его базовым). Конструируем из него после- довательность. Сумма пяти элементов должна быть положите- льна. Добавляем другой символ — « + Сумма шести элемен- тов — отрицательна, поэтому добавляем
В таблице эта часть отделена от остальной символом « |
Что происходит да- льше? Три базовых элемента (повторяют начало) не меняют структуры исследуемого нами объекта. В позицию, отмеченную
«?», мы не можем записать ни «—», ни «+». Запись «—» на эту позицию делает последнюю сумму из пяти элементов отрицате- льной. Запись « + — сумму из шести последних элементов по- ложительной. Чем отличается вторая строка таблицы? После- довательность повторяется два раза (множитель 2 в схеме Евклида). Третья строка таблицы более интересна. Из ба- зового элемента мы конструируем последовательность из двух элементов (сумма их отрицательна). Из неё мы получаем после- довательность длины пять и только затем длины семь, добав- ляя ранее полученную последовательность длины два. Из этих же экспериментов определяется и максимальная длина L - при
Действия математика (на наш взгляд) несколько отличаются от тех, что приведены. Он, быть может, тоже рисует последовательности, но в конечном итоге его результат выглядит иначе. Следует предположение о том,
что L>p+q—2. Затем выполняются рассуждения по индукции,
получается противоречие, и следствием является доказанный факт о том, что L
Итак, пусть мы получили последовательность (регулярную!)
из и
Требуется определить, какие натуральные числа соответствуют им (последний столбец таблицы). Должна быть
зависимость от значений р, q и соотношения количеств «+» и
«-» на различных периодах последовательности. Обозначим через число « + » на периоде тогда отношение числа «-» к числу « + выражается
Вернемся к таблице и попы- таемся определить, как связаны эти отношения на соседних пе- риодах. После некоторых усилий устанавливается следующий

6. Избранные олимпиадные задачи по программированию 317
факт:
при четном значении i и «>»
при нечетном i. Доказательство истинности этого факта мате- матик проводит методом индукции. Что из него следует? Пусть и i=\. Мы имеем неравенство
(i — нечетно). Средневзвешенное чисел в правой и левой частях неравенства принадлежит интервалу, определяемому этими числами, т. е.
Заменим
+ » на число и «-» на число
Из последнего неравенства получаем, что сумма любых р чисел, идущих подряд, равна a
сумма любых q чисел — равна
После этого можно поставить точку в рассуждениях и перейти к написанию программы. А случай
Для значений и q/d
мы можем построить наш объект. Добавим между каждыми элементами построенной последовательности, а также справа и слева нулей. Условия положительности и отрицатель- ности сумм выполняются, а длина равна
или

7. Заметки о тестировании
программ
При написании этой главы на память приходит один пример из собственной практики автора. После окончания университе- та автору пришлось разрабатывать программы (а это было на- чало 80-х годов прошедшего столетия) для специализирован- ных вычислительных комплексов. В силу определенной живости натуры автор быстро стал ведущим разработчиком и отвечал за весь цикл разработки программ и их внедрение, бу- дучи заместителем генерального конструктора по этим вопро- сам. Одну программную ошибку в комплексе, прошедшем все испытания и принятом заказчиком, автору пришлось искать не менее полугода. Среди решаемых задач комплекса было по- строение связных областей (от любой точки области до любой точки можно попасть по точкам связной области) в четырех- мерном пространстве параметров. Эти области изменялись во времени, одни точки области исчезали, другие добавлялись, об- ласти могли объединяться и наоборот. Вот такую динамичную картинку требовалось обрабатывать в реальном масштабе вре- мени, причем поток входной информации (подлежащий обра- ботке) был весьма значительным. Периферийных устройств не было. Программы хранились в ПЗУ, и каждое изменение тре- бовало его перепрограммирования. Для того, чтобы что-то про- смотреть, необходимо было остановить соответствующий про- цессор и с помощью тумблеров набрать адрес регистра или ячейки, содержимое которых после этого отображалось с помо- щью диодов. Ошибка проявлялась нестабильно, только на определенных входных потоках, причем в одних случаях про- исходило зацикливание (не обязательно в одном месте), в дру- гих — бессмысленное «размножение» связных областей. Ошиб- ка проявлялась достаточно редко, и это, а также то, что знание комплекса разработчиками было доскональное, позволило, ви- димо, пройти все испытания. По характеру мигания светодио- дов определялось место работы программы, устройства. Неко- торые сбои устранялись простым ударом кулака по определенному месту соответствующей стойки и т. д. Ошибка оказалась достаточно простой. В том случае, когда связные об- ласти в процессе изменений превращались в одиночные (или почти одиночные) точки и располагались в пространстве пара-

7. Заметки о тестировании программ 319
метров примерно так, как черные клетки на шахматной доске,
нехватало места в оперативной памяти для хранения их описа- ния. Контроля на выход за пределы соответствующих структур данных не было (примерно так же, как выход индекса за преде- лы массива). Никто не предполагал такой ситуации, по всем предварительным расчетам её не могло быть, однако... было по- лучено огромное удовлетворение от проделанной работы.
Появление книги Э. Йодана [12] и др. было воспринято авто- ром как должное, ибо нечто подобное он уже делал на практи- ке, когда, например, в режиме «сухого плавания» (комплекса под рукой не было) искал описанную выше ошибку. Привер- женность технологии нисходящего проектирования программ осталась неизменной все эти годы. Дальнейшее развитие про- граммирования, как науки, так и отрасли производства, только подтвердило правильность революционных идей, высказанных в своё время профессором Э. Дейкстрой.
7.1. О программировании
Программирование — теоретическая и практическая деяте- льность по обеспечению программного управления обработкой данных, включающая создание программ, а также выбор струк- туры и кодирования данных — классическое определение. По- пробуем определить несколько иначе, более конструктивно, рас- сматривая то, чем занимается программист. Есть задача или проблема. В первую очередь программист должен определить возможность ее решения, выбирая соответствующий метод. За- тем разработать проект программы, состоящий из алгоритма на каком-либо из языков программирования, доказать правиль- ность работы программы и предусмотреть возможность ее изме- нения, внесения изменений на этапе сопровождения. Таким об- разом, в укрупненном виде мы видим три этапа: до программирования, программирование и после программирова- ния. Есть еще и четвертый этап. После того, как все казалось бы сделано, ответить на вопрос — «а что если все не так?». Только часть работы связана с выбором структур данных и кодировани- ем — использованием языков программирования. Программиро- вание есть, если так можно выразиться, инженерная работа по конструированию некой целостной системы обработки данных.
Отличие программы, например, от некоторой механической сис- темы, в том, что число взаимодействующих частей в программе настолько велико, что не поддается никакому разумному объяс- нению и проверить работу этой программной системы, переби- рать все возможные способы взаимодействия ее частей немысли-

320
Заметки о тестировании программ
мо даже на сверхбыстродействующих компьютерах в разумные сроки. Итак, выделим это положение: программа (назовем так
по традиции) — сверхсложная система. Где же выход при со- здании таких сверхсложных систем, при достижении их работо- способности? Видимо, только в технологиях, обеспечивающих на выходе качественный и надежный продукт, важнейшим эле- ментом которых является умение тестировать программные ре- шения.
7.2. Практические рекомендации
Общие положения. Практические рекомендации по написа- нию программ основаны на технологии нисходящего проекти- рования. О строгом математическом доказательстве правильно- сти работы обычно не может быть и речи при достаточно сложной программе. Успешная трансляция не есть признак ра- ботающей программы, а правильность работы на некотором на- боре тестов еще не означает, что программа всегда будет рабо- тать правильно, — следует помнить, что различных комбинаций входных данных бывает, как правило, бесконечно
(или «практически» бесконечно) много. Основная идея — не пытаться программировать сразу. Пошаговая детализация ав- томатически заставляет формировать понятную структуру про- граммы. При этом требуется отслеживать правильность детали- зации, создавая набор контрольных точек и просчитывая значения данных в них. Контрольные точки обычно проходят- ся при любых начальных данных (как точка сочленения в гра- фе). Выбор представления данных — один из фундаментальных аспектов разработки программы. Н. Вирт так определял крите- рии этого действия: естественность, структуры данных обяза- ны «вытекать» из специфики задачи; привычность, структуры данных выбираются так, чтобы программирование приближа- лось к утверждению «как говорю, так и пишу программу, ни- чего лишнего»; оптимальность, структуры данных выбирают- ся так, чтобы была возможность построения эффективного алгоритма. Например, решая задачу о построении каркаса ми- нимального веса в графе, естественно выбрать список ребер, а не матрицу инциденций или матрицу смежности.
Примеры плохого программирования. Приведем ряд приме- ров, которые не соответствуют технологии структурного напи- сания программ.
1. Следует придерживаться правила о том, что любой фраг- мент программного кода (логики) должен иметь одну точку входа и одну точку выхода (пусть даже в ущерб эффективности

Заметки о тестировании программ 321
использования памяти). Ниже приводится пример того, как не- большой фрагмент имеет две точки выхода.
While <условие 1> Do Begin
If <условие 2> Then Exit;
End;
Использование конструкции бесконечного цикла только усу- губляет ситуацию.
While True Do Begin
If <условие 2> Then Exit;
End;
2. Искусственные приемы, как, например, продемонстриро- ванный ниже случай выхода из циклической конструкции типа For, приводят, при внесении изменений в программу, к многочисленным и трудно устранимым ошибкам.
For i:=l
N Begin
If <условие> Then i:=N+l;
End;
3. Увлечение параметрами при работе с процедурами и фун- кциями является «болезнью роста» при освоении технологии нисходящего проектирования программ.
Type
Of Byte;
Procedure Swap (Var B:BArray;i,k:Byte);
Var
Begin
=B [i ] ;B [i ] :
[k] ;B [k] :
End;
и вызов Swap(B,i,k) вместо следующего простого текста проце- дуры:
Procedure
Var x:Byte;
Begin
=z ; z :
End;
и вызова

322 7. Заметки о тестировании программ
4. Один профессиональный программист сказал автору в ча- стной беседе о том, что для него критерием подготовленности выпускников высшего учебного заведения к работе является понимание (глубокое) рекурсии и знание динамических струк- тур данных.
Procedure Generate;(*t - глобальная переменная*}
Begin
Generate;
End;
Логичнее выглядел бы следующий фрагмент (вопрос об эко- номии места в стеке адресов возврата не ставится, оно есть и точка).
Procedure
Begin
;
End;
5. Очень трудно убедить школьников в том, что если пере- менная используется только в процедуре, то она и должна определяться в этой процедуре, пусть и с дублированием про- граммного кода. Только через большое количество занятий, по- сле многочисленных ошибок приходит понимание факта. Ти- пичный пример такого написания программ приводится ниже.
Program
Var
Procedure
Begin
с переменными i, j>;
End;
Procedure B;
Begin
с переменными i, j>;
End;
{**}
Begin
<Работа с переменными i, j>
End.

7. Заметки о тестировании программ 323
Временная
Обычно на время решения задачи накладываются определенные ограничения. Размерность зада- чи опишем величиной N. Временная сложность алгоритма яв- ляется линейной при t

O(N), полиномиальной при где q равно обычно 2 или 3, и экспоненциальной при
Эффективными являются алгоритмы первых двух типов. Обыч- но подсказка о том, какой существует алгоритм решения, со- держится в формулировке задачи (имеется в виду олимпиад- ный вариант). Если дано N, большее 50, то следует искать быстрый алгоритм, в противном случае сосредоточиться на эв- ристиках, сокращающих традиционный перебор с возвратом.
Ответим на вопрос: как оценить время работы программы в среде Турбо Паскаль? Обычно используют тот факт, что к ячей- ке с абсолютным адресом $40:$6С (назовем её Timer) один раз в
1/18.2 секунды прибавляется единица (или один раз в каждые 55 миллисекунд). Допустим, что программа должна работать 5 секунд (зафиксировали время в ячейке с именем 77-
В начале работы программы значение из $40:$6С за- помнили в некоторой переменной, например TimeOld. После этой подготовительной работы в расчетной части программы осталось проверять условие
Ес- ли оно выполняется, то время решения задачи истекло. Так как обычно перед завершением задачи требуется записать в вы- ходной файл результат (хотя бы промежуточный, например наилучшее из найденных решений в переборной задаче), а для этого требуется время, то условие пишут с учетом этого факта
Ниже приведен текст фрагмента, в котором считается количество прибавления еди- ницы к ячейке в зависимости от времени, выделенного на рабо- ту программы.
Program
Uses Crt;
Const N=5;
Var
Absolute
TimeOld,
i -.Longlnt;
pp:Boolean;
Begin
ClrScr;
For
To N Do Begin
значение таймера.}
pp:=True;
решения задачи. *}
L:=0;

324
7. Заметки о тестировании программ
While
Do Begin
не истекло время,
отведенное на решение задачи. *}
(L) ; {
единицу к счетчику. *}
If
Then
End;
End;
End;
End.
контроля правильности работы программы. Сфор- мулируем ряд приемов, позволяющих избежать простых оши- бок в разрабатываемых программах. (1) Обычно формат вход- ных данных задачи строго определен. Если в формулировке требуется контролировать корректность ввода данных, то сле- дует выделить эту часть логики в отдельную процедуру(ы). Од- нако в последние годы от требования проверки входных дан- ных отказались (видимо, из-за простоты) — они считаются корректными. Несмотря на это, после ввода данных их следует сразу вывести и проверить, что позволит избежать ошибок это- го типа (на них обычно не обращают внимания и только после значительных усилий возникает вопрос — «а правильно ли в программе вводятся данные»). (2) Иногда полезно отслеживать
(не в пошаговом режиме) трассу работы определенной части программы. Так, при входе в процедуру можно выводить ее имя и значения входных параметров или выводить промежу- точные данные в определенных точках программы. К этому же приему относится и введение дополнительных счетчиков, конт- ролирующих прохождение различных ветвей логики. (3) Син- таксические ошибки устраняются обычно моментально. Для поиска, если так можно выразиться, логических ошибок перво- го типа в среде Турбо Паскаль рекомендуется вести отладку с включенными директивами. Начало программы после нажатия выглядит следующим образом:
{$М 16384,0,655360}.
Изменение, например, R— на R+ позволяет контролировать выход индексов за пределы массива. Логические ошибки следу- ющего уровня сложности связаны обычно с тем, что задача была понята неверно, т. е. решена не та задача, которая была поставлена. В этом случае лучше всего «прогнать» решение на примере, просчитанном «вручную» (обычно такой пример при-

Заметки о тестировании программ 325
водится в формулировке задачи). Неверным может оказаться замысел алгоритма. Правильные решения получаются не для всех исходных данных. Это, вероятно, самый сложный тип ошибок и его рассмотрению посвящен следующий параграф данной главы.
О тестировании программ. Тест является совокупностью исходных данных для проверки работоспособности программы.
Одного теста обычно недостаточно для проверки каждой ветви программы, и говорят о системе тестов. Кроме того, с помощью тестов проверяются количественные ограничения на исходные данные и временные ограничения. Исходя из этого, разумно формировать систему тестов, например, следующим образом:
первый тест должен быть максимально простым; следующие тесты должны проверять вырожденные случаи (например, при поиске решений квадратного уравнения проверяются вырож- денные случаи); обязательно следует проверять граничные слу- чаи (результат описан как тип Integer, а значение превосходит
32767); предельные тесты проверяют решение при наибольших значениях входных параметров задачи, и, разумеется, требует- ся постоянный контроль над временем выполнения программы
(при превышении ограничений по времени выбран не эффек- тивный алгоритм решения).
Автоматизация проверки. Обычно в задаче имена входного и выходного файлов определены. Постоянное изменение имени не очень рационально. Рассмотрим, как выходить из данной ситуации. Во-первых, создается директорий для работы с про- граммой, и он является текущим в системе программирования
Турбо Паскаль. Программа ищет входной файл в текущем ди- ректории и записывает в него выходной файл. Пусть есть сле- дующая «варварская» программа — из файла считываются два числа, их сумма записывается в выходной файл. Кроме того, в программу вставлены не очень понятные операторы. Однако они написаны, и с ними проводится отладка.
Program add;
Var a,b : Integer;
Begin
Assign
Reset (input);
(a,b);
Close (input);
While
Do;
If a = 20 Then b : = Round (a/0) ;