Минимальное множество прямых (рекурсия с возвратом) |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Минимальное множество прямых (рекурсия с возвратом) |
Даша |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм.
|
Lapp |
Сообщение
#2
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Всем доброго времени суток! Прошу помочь со следующей задачей: найти минимальное множество прямых, проходящих через все заданные точки. То есть заданы координаты точек и ответом должно быть число прямых. Не знаю как организовать перебор всех вариантов, очень прошу написать хотя бы в общем виде сам алгоритм. И это нужно сделать с помощью рекурсии? В целом, ничего сложного, но есть непонятные моменты..Допустим, точки заданы массивом (то есть, упорядочены). Делаешь процедуру, которая делает две вещи (либо/либо, как обычно в рекурсии): 1. Если точек 2 или больше, то берет следующую точку и проводит все прямые через нее и все остальные и добавляет их к списку, если их там еще нет; после этого "выкидывает" эту тучку из массива и вызывает себя же. 2. Если точка только одна - выходит. Таким образом будут проведены все прямые. Смысл твоей задачи состоит в том, чтоб отсеять повторы, поэтому нужно всякий раз проверять, не включена ли прямая уже в список. А для этого нужно уметь уметь сравнивать прямые. Например, если две прямые заданы в виде y=ax+b, то они одинаковые, если a1 и b2 соответственно равны a2 и b2. Тут возникает оджин вопрос: как заданы координаты точек? Это действительные числа или целые? Действительные сравнивать несколько труднее.. Говори, что непонятно. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Даша |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Цитата Если точек 2 или больше, то берет следующую точку и проводит все прямые через нее и все остальные и добавляет их к списку, если их там еще нет; Вот это как раз непонятно. Как организовать перебор ВСЕХ возможных вариантов расположения прямых? Координаты заданы целыми числами. |
Lapp |
Сообщение
#4
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Вот это как раз непонятно. Как организовать перебор ВСЕХ возможных вариантов расположения прямых? Так рекурсия же! Она все тебе переберет. Ты только сделай, как я написал выше. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#5
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Даша, я так понимаю, что у тебя особого прогресса нет - да?
Я вот набросал прожку. Посмотри ее.. Если честно, она мне не нравится. Что-то я к вечеру не смог ничего лучше придумать.. Рекурсия там в результате оказалась притянута за уши. Но все же она есть, и прога, вроде, считает. Я проверил на простых конфинурациях до 6 точек )). Проверь получше, если найдешь ошибки - говори. const Входные данные задаются в текстовом файле dasha.dat, по одной точке на строку. Координаты можно задавать действительными числами, но я пока только целые давал. Вот пример: 0 0 Заметь, что в конце НЕ ДОЛЖНО быть пустых строк (то есть курсор стрелками дальше последней строки не должен заходить). На этом примере ответ 8. Пиши, что непонятно, я попробую объяснить . -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Даша |
Сообщение
#6
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Прощу прощения за то что долго не отвечала, не было возможности. Но вы правы, прогресса нет, ибо хотела задать вопрос: понятно что рекурсия будет перебирать все возможные варианты, но непонятно как она будет брать, допустим, четыре точки. Ведь у нас могут лежать четыре точки на одной прямой. И, например, программа возьмет первые две, а затем две другие. Получается надо будет каждый раз где нибудь в массиве запоминать K и B, а затем при высчитывании очередных коэффициентов сравнивать их с уже посчитанными?
За код больщущее спасибо . Только вы наверное не до конца разобрались в условии. Необходимо найти МИНИМАЛЬНОЕ множество прямых, на которых будут лежать все точки. То есть, например, для ваших точек ответ должен быть не 8, а 2. Но, насколько я понимаю, необходимо просто в ваш код добавить дополнительную переменную min, и где нибудь в программе переменную Lines каждый раз сравнивать с min? |
Lapp |
Сообщение
#7
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Прощу прощения за то что долго не отвечала, не было возможности. Но вы правы, прогресса нет, ибо хотела задать вопрос: понятно что рекурсия будет перебирать все возможные варианты, но непонятно как она будет брать, допустим, четыре точки. Ведь у нас могут лежать четыре точки на одной прямой. И, например, программа возьмет первые две, а затем две другие. Получается надо будет каждый раз где нибудь в массиве запоминать K и B, а затем при высчитывании очередных коэффициентов сравнивать их с уже посчитанными? Рекурсия - это в некотором смысле способ хранения большого множества параметров в стеке. Хотя, можно это сочетать и с глобальными массивами.Цитата За код больщущее спасибо . Только вы наверное не до конца разобрались в условии. Необходимо найти МИНИМАЛЬНОЕ множество прямых, на которых будут лежать все точки. То есть, например, для ваших точек ответ должен быть не 8, а 2. Но, насколько я понимаю, необходимо просто в ваш код добавить дополнительную переменную min, и где нибудь в программе переменную Lines каждый раз сравнивать с min? Да, ты права, я неверно понял условие.. Я думал, что надо провести прямую через каждую пару точек, но при этом не учитывать повторения. Оказывается, все иначе..Нет, простой доделкой кода тут не обойтись. Нужно менять всю схему.. Надеюсь, можно будет по крайней мере использовать функции Eq и Aligned. Я немного еще освобожусь и попробую сделать (если никто раньше не сделает)).. А задачка оказалась интереснее, чем я думал! )) -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#8
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Вот. Выстругал буратинку )).
Но снова она мне не по нутру.. Думаю, можно сделать намного красивее.. Может, кто-нить сделает. Я тоже еще подумаю.. Да, как я сказал, пришлось переделать всю схему перебора. Коротко могу изложить так.. Один вызов Draw (от слова рисовать линию) рисует одну линию в цикле по всем парам точек (в двойном цикле). Нарисовав линию, он проверяет, какие точки она еще задела. Все задетые точки заносит в массив Co (Covered). Затем вызывает вторую (следующую) копию. Когда массив Co заполнен до конца (это проверяется при входе в Draw), она смотрит, сколько проведено линий (Lin). Если это число меньше, чем MinLin - обновляет MinLin. Вот, примерно так. Ты посмотри прогу и задавай конкретные вопросы. Работает она, похоже, верно, но.. оооочень медленно. То есть массив из 9 точек обсчитывался на моей тачке почти минуту. При этом время растет с числом точек стремительно (думаю, приблизительно по факториалу). Поэтому 10 точек будет считаться гораздо дольше.. Ускорить можно оптимизацией (возможностей куча), но от характера зависимоти не уйти, думаю (но подумаю еще)). Короче, вот тебе код. Разбирайся и задавай вопросы. const Формат входного файла тот же. Вот на этом выдает 3. 0 0 -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Даша |
Сообщение
#9
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Еще раз выражаю огромную благодарность
По коду в принципе всё понятно, за исключением e= 1e-7; понятно что это константа, но почему она так задается, и вообще про подобное задание констант, если можно, расскажите, а то в университете про такое не рассказывали) От роста времени думаю избавиться не удастся, хотя наверное, оптимизировать немного всё же можно, но для меня главное понимание принципа работы подобного алгоритма, а это с успехом достигнуто). И еще небольшой вопросик не совсем в тему: мне необходимо сделать эту задачу на Delphi в визуальной среде, но решила для начала основу отладить в Паскале, а потом перенести всё это в визуальную среду. Не подскажите где можно прочитать про работу с компонентом TImage в Delphi 7? Мне необходимо будет нарисовать все точки, и собственно, сами прямые, которые покрывают все эти точки. |
-TarasBer- |
Сообщение
#10
|
Гость |
А разве для быстрого переноса Паскальных программ на Дельфи не придумали модуль, который реализует все процедуры модуля Graph через создание формы нужного размера и рисование на ней?
|
Lapp |
Сообщение
#11
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
По коду в принципе всё понятно, Даша, не обижайся, но.. не верится! )) Ответь на пару контрольных вопросов, чтоб меня в этом убедить..1. Зачем каскадный IF (строки 28-37) в функции Aligned? 2. Зачем "if (i<>j) and not Co[j]" (оба условия) в строке 59? 3. Почему Co[i] вычисляется через OR с самим собой (строка 64)? 4. ... Если ты можешь ответить - тогда да, понятно )). Если нет - то нет.. (( Цитата за исключением Это ОООЧЕНЬ странно, что вам не рассказывали про константы. Именованные константы - это очень распространенная и полезная концепция программирования. Я объясню на прмере..e= 1e-7; понятно что это константа, но почему она так задается, и вообще про подобное задание констант, если можно, расскажите, а то в университете про такое не рассказывали) Допустим, ты делаешь прогу.. ну, скажем, модель дорожного движения. Там у тебя машинки ездят всякие.. И у них есть такой параметр, как скорость - у каждого своя в каждый момент времени. Эта скорость должна контролироваться на предмет не превышения максимальной допустимой (я правлиьно сказал? короче, speed limit)). Эта проверка осуществляется в разных местах программы. Speed limit в городе - 60 км/ч. Ты можешь в каждой проверке употребить непосредственно это число, типа так: if (Speed>60) and CopIsAround then Cite; Но завтра Дума (депутаты которой очень любят кататься выпускать законы на эту тему) поднимет этот предел до 70 (или опустит до 50, что более вероятно). И тогда тебе придется отыскивать ВСЕ проверки и заменять в них 60 на 70 (или 50). Причем, нет гарантии, что ты что-то не пропустишь (или автоматом не заменишь название улицы "60 Street" на "70 Street")). Чтобы облегчить себе задачу и избежать таких казусов, существуют те самые константы. Ты объявляешь в разделе констант: const А потом, если потребуется изменить этот предел, тебе нужно это сделать только в одном месте - причем, оно в начале проги! А если одновремено нужно изменить и предел скорости на автобане - пожалуйта, константа FreewaySpeedLimit на следующей строчке! Что происходит на самом деле на этапе компиляции (в Pascal)? Реально компилятор НЕ ЗАВОДИТ дополнительную память под константу (как под переменную), а просто подставляет вместо нее ее реальное значение при каждом вхождении. То есть, грубо говоря, скомпилированный код (выполняемый, то есть exe) будет неотличим в вариантах С константами и БЕЗ них. Я понятно объяснил? По первости может показаться, что это пустая трата времени и тайпинга, но потом увидишь, что константы экономят очень много - как времени, так и всего остального. К тому же, если давать им значащие имена, то это сильно поможет тебе ориентироваться в коде. В данном случае, константа e - это сокращение от Epsilon. Смысл ее - точность при стравлении действительных чисел. Ты же знаешь, что компьютер производит вычисления с определенной точностью. И в результате вычислений, например, Sqrt(Sqr(3)+Sqr(4)), получится не 5, а типа 5.0000002 или 4.9999997. Эти ответы - правильные. Но если ты будешь проверять их правильность так: Correct:= Res=5; - то ты получишь отрицательный ответ (т.е., неправильно). Поэтому нужно сравнивать так: Correct:= Abs(Res-5)<e; , где e - это та самая точность. Именно это я и делаю в функции Aligned при проверке попадания точки на прямую. Цитата От роста времени думаю избавиться не удастся, хотя наверное, оптимизировать немного всё же можно, но для меня главное понимание принципа работы подобного алгоритма, а это с успехом достигнуто). Оч.хор. ))Попробуешь оптимизировать? Цитата И еще небольшой вопросик не совсем в тему: мне необходимо сделать эту задачу на Delphi в визуальной среде, но решила для начала основу отладить в Паскале, а потом перенести всё это в визуальную среду. Не подскажите где можно прочитать про работу с компонентом TImage в Delphi 7? Мне необходимо будет нарисовать все точки, и собственно, сами прямые, которые покрывают все эти точки. Во первых, компонент TImage тут не совсем при чем.. Для рисования с использованием примитивов (точки, линии..) тебе лучше для начала посмотреть в сторону TCanvas, мне кажется, чтобы прочувствовать все на низком уровне доступа к окну. А где прочитать - думаю, в книжке )). В России книг по Delphi на порядок больше, чем тут, так что конкретнее советовать не буду.И еще: ты права, это выходит за пределы и темы, и раздела. Создай новую тему в разделе про Delphi, если тебе нужна помощь. А разве для быстрого переноса Паскальных программ на Дельфи не придумали модуль, который реализует все процедуры модуля Graph через создание формы нужного размера и рисование на ней? А зачем? Чтоб растянуть удовольствие? )) Если чел начал изучать Delphi - пусть делает именно это, а не "как в Delphi рисовать _под_TP" ))-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
-TarasBer- |
Сообщение
#12
|
Гость |
> А зачем? Чтоб растянуть удовольствие?
Для быстрого переноса Паскальных программ, и чтобы при этом не забивать голову ВинАПИ и не портить себя формошлёпством. > Это ОООЧЕНЬ странно, что вам не рассказывали про константы. Именованные константы - это очень распространенная и полезная концепция программирования. Я объясню на прмере.. Мне кажется, она удивлена экспоненциальной записью. На самом деле, 1e-7 это 10^(-7) = 1/10 000 000 То есть если в конце числа стоит "е" а потом ещё число, значит то, что до этого "е" надо умножить на 10 в степени того, что после этого "е". Например: 2е-3 = 2*10^(-3) = 2/1000 = 0.002 1.0034e4 = 1.0034 * 10^4 = 1.0034 * 10000 = 10034 |
Даша |
Сообщение
#13
|
Новичок Группа: Пользователи Сообщений: 20 Пол: Женский Репутация: 1 |
Что же, попробую ответить на ваши вопросы:
1. Чтобы при выполнении первого условия, т.е a.x=b.x, второе условие a.x=c.x не проверялось 2. Чтобы брать те точки, которые не были задеты массиве Co[i] и Со[j] 3. Вот тут да, честно, не очень понятно, хотелось бы объяснений немного. Цитата Попробуешь оптимизировать? Ды с удовольствием бы попробовала, задача ведь достаточно интересная, но, к сожалению, сейчас времени очень не много, необходимо будет еще до конца весны сделать задачу на сильноветвящиеся деревья. Так что к этой я вернусь обязательно, но несколько позже) Цитата Мне кажется, она удивлена экспоненциальной записью. Именно! Вот она меня и смутила. Про именованные константы, естественно, рассказывали, но про то что их можно записывать в таком виде - нет. Хотя про экспоненциальную запись тоже рассказывали, но в голову не пришло что так и константы можно записывать. |
Lapp |
Сообщение
#14
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Для быстрого переноса Паскальных программ, и чтобы при этом не забивать голову ВинАПИ и не портить себя формошлёпством. Я сомневаюсь, чтоб у Даши было много програм для переноса.. А к Graph'овская графике тоже не следует себя приучать, мне кажется.Цитата Мне кажется, она удивлена экспоненциальной записью. Садовая моя башка . Я все не так понял..1. Чтобы при выполнении первого условия, т.е a.x=b.x, второе условие a.x=c.x не проверялось Это ты просто описала действие поля else в операторе if. Ну и что? А зачем нужно это? С точки зрения алгоритма решения.Цитата 2. Чтобы брать те точки, которые не были задеты массиве Co[i] и Со[j] Я не понял, что ты хотела сказать. Не задеты в массиве? Но почему присутствуют индексы i и j?.. Выражайся точнее, пожалуйста.Цитата 3. Вот тут да, честно, не очень понятно, хотелось бы объяснений немного. Будет не объяснение, а совет. Если тебе что-то непонятно в программе - экспериментируй. Возьми очень простую конфигурацию входных данных (сначала просто две точки, если не прояснится - 3, и т.д.) и попробуй УБРАТЬ условие, которое тебе неясно, что делает. И посмотри, как это отразится на результатах работы программы. Проанализируй эти результаты.Цитата Ды с удовольствием бы попробовала, .. Ладно, я не настаиваю )). Хорошо, что у тебя вообще есть интерес.-------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Текстовая версия | 4.05.2024 19:21 |