Задачка
ProRok
33553
|
754
|
0
1533
18
Добавить комментарий
Авторизуйтесь чтобы отправить комментарий
Комментарии
1930
|
48
|
0
Ну блядь, это просто нужно пробовать методом проб и ошибок. Глядишь к разу 25-50 стопроцентово найдёшь правильную траекторию проложения линии =)))
184
|
5
|
0
Вызываюсь за ничю :s18:
33553
|
754
|
0
x5)
Terr.Jen пишет:уже 2 часа сижу нихуя
33553
|
754
|
0
было бы круто если бы кто то доказал что этого сделать нельзя
2704
|
86
|
0
Sorry for english, missing cyrillic keyboard layout on this PC. Looks like the problem could be adressed by graph theory. Please have a look at this classic problem
184
|
5
|
0
А что если тот кто таки проведет кривую получит нобелевскую премию? :s14:
33553
|
754
|
0
karl)marx( пишет:
да ты охуел
33553
|
754
|
0
Flashebanutiy пишет:
ну плюс точно получит :s49:
33553
|
754
|
0
karl)marx( пишет:
и как из этого построить граф? что бы понять сколько там вершин и можно ли решить эту куйню :s27:
184
|
5
|
0
_The_ProRok_ru пишет:
Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез.
Может эта задачка и есть нерешенная проблема? :s40: Типа по математике нарисовать можно, а на практике нет. :s29:
33553
|
754
|
0
ну исходя из моего "божественно нарисованного наглядного графа" задача не решаема
5162
|
145
|
0
Flashebanutiy пишет: да нет же, это доказывается. карл-маркс уже по делу всё написал по идее)
короче, суть в том, что чтобы задача была решаемой - граф должен содержать эйлеров путь.
граф содержит 4 вершины - 3 квадрата и 1 большую внешную вершину. вершины буду называть I, II, III, IV, первые 3 - это перечисление квадратов как при чтении текста.
построю все связи подробно прямо тут:
I (10) IV
I (11) IV
I (12) IV
I (2) II
I (3) III
II (1) IV
II (7) IV
II (8) IV
II (6) III
II (2) I
III (4) IV
III (5) IV
III (9) IV
III (3) I
III (6) II
IV (10) I
IV ()
... можно недописывать, я уже вижу что нельзя.
потому что 3 вершины содержат нечетную степень(количество исходящих рёбер в графе обыкновенном).
объясняю на пальцах почему: рассмотрим граф, в котором эйлеров путь существует. рассмотрим сам путь v1 -> v2 -> ... -> vN. каждая стрелочка прибавляет 1 к степени вершины до неё, и после неё. т.е. даже если вершины повторяются в пути, все вершины кроме v1 и vN должны иметь чётную степень(в неё столько же вошли, столько вышли, по разным рёбрам). тогда либо только 2 вершины содержат нечётную степень(из одной начали, в другой закончили), либо ни одной(тогда это эйлеров цикл, можно начинать из любого места и всегда придёшь в ту же точку)
5162
|
145
|
0
_The_ProRok_ru пишет: БЛЯТЬ ГОВНО НАДО БЫЛО СНАЧАЛА КОММЕНТЫ ЧИТАТЬ :s3: :s3:
5162
|
145
|
0
ну ладно, хоть доказательство на пальцах объяснил.
41000
|
1444
|
0
азаза
ну вы лалки
6798
|
224
|
0
Прямую или отрезок?
5162
|
145
|
0
reps)naneri пишет: отрезок :s14:
33553
|
754
|
0
Clockware пишет:
:s31: