投稿    登录
欢迎来访~

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

Java 崔庆才 31567浏览 5评论

扫码或搜索:进击的Coder

发送

即可立即永久解锁本站全部文章

原题:

解题方法:

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

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

更多文章、联系博主、技术交流、商务合作

扫码或搜索:进击的Coder

进击的Coder

微信公众号 扫一扫关注

喜欢 (26)or分享 (0)

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

发表我的评论
取消评论

表情

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

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
(5)个小伙伴在吐槽
  1. 这个不错
  2. Gölcük Evden Eve nakliyat için hizmet talep edenler arasında Gölcük lokasyonu çok fazla. Peki, Gölcük evden eve nakliyat fiyatları nasıl? Hizmet alacağınız nakliyat firması Gölcük evden eve nakliyat fiyatları hakkında bilgiler,, nakliyatın içeriğine göre fiyatının değişiyorsunuzudur. Bunu bilmeniz gerektiğini, aşağı yukarı ne kadar bir ödeme ile nakliyatın olup olmadığını yönlendirerek fikirlerinizi yapabilirsiniz. Bu sebeple dikkat edilmesi gereken fiyat - performans ilişkisidir. Fiyat - Performans İlişkisi; Gölcük nakliyat fiyatları analiz edilebilir dikkat onayı istediğimizde ne istediğinizi, isteğiniz için ne alacağınızı ve ne için ne zaman isteyeceğinizi belirlediniz. Kaliteli bir hizmet almanızı ister, ödemişinizi tutarın çok da önemli olmasıştur. Talep edilen hizmetin son derece önemli olduğu düşünülürse, normal ücretlerin de normal olduğu sonucuna varmıştır. Neden? Çünkü almakta hizmet, eşyalarınızın hiçbirinde zarar görmeden taşınmasıdır. Bunun için elbette olacak olacak. Bunları da değerlendirme yapıyorsanız, direkt olarak en iyi şekilde hizmet sunma avantajı elde etmek oluyor. https://kocaeliguvennakliyat.com/golcuk-evden-eve-nakliyat.html
  3. Kocaeli evden eve nakliyat sorumluluk isteyen büyük bir hizmet dalıdır. Kendi içerisinde safra çok farklı dallara yarılmış olduğudır. Bu sebeplerden dolayı itina ile yönlendirilmesi ve özen gösterilmesi gerekir. Tabi özen göstermenin de yapıldığını belirten kural ve kaide vardır. Bu kurallara harfiyen uymak ister.Kocaeli nakliyat şirketleri arasında işini layıkıyla yapan firmada olduğu gibi sorunların yaşandığı neden olan kuruluşlarda ne zaman ki vardır. Bizim amacımız en iyi firma olmak üzerine bir bir düşüncedir. Bu düşüncenin korunması mutlu müşteri kitlesini olabildiğince üste çıkarmak vardır. Bunun için Kocaeli nakliyat alanında uzun yılardır görev üstlenen ve öneri önem veren kurumsal firma var ve yeni müşterilere daha iyi hizmet sağlaması için en iyi ve kaliteli hizmet sunmaktır. '' güven nakliyat '' sloganıyla çıktığımız bu yolda binlerce kez sağladığımız otel bu konuda en büyük göstergesi ve bizlerin referansıydı. Bu, sizde taşınmaya karar verebilecek Kocaeli evden eve nakliyat için firma seçiminde hizmet talebinde bulunabilirsiniz. Sizlere özel olarak sunulacak olan Kocaeli evden eve nakliyat fiyatları alıp karar vermek için birde firmamız Kocaeli evden eve nakliyat tavsiyesiyla daha net ve doğru karar verebiliyoruz. https://guvennakliyat41.com/kocaeli-evdeneve-nakliyat.html
  4. 很好
  5. 文章不错,使用归纳法根据给定情形推导出一般情形,然后根据推导公式进行编码,逻辑很清晰!
    pcgrw2019-02-25 23:30 回复