Proving of the Non-recursive Algorithm for 4-Peg Hanoi Tower
Jun Wang, Hongfa Wang, Guoying Yue, Nan Xie, Sukui Lu · 2009
A non-recursive algorithm for 4-Peg Hanoi Tower has been proposed in my previous paper without any logical and mathematical proof. So in this paper, the algorithm is verified in a rigorous and systematic way according to array theories mainly. That elements are arranged in an upper triangular array is proved to be scientific, iteration path based on the cross correlation is proved to be a shortcut to solve the problem, and the minimum iteration is proved to be on more than R(n) for a 4-peg problem with n disks. Therefore, the non-recursive algorithm has been proved to be more superior to traditional recursive algorithm theoretically.