`
izuoyan
  • 浏览: 9219045 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

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

阅读更多

中学数学题目:射击训练,每个靶得分为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代码:

a = ones(1, 11);
a2=conv(a,a);
a4
=conv(a2,a2);
a8
=conv(a4,a4);
a10
=conv(a2,a8);
a10(
91)%arraysinMatlabare1-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 代码:

#-*-coding:cp936-*-

seq
=[]
MAX_SCORE
=10

defbutt(n,score):
globalseq,MAX_SCORE
assert(n>=1andscore>=0)
ifn==1:
ifscore<=MAX_SCORE:
seq.append(score)
printseq
seq.pop()
return1
else:#一次得不了这么多分
return0
else:
cnt
=0
forsinrange(min(MAX_SCORE,score)+1):
#本靶中s环(sin[0,1,2,...]),计算剩下n-1个靶中score-s环的情况
remain_score=score-s;

#剩下n-1个靶全得满分也打不了score-s环,就算了
if(n-1)*MAX_SCORE<remain_score:
continue

seq.append(s)
cnt
+=butt(n-1,remain_score)
seq.pop()
returncnt

if__name__=='__main__':
all
=butt(10,3)
print"Totalcases:",all

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

分享到:
评论

相关推荐

    打靶十次打90环有多少情况.(某企业面试题)

    在这个特定的面试题中,我们被要求计算在十次射击中,总环数达到90环的所有可能情况。由于每次射击的环数可以是1到10之间的整数,我们需要找到所有能够加起来等于90的数字组合。 递归方法是解决这类问题的有效手段...

    前端面试题:前端框架面试题大全

    前端面试题:前端框架面试题大全; 前端面试题:前端框架面试题大全; 前端面试题:前端框架面试题大全; 前端面试题:前端框架面试题大全; 前端面试题:前端框架面试题大全; 前端面试题:前端框架面试题大全; ...

    C/C++程序员面试指南.杨国祥(带详细书签).pdf

    面试题2:在9个点上画10条线 面试题3:100盏灯 面试题4:找出不同的球 面试题5:时针、分针和秒针重合问题 面试题6:可以喝多少瓶汽水 面试题7:怎样拿到第100号球 面试题8:烧绳计时 面试题9:分金条 面试题10:...

    牛客大数据面试题集锦+答案,共523道,46W+字。大厂必备

    以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...

    最新Java面试题视频网盘,Java面试题84集、java面试专属及面试必问课程

    面试题包含了不同技术层面的面试问题,同时也能对一些没有面试开发经验的小白给予不可估量的包装, 让你的薪水绝对翻倍, 本人亲试有效.Java面试题84集、java面试专属及面试必问课程,所有的面试题有视屏讲解, 解答方案....

    面试高频算法题总结-剑指Offer题解

    面试题10:裴波那契数列 面试题11:旋转数组的最小数字 面试题12:矩阵中的路径 面试题13:机器人的运动范围 面试题14:剪绳子 面试题15:二进制中1的个数 面试题16:数值的整数次方 面试题17:打印从1到最大的n位数...

    10万字总结java面试题和答案(八股文之一)Java面试题指南

    JavaOOP面试题 Java集合/泛型面试题 Java异常面试题 Java中的IO与NIO面试题 Java反射面试题 Java序列化面试题 Java注解面试题 多线程&并发面试题 JVM面试题 Mysql面试题 Redis面试题 Memcached面试题 MongoDB面试题 ...

    2021年最新java面试题--视频讲解(内部培训84个知识点超详细).rar

    Java面试题10.ArrayList 和LinkedList的区别 Java面试题11.HashMap和HashTable的区别 Java面试题12.实现一个拷贝文件的工具类要使用字节流还是字符串 Java面试题13.线程的的实现方式?怎么启动线程?怎么区分线程? ...

    功能测试Ⅶ——面试题2:微信朋友圈

    功能测试Ⅶ——面试题2:微信朋友圈

    redis面试题及答案

    **面试题10:Redis在Java中的常见客户端库有哪些?** 答:Jedis、Lettuce和Redisson是常用的Java Redis客户端,其中Jedis小巧易用,Lettuce支持反应式编程,Redisson则提供了更多高级功能如分布式锁。 以上是对...

    Java 面试全解析:核心知识点与典型面试题.zip

    本资源包"Java 面试全解析:核心知识点与典型面试题.zip"包含了多个关键主题,帮助求职者深入理解和掌握 Java 的核心概念,以及应对面试中的各种问题。 1. **设计模式** - 34-设计模式常见面试题汇总.html 设计...

    Java面试题80:java访问redis级redis集群?.mp4

    Java面试题80:java访问redis级redis集群?.mp4

    模拟IC面试题analog面试题.doc

    本文总结了模拟IC面试题中的几个重要知识点,包括 Op-Amp 结构比较、2-stage Op-Amp 的gain 分布、极点分析、Miller 补偿原理、噪声分析和偏移误差分析等。这些知识点对于模拟IC设计和开发非常重要。

    牛客大数据面试题集锦+答案,共523道,46W+字 面试题总结一网打尽

    以后会慢慢把Java相关的面试题、计算机网络等都加进来,其实这不仅仅是一份面试题,更是一份面试参考,让你熟悉面试题各种提问情况,当然,项目部分,就只能看自己了,毕竟每个人简历、实习、项目等都不一样。面试题...

    2018iOS一份高级面试题

    ### 面试题90:什么是 ARC(Automatic Reference Counting)? ARC 是苹果引入的一种自动引用计数机制,用于简化内存管理。在 ARC 下,编译器自动处理 retain 和 release 操作,程序员无需显式调用这些方法。这有助...

    计算机和JAVA 面试题大全

    【计算机和JAVA 面试题大全】 在计算机科学与技术领域,尤其是软件开发行业,Java是一种广泛应用的编程语言,以其跨平台、面向对象和高效性而受到赞誉。本资料集涵盖了丰富的Java面试题,旨在帮助求职者准备Java...

    2019互联网面试题第2季,互联网面试题及答案,Java

    "2019互联网面试题第2季"聚焦了这一年度的重要面试趋势和热门问题,旨在帮助求职者更好地准备并理解面试官可能提出的各种问题。这份资料可能包含一系列的面试题目、解答以及相关思维导图,帮助求职者系统地梳理和...

    java面试题,J2EE面试题 笔试题

    2、各个公司面试题 3、J2EE初学者面试题 4、J2EE面试题(打码查错题) 5、java_华为笔试题 6、java常见面试题 7、java程序员面试宝典 8、java面试题及答案 9、java面试题编程篇 10、Oracle面试题 11、Oracle企业面试...

    剑指offer(java版67题)

    面试题 2:替换空格(考点: 字符串) 2 面试题 3:从尾到头打印链表(考点: 链表) 2 面试题 4:重建二叉树(考点: 树) 4 面试题 5:用两个栈实现队列(考点: 栈和队列) 5 面试题 6:旋转数组的最小数字(考点:...

Global site tag (gtag.js) - Google Analytics