投稿    登录
  博主录制的Python3爬虫视频教程已发布!详情请戳Python3爬虫视频教程!希望大家支持!非常感谢!

递归求解排队进电影院问题,附带JAVA代码

Java 崔庆才 3217浏览 6评论

原题:

解题方法:

此题可以用递归方式求解,详细求解过程如下:

符合条件的情况必须是拥有1美元的人前方必须要有50美分的人来排队,要不然不可能找零开,即必须满足从头数50美分的人数大于1美元的人数.

我们直接求解符合条件的情况.我们先不考虑持有50美分的人的次序,仅考虑持有1美元的人的次序,最后的结果再乘以n! 就可以了.

可以转化为50美分的人已经排好,由持有1美元的人进行插空排列.

首先1美元的人是不可能插到队头的,所以可以插的空有n个.

定义一个函数f(n.m),这表示有n个1美元的人插m个空的方法数,这m个空是从队尾向前数的m个空的位置.

比如f(4,4)的求解

●1●2●3●4  黑点表示50美分的人,1234表示可以插的空

第一个空可以有0人,可以有1个人.但不可能有2个人及以上

1.当有1人的时候,这个位置4个人四选一,剩下的方式为f(3,3),故为4*f(3,3)

2.当没有的人的时候,则方式为f(4,3)

所以排列方式为f(4,4)=4*f(3,3)+f(4,3)=A(4)(0)*f(4,3)+A(4)(1)*f(3,3)

注:A(m)(n)在此表示m!/(m-n)! 如A(4)(2)表示4×3=12.A(5)(3)表示5x4x3=60.

再如:f(4,3)的求解

是四个人插后三个空,

● ●1●2●3 黑点表示50美分的人,123表示可以插的空

第一个空可以没人,可以1个人,可以2个人,但不能有3人及以上.

1.当有0人的时候,则只有四个人插后两个空了,即为f(4,2)

2.当有1人的时候,选其中1人,四选一,剩下的3人插2个空,方法数为4*f(3,2)

3.当有2人的时候,选其中的2人,四选二排列,剩下的2人插两个空,方法数为A(4)(2)*f(2,2)

所以排列方式为f(4,3)=f(4,2)+4*f(3,2)+A(4)(2)*f(2,2)=A(4)(0)*f(4,2)+A(4)(1)*f(3,2)+A(4,2)*f(2,2)

发现规律了吗?在此我们可以总结出递推式

所以最后的结果就简单了,我们再乘上50美分的人的全排列就是最后的结果了.

最后的答案即为A(n)(n)*f(n,n)

JAVA代码实现如下:

利用了BigInteger求解,防止越界的出现.在main函数里可以修改n的值来计算.

转载请注明:静觅 » 递归求解排队进电影院问题,附带JAVA代码

喜欢 (17)or分享 (0)

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的

想结交更多的朋友吗?

来进击的Coder瞧瞧吧

进击的Coder

QQ群号 99350970 立即加入

进击的Coder灌水太多?

这里是纯粹的技术领地

激进的Coder

QQ群号 627725766 立即加入

想找人聊天解闷?想要学习干货?

微信公众号进击的Coder为你打造

进击的Coder

微信公众号 扫一扫关注