Question

Se considera un numar natural n nenul. Sa se elaboreye un program care sa afiseze si sa contorizeze toate modalitatile de a scrie acest numar ca suma de minim doua numere intregi consecutive. De exemplu pentru n´6 veti obtine 3 modalitati: 1+2+3, 0+1+2+3, -5-4-3-2-1+0+1+2+3+4+5+6.
Fisierul de iesire sume.out va contine pe prima linie numarul k de modalitati de a scrie numarul ca suma de numere intregi consecutive, iar pe urmatoarele k linii cate doua numere intregi n, s, separate prin spatiu, reprezentind, respectiv, numarul de termeni si primul termen din suma corespunzatoare liniei.

Mai jos e varianta mea. Exista ceva mai eficient?

#include <fstream.h>
  int main()
{ 
  int T[10000], i, j, suma, k=0, n, vec=0, nr;  
   cout<<"n="; cin>>n;
 
  for (i=-n; i<n; i++)   
  {   
  for (j=i, suma=0, nr=0; suma<n; j++)       
       {       
        suma+=j;       
        nr++;     
        }       
   if (suma==n)        
   {       
   k++;        
   T[vec]=nr;        
   vec++;        
   T[vec]=i;        
   vec++;       
   }   
}
 
 ofstream sume("sume.out");   
   sume<<k<<"\n";   
 for (i=0; i<vec; i++)   
   {    
   sume<<T[i]<<" ";    
   i++;    
   sume<<T[i]<<"\n";   
   } 
sume.close(); 
return 0;
}

Answer 1

Prefer varianta asta:

#include <iostream>
using namespace std;

int x[20000], v[1000][2], n, nr;

void afis()
{
    cout << nr << '\n';
    for(int i=1; i<=nr; i++)
        cout << v[i][0] << ' ' << v[i][1] << '\n';
}

void afis(int k)
{
    nr++;
    v[nr][0] = k;
    v[nr][1] = x[1];
}

int valid(int k)
{
    int suma = 0;
    for(int i=1; i<=k; i++) suma += x[i];
    if(suma == n) return 1;
    return 0;
}

void bkt(int pas)
{
    for(int i=1-n; i<=n; i++) {
        x[pas] = i;
        if( (pas == 1) || (x[pas] == x[pas-1] + 1) ) {
            if(valid(pas) && pas != 1) afis(pas);
            else bkt(pas+1);
        }
    }
}

int main()
{
    cin >> n;
    bkt(1);
    afis();
    return 0;
}