第归算法实现(分析)

问题: 一个设计运动员打靶，靶一共10环，连开10环打中90环的可能性有多少？请用第归算法实现？
分析：
1）每次打靶可能的得分范围是什么？
靶有10个环，那么当打中时，分数可为1-10，如果未打中得分为0，所以每次打靶得分的范围为0-10，共有11中可能
2）计算有多少种可能最直接的方法：
打10次靶，分别记录这10次打靶过程，用循环来完成
for(int i1=0;i1<=10;i++)
{
      for(int i2=0;i2<=10;i2++)
      {
           for(int i3=0;i3<=10;i3++)
           {
                  ---
                   for(int i10=0;i10<=10;i10++)
                   {
                           if(i1+i2+i3+.+i10=90)
                           {
                                 //一种可能
                           }
                   }
                  ---
           }
      }
}
但是这样做有两点不足:
1)如果题目改为连打1000枪，得分为900的可能性，估计这种写法的要哭了
2)考虑不周全，如果第一次打靶得分为0，还有9次机会，这9次机会，就要求枪枪都是满分，如果第二枪，得分不是10，那第三枪不用打就知道可能没有可能性了。就比如乒乓球比赛一样，5局3胜制，如果进行了3局都是一个人胜利的话，比赛这时候就可以宣告结束。而继续下去就是浪费时间和精力
2。采用第归的方法来解决上述问题
   第归就是自己调自己，如果没有结束限制的话，第归的效果和dead loop是一样的，但是第归正常情况下都会有结束标志，而且第归的意义就在于完成循环层数不明确或者层数明确但是数值非常大的情形。使用它的注意点就是第归函数肯定要具有一个或者一个以上的形参，没有参数的第归就形成了死循环。而且第归中函数每次调用自己的时候，需要小心谨慎的控制参数。尽量防止死循环的产生，第归和栈关系密切。
要实现上述功能，第归函数要完成的功能主要有:
1)当传入的当前打靶次数为小于1，或者大于规定次数的时候，应该退出第归函数的执行
2)当余下的打靶次数中每次都得满分，但能无法达到目标分数的时候，应该退出第归
3)如果没有上述两种情况，就应该执行第归
实现代码:
1using System;
2
3namespace Test
4{
5    /**//// <summary>
6    /// ShotScore 的摘要说明。
7    /// </summary>
8    public class ShotScore
9    {
10        //总共有多少种可能性
11        int SumRate = 0;
12        //每次可能命中的几率范围
13        int[] ScoreArray;
14        //总共需要多少分
15        int totalScore=0;
16        //一共能打多少次
17        int totalShot=0;
18        //当前共打中环数
19        public ShotScore(int[] sa,int ts,int t)
20        {
21            this.ScoreArray = sa;
22            this.totalShot = ts;
23            this.totalScore = t;
24        }
25        public int GetSum()
26        {
27            return SumRate;
28        }
29        public void Compute(int currentShot,int cNum)
30        {
31            //打多打少都不行
32            if(currentShot<0||currentShot>totalShot)
33            {
34                return;
35            }
36            //以后枪枪都中10都不能满足条件,game over
37            if(((totalShot-currentShot+1)*10)<(totalScore-cNum))
38            {
39                return;
40            }
41            //打够次数了并且总共达到了预期环数
42            if(currentShot==totalShot)
43            {               
44                //这种可能性成立
45                SumRate++;   
46                return;   
47            }
48            for(int i=0;i<ScoreArray.Length;i++)
49            {
50                Compute(currentShot+1,cNum+ScoreArray[i]);
51            }
52            
53        }
54    }
55}
56
最后结果为:92378
总结：这个问题主要考察了程序员的逻辑思考能力和对第归函数的应用。十分简单。但逻辑一定要清楚，分析问题的方法一定要准确。

great!!!!!!!!!

nice ~~~

如下思考:
认为int compute( int n,int score)返回可能数,则
compute( n ,score) = compute( n-1, score-0)+ compute( n-1,score-1)+...+compute( n-1,score - 10)
当n==1时,如果score<=10则返回1,否则返回0
当n>1时,如果score > 10 *n则返回0,如果score==10*n则返回1

程序如下:
int compute(int n,int score)
{
      int posibility = 0;
      if( n == 1 )
     {
         if( score <= 10 )  return 1;
         else return 0;
      }
     else if( score > 10*n )  return 0;
     else if( score == 10*n ) return 1;
     else
     {
         for( int i=0;i<=10;i++)
             posibility += compute( n-1, score - i );
      }
      return posibility;
}