Javascript-форум (https://javascript.ru/forum/)
-   Общие вопросы Javascript (https://javascript.ru/forum/misc/)
-   -   задача "Пересечение сторон фигуры линией в одной точке" (https://javascript.ru/forum/misc/6959-zadacha-peresechenie-storon-figury-liniejj-v-odnojj-tochke.html)

lh2030 08.01.2010 11:05

задача "Пересечение сторон фигуры линией в одной точке"
 
Привет всем.
Попалась на глаза задача, действует подобно медиавирусу.
Думаю попробовать ее решить на js. Буду рад, если кто поможет :)

Дано:
Фигура, если ее представить через 0-1, то она выглядит так:
0 1 1 1 0 1 1 1 0
1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0
1 1 1 1 1 1 1 1 1
0 1 0 1 1 1 0 1 0
где,
0 - точки пересечения линий фигуры
1 - точки сторон фигуры
Найти:
Линию, которая пересекается стороны фигуры в одной точке (или доказать, что она невозможна)
Дополнительное условия: линия не может себя пересекать
Не решение:
во вложении
Не решение2:
Пробовал решить через "поиск решения" в excel-е, ввел ограничения по выходным суммам и точкам, но не смог реализовать ограничение - одна точка на сегменте линии фигуры.

Gvozd 08.01.2010 12:10

Цитата:

Сообщение от lh2030
или доказать, что она невозможна

вместо того чтоб бежать кодить (кстати Excel и JS не улчшие средства для решения объемных вычислительных задач, а здесь вариантов O(2^36) ), стоит иногда чуть-чуть подумать
область с четным количеством сторон не должна содержать концов кривой, либо содержать их оба(кривая проходя насквозь затрагивает две стороны-при входе и выходе)
область с нечетным количеством сторон должна содержать ровно один конец кривой, и несколько раз "протыкаться" кривой
всего областей с нечетным количеством сторон - 4 (верхняя левая-5, верхняя правая-5, нижняя средняя-5, внешняя-9)
так как у кривой только два конца, то для данного случая нужно ровно 2 кривых, чтобы выполнить условие
Цитата:

Сообщение от lh2030
в одной точке


lh2030 08.01.2010 14:17

Вложений: 1
то Gvozd:
I.
можешь изобразить графически свою мысль?

II.
вообще, я попробовал формализовать твой топик и у меня возникли сомнения по поводу твоих аксиом
Ты говоришь, что
если :
1. четное кол-во сторон [в области фигуры] =>
а) не содержит конца кривой
б) содержит оба конца кривой (вход-выход)

2. нечетное кол-во сторон [в области фигуры] =>
несколько концов кривой (вход и несколько входов-выходов)

то:
нужно 2 кривые, чтобы выполнить [Пересечение сторон фигуры кривой в одной точке]


я не согласен с твоим то, т.к.
твое если2 описывает ситуацию, когда нужно выполнить [Кривая должна быть закрытой], а не [Пересечение сторон фигуры кривой в одной точке]. Графический примеры решения для пунктов 1 и 2 во вложении.

Gvozd 08.01.2010 15:44

Цитата:

Сообщение от Gvozd
область с нечетным количеством сторон должна содержать ровно один конец кривой,

Цитата:

Сообщение от lh2030
2. нечетное кол-во сторон [в области фигуры] =>
несколько концов кривой (вход и несколько входов-выходов)

ты меня переврал.поэтому и сомнения возникли

твой рисунок 1а имеет на каждой стороне по 2 пересечения, что противоречит твоему условию
Цитата:

Сообщение от lh2030
Линию, которая пересекается стороны фигуры в одной точке

на рисунке изображены случай 1а и 1б для квадрата
внешнюю область я также рассматриваю как область, и поэтому выделил цветом.
как видим в обоих случаях для обоих областей выполняется одно из двух условий (1а,1б)
если соединить ближайшие концы, то для обоих фигур будет выполнено услвоие 1а
моя же аксиома 2, звучит не так как вы ее написали, а так:
2. нечетное кол-во сторон [в области фигуры] =>
Код:

ровно один конец кривой (вход или выход)
все ваши рисунки 2а подтверждают эту аксиому, не нарушая 1-ю аксиому
на каждом из тех рисунков ровно по две нечетных области, и каждая из них содержит ровно по одному концу
в вашей же фигуре из задачи, нечетных фигур 4, и поэтому должно быть 4 конца кривых, как минимум(не забываем что в четных областях могут быть пары концов), то есть не менее двух кривых смогут пересечь каждую сторону ровно по одному разу(только одна кривая может пересечь сторону.)
а з

lh2030 08.01.2010 20:09

то Gvozd:
Благодарю за ответ, да, я действительно неправильно понял твой первый пост, мне нужно сейчас идти - завтра утром обязательно переосмыслю постановку с введением внешней области, как важного элемента и непременно отпишусь

p.s.
Прошу воспринимать мое "ты" как способ более коммуникативного общения, мне так проще находить общий язык, более структурного взаимодействия, так сказать :)

Gvozd 08.01.2010 21:36

Цитата:

Сообщение от lh2030
Прошу воспринимать мое "ты" как способ более коммуникативного общения

без проблем

кстати вся эта аксиоматика не затрагивает вопрос самопересечений кривой.
этот вопрос мне кажется можно контролировать уже только во время перебора.

lh2030 14.01.2010 10:11

Вложений: 1
все, я понял твою мысль. Абсолютно с тобой согласен. Спасибо огромное.
p.s. Думаю вот так формализовать мысль, для наглядности:

II.
Решение:
т.к. :
1. четное кол-во сторон [в области фигуры] =>
а) не содержит конца кривой, пр.: рис. 1а
б) содержит оба конца кривой (вход-выход), пр.: рис. 1б

2. нечетное кол-во сторон [в области фигуры] =>
а) один конец кривой (вход или выход), пр.: рис. 2а

то:
т.к. 
4 нечетных области (рис. 3а), значит 4 точки (выход ИЛИ вход)
2 четных области, значит 0 точек(вход и выход - 1 точка) или 2 точки (вход И выход)

т.к.
а] вход ИЛИ выход = 1 кривая (открытая, пр.: рис. 2а)
б] вход И выход = 1 кривая (закрытая)

следовательно (из а], с учетом рис. 2б) фигуру пересекают НЕ МЕНЕЕ 2 кривых

Ane4ka93 07.12.2010 19:01

у меня вопрос так а как тогда решить 3а???

Ane4ka93 07.12.2010 19:10

lh2030,
привет)
у меня к тебе вопрос - так ты смог эту задачу решить или нет??

justguest 11.03.2011 20:03

lh2030,
Нифига ты не решил. Только выежнулся и все.


Часовой пояс GMT +3, время: 17:06.