Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться
 Скачать 5.46 Mb.
|
|
И наконец, новый вариант процедуры 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. |