递归算法的方法

递归算法的方法

面试例题1：一个射击运动员打靶，靶一共有10环，连开10枪打中90环的可能性有多少种？请用递归算法编程实现。[中国某著名通信企业H面试题]


问题所在原文http://book.csdn.net/bookfiles/107/1001073091.shtml。

我自己和同事想自己做做看。我用了几乎3个小时的时间才算弄出来，实在应该多多思考，多多练习。
我的程序如下:
package digui;

public class daba {

public int sum = 0 ;

/**
*
* @param time 总共可以尝试的次数.
* @param score time次要求获得的环数.
* @return time次完成score分数的可能情况数.
*/
public int f(int time,int score){
int all = 0;
if(score/time>10)
return 0 ;
if(time==1)
return 1 ;
for (int i = 0; i <= 10; i++) {
int tmp = f(1,i)*f(time-1,score-i);
if(tmp>=1)
all += tmp;
}
return all;
}

/**
*
* @param time 总次数
* @param score time次数所要求达到得环数
* @param arr 每次所中得环数.
*/
public void f2(int time,int score,int[] arr){
// System.out.println("time="+time+",score="+score);
if(score/time>10)
return ;
if(time==1){
arr[0]=score;
output(arr);
return ;
}
for (int i = 0; i <= 10; i++) {
arr[time-1] = i ;
f2(time-1,score-i,arr);
}
}

private void output(int[] arr) {
String result = "" ;
for (int i = 0; i <= 9; i++) {
result+=arr[i]+" ";
}
System.out.println(result);
sum++;

}


public daba() {
super();
// TODO Auto-generated constructor stub
}

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
daba obj = new daba();
//System.out.println(obj.f(10,90));;
int[] arr = new int[10];
obj.f2(10,90,arr);
System.out.println(obj.sum);
}

}
======================= 以上是我的程序=======下面是书中的解法============
package digui;

public class daba2 {

// public static int[] store;

// 相当于设置了全局变量

// 这个全局变量sum是包含在M类中的

public static int sum;

public daba2()

{
int sum = 0;
// int[] store = {1,2,3,4,5,6,7,8,9,0};
}

// 打印函数

// 符合要求的则把它打印出来

public static void Output(int[] store2) {

String result = "" ;
for (int i = 9; i >= 0; --i) {
//System.out.print(store2[i]+" ");
result+=store2[i]+" ";
}
System.out.println(result);
sum++;
}

// 计算总数，返回sum值
public static int sum2() {
return sum;
}

public static void Cumput(int score, int num, int[] store2)

{

// 如果总的成绩超过了90环（也就是score<0），或者如果剩下要打靶

// 的成绩大于10环乘以剩下要打的次数，也就是说即便后面的都打10环

// 也无法打够次数，则退出递归

if (score < 0 || score > (num + 1) * 10) // 次数num为0～9

{

return;

}

// 如果满足条件且达到最后一层

if (num == 0)

{

store2[num] = score;

Output(store2);

return;

}

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

{

store2[num] = i;

Cumput(score - i, num - 1, store2);

}

// Console.Write(" {0}",store2[5]);

}

public static void main(String[] args) {

int[] store;

store = new int[10];

int sum = 0;

// int a=90;

// int b=9;

// Output();

daba2.Cumput(90, 9, store);

sum = daba2.sum2();

// M.Cumput2(a,b,store);

// Console.Write(" {0}",store[3]);

// cout<<"总数:"<<sum<<endl;

System.out.println(sum);

}

}