рекурсия- разбиение и сборка квадрата |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
рекурсия- разбиение и сборка квадрата |
Екатерина7 |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
помогите, пожалуйста, разобраться с задачей
Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток. Полученные прямоугольные куски перемешаны. Требуется из заданных прямоугольников снова составить квадрат. Квадрат не обязательно должен быть составлен из прямоугольников в том же порядке, в каком он разрезан. При сборке прямоугольники можно поворачивать. (число N не задано, можно брать любое) |
Lapp |
Сообщение
#21
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
функция для определения пересечений есть, остаётся перебирать?) Перебирать что? Входных данных пока еще нет..Можно, конечно, полагать, что это забота не наша, а проверяющего задание, но как тогда отлаживаться? И, в любом случае, как ни крути, нужно все же договориться о формате ввода.. Я все же предлагаю подумать о том, как подготовить (ну и в какой форме сохранить) входной набор прямоугольников. И еще одна просьба: не гоните, дайте автору темы хотя бы отреагировать и задать вопросы.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
Сообщение
#22
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Кать, если тебе не актуально уже, ты скажи.
А если такими темпами, то и к следующему пнд не будет готово. С чем загвоздка? Если что-то неясно - спрашивай. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
Сообщение
#23
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
да,Lapp, с математикой все понятно.. да и с кусочком программы вроде бы тоже..)
Добавлено через 2 мин. извиняюсь,у меня пару дней с инетом проблемы были,не могла ответить..(( все нормально..вроде бы понятно.. все остается так же актуальным.. Добавлено через 9 мин. входные данные- параметры прямоугольников,как говорил Unconnected.так? |
Lapp |
Сообщение
#24
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
входные данные- параметры прямоугольников,как говорил Unconnected.так? Да, так. Вопрос, как. По условию, у нас должен быть на входе набор прямоугольников, из которого заведомо можно построить квадрат, поскольку "Лист бумаги в клетку квадратной формы размера NxN произвольно разрезан на прямоугольные части, каждая из которых имеет целое число клеток". Если такой набор приложен к условию, то наша задача облегчается (Катя, ты спроси преподавателя - может, у него есть такой). Если нет - то надо его сначала сделать, то есть нам нужно имплементить способ разрезания квадрата. Либо.. У набора, из которого можно построить квадрат есть одно обязательное свойство: сумма всех клеток всех его прямоугольников равна количеству клеток в квадрате, то есть N*N. Но это не есть достаточное условие. Предположим, мы создали набор прямоугольников (со стороной не больше, чем N), и сумма их площадей (клеток) равна N*N (это сделать нетрудно - легче, чем разрезать). Далее, наша будущая программа попытается собрать из них квадрат. Если у нее это получается, то она выдает ответ: "квадрат собрать можно" (и, может быть, порядок сборки). Если же все ее попытки заканчиваются ничем. то она говорит: "квадрат собрать невозможно". То, что я предложил выше - это видоизменение условия. Я не знаю, насколько такие зменения допустимы. Поэтому я предлагаю: Катя, спроси преподавателя: 1. существует ли набор входных данных для проверки? Если да, то где его взять и в каком он формате. 2. если нет, то возможно ли вместо повторной сборки просто брать случайный набор (с суммарной площадью N*N) и говорить, можно ли из него собрать квадрат (с выдачей порядка сборки в случае удачи). Либо спроси, либо сама скажи, что делать, потому что от этого зависит программа. Ok? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
Сообщение
#25
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
набора входных данных нет.. думаю, что можно брать вместо повторной сборки просто случайный набор..
|
Lapp |
Сообщение
#26
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
думаю, что можно брать вместо повторной сборки просто случайный набор.. Хорошо. Ну, давай тогда делать случайный набор. Создать и записать в файл square.dat в таком формате: длина и ширина на одной строке; строк стролько, сколько прямоугольников.Сможешь сделать? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
Сообщение
#27
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
если честно, несовсем:( у меня с этим возникли трудности.. вооюще затрудняюсь начать..
|
Lapp |
Сообщение
#28
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Ну, начать я тебе помогу
var Можешь продолжить? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Екатерина7 |
Сообщение
#29
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
наверно нет.. затрудняюсь.. в написанном могу разобраться.. а так..
|
Unconnected |
Сообщение
#30
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Екатерина7, ты какой курс, если не секрет?
Просто, видимо, у тебя практики мало было. Очень мало. А тут раз - и рекурсия с квадратами... -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Екатерина7 |
Сообщение
#31
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
не секрет- 4-й.. да.. нас плохо научили программир.. первые курсы особенно.. вот так все и пошло.. сейчас более менее с остальным стараюсь разбираться, а вот эту задачу не могу сделать..(
|
Екатерина7 |
Сообщение
#32
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
|
klem4 |
Сообщение
#33
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Перебор с рекурсией, код неважнецкий, но работает
{$mode TP} -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Lapp |
Сообщение
#34
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Перебор с рекурсией, код неважнецкий, но работает Круто, Клёма! А как ты задаешь начальные данные?Я седни попожжее выложу свой тож тогда. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
klem4 |
Сообщение
#35
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Код f[1]._new(2,1,'a'); f[2]._new(2,2,'b'); ... это массив "кусочков", параметры - длина, ширина и буква. Код bf._new( 4 ); // собственно объект - поле, параметр - размер (4х4) writeln(bf.fill(f, 0)); // заполнение поля, вернет true если можно заполнить из кусочков, хранящихся в f -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Unconnected |
Сообщение
#36
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
А теперь возникает вопрос: с какой вероятностью Екатерине7 поверят, что она это писала сама?
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Екатерина7 |
Сообщение
#37
|
Новичок Группа: Пользователи Сообщений: 43 Пол: Женский Репутация: 0 |
поверят, я постараюсь разобраться))
Добавлено через 3 мин. проверим потом на практике с какой вероятностью)) |
Lapp |
Сообщение
#38
|
Уникум Группа: Пользователи Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
проверим потом на практике с какой вероятностью)) Если бы я принимал, она бы стремилась к нулю )). И все же желаю успехов (особенно в "разобраться").Выкладываю свой код тоже. Я хотел выделить подготовку начальных данных в отдельную прогу и писать их в файл, но не сделал.. uses Катя, ты спрашивай больше. Не стесняйся Добавлено через 4 мин. klem4, зачем отключил $R ? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
volvo |
Сообщение
#39
|
Гость |
Цитата klem4, зачем отключил $R ? Ну, так со включенным-то работать не будет Вылетит за границы массива и все, ко второму элементу уже не обратиться. А я ведь этот случай описывал специально, в "Как не надо писать программы"... |
klem4 |
Сообщение
#40
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
К сожалению не знаю как еще дин. массивы в таком виде с fpc подружить
-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Текстовая версия | 12.05.2024 22:22 |