Было n палочек одинакового размера. Эти палочки сломали на разные части. Требуется собрать эти палочки.
Например:
Входные даные: 1 5 2 5 2 1 2 1 5
Выходные даные:
1 5
1 5
2 2 2
1 5


P.S. Поделитесь идеями, пожалуйста! Буду очень благодарен!

А начальный размер указан?
Из твое примера можно получить и такой вариант:
1 5 1 5
2 2 2 1 5

boevik, я забыл дописать в условии, что исходные палочки минимальной длины.

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] = первый элемент, второй элемент, ... , последний элемент, при этом
первый элемент = бывший второй элемент и т.д. То есть удаляя элемент мы сдвигаем все остальные влево.

Ну а дальше придумываем что-нибудь такое:

Код

while i < n {   y[i] = y[i] + x[0]   удаляем x[0] из x[]   while Sum(y[i]) < l   {      d = l - Sum(y[i])      while (пока не нашли)      {         ищем в x[] элемент равный d, когда нашли: j = номер этого элемента         d = d - 1      }      y[i] = y[i] + x[j]      удаляем x[j] из x[]   }   i + 1 }

Давай отстроимся от палочек. Тогда задачу сформулировать можно так:

Имеющийся массив чисел разделить на группы так, чтобы сумма чисел каждой группы была одна и та же, а количество групп максимально... верно?

Тогда:

Начинаем с подсчета общей суммы и разложения ее на множители. Сумма в каждой группе (и кол-во групп) есть произведение части из сомножителей (очевидно), а также сумма числе в группе не менее максимального числа (тоже очевидно). А далее - перебор возможных сочетаний сомножителей (подбор суммы в группе) в сторону увеличения до тех пор пока не будет найдено деление на группы.

Само деление выполняется стандартно - числа сортируются, набор группы ведется в направлении уменьшения (т.е. прибавляем очередное число списка, сумма не превышена - фиксируем и едем дальше, превышена - отбрасываем и опускаемся ниже, в общем типично рекурсивная задача).

Это сообщение отредактировал(а) Akina - 29.11.2004, 09:40

Модератор: Название темы должно отражать ее суть!


gluck
http://forum.vingrad.ru/index.php?showtopic=34389

Akina, а у меня никакой рекурсии нет

cardinal
Ты делал исходя из предположения, что количество палочек тебе известно - сие раз - и не предохранялся от возможного промежуточного переполнения (вернее, оно не нужно из второго твоего предположения что каждая палочка была разломлена строго на 2 части). Если это неверно - в общем случае, а не частном - то без (псевдо)рекурсии не обойтись.

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 палочки, собираем, получается

Классно! А главное без рекурсии Что думаете?

Cardinal, что-то я твою идею не совсем уловил!
Если тебе не сложно, можно поподробнее?

Цитата(gluck @ 3.12.2004, 20:21)

Если тебе не сложно, можно поподробнее?

Помоему подробней некуда уже

Возьми любые "входные данные" и пройдись с ними по пунктам 1-5 описанным выше. Как будет конкретный вопрос по конкретному пункту, то тогда и задавай, а так что я сто раз одно и тоже писать буду?

Самой большой проблемой думаю будет пункт 3. Я пока не придумал как собрать все варианты (то есть алгоритм хороший не придумал)... Может у кого есть какие мысли?

cardinal, допустим нашел ты длину палочек, а как ты собираешься собирать их без рекурсии? По-моему, тут вся фишка в сборке палочек, а не определении длины.

Цитата(gluck @ 4.12.2004, 16:06)

cardinal, допустим нашел ты длину палочек, а как ты собираешься собирать их без рекурсии?

Цитата(cardinal @ 29.11.2004, 21:00)

....... берем число 2, значит нам надо собрать 12 палочек, собираем, обламываемся

Объясняю как мы обламываемся

Вот наши данные (их надо где-нибудь запомнить, т.к. массив мы будем изменять см. ниже)
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.

Цитата(cardinal @ 29.11.2004, 23:00)

Идея с разложением на множители неплохая  А может тогда проще.

То что я предлагаю - именно в этом и заключается.

Цитата(cardinal @ 29.11.2004, 23:00)

Классно! А главное без рекурсии  Что думаете?

не будет рекурсии - будет псевдорекурсия кучей while-ов и аналогичных структур. прямой алгоритм тут не построить.

Цитата(cardinal @ 3.12.2004, 22:46)

Самой большой проблемой думаю будет пункт 3. Я пока не придумал как собрать все варианты (то есть алгоритм хороший не придумал)... Может у кого есть какие мысли?

да запросто. перебрать возможные сочетания множителей - задача дилетантская, тебе просто думать лень. Перемножить - тем более. Единственная тонкость - после получения полного списка составных множителей этот список надо отсортирить по возрастанию, и потом уже пробовать собирать палочки.

gluck
Поинтересуйся такой вещью, как китайская теорема об остатках. Наведет на мысли