程序員打靶問(wèn)題及解析
面試?yán)} 1：一個(gè)射擊運(yùn)動(dòng)員打靶，靶一共有 10 環(huán)，連開(kāi) 10 槍打中 90 環(huán)的可能性有多少種？請(qǐng)用遞歸算法編程實(shí)現(xiàn)。[中國(guó)某著名通信企業(yè) H面試題]解析：靶上一共有 10 種可能——1 環(huán)到 10 環(huán)，還有可能脫靶，那就是 0 環(huán)，加在一起共 11 種可能。這是一道考循環(huán)和遞歸的面試題。我們?cè)谶@個(gè)程序中將利用遞歸的辦法實(shí)現(xiàn)打靶所有可能的演示，并計(jì)算出結(jié)果。讀者會(huì)問(wèn)，難道一定要使用遞歸？當(dāng)然不是。我們也可以連續(xù)用 10個(gè)循環(huán)語(yǔ)句來(lái)表示程序，代碼如下：
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();
}
......
}
}
}
但是，上面的循環(huán)程序雖然解決了問(wèn)題，但時(shí)間復(fù)雜度和空間復(fù)雜度無(wú)疑是很高的。比較好的辦法當(dāng)然是采用遞歸的方式，事實(shí)上公司也就是這么設(shè)計(jì)的。遞歸的條件由以下 4 步完成：
（1）如果出現(xiàn)這種情況，即便后面每槍都打 10 環(huán)也無(wú)法打夠總環(huán)數(shù) 90，在這種情況下就不用再打了，則退出遞歸。代碼如下：
if(score < 0 || score > (num+1)*10 ) //次數(shù)num 為0～9
{
return;
}
（2）如果滿足條件且打到最后一次（因?yàn)楸仨毚?10 次），代碼如下：
if(num == 0)
{
store2[num] = score;
Output( store2);
return;
}
（3）如果沒(méi)有出現(xiàn)以上兩種情況則執(zhí)行遞歸，代碼如下：
for(int i = 0; i <= 10; ++i)
{
//這里實(shí)際上為了方便把順序倒了過(guò)來(lái)，store2[9]是第1 回
//store2[8]是第 2 回⋯⋯store2[0]是第 10 回
store2[num] = i;
Cumput(score - i, num - 1,store2);
}
（4）打印函數(shù)，符合要求的.則把它打印出來(lái)。代碼如下：
public static void Output(int[] store2)
{
for(int i = 9; i>=0; --i)
{
Console.Write(" {0}",store2[i]);
}
Console.WriteLine();
sum++;
}
答案：
用 C#編寫(xiě)的完整代碼如下：
using System ;
public class M
{
//public static int[] store;
//相當(dāng)于設(shè)置了全局變量
//這個(gè)全局變量sum 是包含在M 類中的
public static int sum;
public M()
{
int sum =0;
// int[] store = {1,2,3,4,5,6,7,8,9,0};
}
//打印函數(shù)
//符合要求的則把它打印出來(lái)
public static void Output(int[] store2)
{
for(int i = 9; i>=0; --i)
{
Console.Write(" {0}",store2[i]);
}
Console.WriteLine();
sum++;
}
//計(jì)算總數(shù)，返回 sum 值
public static int sum2()
{
return sum;
}
public static void Cumput(int score, int num, int[] store2 )
{
//如果總的成績(jī)超過(guò)了90 環(huán)（也就是 score<0），或者如果剩下要打靶
//的成績(jī)大于10 環(huán)乘以剩下要打的次數(shù)，也就是說(shuō)即便后面的都打10 環(huán)
//也無(wú)法打夠次數(shù)，則退出遞歸
if(score < 0 || score > (num+1)*10 ) //次數(shù)num 為 0～9
{
return;
}
//如果滿足條件且達(dá)到最后一層
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<<"總數(shù):"<<sum<<endl;
Console.Write(" 總數(shù): {0}",sum);
}
}
程序結(jié)果一共有 92 378 種可能。
也可以用 C++編寫(xiě)，代碼如下：
#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 ) //次數(shù)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<<"總數(shù):"<<sum<<endl;
return 0;
}
【程序員打靶問(wèn)題及解析】相關(guān)文章：
程序員面試問(wèn)題及答案10-08
意大利留學(xué)常見(jiàn)問(wèn)題及解析08-17
職場(chǎng)新人常見(jiàn)問(wèn)題及解析10-20
新加坡留學(xué)反簽證相關(guān)問(wèn)題及解析10-18
俄羅斯留學(xué)的問(wèn)題及詳細(xì)解析07-11