 |
 |
 |
 |
|
 |
 |
158
максимальный маршрут:
1
3
2
4
длина =18
минимальный маршрут:
1 2 4 3
длина = 14
Четвертую задачу можно отнести к геометрическим задачам, решение которых опирается на
некоторые геометрические законы и свойства. Эта задача наиболее сложная среди рассмотренных задач
из-за необходимости привлечения определенных математических знаний для организации ее решения.
Задача 4. «Ломаная».
Найти все точки самопересечения разноцветной замкнутой линии, заданной на плоскости
координатами своих вершин в порядке обхода ломаной. Данные о ломаной представляются таблицей:
х
у
0
1
1
0
0
1
1
1
Особенность этой задачи - большое число частных случаев, связанных с возможным вырождением
или наложением отрезков ломанной линии. Именно эти ситуации и составляют содержание тестов, на
которых большинство программ дают неправильные результаты.
Приведем проверочные тесты:
Tecт1. (Основной случай)
0
0
0
1
1
0
1
1
Правильные результаты:
точки пересечения
0.5
0.5
Тест 2. (Основной случай)
0
0
0
1
1
1
1
0
Правильные результаты:
точки пересечения:
отсутствуют
Тест3. (Наложение вершины)
0
0
0
1
0.5
0