Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #1 (permalink)  
Старый 08.01.2010, 11:05
Новичок на форуме
Отправить личное сообщение для lh2030 Посмотреть профиль Найти все сообщения от lh2030
 
Регистрация: 08.01.2010
Сообщений: 7

задача "Пересечение сторон фигуры линией в одной точке"
Привет всем.
Попалась на глаза задача, действует подобно медиавирусу.
Думаю попробовать ее решить на 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-е, ввел ограничения по выходным суммам и точкам, но не смог реализовать ограничение - одна точка на сегменте линии фигуры.
Ответить с цитированием
  #2 (permalink)  
Старый 08.01.2010, 12:10
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,246

Сообщение от lh2030
или доказать, что она невозможна
вместо того чтоб бежать кодить (кстати Excel и JS не улчшие средства для решения объемных вычислительных задач, а здесь вариантов O(2^36) ), стоит иногда чуть-чуть подумать
область с четным количеством сторон не должна содержать концов кривой, либо содержать их оба(кривая проходя насквозь затрагивает две стороны-при входе и выходе)
область с нечетным количеством сторон должна содержать ровно один конец кривой, и несколько раз "протыкаться" кривой
всего областей с нечетным количеством сторон - 4 (верхняя левая-5, верхняя правая-5, нижняя средняя-5, внешняя-9)
так как у кривой только два конца, то для данного случая нужно ровно 2 кривых, чтобы выполнить условие
Сообщение от lh2030
в одной точке
Ответить с цитированием
  #3 (permalink)  
Старый 08.01.2010, 14:17
Новичок на форуме
Отправить личное сообщение для lh2030 Посмотреть профиль Найти все сообщения от lh2030
 
Регистрация: 08.01.2010
Сообщений: 7

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

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

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

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


я не согласен с твоим то, т.к.
твое если2 описывает ситуацию, когда нужно выполнить [Кривая должна быть закрытой], а не [Пересечение сторон фигуры кривой в одной точке]. Графический примеры решения для пунктов 1 и 2 во вложении.
Изображения:
Тип файла: jpg zadacha-.jpg (39.2 Кб, 16 просмотров)
Ответить с цитированием
  #4 (permalink)  
Старый 08.01.2010, 15:44
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,246

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

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

Последний раз редактировалось Gvozd, 30.04.2012 в 23:36.
Ответить с цитированием
  #5 (permalink)  
Старый 08.01.2010, 20:09
Новичок на форуме
Отправить личное сообщение для lh2030 Посмотреть профиль Найти все сообщения от lh2030
 
Регистрация: 08.01.2010
Сообщений: 7

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

p.s.
Прошу воспринимать мое "ты" как способ более коммуникативного общения, мне так проще находить общий язык, более структурного взаимодействия, так сказать
Ответить с цитированием
  #6 (permalink)  
Старый 08.01.2010, 21:36
Аватар для Gvozd
Матрос
Отправить личное сообщение для Gvozd Посмотреть профиль Найти все сообщения от Gvozd
 
Регистрация: 04.04.2008
Сообщений: 6,246

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

кстати вся эта аксиоматика не затрагивает вопрос самопересечений кривой.
этот вопрос мне кажется можно контролировать уже только во время перебора.
Ответить с цитированием
  #7 (permalink)  
Старый 14.01.2010, 10:11
Новичок на форуме
Отправить личное сообщение для lh2030 Посмотреть профиль Найти все сообщения от lh2030
 
Регистрация: 08.01.2010
Сообщений: 7

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

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

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

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

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

следовательно (из а], с учетом рис. 2б) фигуру пересекают НЕ МЕНЕЕ 2 кривых
Изображения:
Тип файла: jpg zadacha++.jpg (126.7 Кб, 21 просмотров)
Ответить с цитированием
  #8 (permalink)  
Старый 07.12.2010, 19:01
Новичок на форуме
Отправить личное сообщение для Ane4ka93 Посмотреть профиль Найти все сообщения от Ane4ka93
 
Регистрация: 07.12.2010
Сообщений: 2

у меня вопрос так а как тогда решить 3а???
Ответить с цитированием
  #9 (permalink)  
Старый 07.12.2010, 19:10
Новичок на форуме
Отправить личное сообщение для Ane4ka93 Посмотреть профиль Найти все сообщения от Ane4ka93
 
Регистрация: 07.12.2010
Сообщений: 2

lh2030,
привет)
у меня к тебе вопрос - так ты смог эту задачу решить или нет??
Ответить с цитированием
  #10 (permalink)  
Старый 11.03.2011, 20:03
Новичок на форуме
Отправить личное сообщение для justguest Посмотреть профиль Найти все сообщения от justguest
 
Регистрация: 11.03.2011
Сообщений: 1

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


Опции темы Искать в теме
Искать в теме:

Расширенный поиск