递归算法的方法
面试例题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);
}
}
本文地址：http://www.45fan.com/bcdm/69017.html