Задачи на перестановки |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Задачи на перестановки |
Unconnected |
15.01.2010 22:08
Сообщение
#1
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Привет всем.
Меня заинтересовала задача из соседней темы, про перестановки в числах. Цитата Задача 4 "Сумма двух чисел" Имя входного файла: sum.in Имя выходного файла: sum.out Максимальное время работы на одном тесте: 2 секунды Максимальный объем используемой памяти: 64 мегабайта Заданы три числа: a, b, c. Необходимо выяснить, можно ли так переставить цифры в числах a и b, чтобы в сумме получилось c. Формат входных данных Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом. Формат выходных данных Если искомая перестановка цифр возможна, необходимо вывести в выходной файл слово YES, в противном случае — выведите слово NO. При положительном ответе необходимо вывести во второй строке выходного файла число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей. Числа в строке разделены пробелом. Примеры входных и выходных файлов sum.in sum.out 12 31 25 ***YES*** **********12 13*** 12 31 26 ***NO*** Вот что я сделал: const m=6; Мой алгоритм перестановок (для трёхзначных чисел) основан на том, что если в числе переносить первую цифру в конец, пока не получится исходное число, а потом поменять 2 и 3 цифры местами и сделать то же самое, то получатся все перестановки.. Например: 123 231 312 меняем, 132 321 213 Получилось 6 перестановок, как раз 3!, как и должно быть. Моя программа почему-то не заполняет корректно массив (процедура Generate). Сообщение отредактировано: Unconnected - 18.01.2010 13:21 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Unconnected |
17.01.2010 15:28
Сообщение
#21
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Цитата А рекурсия - дубовый метод, много мозгов не требует )). К моим мозгам она чересчур требовательна)) Короче, я попробовал для начала понять, что она делает эта рекурсия, расставил примерные комментарии.. const Мне понравилась строка Ord(s[i])-48, получается, это быстрый способ перевести строку с цифрой в цифру. Куда мне анализировать, почему время не увеличивается - я в механизм работы въехать не могу..)) Хотя, меня преследует ощущение, что в цикле else with a[n] do for i:=1 to Length(s) do if not (i in d) then begin всегда будет обрабатываться только 1ый символ, но это мои интуитивные домыслы конечно)) К ним я пришёл, расписав на бумаге значения переменных при двух двузначных слагаемых. Наверное, ошибся где-то. Запрос. На комментарии:) Цитата И что, понадобилось передавать num? Не понадобилось, так лучше. Сообщение отредактировано: Unconnected - 18.01.2010 0:52 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Unconnected |
18.01.2010 0:54
Сообщение
#22
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
//подновил время, правил пост
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
18.01.2010 4:25
Сообщение
#23
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
К моим мозгам она чересчур требовательна)) Ошибаешься; ниже убедишься.Цитата Короче, я попробовал для начала понять, что она делает эта рекурсия, расставил примерные комментарии.. От комментариев мало толку, если они просто выражают словами то, что написано на языке. Старайся вложить в комменты больше смысла. Я понимаю, что тут ты не мог это сделать, это на будущее для собственных прог )).Цитата Куда мне анализировать, почему время не увеличивается - я в механизм работы въехать не могу..)) Для этого не нужно глубоко въезжать в алгоритм. С этого и начнем..Каков бы ни был олгоритм - это все равно перебор. Согласен? Этого знания достаточно. На первый взгляд кажется, что такие совпадения (описанные в условии, когда сумма равна заданному числу) должны быть достаточно редки. И поэтому когда я подготавливал входные данные, я делал так: - пишу несколько слагаемых (10 штук, для этого нужно заменить тип integer на LongInt в слагаемых и сумме); - считаю их сумму и приписываю ее сзади; - перемешиваю цифры в слагаемых. Такой способ, конечно, гарантирует ответ YES при правильной работе программы. После этого я запускал прогу.. и она выдает ответ через мгновение. Почему? Во-первых, я заметил, что ответ не тот, который я поготовил, а другой. Я решил: повезло, оказался еще один ответ! - и немного изменил данные (слагаемые и сумму, чтоб снова гарантировать ответ). И снова аналогичный результат. Вот тогда я, наконец, дал себе труд подумать минуту.. Собственно, минуты не потребовалось. У меня 10 слагаемых, каждое от 2 до 4 знаков. Всего примерно 30 цифр. Сколько существует перестановок 30 цифр? Ответ: бешеное количество, а именно 30!. Даже если учесть, что из этих 30 цифр всего 10 различных, их число все равно остается фантастическим. Это число гораздо больше самой суммы, и больше длины диапазона, в котором сумма может меняться. Что это означает? То, что: 1. если мы наобум напишем слагаемые и сумму, ответ с подавляющей вероятностью будет YES; 2. на каждую сумму существует не просто несколько, а очень много разных комбинаций, удовлетворяющих условию. Это понятно? Если нет, перечитай, пока не разберешься. А когда разберешься, сразу станет само собой понятно, что программа находит первую из очень многих комбинаций, удовлетворяющих решению, и для этого ей не требуется слишком много времени. Поскольку ей нет нужды сканировать все комбинации. А раз валидных комбинаций много, значит, скорее всего есть и вблизи начала поиска.. ) Когда это все промелькнуло в моей голове (как задница того комара, который налетел на лобовое стекло), я просто закомментировал две строчки в проге: // close(f); - рассудительно решив, что уж теперь-то истинное время работы программы (перебор всех возможных комбинаций) от меня не уйдет.. Хрен-та! Я запустил прогу, увидел, что она действительно не вышла сразу, прикрыл окошко и пошел заниматься чем-то другим. Когда я минут через 20-30 снова заглянул в то окно, программа все работала. Я прервал ее по Ctrl-C и пошел в Far смотреть выходной файл. Его размер был 50 МБ, в нем было больше миллиона строк.. То есть программа уже нашла примерно миллион решений и прилежно продолжала искать остальные - видимо, полагая, что мне это жизненно важно )). Думаю, она делала бы это всю мою оставшуюся жизнь.. Забавно, что при небольшом числе слагаемых и цифр результат как раз обратный: получить заранее заданную сумму двух двузначных числе посредством перестановок их слагаемых намного труднее. По-видимому, мозг улавливает этот факт и потом пропорционально его масштабирует. То есть происходит нечто подобное тому, что мешает нормальным людям понять Теорию Относительности: мозг основывается на чувственном опыте и с большим трудом поддается перестройке под давлением разумной агументации.. Про рекурсию напишу чуть-чуть позже.. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Lapp |
18.01.2010 7:17
Сообщение
#24
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
Так, процесс в целом нам стал более понятен, теперь можно перейти к более техническим вопросам
Запрос. На комментарии:) RFC? Ok.Давай я лучше попробую описать способ. Думаю, это будет полезнее. Для начала забудем про рекурсию. Рекурсия не должна быть самоцелью. Она должна появиться сама собой из естественного пути решения. Итак, у нас есть набор цифр, записанных в массив (или строку, что то же самое). Нам нужно найти все возможные перестановки. Как? Извини, но твой способ не совсем ... мм.. удобный, а точнее - неуниверсальный. Давай действовать иначе.. Всего у нас n позиций. На первую мы ставим в цикле по очереди все имеющиеся цифры (элементы массива цифр). Далее, на каждом конкретном шагу этого цикла мы ставим на вторую позицию все элементы массива цифр, кроме того, который поставили на первую. То есть вложенный цикл с проверкой. Если позиций больше двух, повтояем то же самое. Вот пример для перемешивания цифр в 4-значном числе: a:='2601'; Все просто и понятно, так ведь? Вложенный цикл, причем вложенность равна длине (значности) исходного числа. Но, со всеми преимуществами, налицо и один недостаток. Дело в том, что Паскаль не допускает чего-то типа "вложенности переменной длины". И что же, нам для каждой длины делать свой фрагмент кода?? Вообще-то, не такой уж и абсурдный вариант, как кажется на первый взгляд. Длин будет вряд ли больше 1 - 2 десятков - так, что же? В исходной задаче вообще можно было ограничиться двумя вариантами (двузначные и трехзначниые) - разве это много? Определяем длину числа и переводим стрелки на нужный кусок программы.. Это, конечно, некрасиво .. И никто не гарантирует, что в другой задаче не будет большего числа вариантов, типа сто или тысяча. Как быть? Путей для разрешения этой проблемы несколько. Первый, самый банальный.. На каждом этапе вложенности делать проверку глубины. Глубину мы можем отслеживать с помощью некоторой специальной переменной, назовем ее Depth. При входе на очередной уровень, мы инкриминируем эту переменную и сравниваем ее с максимальной глубиной (равной длине числа). Приведенный мной выше кусок можно модифицировать в соответствии со сказанным так, что он будет работать для длин от 1 до 4: a:='2601';Здесь мы избежали дублирования больших кусков кода, но нам пришлось несколько раз (в схожей ситуации) вызывать процедуру обработки результата, что тоже несколько коробит.. Да и сам по себе вложенный цикл тоже не радует глаз: мы должны предусмотреть вложенность, равную максимально возможной длине числа. В нашем примере это всего лишь 3, но будем смотреть шире! Я сказал, что путей у нас не один. Что еще мы можем придумать? Строго говоря, есть еще средства.. Например, мы можем организовать схему с одним циклом, но со сложным манипулированием индексом. То есть в тотмомент, когда по индее нужно было бы войти во вложенный цикл мы будем сохранять текущий индекс в специальном массиве (длины, равной длине числа) и присваивать ему начальное значение (единицу). Тем самым цикл уже будет совсем другим, новым. Затем, когда нужно выходить из вложенного цикла, мы будем вынимать заранее сохраненное значение из массива - то есть возвращаться на предыдущий уровень. Цикл при этом будет продолжаться, как ни в чем ни бывало.. Индексом того массива для запоминания параметра цикла будет служить все та же Depth. Схема вполне осуществимая, хотя и не самая простая. В чем ее суть? В том, что мы повторно используем код несколько раз. Сначала для одного цикла, потом для вложенного, потом для следующего вложенного.. Код один, но параметр цикла, поскольку он сохраняется и перекладывается туда-обратно, различный на разных этапах. Не надо сейчас сразу бросаться писать код для этого алгоритма, просто уясни, что такая схема вполне осуществима. Уяснил? Продолжаем. На чем мы остановились? На том, что максимально увеличили КПД написанного нами кода, посредством использования его с различными данными (вспомни, что программа=алгоритм+данные). Позвольте, но ведь в Паскале уже есть средство для этого! Это средство называется процедура/функция. Она делает как раз то, что мы хотим: выполняет тот же самый код с разными данными! Эти данные передаются в параметрах. При этом старые параметры никуда не деваются, не забываются, не затираются, а остаются в стэке. Таким образом, нам даже не нужно будет сохранять параметр цикла (и другие данные, если потребуется) в специально подготовленном для этого массиве! И сам массив, выходит, нам тоже не нужен. Давай ближе к делу. Нам нужно организовать вложенный цикл? Хорошо. Мы сделаем процедуру, которая содержит цикл. А в том месте, в котором мы должны были бы перейти к вложенному циклу, мы просто поставим вызов этой же самой процедуры. При этом процедура работает с глобальными параметрами (кроме переменной цикла), так что все тип-топ, никакой пуницы. Вот она, рекурсия, и вылезла - сама собой, причем в полной красе )). Осталось добавить только еще одну маленькую деталь.. Когда вложенные циклы написаны явно, у нас практически нет опасности зациклиться: мы пройдем каждый цикл и в конце концов выйдем. Если же мы просто будем вызывать и вызывать нашу рекурсивную процедуру, входя все глубже и глубже, то как мы будем вылезать обратно?? Вот тут все-таки нужно использовать специальную переменную, которую в принципе можно организовать по-разному, но обычно удобно передавать как параметр рекурсивной процедуры. Если устроить процедуру так: procedure Recurse(l:integer);- то никакого зацикливания не получится. По достижении максимальной вложенности мы вместо очередного вызова процедуры (то есть вместо следующего вложения цикла) произведем обработку результата и выйдем. Боюсь, меня сегодня уже не хватит на написание комментов к той проге, чтобы от теории перейти наконец к практике. Если это по-прежнему требуется (?), я сделаю потом . -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Unconnected |
18.01.2010 10:17
Сообщение
#25
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Lapp, спасибо огромное!! Это редкий случай, когда в статье (тянет на неё) я понял всё, от начала до конца)) Только прочитал первый пример с циклами, и уже понял, для чего множество там и всё остальное)) У меня, кстати, была мысль, ещё в начале, что когда слагаемых так много, то будет явно больше одной комбинации.. Большой плюс тебе:) Добавлено через 19 мин. Я, кажется, подловил твою программу Например, входные данные: 1111 11 111 111 1111 111 1111 1111 122 5000 Прога задумалась. Слагаемых столько же. Но, как я понял, нужных комбинаций намного меньше, и они заключаются в последнем слагаемом, а до него ещё дойти надо_) Сообщение отредактировано: Unconnected - 18.01.2010 10:43 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Unconnected |
18.01.2010 12:23
Сообщение
#26
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Я тут решил для закрепления решить сам задачку на рекурсию, тоже на перестановки (поэтому в этой же теме пишу), задача такая:
Цитата Неподвижные точки (Время: 1 сек. Память: 16 Мб Сложность: 57%) Перестановкой P[1..n] размера n называется набор чисел от 1 до n, расположенных в определенном порядке. При этом в нем должно присутствовать ровно один раз каждое из этих чисел. Примером перестановок являются 1,3,4,5,2 (для n=5) и 3,2,1 (для n=3), а, например, 1,2,3,4,5,1 перестановкой не является, так как число 1 встречается два раза. Число i называется неподвижной точкой для перестановки P, если P[i] = i. Например, в перестановке 1,3,4,2,5 ровно две неподвижных точки: 1 и 5, а перестановка 4,3,2,1 не имеет неподвижных точек. Даны два числа: n и k. Найдите количество перестановок размера n с ровно k неподвижными точками. Входные данные Входной файл INPUT.TXT содержит два целых числа n (1 ≤ n ≤ 9) и k (0 ≤ k ≤ n). Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. Примеры № INPUT.TXT OUTPUT.TXT 1 5 2 20 2 9 6 168 3 2 1 0 4 9 0 133496 Получилось это: {$APPTYPE CONSOLE} Вылетает с каким-то неизвестным исключением (an unhabled win32 exception) Подскажите, в чём ошибка? Сообщение отредактировано: Unconnected - 18.01.2010 13:13 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
volvo |
18.01.2010 13:21
Сообщение
#27
|
Гость |
Цитата Подскажите, в чём ошибка? Цитата res:=''; |
Unconnected |
18.01.2010 13:24
Сообщение
#28
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Ага, теперь нормально, только на входных данных 5 2 ответ 1 выдаёт, мол только одна возможная перестановка, а их 20.
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
volvo |
18.01.2010 13:25
Сообщение
#29
|
Гость |
P.S.
Цитата Вылетает с каким-то неизвестным исключением (an unhabled win32 exception) Не совсем так... Это не неизвестное исключение. Оно просто необработанное (unhandled). Если бы ты обернул это все в try/except - получил бы диагностику ошибки (т.е., обработал бы выброшенное исключение)Добавлено через 48 сек. Цитата Ага, теперь нормально Хм... Ну, так покажи, как оно стало нормально Что исправил? |
Unconnected |
18.01.2010 13:48
Сообщение
#30
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Нормально - в смысле ошибка не вылетает:) А результат неправильный даёт. Убрал res:=''; перед if (lk=len) then begin ..
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
volvo |
18.01.2010 14:08
Сообщение
#31
|
Гость |
Цитата А результат неправильный даёт. Еще бы... У тебя переменная res описана локально, значит, хранит мусор. А ты содержимое этого мусора сравниваешь с какими-то значениями. Тебе еще повезло, что не вылетает. Окажется эта самая локальная строка короче чем lk символов - получишь опять вылет... |
volvo |
18.01.2010 14:38
Сообщение
#32
|
Гость |
P.S. На самом деле, твоя задача может решаться вот так:
uses sysutils;, если рекурсивно... Попробуй разобраться в алгоритме работы если надо - я прокомментирую, что здесь происходит Естественно, от IntToStr и StrToInt надо будет избавиться, они только замедляют выполнение, но чтобы разобраться что к чему, они подходят больше, чем непосредственное конвертирование. Да... Работу с файлами я не стал добавлять, задал значения константами. Для отладки - гораздо удобнее (по крайней мере мне). |
Unconnected |
18.01.2010 15:09
Сообщение
#33
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Ого.. решение короче намного, без множества и заполнение строки происходит прямо в функции.. Только сейчас, кстати, я понял, что мог бы и не заполнять заранее строку так, чтобы там были две "неподвижные" точки - можно было просто перебирать всё - немного, 5! - и считать неподвижные точки. Примерно я этот алгоритм понял - потрассировав немного - те же перестановки, только основанные на длине строки-параметра. И всё же, можно услышать, что было неправильно в моей функции?
Сообщение отредактировано: Unconnected - 18.01.2010 15:09 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
volvo |
18.01.2010 17:17
Сообщение
#34
|
Гость |
Цитата И всё же, можно услышать, что было неправильно в моей функции? Смотри. Начинаем с генерации строки S. Что у тебя в результате получается, для kol = 5, расскажи? У тебя получается строка "12234". Это что значит? Вообще по твоей задумке, что должна содержать строка S? Все символы, которые потом будут во всех вариациях переставляться, или что? |
Unconnected |
18.01.2010 17:26
Сообщение
#35
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Да, сначала я хотел заполнить строку с двумя неподвижными точками и чтобы нашлись все возможные вариации и посчиталось количество нужных мне вариантов. Только я не учёл, что там не только цифры от 1 до k-1 могут быть. Я имею в виду, на Подвижных позициях. Поздно что-то дошло..))
-------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Lapp |
19.01.2010 2:21
Сообщение
#36
|
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159 |
редкий случай, когда в статье (тянет на неё) я понял всё, от начала до конца)) Это и была моя цель )).Цитата Я, кажется, подловил твою программу Да подловить несложно. Можно просто написать в качестве суммы число, которое заведомо не получится (типа 2 или -5 )) и заставить ее написать NO (через пару годиков работы)).Например, входные данные: 1111 11 111 111 1111 111 1111 1111 122 5000 Прога задумалась. Правильно я понимаю, что комменты уже не нужны? -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
Unconnected |
19.01.2010 7:29
Сообщение
#37
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Цитата Правильно я понимаю, что комменты уже не нужны? Ага, правильно. Надеюсь, эта тема поможет ещё кому-то понять рекурсию:) -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Unconnected |
20.01.2010 0:18
Сообщение
#38
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
И снова я... Уж очень хочется что-то самому полностью решить, рекурсивно)
Задача про Дед-Мороза. Цитата Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм. Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз. Входные данные В единственной строке входного файла INPUT.TXT содержится четыре целых числа X, Y, Z и W (1 ≤ X, Y, Z ≤ 100, 1 ≤ W ≤ 1000). Выходные данные Выходной файл OUTPUT.TXT должен содержать одно целое число – количество вариантов подарков. Пример № INPUT.TXT OUTPUT.TXT 1 10 25 15 40 3 uses sysutils; Короче идея в том, чтобы в переменную res суммировать вес сладостей, по очереди, чтобы получились все возможные комбинации, а потом проверять общий вес. Также учтено, что вес могут составлять не обязательно 3 подарка. Я долго мучил этот код, он, как я понял, не все варианты перебирает.. Подскажите пожалуйста на словах, что не так:) -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Unconnected |
20.01.2010 18:19
Сообщение
#39
|
mea culpa Группа: Пользователи Сообщений: 1 372 Пол: Мужской Реальное имя: Николай Репутация: 24 |
Короче я вроде бы разобрался, уже несколько задач сам решил... А про Деда Мороза решение такое:
var f:textfile; Lapp и Volvo, еще раз спасибо за помощь:) Сообщение отредактировано: Unconnected - 20.01.2010 18:29 -------------------- "Знаешь, стыдно - когда не видно, что услышал всё, что слушал.."
|
Текстовая версия | 13.06.2024 6:40 |