面試例題 1：一個射擊運動員打靶，靶一共有 10 環，連開 10 槍打中 90 環的可能性有多少種？請用遞歸算法編程實現。[中國某著名通信企業 h面試題]
解析：靶上一共有 10 種可能——1 環到 10 環，還有可能脫靶，那就是 0 環，加在一起共 11 種可能。這是一道考循環和遞歸的面試題。我們在這個程式中將利用遞歸的辦法實現打靶所有可能的演示，並計算出結果。讀者會問，難道一定要使用遞歸？當然不是。我們也可以連續用 10個循環語句來表示程式，代碼如下：
for (i1=0;i1<=10;i1++)
{
for (i2=0;i2<=10;i2++)
{
for (i3=0;i3<=10;i3++)
{
......
for (i10=0;i10<=10;i10++)
{
if(i1+i2+i3+...+i10=90)
print();
}
......
}
}
}
但是，上面的循環程式雖然解決了問題，但時間複雜度和空間複雜度無疑是很高的。比較好的辦法當然是採用遞歸的方式，事實上公司也就是這么設計的。遞歸的條件由以下 4 步完成：
（1）如果出現這種情況，即便後面每槍都打 10 環也無法打夠總環數 90，在這種情況下就不用再打了，則退出遞歸。代碼如下：
if(score < 0 || score > (num+1)*10 ) //次數num 為0～9
{
return;
}
（2）如果滿足條件且打到最後一次（因為必須打 10 次），代碼如下：
if(num == 0)
{
store2[num] = score;
output( store2);
return;
}
（3）如果沒有出現以上兩種情況則執行遞歸，代碼如下：
for(int i = 0; i <= 10; ++i)
{
//這裡實際上為了方便把順序倒了過來，store2[9]是第1 回
//store2[8]是第 2 回⋯⋯store2[0]是第 10 回
store2[num] = i;
cumput(score - i, num - 1,store2);
}
（4）列印函式，符合要求的則把它列印出來。代碼如下：
public static void output(int[] store2)
{
for(int i = 9; i>=0; --i)
{
console.write(" {0}",store2[i]);
}
console.writeline();
sum++;
}
答案：
用 c#編寫的完整代碼如下：
using system ;
public class m
{
//public static int[] store;
//相當於設定了全局變數
//這個全局變數sum 是包含在m 類中的
public static int sum;
public m()
{
int sum =0;
// int[] store = {1,2,3,4,5,6,7,8,9,0};
}
//列印函式
//符合要求的則把它列印出來
public static void output(int[] store2)
{
for(int i = 9; i>=0; --i)
{
console.write(" {0}",store2[i]);
}
console.writeline();
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 class myapp
{
public static void main( )
{
int[] store;
store = new int[10];
int sum = 0;
//int a=90;
//int b=9;
//output();
m.cumput(90,9,store);
sum = m.sum2();
//m.cumput2(a,b,store);
//console.write(" {0}",store[3]);
//cout<<"總數:"<<sum<<endl;
console.write(" 總數: {0}",sum);
}
}
程式結果一共有 92 378 種可能。
也可以用 c++編寫，代碼如下：
#include <iostream>
using namespace std;
int sum;
int store[10];
void output()
{
for(int i = 9; i>=0; --i)
{
cout<<store[i]<<" ";
}
cout<<endl;
++sum;
}
void cumput(int score, int num)
{
if(score < 0 || score > (num+1)*10 ) //次數num 為0～9
return;
if(num == 0)
{
store[num] = score;
output();
return;
}
for(int i = 0; i <= 10; ++i)
{
store[num] = i;
cumput(score - i, num - 1);
}
}
int main(int argc, char* argv[])
{
cumput(90, 9);
cout<<"總數:"<<sum<<endl;
return 0;
}