投稿    登录
  《Python3网络爬虫开发实战》赠书活动正在进行中!详情请戳赠书活动!欢迎参与!非常感谢!

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

Java 崔庆才 14726浏览 996评论

原题:

解题方法:

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

符合条件的情况必须是拥有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代码

喜欢 (26)or分享 (0)

我的个人微信公众号,联系我请直接在公众号留言即可~

扫码或搜索:进击的Coder

进击的Coder

微信公众号 扫一扫关注

想结交更多的朋友吗?

来进击的Coder瞧瞧吧

进击的Coder

QQ群号 99350970 立即加入

进击的Coder灌水太多?

这里是纯粹的技术领地

激进的Coder

QQ群号 627725766 立即加入

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

发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(996)个小伙伴在吐槽
  1. I would like to thnkx for the efforts you have put in writing this blog. I am hoping the same high-grade blog post from you in the upcoming as well. In fact your creative writing abilities has inspired me to get my own blog now. Really the blogging is spreading its wings quickly. Your write up is a good example of it.
    Aerie Promo Code2019-02-18 16:16 (18小时前)回复
  2. A big thank you for your blog article.Thanks Again. Want more.
    anal porno2019-02-17 15:21 (2天前)回复
  3. cialis tadalafil 5mg once a day cialis cost sildenafil and tadalafil combination
    buy generic cialis2019-02-17 13:06 (2天前)回复
  4. I think that is an fascinating point, it made me think a bit. Thanks for sparking my thinking cap. Sometimes I get so much in a rut that I just believe like a record.
    child porn2019-02-17 11:48 (2天前)回复
  5. Thanks-a-mundo for the article post.Really thank you! Fantastic.
    Children Book Publisher2019-02-17 09:41 (2天前)回复
  6. Really enjoyed this post.Much thanks again. Want more.
1 65 66 67