Рекурсия. Си.

[MAKEDON]

Нужно написать рекурсивную функцию, которая представляет число N в виде M слагаемых. Все возможные варианты вывести на экран.

Я пока даже алгоритм себе не представляю. Натолкните на мысль, как решить, а уж с реализацией разберусь..

[Sazary]

Как-то так:

В цикле от 1 до N (пусть по i) первое слагаемое получаем как i*k, где k - от 0 и пока i*k<=N.
Потом спускаемся рекурсивно. При этом передаем себе глубину, предыдущее значение i, текущую сумму и уже сформированную строку (сумму слагаемых). И то же самое.
Условие выхода - достигли M или текущая сумма >N. Если достигли нужной глубины, проверяем сумму. Если она равна N, то выводим строку. Иначе просто выходим.

[MAKEDON]

Да, было бы неплохо!

[Sazary]

Да я вот что-то поторопился ) Вернее, исходник есть (он на C++), но вот только не могу вспомнить, на сумму чего он раскладывает )

#include <iostream>
#include <conio.h>
#include <fstream>
#include <string>

using namespace std;

const int kol=3;
int cen[kol];
int cnt=0;
ofstream fout;
int N;

string arsItoS(int k)
 {
		string s="";
		int a;
		char c;
		if(k==0)
		{
			 s += (char)(k+48);
			 return s;
			}
		while(k>0)
		 {
				a = k%10;
				s += (char)(a+48);
				k /= 10;
			}
		for(a=0;a<s.length()/2;a++)
		 {
				c = s[a];
				s[a] = s[s.length()-a-1];
				s[s.length()-a-1] = c;
			} 
		return s;
	}
//-------

void rec(int tekcen,int k, string str)
 {
		int i,j,t;
		string tt;
	if(k==kol) 
	 {
			/* елси нужно, чтобы сумма была равна N, то заменить условие на '==' */
			if(tekcen==N)  
			 {
					cnt++;
					cout<<str<<endl;
					fout<<str<<endl;
				}
			return;
		}
	if(tekcen>N) return;
	j=0;
	do
	 {
			tt = str;
			t = tekcen+cen[k]*j;
	  if(j!=0) tt += "+" + arsItoS(j) + "*" + arsItoS(cen[k]);
			rec(t,k+1,tt);
			j++;
		} while(t<=N);
	
	return;		
	}


int main(){
int i,j;
string str;
fout.open("foutput.txt");

cen[0]=17;
cen[1]=5;
cen[2]=1;

cout<<"N= ";
cin>>N;
cout<<endl;

for(i=0;i<kol;i++)
{
	j=1;
	while(cen[i]*j<=N)
	 {
			str = "";
			str += arsItoS(j)+"*"+arsItoS(cen[i]);
			rec(cen[i]*j,i+1,str);
			j++;
		}
}
cout<<"\nVsego: "<<cnt;
fout<<"\nVsego: "<<cnt;
fout.close();
getch();
return 0;
}

Рекурсивная функция - rec. arsItoS - это для преобразования числа в строку (не помню, зачем я тогда с этим намудрил )

Естественно, если вам на си нужно, то там все строковые операции переделать придется. Но, думаю, идею вы уловите.

[Sazary]

Вот оно. Все закомментил.

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

int N,M,count;

// принимаем глубину, текущую сумму, предыдущее число и сформированную строку
void rec(int glub, int tekSum, int pred, char *str)
{
 if(glub==M)  // если достигли нужной глубины
  {
   if(tekSum == N)  // и сумма совпадает с N
    {
     printf("%s\n",str);  // выводим строку
     count++;  
    }
   return;   
  }
 //------
 int j=pred+1;   // текущее слагаемое
 char buf[100],tmp[500];
 
 while(tekSum+j<=N)  
  {
  strcpy(tmp,str);  
   // это чтобы не было лишнего плюса в начале
  if(glub>0 && j!=0 && strcmp(tmp,"")!=0) strcat(tmp," + "); 
  itoa(j,buf,10);  // число в строку
  strcat(tmp,buf);
  strcat(tmp,"\0");
  rec(glub+1,tekSum+j,j,tmp);
  j++;
  }
}

int main()
{
char str[500];

printf("Enter a number N: ");
scanf("%d",&N);
printf("Enter count M: ");
scanf("%d",&M);
printf("\n");

strcpy(str,"");
count = 0;
rec(0,0,0,str);

printf("\nVsego: %d\n",count);

getch();
return 0;
}

[vcv-igors]

Не могу прогу написать с рекурсией, чтоб правильно функционировало (с возвратом значения,т.е. обнуление ). Дайте хотя бы ссылку,где похожее найти.

Пусть x1=x2=x3=1, xi=xi-1+xi-3, i=4,5...
Найти сумму Е (от 1 до 100 или n) = xi/2^i.