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

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

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

  • Библиографический указатель

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


    Скачать 5.46 Mb.
    НазваниеПо вопросам приобретения обращаться
    Дата06.12.2019
    Размер5.46 Mb.
    Формат файлаpdf
    Имя файлаProgrammirovanie_v_algoritmakh.pdf
    ТипДокументы
    #98984
    страница26 из 26
    1   ...   18   19   20   21   22   23   24   25   26
    И наконец, новый вариант процедуры Solve.
    Procedure Solve;
    Var i -.Integer;
    Begin
    'photoA.
    Assign
    For i := 1 To Size Do Begin
    FillChar ( used ,
    False);
    {*Считаем все номера
    *}
    For j
    1
    Size Do
    If TempRes [ NewLine [j] ] < 0 Then
    NewLine [j] := FindLast ( NewLine [j] );{*Этим
    мы сокращаем количество
    пере
    по ссылочным ячейкам при
    поиске ячейки с
    значительно
    ускоряя тем самым обработку следующей
    строки при слиянии связных областей. *}
    If (TempRes [ NewLine [j] ] > 0) And Not Used
    [NewLine [j]] Then Begin

    338
    7. Заметки о тестировании программ
    If
    [ NewLine [j] ] > Res Then Res : =
    [ NewLine [j] ];
    Used [ NewLine [j] ] := True;
    End;
    End;
    OldLine := NewLine;
    End;
    End;
    Для иллюстрации логи- ки, а именно изменения зна- чений в массивах NewLine и
    TempRes, рассмотрим про- стой пример, первые две строки которого изображены на рисунке.
    1 2
    3 4
    5
    NewLine
    1 0 2 0 3 0 4 0 5 0 6 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 2 0 0 0 0 0 0 0
    TempRes
    0 0 0 0 2
    3 0 0 0 0 0 0 0 0
    - 2 - 3 8 0
    Примечание
    После обработки 1 -й строки сформировано пять связных областей,
    площадь каждой из них равна 1
    Обрабатываем 2-ю строку. В 1-м столбце таблицы указывается номер клетки строки
    Указывается последовательное изменение значений в массивах при работе
    Простое добавление к связной области
    «Склейка» связных областей. Площадь записана во второй ячейке. Первая переходит в разряд ссылочных
    Простое добавление связной области
    «Склейка» с 3-й связной областью из предыдущей строки. Приводится окончательный вид массива TempRes

    7. Заметки о тестировании программ
    339
    /
    9 10 5 5 5 5 5 5 5 5 5 5
    - 2 - 3 - 4 - 5 14-1 0 00 0
    - 2 - 3 - 4 - 5 15-1 00 00
    - 5 - 5 - 5 - 5 15-1 00 00
    Примечание
    «Склейка» с 5-й связной областью из предыдущей строки
    Работа процедуры окончена
    Готовим данные для следующего вызова
    CompareLines. Цепочка ссылок сокращена до одной - на ячейку с площадью
    Этот вариант программы «разбирается» с тестом типа «зубь- ев» размером 1000*1000 за 3 секунды. Можно ли продолжить совершенствование программы решения задачи? Безусловно,
    ибо нет предела совершенству. Мы не использовали динамиче- ские структуры данных. А может быть, есть вариант не по- строчного сравнения клеточных полей. Да даже написание про- грамм, генерирующих входные файлы различных типов,
    интереснейшая задача.

    Библиографический указатель
    1. Алексеев А. В. Олимпиады школьников по информатике.
    Задачи и решения. — Красноярск: Красноярское книжное из- дательство, 1995.
    2. Андреева Е. В., Фалина И. Н. Информатика: Системы счисления и компьютерная арифметика. — М.: Лаборатория
    Базовых Знаний, 1999.
    3. Бабушкина И. А., Бушмелева Н. А., Окулов С. М., Чер- ных С. Ю. Конспекты занятий по информатике (практикум по
    Паскалю). — Киров: Изд-во ВятГПУ, 1997.
    4. Бадин Н. М., Волченков С. Г., Дашниц Н. Л., Корнилов
    П. А. Ярославские олимпиады по информатике. — Ярославль:
    Изд-во ЯрГУ, 1995.
    5. Беров В. И., Лапунов А. В., Матюхин В. А., Понома- рев А. А. Особенности национальных задач по информатике. —
    Киров: Триада-С, 2000.
    6. Брудно А. П., Каплан Л. И. Московские олимпиады по программированию. — М.: Наука, 1990.
    7. Виленкин Н. Я. Комбинаторика. — М.: Наука, 1969.
    8. Вирт Н.

    М.: Наука, 1989.
    9. Гусев В. А., Мордкович А. Г. Математика: Справочные материалы. — М.: Просвещение, 1990.
    10. Дагене В. А., Григас Г. К., Аугутис К. Ф. 100 задач по программированию. — М.: Просвещение, 1993.
    11. Емеличев В. А., Мельников О. И., Сарванов В. И., Тыш- кевич Р. И. Лекции по теории графов. — М.: Наука, 1990.
    12. Йодан Э. Структурное проектирование и конструирова- ние программ. — М.: Мир, 1979.
    13. Касаткин В. Н. Информация. Алгоритмы. ЭВМ. — М.:
    Просвещение, 1991.
    14. Касьянов В. Н., Сабельфельд В. К. Сборник заданий по практикуму на ЭВМ. — М.: Наука, 1986.
    15. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989-1996. — М.:
    «ABF», 1996.

    Библиографический указатель
    341 16. Кристофидес Н. Теория графов. Алгоритмический под- ход. — М.: Мир, 1978.
    17. Лапунов А. В., Окулов С. М. Задачи международных олимпиад по информатике. — Киров, Изд-во ВятГПУ, 1993.
    18. Липский В. Комбинаторика для программистов. — М.:
    Мир, 1988.
    19. Окулов С. М., Пестов А. А. 100 задач по информати- ке. — Киров, Изд-во ВятГПУ, 2000.
    20. Окулов С. М., Пестов А. А., Пестов О. А. Информатика в задачах. — Киров, Изд-во ВятГПУ, 1998.
    21. Окулов С. М. Конспекты занятий по информатике (алго- ритмы на графах): Учебное пособие. — Киров, Изд-во ВятГПУ,
    1996.
    22. Окулов С. М. Задачи кировских олимпиад по информа- тике. — Киров, Изд-во ВятГПУ, 1993.
    23. Окулов С. М. Основы программирования. — М.: Лабора- тория Базовых Знаний, 2001.
    24. Препарата Ф., Шеймос М. Вычислительная геометрия:
    введение. — М.: Мир, 1989.
    25. Савельев Л. Я. Комбинаторика и вероятность. — Новоси- бирск: Наука, 1975.
    26. Усов Б. Б. Комбинаторные задачи// Информатика. 2000.
    №39.
    1   ...   18   19   20   21   22   23   24   25   26


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