Witam. Mam problem z wymyśleniem jak napisać program który obliczy mi na ile sposób mogę rozpisać liczbę naturalną n, na jej sumy naturalne.
Np.
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1
Myślałem nad wzorem rekurencyjnym jakiś, wiem , że da się to napisać iteracyjnie ale tu już w ogóle brakuje pomysłu . Od razu zaznaczam, że nie jestem studentem tylko licealistą i nie proszę o rozwiązanie tylko wskazówki. Pozdrawiam :)
0
1
Nie wiem czy nie lepiej było by zacząć od 1 1 1 1 1, i potem dodać 2 jedynki do siebie uzyskując 2 1 1 1. Potem 2 2 1, 3 2, itd. No chyba że jest na to jakiś wzór, ale chwilowo nic takiego nie kojarzę.
edit: no chyba żeby tak: 5 - 1 równa się 4, na ile sposobów można uzyskać 4? i tak dopóki nie dojdziesz do 5 - 4 = 1
2
Program udało mi się napisać, jest to https://en.wikipedia.org/wiki/Partition_(number_theory)
package partition;
public class Partition {
public static int counter = 0;
public static void partition(int n) {
partition(n, n);
}
public static void partition(int n, int max) {
if (n == 0) {
Partition.counter++;
return;
}
for (int i = Math.min(max, n); i >= 1; i--) {
partition(n - i, i);
}
}
public static void main(String[] args) {
partition(5);
System.out.println(Partition.counter - 1);
}
}