Например:
Входные даные: 1 5 2 5 2 1 2 1 5
Выходные даные:
1 5
1 5
2 2 2
1 5
P.S. Поделитесь идеями, пожалуйста! Буду очень благодарен!
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > --------------- |
| Автор: gluck 28.11.2004, 16:46 |
| Было n палочек одинакового размера. Эти палочки сломали на разные части. Требуется собрать эти палочки. Например: Входные даные: 1 5 2 5 2 1 2 1 5 Выходные даные: 1 5 1 5 2 2 2 1 5 P.S. Поделитесь идеями, пожалуйста! Буду очень благодарен! |
| Автор: boevik 28.11.2004, 16:54 |
| А начальный размер указан? Из твое примера можно получить и такой вариант: 1 5 1 5 2 2 2 1 5 |
| Автор: gluck 28.11.2004, 18:18 |
| boevik, я забыл дописать в условии, что исходные палочки минимальной длины. |
| Автор: cardinal 28.11.2004, 20:08 | ||
| n как я понял известно... Тогда так: x[0..r] - массив длин сломанных палочек i счетчик, i = 0 j счетчик, j = 0 d переменная, d = 0 1. Считаем сумму всех длин x[0] + x[1] + ... + x[r] и получаем Sum(x[]) 2. Соответсвенно длина изначальных палочек равна l = Sum(x[])/n 3. Делаем массив y[0..n] каждый элемент массива y является массивом и добавляя в массив y[] один элемент (новый элемент), например к y[0], мы получаем y[0] = первый элемент, второй элемент, ... , новый элемент. 4. Удаляя например первый элемент из массива y[0] = первый элемент, второй элемент, ... , последний элемент мы получим y[0] = первый элемент, второй элемент, ... , последний элемент, при этом первый элемент = бывший второй элемент и т.д. То есть удаляя элемент мы сдвигаем все остальные влево. Ну а дальше придумываем что-нибудь такое:
|
| Автор: Akina 29.11.2004, 09:37 |
| Давай отстроимся от палочек. Тогда задачу сформулировать можно так: Имеющийся массив чисел разделить на группы так, чтобы сумма чисел каждой группы была одна и та же, а количество групп максимально... верно? Тогда: Начинаем с подсчета общей суммы и разложения ее на множители. Сумма в каждой группе (и кол-во групп) есть произведение части из сомножителей (очевидно), а также сумма числе в группе не менее максимального числа (тоже очевидно). А далее - перебор возможных сочетаний сомножителей (подбор суммы в группе) в сторону увеличения до тех пор пока не будет найдено деление на группы. Само деление выполняется стандартно - числа сортируются, набор группы ведется в направлении уменьшения (т.е. прибавляем очередное число списка, сумма не превышена - фиксируем и едем дальше, превышена - отбрасываем и опускаемся ниже, в общем типично рекурсивная задача). |
| Автор: podval 29.11.2004, 10:36 |
| Модератор: Название темы должно отражать ее суть! gluck http://forum.vingrad.ru/index.php?showtopic=34389 |
| Автор: cardinal 29.11.2004, 16:43 |
Akina, а у меня никакой рекурсии нет  |
| Автор: Akina 29.11.2004, 17:08 |
| cardinal Ты делал исходя из предположения, что количество палочек тебе известно - сие раз - и не предохранялся от возможного промежуточного переполнения (вернее, оно не нужно из второго твоего предположения что каждая палочка была разломлена строго на 2 части). Если это неверно - в общем случае, а не частном - то без (псевдо)рекурсии не обойтись. |
| Автор: cardinal 29.11.2004, 22:00 |
| Akina, понял... Идея с разложением на множители неплохая А может тогда проще. (обсуждаем на верхнем примере) 1. Посчитали сумму 24. 2. Разложили на множители: 1*2*2*2*3 (с единичкой понятней) 3. Собрали и посчитали всевозможные произведения (все разные): 1*2, 1*3, 2*2, 2*3, 2*2*2, 2*2*3, 2*2*2*3. 4. Минимальное дает нам длину палочек, если мы их можем слепить! 5. Начинаем лепить: ....... берем число 2, значит нам надо собрать 12 палочек, собираем, обламываемся ....... берем число 3, значит нам надо собрать 8 палочек, собираем, обламываемся ....... берем число 4, значит нам надо собрать 6 палочек, собираем, обламываемся ....... берем число 6, значит нам надо собрать 4 палочки, собираем, получается Классно! А главное без рекурсии Что думаете? |
| Автор: gluck 3.12.2004, 21:21 |
| Cardinal, что-то я твою идею не совсем уловил! Если тебе не сложно, можно поподробнее? |
| Автор: cardinal 3.12.2004, 21:46 | ||
Помоему подробней некуда уже Возьми любые "входные данные" и пройдись с ними по пунктам 1-5 описанным выше. Как будет конкретный вопрос по конкретному пункту, то тогда и задавай, а так что я сто раз одно и тоже писать буду? Самой большой проблемой думаю будет пункт 3. Я пока не придумал как собрать все варианты (то есть алгоритм хороший не придумал)... Может у кого есть какие мысли? |
| Автор: gluck 4.12.2004, 17:06 |
| cardinal, допустим нашел ты длину палочек, а как ты собираешься собирать их без рекурсии? По-моему, тут вся фишка в сборке палочек, а не определении длины. |
| Автор: cardinal 4.12.2004, 17:44 | ||||
Объясняю как мы обламываемся Вот наши данные (их надо где-нибудь запомнить, т.к. массив мы будем изменять см. ниже) 1 5 2 5 2 1 2 1 5 Мы пускаем цикл от i=0;i<12;i++ (так как двенадцать палочек надо собрать) и лепим... Первый проход 1 + 1 (пробегали слево направо и искали слогаемые, когда нашли обнулили их) От массива осталось 0 5 2 5 2 0 2 1 5 Наткнувшись на 5 мы уже обламались, т.к. длина палочек должна равнятся 2... Ну и так далее... Как дошли до 6 (то есть собрать надо 4 палочки) мы опять вваливаемся в цикл цикл i=0;i<4;i++ Первый проход 1 + 5 от массива осталось 0 0 2 5 2 1 2 1 5 Второй проход 2 + 2 + 2 от массива осталось 0 0 0 5 0 1 0 1 5 и т.д. Ну то есть собрали 4 палки длиной по 6.  |
| Автор: Akina 6.12.2004, 10:06 | ||||||
То что я предлагаю - именно в этом и заключается.
не будет рекурсии - будет псевдорекурсия кучей while-ов и аналогичных структур. прямой алгоритм тут не построить.
да запросто. перебрать возможные сочетания множителей - задача дилетантская, тебе просто думать лень. Перемножить - тем более. Единственная тонкость - после получения полного списка составных множителей этот список надо отсортирить по возрастанию, и потом уже пробовать собирать палочки. |
| Автор: podval 6.12.2004, 11:40 |
| gluck Поинтересуйся такой вещью, как китайская теорема об остатках. Наведет на мысли |
| Автор: cardinal 6.12.2004, 16:11 | ||||||
А я хочу именно не перемножая
псевдорекурсия это не куча while-ов  и пока я не знаю чего в моем алгоритме непрямого...
Твое предложение закачивается на рекурсии |
| Автор: Akina 6.12.2004, 16:33 | ||||
| cardinal рекурсия будет не одна... первая - при разложении на множители. Вторая - при построении списка делителей. Третья - при попытке собрать из набора палочки текущего размера. Это если сортировку использовать нерекурсивную. У меня слова о рекурсии относятся к последнему этапу - т.е. к попытке из набора обломков собрать палочки заданной длины.
не выйдет. вернее выйдет, но кто-то еще раньше говорил:
ты имел в виду что будешь заменять умножение сложением?  |
| Автор: cardinal 6.12.2004, 16:41 | ||||||
Я имел в виду собрали всевозможные произведения из множителей. Вичислять их я не собирался
А это еще зачем?
Здесь у меня циклы... Как делать объяснил выше... |
| Автор: Akina 6.12.2004, 16:53 |
| cardinal да все понятно... можно и будет работать... но если палочка может быть разломана как на 2, так и на 2000 кусков, а кол-во кусков - миллионы-миллиарды, ты умрешь в этих циклах... Что до сборки делителей - ты значение ака величину очередного делителя считать будешь? или так и оставишь в виде горсти простых сомножителей? |
| Автор: cardinal 6.12.2004, 21:16 | ||||
ага
А у тебя стэк кончится |