Здравейте! Трябва да реша една задача с рекурсия, която да разбива естествени числа, но не ми е ясно как ще стане. На теория знам какво трябва да се направи, но кодирано ми е трудно да я осъществя. Задачата трябва да е написана на c++ ,а ето я и нея: Разбиване на естествено число N наричаме последователност от естествени числа, чиято сума е N.  Да се състави програма, която реализира разбиването на дадено естествено число N.  Написвам от клавиатурата числото 4(примерно), това число трябва да се разбие на всички възможни събираеми. 1+1+1+1, 2+1+1, 3+1 4+0. Ако някой има идея за сорс код, моля да сподели. Благодаря!

Числата би трябвало да са 1+1+1+1, 2+1+1, 2+2 и 3+1  но не и 4+0 .  Имаше преди време такава тема ама не ми се търси.

Редактирано 24 март 201610 г. от ined (преглед на промените)

Да, щото нулата е специален случай при операцията събиране.

Ако се допусне нула в отговорите се получава манджа с грозде

#include <iostream>

using namespace std;

int *s;
void out(int x, int step,int pos)
{
     if (x==0) 
     {
          --pos;
          for(int i=0; i<pos;++i)
              cout<<s[i]<<"+";
          cout<<s[pos]<<endl;
          return;
     }
     for (int i=step; i>0; --i)
     {
         if (x>=i) 
         {
             s[pos]=i;   
             out(x-i,i,pos+1);
         }
     }
}

int main()
{
    int n;
    while(1) 
    {
        cout<<"n = ";
        cin>>n;
        if (n<1) break;
        s=new int[n];
        out(n,n-1,0);
        delete[] s;
    }
}

 

Редактирано 25 март 201610 г. от ined (преглед на промените)

преди 2 часа, ined написа:

#include <iostream>

using namespace std;

int *s;
void out(int x, int step,int pos)
{
     if (x==0) 
     {
          --pos;
          for(int i=0; i<pos;++i)
              cout<<s[i]<<"+";
          cout<<s[pos]<<endl;
          return;
     }
     for (int i=step; i>0; --i)
     {
         if (x>=i) 
         {
             s[pos]=i;   
             out(x-i,i,pos+1);
         }
     }
}

int main()
{
    int n;
    while(1) 
    {
        cout<<"n = ";
        cin>>n;
        if (n<1) break;
        s=new int[n];
        out(n,n-1,0);
        delete[] s;
    }
}

 

Благодаря ти!!

#include <iostream>
#include <vector>
using namespace std;

vector <vector <vector <int>>> common_cup =
{ { {} }, { {} }, { { 2 }, { 1, 1 } } };      // общия кюп


void findsums(int n)
{
	int i, j;
	int diff;
	if ((common_cup.size() == n + 1)) return;
	findsums(n - 1);
	common_cup.push_back({ { n } });
	for (i = n - 1; i >= n / 2 + n % 2; i--)
	{
		diff = n - i;
		for (j = 0; j < common_cup[i].size(); j++)
		{
			if (common_cup[i][j][0] < diff) continue;
			common_cup[n].push_back(common_cup[i][j]);
			common_cup[n][common_cup[n].size() - 1]
				.insert(common_cup[n][common_cup[n].size() - 1].begin()
				, diff);
		}
	}
}

int main()
{
	int i, j;
	int n;
	cout << "n = ";
	cin >> n;
  	if (n < 2)
	{
		cout << "No solution.";
		return 0;
	}
	findsums(n);
	for (i = 1; i < common_cup[n].size(); i++)
	{
		for (j = 0; j < common_cup[n][i].size(); j++)
		{
			cout << common_cup[n][i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

 

Редактирано 25 март 201610 г. от Реджеп Иведик (преглед на промените)