Скриншот работающей программы показан на рис. 2.7.

Стоит отметить, что здесь нужно очень внимательно обходиться с типами. Если вы присмотритесь к окружностям, обозначающим общие точки уравнений прямых лазера и зеркал, то увидите, что центры этих окружностей не лежат точно на одной прямой, а с небольшим смещением. Мало того, если вы измените все переменные типа long double на переменные типа double, вы заметите, что после девятой итерации луч лазера пойдёт не так, как раньше!

По этому поводу с нескрываемым удовольствием приведу цитату из книги Герба Саттера: Вычисления с плавающей точкой сложны, трудны и почти всегда - неочевидны. Я бы сказал - с известной долей самомнения - что все программисты делятся на три группы: те, кто знают, что они не понима-

2 Herb Sutter. Exceptional C++ Style. Pearson Education, Inc., 2004 (Герб Carrep. Новые сложные

задачи на C++. Вильяме. 2005).

20 70083 440 310135 5tl 4505115150 ?401?0 35150 540130 35150 34и1Л35150

ftfc 2.7. Приложение Лабиринт для лазера

ЮТ вычисления с плавающей точкой (и они правы); те, кто думают, что они понимают их (но они ошибаются); и те немногие эксперты, которые совсем не уверены в том, что когда-либо полностью сумеют разобраться в вычислениях с плавающей точкой (и это мудро) .

Па этом задание считается выполненным.

рисуем отрезок луча и назначаем новую отправную точку

F Main->Canvas->LineTo(laser.X = vm[rein index] .х,

laser.y = vm[rem index].у);

отражаем луч лазера от найденного зеркала и меняем /У значение индекса зеркала, от которого был отражён лазер

Reflect(laser.ange,

mirrors[rem index = vm[rem index].pos].angle);

исключим возможность проверки пересечения луча с текущим отражающим зеркалом на следующей итерации mirrors[rem index].prev iter reflected = true;

обновляем уравнение прямой луча

laser.к = tan(laser.angle);

laser.b = laser.y - laser.k*laser.x;

пунктиром обозначим отражённый луч F Main->Canvas->Pen->Style = psDot;

F Main->Canvas->LineTo(laser.X + 50*cos(laser.angle),

laser.y + 50*sin(laser.angle)); F Main->Canvas->Pen->Style = psSolid;

else

Application->MessageBdxA(JIy4 дальше не пойдёт ,

Ни одно зеркало не может отразить луч , 0);

else

Application->MessageBoxA( Зеркал нет или они параллельны ходу луча , Ни одно зеркало не может отразить луч , 0);

ГЛАВА 3. АЛГОРИТМЫ НА графах

Глава 3. Алгоритмы на графах

Раздел, посвященный графам, можно встретить практически в любом учебнике по компьютерной науке. Это неудивительно: графы используются при решении самых разных задач от планирования маршрута по карте города до разработки разумной стратегии при игре в шахматы. При этом, к сожалению, основные принципы иллюстрируются одними и теми же классическими алгоритмами: Прима-Краскала (построение телефонной сети), Дей-кстры (поиск оптимального маршрута), обход графа в глубину / в ширину и так далее. Безусловно, знакомство с ними абсолютно необходимо, однако многие интересные задачи при таком подходе остаются за рамками книг.

В этой главе мы рассмотрим интересные практические применения некоторых алгоритмов из теории графов. Например, задача Планировщик СУБД иллюстрирует поиск циклов, а Сортировка сайтов - выявление компонент связности. Большое внимание уделено также алгоритму волновой трассиробки - очень интересному частному слзгчаю алгоритма Дейкс-тры, используемому при поиске маршрута в лабирю1те, а также при заливке замкнутого контура.

3.1. АНАЛИЗ ГРАФОВ

3.1.1. Решение неразрешимой задачи Анализ проблемы останова

Заранее прошу прощения за слишком длинную формулировку, но задача, как мне кажется, того стоит.

В теории вычислений доказывается, что так называемая задача останова не может быть решена никаким алгоритмом, реализованным на обычном ком-пьютере Формулировка задачи останова очень проста. Даётся описание

1 Точнее, этот результат доказывается для машины Тьюринга, принципиально отличающейся от

компьютера наличием бесконечной памяти (и, таким образом, являющейся ещё более мощным устройством).

произвольного алгоритма на каком-либо формальном алгоритмическом языке (например, на Паскале). За конечное время требуется определить, закончит ли этот алгоритм работу или будет продолжать выполняться бесконечно долго.

Многим кажется, что любой программист если не с первого, то со второго взгляда способен определить, зависает ли программа в бесконечном цикле или нет, но на самом деле это не так. Конечно, в простых случаях распознать зависание нетрудно, но существуют и задачки посложнее. Например, представьте себе такой алгоритм:

* N , 2

Для справки: совершенными называются числа, равные сумме всех своих делителей, кроме себя. Например, 6 = 3 + 2+1,28 =14+ 7 + 4 + 2+1.

Приведённый алгоритм заканчивает работу, найдя первое нечётное совершенное число (в предположении, что переменная N имеет потенциально неограниченный размер и может хранить любые, сколь угодно большие целые числа). Ситуация интересна тем, что на сегодняшний день никто не знает, существуют ли вообще нечётные совершенные числа. Поэтому дать правильный ответ на вопрос об останове программы их поиска весьма затруднительно. Просто запустить программу и проанализировать её поведение тоже не получится. Если окажется, что нечётных совершенных чисел не существует, мы не сумеем получить ответ за конечное время - программа будет перебирать все целые числа по очереди, а целых чисел, как известно, бесконечное множество.

То, что задача останова не решается с помощью компьютера - факт доказанный. Можно ли создать какое-либо более мощное решающее устройство - неизвестно. Сформулированный в 1936 году тезис Чёрча-Тьюринга утверждает, что нельзя. В целом научное сообщество к нему склоняется, но ни строгих доказательств, ни контрпримеров мы до сих пор не имеем.

Однако обычные компьютерные программы обладают одним важным свойством, отличающим их от алгоритмов в математическом смысле этого слова. Дело в том, что любая реальная переменная или структура данных имеет ограниченный размер. Так, выше я заметил, что переменная N может хранить любое число. Если же рассмотреть более реалистичный сценарий и предположить, что N представляет собой беззнаковую 32-разрядную переменную, то окажется, что как только значение N превысит 2 - 1, произойдёт переполнение. Таким образом, задача останова для обычных ком-