Partitiile unui numar natural

Partiţiile unui număr natural. Fie n>0, natural. Să se scrie un program care să afişeze toate partiţiile unui număr natural n.

Numim partiţie a unui număr natural nenul n o mulţime de numere naturale nenule {p1, p2, …, pk} care îndeplinesc condiţia p1+p2+ …+pk = n.

Ex: pt n = 4 programul va afişa:

4 = 1+1+1+1

4 = 1+1+2

4 = 1+3

4 = 2+2

4 = 4

Observaţii: – lungimea vectorului soluţie cel mult n;

• • există posibilitatea ca soluţiile să se repete;

  • condiţia de final este îndeplinită atunci când suma elementelor vectorului soluţie este n.

Am menţionat mai sus că vom folosi doi parametri, unul pentru poziţia în vectorul soluţie şi un al doilea în care avem sumele parţiale la fiecare moment. Avem determinată o soluţie atunci când valoarea celui de-al doilea parametru este egală cu n.

În această situaţie la fiecare plasare a unei valori în vectorul sol valoarea celui de al doilea parametru se măreşte cu elementul ce se plasează în vectorul soluţie. Apelul procedurii back din programul principal va fi back(1, 0).

Există şi posibilitatea de a apela procedura back din programul principal back(1, n) şi valoarea celui de al doilea parametru se decrementează cu elementul ce se plasează în vectorul sol, iar o soluţie avem când acest parametru este zero. Indiferent care modalitate este aleasă acest al doilea parametru ne permite să optimizăm puţin programul în sensul că putem considera nişte condiţii de continuare mai strânse.

#include<iostream>

int n, ns,sol[20];

void afis(int l)

{ int i;

ns++;

cout<<„Solutia nr. „<< ns<<” : „;

for(i=1;i<=l;i++) cout<<sol[i]<<” „;

cout<<endl;

}

void back(int i, int sp)

{ int j;

if (sp==n) afis(i-1);

else for(j=1;j<=n-sp;j++)

if (j>=sol[i-1])

{

sol[i]=j;

back(i+1, sp+j);

}

}

void main()

{

cin>>n;

ns=0;

back(1,0);

cout<<ns<<” solutii”;

}