一到考研题，测测大家递归的功底，^_^
[程序说明]
对于正整数N，输出其和等于N且满足以下限制条件的所有正整数的和式，即组成和式的数字自左至右构成一个非递增的序列。如N=4，程序输出为：
4=4
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1
程序中分别采用递归和非递归解法的两个函数RD（）和ND（）。
函数RD（）采用递归解法，它有两个参数N和K。其意义分别是被分解和式的数N，及当前第K度分解。算法思想是对N的所有合理的和式分解，将分解出的数（称为和数）存于数组A{}中。当其中一个分解已不再需要进一步分解时，即找到一个解，将存于数组A{}中的一个完整和式的和数输出。当还需要进一步分解时，以要进一步分解的数及分解深度为参数，递归调用分解和式函数。
int a[100];
void rd(int n,int k)
{
int i,j;
if (______1________)
a[0] = n;
for(j=_____2_______;j>=1;j--)
{
a[k] = j;
if(_____3_________)
{
printf("\n %d=%d",a[0],a[1]);
for(i=2;i<=k;i++)
printf("+%d",a[i]);
}
else
rd(____4____,_____5____)
}
}
main()
{
int n;
printf("\n enter n:");
scanf("%d",&n);
rd(n,_______6________);
}
我脑袋都快想破了，呜呜呜呜呜！！！看看大家到底都有多牛！！！
问题点数：20、回复次数：28Top
1 楼snowmansh（阿须）回复于 2005-11-22 12:25:18 得分 0
我要是写这样的代码,
不管多牛, 会老板抄鱿鱼的.Top
2 楼weisunding（鼎鼎）回复于 2005-11-22 12:34:59 得分 0
典型应试教育，自己写一个根本不难。想测试递归能力，自己再算一下8皇后问题啊。（我BLOG上有）
_______________________________
C/C++,C#,LINUX...
http://blog.csdn.net/weisunding
Top
3 楼xpzheng（快放假了）回复于 2005-11-22 12:39:27 得分 0
支持楼上的！
Top
4 楼K（）回复于 2005-11-22 13:14:12 得分 0
递归难啊Top
5 楼pengjay（）回复于 2005-11-22 13:36:37 得分 20
#include <stdio.h>
int a[100];
void rd(int n, int k)
{
int i,j;
if(k==1)
{
a[0]=n;
}
for(j=a[k-1]<=n?a[k-1]:n+1;j>=1; j--)
{
a[k]=j;
if(n==0)
{
printf("\n%d=%d",a[0],a[1]);
for(i=2;i<k;i++)
printf("+%d",a[i]);
}
else
{
rd(n-j,k+1);
}
}
}
int main()
{
int n;
printf("\nEnter n:");
scanf("%d",&n);
rd(n,1);
return 0;
}Top
6 楼cnsdwfwy（情报工作者）回复于 2005-11-22 15:19:14 得分 0
不要打击lz了，我倒是觉得多学习一些这样的问题挺好的。
Top
7 楼Kartor（開拓者）回复于 2005-11-22 17:57:50 得分 0
啊！pengjay(鹏仔) 你真是 太 NB了 可惜 我只能给你 20分呀！！！
^_^Top
8 楼Kartor（開拓者）回复于 2005-11-22 17:58:19 得分 0
这些东西 训练下编程的思维蛮好的，工作上 很难碰到啦！！！Top
9 楼NeuSoftRen（）回复于 2005-11-22 18:20:10 得分 0
看别人完整的代码都费尽，更何况是填空
下面是自己按照自己的思路写的，代码挺多，希望能对楼主有个借鉴的作用
#include<stdio.h>
int a[100];
void rd(int n,int k);
void print_one(int length);
int main()
{
rd(4,0);
return 0;
}
void print_one(int length)
{
int i=0;
printf("%d%c",a[0],'=');
for(i=1;i<=length;i++)
{
if((a[i]!=-1)&&(a[i+1]!=-1))
{
printf("%d%c",a[i],'+');
}
else if((a[i]!=-1)&&(a[i+1]==-1))
{
printf("%d\n",a[i]);
}
}
}
void rd(int n,int k)
{
int i =0;
int length;
if(0 == k)
{
a[0] = n;
a[1] = n;
for(i=2;i<100;i++)
{
a[i] = -1;
}
printf("%d%c%d\n",a[0],'=',a[1]);
rd(n,k+1);
}
else
{
for(i=2;i<100;i++)
{
if(a[i] == -1)
{
length =i;
break;
}
}
if(a[2] ==2)
{
a[2]-=1;
a[length++]=1;
}
else
{
if(--a[1] == 1)
{
a[length++]=1;
print_one(length);
return;
}
if(a[2]!=-1)
{
a[2]+=1;
}
else
{
a[2] =1;
}
}
print_one(length);
rd(n,k+1);
}
}Top
10 楼henan_lujun（地平风线）回复于 2005-11-23 08:20:48 得分 0
查看！Top
11 楼f123（风子）回复于 2005-11-23 11:51:25 得分 0
一般说来这种题里面的代码都是挺经典的。值得一看。
你看 NeuSoftRen() 写了八十多行，但原题才不到四十行Top
12 楼province_（雍昊）回复于 2005-11-23 12:01:43 得分 0
更简单也可以吧，原题可读性不好，当然它的好处是不用计算和是否等于目标数。如果把第二个参数换成与目标的差值，也可以不必计算和是否等于目标。Top
13 楼langzi520（虽左但右）回复于 2005-11-23 20:00:44 得分 0
学习
Top
14 楼province_（雍昊）回复于 2005-11-23 22:18:12 得分 0
Dim a(99) As Long
'n表示从n到1选，LNGLEFT表示与目标的差距，INDEX是取得的数据存放的
'位置。
Sub rd_(ByVal n As Long, ByVal lngLeft As Long, ByVal index As Long)
Dim j As Long
While n > 0
'当前的n小于等于差距则保存本n
If n <= lngLeft Then a(index) = n
'当前的n等于差距，则显示此次的和式
If n = lngLeft Then
While a(j) > 0
Text1 = Text1 & a(j) & "+"
j = j + 1
Wend
'去掉末尾多余的+号
Text1 = Mid(Text1, 1, Len(Text1) - 1) & vbCrLf
End If
'若取得的n小于差距，则继续递归
If n < lngLeft Then rd_ n, lngLeft - n, index + 1
n = n - 1
Wend
'清除存放单元的内容
a(index) = 0
End SubTop
15 楼laomai（老迈）回复于 2005-11-24 09:49:48 得分 0
先看看，呵呵Top
16 楼hongfeeling（无烟亦如烟）回复于 2005-11-24 10:37:19 得分 0
不知道LZ是考哪个学校的，考试题型有程序填空。
1. if (1==k)
2. for(j=n;j>=1;j--)
3.if(0==n-j)
4&5.rd(n-j,k+1);
6.rd(n,1);
如下测试通过：
enter n:5
5=5
5=4+1
5=3+2
5=3+1+1
5=2+3
5=2+2+1
5=2+1+2
5=2+1+1+1
5=1+4
5=1+3+1
5=1+2+2
5=1+2+1+1
5=1+1+3
5=1+1+2+1
5=1+1+1+2
5=1+1+1+1+1
Top
17 楼hongfeeling（无烟亦如烟）回复于 2005-11-24 10:56:39 得分 0
哦 不好意思
没有满足非递增序列Top
18 楼leoduba（想工作但无人招）回复于 2005-11-24 11:11:25 得分 0
markTop
19 楼hongfeeling（无烟亦如烟）回复于 2005-11-24 11:12:41 得分 0
2. 改成 for(j=a[k-1]<n?a[k-1]:n;j>=1;j--)Top
20 楼beijibingshan（Zealot）回复于 2005-11-24 14:22:32 得分 0
考研居然有这种题？
要是都是这种的话。。。。。。。。。。。Top
21 楼Kart_Eagle（猫）回复于 2005-11-25 12:26:53 得分 0
#include<iostream>
using namespace std;
int a[100];
void rd(int n,int k)
{
int i,j;
if (k==1)
a[0] = n;
for(j=(a[k-1]<n?a[k-1]:n);j>=1;j--)
{
a[k] = j;
if(n==j)
{
cout<<"\n"<<a[0]<<"="<<a[1];
for(i=2;i<=k;i++)
cout<<"+"<<a[i];
}
else rd(n-j,k+1);
}
}
void main()
{
int n;
cout<<"\n enter n:";
cin>>n;
rd(n,1);
cout<<endl;
}
Top
22 楼Kart_Eagle（猫）回复于 2005-11-25 12:27:26 得分 0
不好意思
用C++写的
忘改过来了……Top
23 楼hongfeeling（无烟亦如烟）回复于 2005-11-25 12:49:00 得分 0
这帖人气很旺呀 。
LZ怎么不见有过来，紧张复习中？Top
24 楼ugg（逸学堂(exuetang.net)）回复于 2005-11-25 14:06:16 得分 0
计算机算法分析与设计
第8页，第八页Top
25 楼Kartor（開拓者）回复于 2005-11-28 17:48:06 得分 0
不好意思，这两天放假！^_^Top
26 楼Kartor（開拓者）回复于 2005-11-28 17:49:58 得分 0
这是 华中科技大学 2002 的研究生试题，而且，中科院在 96年也考过，蛮经典的哦！！Top
27 楼Kartor（開拓者）回复于 2005-11-28 17:55:19 得分 0
没想到，都出现 三份答案了，可怜我当时，一头雾水，明天好好学习下各位的精神。呵呵!Top
28 楼thankgb（）回复于 2005-11-28 18:39:29 得分 0
强~~~我弄了半天没弄对~~Top
