Главная страница
Навигация по странице:

  • 6. Избранные олимпиадные задачи по программированию 317

  • 7. Заметки о тестировании программ

  • 7. Заметки о тестировании программ 319

  • Заметки о тестировании программ 321

  • 322 7. Заметки о тестировании программ

  • 7. Заметки о тестировании программ 323

  • Заметки о тестировании программ 325

  • По вопросам приобретения обращаться


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница24 из 26
    1   ...   18   19   20   21   22   23   24   25   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) ;

    1   ...   18   19   20   21   22   23   24   25   26


    написать администратору сайта