### 10254.the priest mathematician

## >> বুধবার, ১৮ নভেম্বর, ২০০৯

The ancient folklore behind the"Towers of Hanoi"puzzle invented by E. Lucas in1883is quite well known to us. One more recent legend tells us that the Brahmin monks from Benares never believed that the world could vanish at the moment they finished to transfer the64discs from the needle on which they were to one of the other needles, and they decided to finish the task as soon as possible.

**Fig: The Four Needle (Peg) Tower of Hanoi**

One of the priests at the Benares temple (who loved the mathematics) assured their colleagues to achieve the transfer in the afternoon (the rhythm they had thought was a disc-per-second) by using an additional needle. They couldn't believe him, but he proposed them the following strategy:-- First move the topmost discs (say the topkdiscs) to one of the spare needles.-- Then use the standard three needles strategy to move the remainingn-kdiscs (for a general case with n discs) to their destination.-- Finally, move the topkdiscs into their final destination using the four needles.He calculated the value tokin order to minimize the number of movements and get a total of18433transfers, so they spent just5hours,7minutes and13seconds against the more than500000millions years without the additional needle (as they would have to do2^64-1disc transfers. Can you believe it?)Try to follow the clever priest's strategy and calculate the number of transfer using four needles but according with the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. Of course, the main goal is to calculate the k that minimize the number of transfers (even thought it is not know for sure that this is always the optimal number of movements).

InputThe input file contains several lines of input. Each line contains a single integerN, which is the number of disks to be transferred. Here0<=N<=10000. Input is terminated by end of file.

OutputFor each line of input produce one line of output which indicates the number of movements required to transfer theNdisks to the final needle.

Sample Input:122864Sample Output:1376918433Interesting matter:1.First I submit this code in CPP: Runtime: .068 s Ranking: 172.Second time, I submit this code in JAVA: Runtime: 1.024 Ranking: Can’t see, because CPP code is better

3.Third time ,I submit this code in ANSI C: Runtime: 0.008 Ranking : 2 (What !)

Description:

1. If number of disk is 0, then move 0.2. If number of disk is 1, then move 1.3. If number of disk is 2, then move 3.4. If number of disk is 3, then move 5.5. If number of disk is 4, then move 9.6. If number of disk is 5, then move 13.7. If number of disk is 6, then move 17.8. If number of disk is 7, then move 25. 9. If number of disk is 8, then move 33.10. If number of disk is 9, then move 41.11. If number of disk is 10, then move 49.12. If number of disk is 11 then move 65.13. If number of disk is 12, then move 81.14. If number of disk is 13, then move 97.15. If number of disk is 14, then move 113.16. If number of disk is 15, then move 129.So from disk number 2, we find a series,3,5,9,13,17,25,33,41,49,65,81,97,113,129………………………………………………………………………………………………..Algorithm:

f(n)=f(n-1)+2^i, where f(0)=0,f(1)=1,i=2,3,4,5i=1, then loop = i+1=2, diff=2^1=2loop:1. f(2)=f(1)+2=1+2=32.f(3)=f(2)+2=3+2=5i=2,then loop=i+1=3,diff=2^2=41.f[4]=f[3]+4=5+4=92.f[5]=f[4]+4=9+4=133.f[6]=f[5]+4=13+4=17……******Use Big Number f[0]=0,f[1]=1;i=2;loop_c;int j=1;diff=1;while(i<=max_disk){loop_c=j+1;diff=diff+diff;for(int p=1;p<=loop_c;p++){f[i]=f[i-1]+diff;i++;if(i>max_disk)break;}j++;}Now try yourself…..Or download code:

DOWNLOAD DOCUMENT FILE :

## 1 মন্তব্য(গুলি):

Thanks mi8...

একটি মন্তব্য পোস্ট করুন