Здравствуйте, m.a.g., Вы писали:
MAG>Здравствуйте, m.a.g., Вы писали:
MAG> MAG>>Сводится к поиску Эйлерова пути в графе. Не существует при наличии более чем двух вершин нечетной степени, что так для вышеприведенного ри MAG>>сунка. Такого обхода нет.
MAG>Ой. Пересечь, а не нарисовать.... Посыпаю свою голову пеплом.
Не надо посыпать! От этого не легче.
Возможный путь лежит на "двойственном" к исходному (правильно?) графе, и называется действительно Эйлеров путь. У этого графа 6 вершин (одна внешняя) и у 4-х из них число выходящих ребер нечетно. И соответственно — решений нет.
Поэтому, привожу решение!
Сначала внимательно прочитаем условие...
"Требуется одной линией, не отрывая карандаша от бумаги, пересечь... "
... и подсказку...
"И все таки решение есть
Возможно оно не совсем простое и не лежит на поверхности."
Вот одно из возможных решений
Рисовать начинаем по красной линии из среднего нижнего прямоугольника, поднимаемся до зеленой линии, загибаем бумагу сверху так, чтобы её край совпадал с зелёной линией. Синий отрезок проходит по загнутому краю, затем снова идем по красной линии. Когда снова доходим до зеленой линии, разгибаем бумагу и завершаем по коричневой линии.
Здравствуйте, flatch, Вы писали:
F>Дана такая фигура:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
Здравствуйте, MAN2, Вы писали:
MAN>Здравствуйте, flatch, Вы писали:
F>>Дана такая фигура:
F>> F>>
F>>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>>Решение точно есть.
Решений нет!
В рисунке есть 3 области (широкие прямоугольники), с 5-ю отрезками.
Каждый из которых нужно пересечь.
Линия, проходящая через данную область пересекает 2 отрезка.
Значит есть 2 линии, проходящие через данную область и одна, не проходящая, то есть конец или начало линии.
Здравствуйте, flatch, Вы писали:
F>Дана такая фигура:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
Здравствуйте, flatch, Вы писали:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
Сводится к поиску Эйлерова пути в графе. Не существует при наличии более чем двух вершин нечетной степени, что так для вышеприведенного ри
сунка. Такого обхода нет.
Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
Здравствуйте, flatch, Вы писали:
F>Дана такая фигура:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
MAG>Сводится к поиску Эйлерова пути в графе. Не существует при наличии более чем двух вершин нечетной степени, что так для вышеприведенного ри MAG>сунка. Такого обхода нет.
Ой. Пересечь, а не нарисовать.... Посыпаю свою голову пеплом.
Здравствуйте, m.a.g., Вы писали:
MAG>Сводится к поиску Эйлерова пути в графе. Не существует при наличии более чем двух вершин нечетной степени, что так для вышеприведенного ри MAG>сунка. Такого обхода нет.
И все таки решение есть
Возможно оно не совсем простое и не лежит на поверхности.
Здравствуйте, MAN2, Вы писали:
MAN>Здравствуйте, flatch, Вы писали:
F>>Дана такая фигура:
F>> F>>
F>>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>>Решение точно есть.
Shit... Не заметил... Один отрезок всё-таки 2 раза пересёк...
Здравствуйте, flatch, Вы писали:
F>Дана такая фигура:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
Вроде бы решил, только как сюда картинку добавить?
Здравствуйте, Int, Вы писали:
Int>Здравствуйте, flatch, Вы писали:
F>>Дана такая фигура:
F>> F>>
F>>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>>Решение точно есть.
Int>Вроде бы решил, только как сюда картинку добавить?
Закачиваешь картинку куда-нибудь, а затем пишешь её урл в [iтg] и [/img]
Только проверь все отрезки, я же говорил, что решений нет
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, m.a.g., Вы писали:
MAG>>Здравствуйте, m.a.g., Вы писали:
MAG>> MAG>>>Сводится к поиску Эйлерова пути в графе. Не существует при наличии более чем двух вершин нечетной степени, что так для вышеприведенного ри MAG>>>сунка. Такого обхода нет.
MAG>>Ой. Пересечь, а не нарисовать.... Посыпаю свою голову пеплом.
M>Не надо посыпать! От этого не легче. M>Возможный путь лежит на "двойственном" к исходному (правильно?) графе, и называется действительно Эйлеров путь. У этого графа 6 вершин (одна внешняя) и у 4-х из них число выходящих ребер нечетно. И соответственно — решений нет.
M>Поэтому, привожу решение!
M>Сначала внимательно прочитаем условие... M>"Требуется одной линией, не отрывая карандаша от бумаги, пересечь... "
M>... и подсказку...
M>"И все таки решение есть M>Возможно оно не совсем простое и не лежит на поверхности."
M>Вот одно из возможных решений M>
M>Рисовать начинаем по красной линии из среднего нижнего прямоугольника, поднимаемся до зеленой линии, загибаем бумагу сверху так, чтобы её край совпадал с зелёной линией. Синий отрезок проходит по загнутому краю, затем снова идем по красной линии. Когда снова доходим до зеленой линии, разгибаем бумагу и завершаем по коричневой линии.
M>(Моя сама решила )
Ты хочешь сказать, что синий отрезок не пересекает верхний левый отрезок ?
Здравствуйте, MAN2, Вы писали:
M>>Вот одно из возможных решений M>>
M>>Рисовать начинаем по красной линии из среднего нижнего прямоугольника, поднимаемся до зеленой линии, загибаем бумагу сверху так, чтобы её край совпадал с зелёной линией. Синий отрезок проходит по загнутому краю, затем снова идем по красной линии. Когда снова доходим до зеленой линии, разгибаем бумагу и завершаем по коричневой линии.
M>>(Моя сама решила )
MAN>Ты хочешь сказать, что синий отрезок не пересекает верхний левый отрезок ?
Нет. Синяя линия идет по загнутой части листа, которая закрывает на это время часть исходной фигуры.
Здравствуйте, mogadanez, Вы писали:
MAN>>
M>разрешите слегка подправить ваше решение
M>
M>при желании можно и петлю слева снизу развернуть, чтобы себя не пересекать.
M>по моему чудненько
уже увидел.... видимо всетаки нужно пересекать в углах сразу несколько отрезков, как ниже кто-то предложил.
автор ведь сказал что решение не совсем тривиальное
Здравствуйте, flatch, Вы писали:
F>Дана такая фигура:
F> F>
F>Требуется одной линией, не отрывая карандаша от бумаги, пересечь все отрезки, существующие в данной фигуре (16 штук). Причем, никакой отрезок нельзя пересекать дважды.
F>Решение точно есть.
Мне кажется что задача действ. сводится к отысканию Эйлерова пути на графе. Явный граф можно получить взяв области (их 6) за вершины, а границы — за ребра. Соотв решения нет ибо три больших прямоугольника — это вершины с нечетными степенями.
Здравствуйте, IO, Вы писали:
F>>Решение точно есть.
IO>Мне кажется что задача действ. сводится к отысканию Эйлерова пути на графе. Явный граф можно получить взяв области (их 6) за вершины, а границы — за ребра. Соотв решения нет ибо три больших прямоугольника — это вершины с нечетными степенями.
Четыре вершины с нечетными степенями — одна находится снаружи исходной фигуры и у неё степень 9.
Здравствуйте, mogadanez, Вы писали:
M>>Чудненько, но таки неправильненько
M>уже увидел.... видимо всетаки нужно пересекать в углах сразу несколько отрезков, как ниже кто-то предложил. M>автор ведь сказал что решение не совсем тривиальное
Т.е. линия должна быть толстенькая?
Тогда, упрощаем даже такое решение: саму линию делаем толстой (до неприличия), а саму фигуру — ма-а-ленькой — ма-а-ленькой... И с левого верхнего угла листа в правый нижний, с размахом и нажимом...
M>Т.е. линия должна быть толстенькая?
M>Тогда, упрощаем даже такое решение: саму линию делаем толстой (до неприличия), а саму фигуру — ма-а-ленькой — ма-а-ленькой... И с левого верхнего угла листа в правый нижний, с размахом и нажимом...
я имелл ввиду такое:
какие отрезки мы пересекаем в данном случае? 3 или ни одного?
Здравствуйте, mogadanez, Вы писали:
M>>Т.е. линия должна быть толстенькая?
M>>Тогда, упрощаем даже такое решение: саму линию делаем толстой (до неприличия), а саму фигуру — ма-а-ленькой — ма-а-ленькой... И с левого верхнего угла листа в правый нижний, с размахом и нажимом...
M> M>я имелл ввиду такое: M> M>какие отрезки мы пересекаем в данном случае? 3 или ни одного?
Отрезок (в отличии от интервала) включает в себя свои концы.
Так что все 3
Здравствуйте, flatch, Вы писали:
4>>>может быть так:
4>>>
M>>хе... интересно, в задании ничего не говорится про пересечения в углах. как это трактовать? =)
F>Неее, так нельзя . И толстыми линиями, как кто-то предлагает вверху — тоже не пойдет.
Здравствуйте, 4mbi3nt, Вы писали:
4>а ты хоть сам правильное решение знаеш?
Я знаю решения не существует.
Ели только не использовать какой нибудь чит типа проведения линии через стыки отрезков хотя трудно сказать можно ли это назвать решением.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Посыпаю свою голову пеплом.
Евгений
