若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1539: The Priest Mathematician

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,341

题目描述

The ancient folklore behind the “Towers of Hanoi'' puzzle is quite well known. A more recent legend tells us that once the Brahmin monks discovered how long it would take to finish transferring the 64 discs from the needle which they were on to one of the other needles, they decided to find a faster strategy and be done with it.

The Four Needle (Peg) Tower of Hanoi
One of the priests at the temple informed his colleagues that they could achieve the transfer in single afternoon at a one disc-per-second rhythm by using an additional needle. He proposed the following strategy:

First move the topmost discs (say the top k discs) to one of the spare needles.
Then use the standard three needles strategy to move the remaining n – k discs (for a general case with n discs) to their destination.
Finally, move the top k discs into their final destination using the four needles.
He calculated the value of k which minimized the number of movements and found that 18,433 transfers would suffice. Thus they could spend just 5 hours, 7 minutes, and 13 seconds with this scheme versus over 500, 000 million years without the additional needle!

Try to follow the clever priest's strategy and calculate the number of transfers using four needles, where the priest can move only one disc at a time and must place each disc on a needle such that there is no smaller disc below it. Calculate the k that minimizes the number of transfers under this strategy.

输入

The input file contains several lines of input. Each line contains a single integer 0<= N<=10, 000 giving the number of disks to be transferred. Input is terminated by end of file.

输出

For each line of input produce one line of output which indicates the number of movements required to transfer the N disks to the final needle.

样例输入

1
2
28
64

样例输出

1
3
769
18433

参考代码

暂无

解析

暂无

hustoj

发表评论 取消回复

邮箱地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 Skip 原站点
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist