河内塔/汉诺塔问题Thelegendwrittenabovestatesthattheworldwillendwhenall64discshavebeenmoved.Ifthepriestscanmove5discsperminute,howmanyyearswouldittaketomoveall64discs?大致意思：传说描述着世界各

Question

河内塔/汉诺塔问题
The legend written above states that the world will end when all 64 discs have been moved. If the priests can move 5 discs per minute, how many years would it take to move all 64 discs?
大致意思：传说描述着世界各国将结束时,64个光盘才可移至完毕.如果祭司可以每分钟移动5个光盘,需要多少时间可以移动完所有的光盘?

Answer 1

设f(n)为第n次移动的次数,则f(n)=2f(n-1)+1
且f(1)=1;
所以f(n)+1=2(f(n-1)+1)
f(n)+1=(f(1)+1)*2^(n-1)
所以f(n)=2^n-1
所以f(64)=2^64-1
时间为(2^64-1)/5分钟