面试题2：10个靶打中90环的情况有多少种？

你的名字 2022-09-17 06:19 124阅读 0赞

中学数学题目：射击训练，每个靶得分为0环到10环（共11种可能），一个人打了10个靶，那么：

打中0环的可能只有一种，即每个靶都打种0环。打中100环情况一样，只不过把得分换为丢分。

打中1环有10种可能，即第1个靶打中1环，其余的靶打中0环；或者第2个靶打中1环，其余的靶打中0环；……或者第10个靶打中1环，其余的靶打中0环。打中99环情况一样，只不过把得分换为丢分。

打中2环有55种可能，分为两类，1) 这2环在同一个靶上，有10种可能；2) 这2环分两个靶打中，每个靶1环，有10\*9/2 = 45 种可能。一共有55种可能。打中98环情况一样，只不过把得分换为丢分。

问打中90环的情况有多少种。

思路1：用生成函数。求多项式(x^10 + x^9 + ... + x + 1)^10中x^90那项的系数，为92378。Matlab代码：

![None.gif][]a = ones(1, 11);

![None.gif][]a2 = conv(a,a);  
![None.gif][]a4 = conv(a2,a2);  
![None.gif][]a8 = conv(a4,a4);  
![None.gif][]a10 = conv(a2,a8);  
![None.gif][]a10( 91 )  %  arrays  in Matlab are  1 \- based.

ans = 92378

这个办法对所有的环数都成立。

思路2：多重组合。一共在10个靶上丢了10环，考虑把10个相同的小球放到一排10个杯子里边的情况有多少种。10个杯子之间有9个隔板，假设我们有一排19个小坑，选出其中10个小坑放球，另外那9个坑放隔板，那么第1个隔板之前的小球（可能为0个，也可能为10个）放入第1个杯子，第1个和第2个隔板之间的小球（可能为0个，也可能为10个）放入第2个杯子，依此类推，第9个隔板之后的小球放入第10个杯子。那么情况一共有C(10, 19) ＝92378种。

10个靶中n环的情况数为C(n, 10+n-1)，对0<=n<=10成立。

如果10个靶中了11环，按这个公式计算出的答案是167960，这是错误的，因为它把“一个靶中11环”的情况也算了进去，正确的答案是167960-10=167950。

思路3：递推（递归）。适合列举出全部情况。考虑10个靶中3环，对于第1个靶：如果中0环，那问题转为求剩下9个靶里中3环的情况；如果中1环；问题转为求剩下9个靶里中2环的情况；如果中2环；问题转为求剩下9个靶里中1环的情况；如果中3环；问题转为求剩下9个靶里中0环的情况。这样每一步问题规模都在缩小，缩小到只有1个靶时就可以直接给出答案了。

Python 代码：

![None.gif][]\# \-\*- coding: cp936 -\*-   
![None.gif][]   
![None.gif][]seq  =  \[\]  
![None.gif][]MAX\_SCORE =10   
![None.gif][]  
![None.gif][] def  butt(n, score):  
![None.gif][]global  seq, MAX\_SCORE  
![None.gif][]assert(n >=1and score >=  0)  
![None.gif][]if n ==1 :  
![None.gif][]if score <=  MAX\_SCORE:  
![None.gif][] seq.append(score)  
![None.gif][]print  seq  
![None.gif][] seq.pop()  
![None.gif][]return1   
![None.gif][] else: \# 一次得不了这么多分   
![None.gif][] return  0  
![None.gif][]else :  
![None.gif][] cnt =  0  
![None.gif][]for s in range(min(MAX\_SCORE, score)\+1 ):  
![None.gif][]\# 本靶中s环（s in \[0, 1, 2, ...\]），计算剩下 n-1 个靶中 score - s 环的情况   
![None.gif][]  remain\_score = score \-  s;  
![None.gif][]  
![None.gif][]\# 剩下 n-1 个靶全得满分也打不了 score-s 环，就算了   
![None.gif][] if (n\-1)\*MAX\_SCORE <  remain\_score:  
![None.gif][]continue   
![None.gif][]  
![None.gif][] seq.append(s)  
![None.gif][] cnt  \+= butt(n\-1 , remain\_score)  
![None.gif][] seq.pop()  
![None.gif][]return  cnt  
![None.gif][]  
![None.gif][]if\_\_name\_\_=='\_\_main\_\_' :  
![None.gif][] all = butt(10, 3 )  
![None.gif][]print"Total cases:" , all  
![None.gif][]

这实际上还可以看成一个动态规划问题，如果把中间结果记下来，可以避免很多重复计算。另外如果把MAX\_SCORE设为1，那么这个程序可以用来生成所有组合。

[None.gif]: /images/20220828/5f77652c75eb48bea7d77ae3cdf667eb.png