Proof Wanted

Правка en2, от 040902fyn, 2021-10-19 02:59:02

There are four towers who is named A,B,C,D respectively.

Initially there are n disks. All disks are different in size.

The disks are initially stacked on tower A increasing in size from the top to the bottom.

You can't put disk A onto disk B if the size of disk A is bigger than the size of disk B.

The goal is to transfer all of the disks from tower A to tower D with smallest amount of options.

Above all is the description of the problem.

The solution uses $$$f(n)$$$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower D. And it uses $$$d(n)$$$ to represent the minimum times to transfer n disks increasing in size from the top to the bottom from tower A to tower C without the help of tower D (It means you can't stack disks on tower D).

Then the solution claims that $$$f(n) = min(2 \times f(i) + d(n - i)) (1 \le i \lt n)$$$, but I don't know why. Please give me a proof,thanks!

Теги #proof, recruitment

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский 040902fyn 2021-10-19 02:59:02 2 Tiny change: 're n disks, All disks' -> 're n disks. All disks'
en1 Английский 040902fyn 2021-10-18 06:01:13 987 Initial revision (published)