下面程序的执行过程是怎么样的???

来源:百度知道 编辑:UC知道 时间:2024/06/17 05:00:32
/*输入两个整数m和n,从数列1,2,3...n中随意取几个数,使其和m等于,要求将其中所有可能的组合列出来,编程求解*/
#include<iostream>
#include<string>
using namespace std;
int mVal,nVal;
int * pOut;

void calFun(int m, int n)
{
if ( m < 1 || n < 1 || ( n == 1 && m != 1) )
return;
if ( m == n )
{
pOut[n] = 1;
for ( int i = 1; i <= nVal; ++i)
{
if ( pOut[i] )
cout<<i<<" ";
}

cout<<endl;
pOut[n] = 0;
}

calFun(m, n-1);///这里
pOut[n] = 1;
calFun( m - n, n - 1 );///这里,这两个地方是如何执行过来的呢?????????????
pOut[n] = 0;
}

int main()
{
cout<<"m:";
cin>>mVal;
cout<<"n:";
cin>>nVal;
if ( mVal < nVal )
nVal = mVal;
pOut = new int[nVal + 1];
memset( pOut,0,(nVal+1)*sizeof(int) );

calFun(mVal,nVal);
delete []pOut;

1-n中选取数的组合,使得和为m.这一问题可分为两个子问题:
1.从1到n-1中选取数的组合,使得和为m
2.n一定入选,在1到n-1中选取数的组合,使得和为m-n
当然,问题2的前提是m>=n,m<n的情况已经在calFun的函数的第一句
if ( m < 1 || n < 1 || ( n == 1 && m != 1) )
return;
就直接无视了.

至于递归是怎么实现的,我建议里找本讲数据结构和算法的书,看下递归和利用栈实现非递归这方面的知识.

calFun(m, n-1);///这里

程序运行到这里,你把m,n-1都代进去,重新进入calfun的第一行。(其实是开了另外一块内存,存放新的calfun函数,然后第一个calfun等待这条语句返回。
对于每一个都是这样。
就这样了,能理解就很简单了。你这个是单线程的。calfun里面的calfun就相当于子函数。直接copy过来,那个参数改一下就行了,相当于在一个函数里面,内嵌了n个自己的副本。不过每个副本的参数不一样。然后从最底层,(也就是使calcfun能运行下去的最小参数值)开始依次返回。

不是从1-n么
那么就从1开始循环
最开始认为1个数,看是否=m
然后认为2个数,那么m-1看看是不是在1-n中,如果在,这就是一种组合了。
如此周而复始下去

这个问题我很想知道的是,不用递归的方法如何实现...

这两个递归是有点乱,高手求教

递归呀!