Question

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale ordonate crescător astfel încât diferența dintre doi termeni consecutivi ai sumei să fie cel puțin 2.

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

#include <cmath>

using namespace std;

int st[100], n, suma;

ifstream fin("partitiinr.in");

ofstream fout("partitiinr.out");

void citire(int& n)

{

   fin >> n;

}

int valid(int k)

{

   suma = 0;

   if (k > 1)

       if (st[k] - st[k-1] < 2)

           return 0;

   for (int i = 1; i <= k; i++)

       suma += st[i];

   if (suma <= n)

       return 1;

   return 0;

}

int solutie(int k)

{

   return suma == n;

}

void afis(int k)

{

   for (int i = 1; i <= k; i++)

       fout << st[i] << ' ';

   fout << '\n';

}

void bkt(int k)

{

   int i;

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

   {

       st[k] = i;

       if (valid(k))

       {

           if (solutie(k))

               afis(k);

           else

               bkt(k + 1);

       }

   }

}

int main()

{

   citire(n);

   bkt(1);

   return 0;

}

Explicație: