Минимальное множество прямых (рекурсия с возвратом) |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Минимальное множество прямых (рекурсия с возвратом) |
Даша |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.
|
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Вот. Выстругал буратинку )).
Но снова она мне не по нутру.. Думаю, можно сделать намного красивее.. Может, кто-нить сделает. Я тоже еще подумаю.. Да, как я сказал, пришлось переделать всю схему перебора. Коротко могу изложить так.. Один вызов Draw (от слова рисовать линию) рисует одну линию в цикле по всем парам точек (в двойном цикле). Нарисовав линию, он проверяет, какие точки она еще задела. Все задетые точки заносит в массив Co (Covered). Затем вызывает вторую (следующую) копию. Когда массив Co заполнен до конца (это проверяется при входе в Draw), она смотрит, сколько проведено линий (Lin). Если это число меньше, чем MinLin - обновляет MinLin. Вот, примерно так. Ты посмотри прогу и задавай конкретные вопросы. Работает она, похоже, верно, но.. оооочень медленно. То есть массив из 9 точек обсчитывался на моей тачке почти минуту. При этом время растет с числом точек стремительно (думаю, приблизительно по факториалу). Поэтому 10 точек будет считаться гораздо дольше.. Ускорить можно оптимизацией (возможностей куча), но от характера зависимоти не уйти, думаю (но подумаю еще)). Короче, вот тебе код. Разбирайся и задавай вопросы. const Формат входного файла тот же. Вот на этом выдает 3. 0 0 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 3.05.2024 4:30 |