Здраствуйте. Помню очень давно решал задачу, но не помню точные цифры, в общем, дело было так:
Есть круг. Надо с помощью (вроде) 5 (но, кажется, надо больше) прямых разделить круг на (вроде) 20 частей, не важно каких, но так, чтобы в любой точке круга пересекалось не больше 2 (это точно) прямых.
P.S. Если задача решалась, покажите, пожалуйста место с ответом, очень охото вспомнить детство .
ИМХО для 5 больше 16 не получить ибо если пересечь каждую с каждой полечим питиконечную звезду у которой 6 частей в нутри и 10 с наружи.
Для 6 можно получить 22.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>ИМХО для 5 больше 16 не получить ибо если пересечь каждую с каждой полечим питиконечную звезду у которой 6 частей в нутри и 10 с наружи. WH>Для 6 можно получить 22.
А задачка-то оказалась проще паренной репы! Даже можно составить уравнение, сколько получится мах частей из n прямых. Причем, как в прямом виде, так и рекурсивно.
P.S. На счет пареной репы я загнул: репу запарить, я думаю, труднее.
Здравствуйте, Real 3L0, Вы писали:
R3>А задачка-то оказалась проще паренной репы! Даже можно составить уравнение, сколько получится мах частей из n прямых. Причем, как в прямом виде, так и рекурсивно.
Здравствуйте, WolfHound, Вы писали:
ММ>>n*(n+1)/2 + 1 WH>А ты можешь доказать что при любом n можно пересечь каждую с каждой и при этом чтобы ни какие 3 прямые не пересекались в одной точке?
Первая часть сводится к тому, что при любом n можно построить прямую, непараллельную имеющимся n. Алгоритма предложить не могу, но сделать это можно всегда (по крайней мере для конечных n).
Если при этом образовалось пересечение 3 прямых в одной точке, то параллельным переносом новопостроенной прямой, можно выйти из этой ситуации, т.к. кол-во точек пересечения конечно (n*(n-1)/2).
Единственная проблема состоит в том, что не всегда можно к уже имеющимся n-1 прямым добавить еще одну, так чтобы все точки пересечения этой прямой с остальными попали внутрь круга.
Но если речь не идет о добавлении, то можно загнать все получившиеся точки пересечения в круг уменьшением масштаба.
.
