Witam. Mam zadanie, aby napisać program w języku C++, który będzie wypisywał dla dowolnej liczby podział na wszystkie możliwe sumy (z kolejnymi liczbami ułożonymi niemalejąco). Na przykład, dla liczby 5 wypisze on kolejne linijki:
5=5
5=1+4
5=1+1+3
5=1+1+1+2
5=1+1+1+1+1
5=1+2+2
5=2+3
Program ma być napisany rekurencyjnie. Nie mam pojęcia jak się w ogóle za to zabrać, każda próba jest dość daleka od wyniku który mam otrzymać.
0
0
n = 1 + (n-1) = 2 + (n-2) = 1 + (2 -1) [! Tutaj rekurencja] + (n-2)
Jakos tak chyba
0
Ja to bym zrobił tak (pseudokod, specjalnie nie c/c++, żebyś jednak się wysilił):
function sums(num)
prefix = Array[ ]
sums_recursion(prefix, num)
function sums_recursion(prefix, num)
print(prefix, num)
maxx = floor(num / 2)
minx = 1
if prefix not empty
minx = last_element(prefix)
for x in [minx..maxx]
prefix.push(x)
sums_recursion(prefix, num - x)
prefix.pop()
Tzn:
- Podzieliłbym rozkład sumy na prefiks i n.
- Budowałbym rekurencyjnie, dodając na kolejnych poziomach rekurencji liczbę do prefiksu sumy.
- Prefiks jest posortowany nie-malejąco na każdym poziomie rekurencji.
- Liczba n jest większa lub równa od ostatniego elementu z prefiksu.