IMHO.WS - Задача. Помогите кто может.

IMHO.WS (http://www.imho.ws/index.php)

- Программирование (http://www.imho.ws/forumdisplay.php?f=40)

- - Задача. Помогите кто может. (http://www.imho.ws/showthread.php?t=99648)

Задача. Помогите кто может.

Как можно рекурсивно подсчитать кол-во возможних вариантов составить число с помощью умножения и сложения. Умножение на 1 не считается. Т.е. поясню на примере есле допустим дано число 4 то все возможные действя будут такими:

Код:

4

(1+ 3) (1+ (1+ 2)) (1+ (2 +1)) (1+ (1+ (1+1))) (1+ ((1+1) +1))

(2 + 2) (2 + (1+1)) ((1+1) + 2) ((1+1) + (1+1))

(3+1) ((1+ 2) +1) ((2 +1) +1) ((1+ (1+1)) +1) (((1+1) +1) +1)

(2*2) (2*(1+1)) ((1+1)*2) ((1+1)*(1+1))

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

(тут была не совсем верная попытка решения задачи) ;)

Как не крути, везде есть подводные камни... :biggrin:

Видел я эту попытку, весьма интересный подход, даже на некоторые мысли натолкнул, только вот все не то получается. ;0( Может еще какие идеи есть? :confused:

точного алгоритма я не знаю, но вот, что приходит на ум:
-нам известно сколькими способами можно записать число только используя операцию сложения (вроде это не сложно, просто сначала все единицы, потом вычитаем одну позицию, двойку перемецаем по всем оставшимся, затем вычитаем две позиции, тройку перемещаем по всем оставшимся, короче суть в том, что вроде количество сложений мы узнаем за "констатнту", т.е. не тратим на это времени :confused: )
-а затем остается только найти все простые делители этого числа (можно обычным перебором, есть конечно и другие алгоритмы, но если число не очень большое, то перебор подойдет, причем перебирать нужно, как известно, до квадратного корня этого числа, плюс можно составить заранее таблицу простых чисел до какого-нибудь, что в разы увеличит время) и для каждого делителя (и их произведения, это в цикле) вызываем процедуру подсчитывания количества представлений с помощью сложения... В итоге получаем трудоемкость, сравнимую с нахождением простых делителей числа + само количество простых делителей (последнее можно и не считать)... Посмотри, может идею поймешь, дальше разовьешь, если что, пиши, сейчас буду думать над первым шагом этого алгоритма:)

Цитата:

Izzyy:
Может еще какие идеи есть?

Есть, но все они имеют некоторую проблему:

1) генеряться "лишние" последовательностм
ИЛИ
2) выбор порядка действий для суммы (или расстановка скобок)

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

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

Код:



unsigned long sumNum(unsigned int n)

{

 int i;

 unsigned long count=1;



 if (n==2) return 1;



 for (i=1; i<n; ++i)

  count+=sumNum(n-i)+sumNum(i);



 return count;

}

А может сам подход ошибочний.
Буду рад любым идеям.

Ну неужели ни у кого нет еще каких нибудь идей?