Question

一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。[中国某著

各为高手。帮我看看啊。我是从f(1,10)开始的，可是运行不出来，帮我看看啊，这是我写的源码
# include<stdio.h>
int a[11];
void prints();
int f(int time,int score);
void main()
{
f(1,0);
}
void prints()
{
int i;
for (i=1;i<11;i++) {
printf("%d",a[i]);
}
printf("\n");
}
int f(int time,int score)
{
int i;
if (time==2 && score<10) {
return 0;
}
if (time>10 && score==90) {
prints();
}
else
for (i=0;i<=10;i++) {
a[time]=i;
score=score+i;
f(time+1,score);
}
}
if (time==2 && score<10) { //// 判断如果递归到第二次，并且score<10就退出，因为如 果还是小于10就不会达到90
return 0;
}
if (time>10 && score==90) {////递归结束，大于10，并且等于90
prints();
}
for (i=0;i<=10;i++) { //递归 ，用一个数组来表示，1代表一环，有10个数来表示
a[time]=i;
score=score+i;
f(time+1,score);

Answer 1

先把问题在纸上描述清楚，再开始写程序，我看你的问题补充部分就是在纠缠细枝末节的i++、数组等问题，根本没有命中问题的要害。

先把你要求的问题转化一下，就是10个数加起来等于90，但十个数都不超过10，列方程如下

x1+x2+...+x10==90, 0<=x1,x2,...,x10<=10

那么开始来想递归，递归要先想递归什么时候结束，假定已经打了9枪，剩下最后一枪 x10，那么这样写：

foo(sum, left=1 ){
if(left==1){

for(x10=0;x10<11;x10++){

if(sum + x10 ==90)
cnt++;

}
return cnt;
}
}
再想递归的一般情况，递归函数
foo(sum, left) 表示当前总和为sum，还剩下left枪的，最后总和为90的所有组合数。
那么当前打了x环，之后，总和就是sum+x， 还剩下left-1枪

所以写出来就是：

foo(sum, left)
{
for(x=0;x<11;x++){
cnt += foo(sum+x9, left-1)
}
return cnt;

}

把上面2段合起来就是：
foo(sum, left)
{
cnt = 0;

if(left==1){
for(x=0;x<11;x++){
if(sum + x ==90)
cnt++;
}
return cnt;
}
for(x=0;x<11;x++){
cnt += foo(sum+x, left-1);
}
return cnt;
}
最后写main函数

int main()
{
foo(0, 10);

}

当你把递归写正确之后，再考虑优化你的算法，比如剪枝策略，把某些明显不可能的解去掉，这样就可以加速你的代码的运行。

追问

我理解了你的意思，但是你的程序有点小错误，第一，你从10开始，那就是打了9，8 ，7，6，5，4，3，2，1，0，所以if(left==1){要改成if(left==0)才是最后一枪。
你定义的cnt不是计算器吗？
但是cnt += foo(sum+x, left-1);为什么剩下的枪术的总和还要加cnt计数器呢？直接for(x=0;x<11;x++)
foo( sum+x, left-1); 不是可以吗？你在外面定义一个计数器 累加，在打印出来不是可以吗？
而且你把cnt定义在函数里面他会变0的

追答

累加那里肯定是你理解错了，当然要把当前每一种情况都加一起，才是总的数量啦。
直接for(x=0;x<11;x++)
foo( sum+x, left-1);
计算的结果没有返回呀。

你理解了思路就好，我也是匆匆写的伪代码，所以难以保证正确性。关键是把思路理清楚了，其它细节部分在慢慢修正。
自己要维护一组测试数据，通过不断调整程序来让你的程序最终符合测试结果，就OK了。

追问

弱弱的下，if(left==1){
for(x=0;x<11;x++){
if(sum + x ==90)
cnt++;你这边不是累加了吗？ 为什么还要 f(sum+x, left-1) 累加，不是一项功能吗？
}
不然这个f(sum+x, left-1) 你代表什么 ？不是符合到最后一项满足条件才累加吗？你这样累加没意义啊。

追答

这是一颗搜索树，树的每一层节点都要累加，不是到了最下面才累加的。建议你自己拿一张纸来画一下这个树，你画出来了，在每个节点写上相应的文字，就理解这个问题了。
if(left==1)这里是递归的2个分支，总会从一个分支就返回了，不会有2个地方都累加的。

另外，这个问题可以用组合数学里的不定方程求解法来求解，直接用数学公式算出答案。如果我用2种不同的算法，都是算出了相同的答案，那么我可以很有把握地说，我的解法是对的。

追问

你看。我用另一种算法也可以，我运行叻。是正确的。

# include<stdio.h>   

int f(int time,int score)

{

int i;

if(time>11) {return 0;}

    if (score<(time-2)*10) {

    return 0;

}

if (time>10 && score==90) {

count++;

}

else

{

  for (i=0;i<=10;i++) {

score=score+i;

f(time+1,score);

score=score-i;

  }          可能我和你的算法有点不一样。

  }

}