有三個立柱A、B、C。A柱上穿有大小不等的圓盤N個,較大的圓盤在下,較小的圓盤在上。要求把A柱上的圓盤全部移到C柱上,保持大盤在下、小盤在上的規律(可借助B柱)。每次移動只能把一個柱子最上面的圓盤移到另一個柱子的最上面。請輸出移動過程。

解答

這是動態規劃問題中的一種,用遞歸來實現較為簡單方便。

對于"將moveSum個圓盤從from柱移動到to柱(借助by柱)"這個問題,我們可以通過以下三步實現:

  • 將from柱最上面的moveSum-1個圓盤移動到by柱(借助to柱)
  • 將from柱上剩下的那1個圓盤直接移動到to柱
  • 將by柱上的moveSum-1個圓盤移動到to柱(借助from柱)

執行的流程如下:

原文鏈接:https://blog.51cto.com/myunix/2399892