Proof Wanted
Разница между en1 и en2, 2 символ(ов) изменены
> 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 < n)$, but I don't know why. Please give me a proof,thanks!↵

История

 
 
 
 
Правки
 
 
  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)