uva 10795 A Different Task

<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=456&amp;page=show_problem&amp;problem=1736">點選打開連結uva 10795</a>

思路：遞歸

<a href="http://www.cnblogs.com/arbitrary/archive/2012/12/11/2813245.html">點選打開連結</a>

1  新漢諾塔：标準的漢諾塔上有n個大小各異的盤子。給定一個初始局面，求它到給定目标局面至少需要多少步

2  舊漢諾塔：将A柱子上的n個盤子，移到B柱子上

3  舊漢諾塔 f(n)=f(n-1)+1+f(n-1)=(2^n)-1;f(1)=1;

    首先需要把編号最大的盤子N移到目标柱子上，于是需要有這樣的局面：假設N需要從A移到B，A隻有N，B是空的，C上面是N-1到1，是以需要将N-1移到C，然後将N移到B，最後将N-1移到B。是以f(n)=2*f(n-1)+1;

4 新漢諾塔問題：首先找最大不在目标柱子上的盤子K，因為如果最大的盤子在目标柱子上它不需要移動，也不礙事。

   是以問題就成了把K移動到目标柱子，把1到(k-1)移動到中轉柱子，是以假設K從A移動到B，A隻有K，B是空的，C上面是K-1到1，把這個局面稱為參考局面。因為移動是對稱的，是以從參考局面移到目标局面與目标局面移到參考局面是一樣的步數。

   是以問題變成答案=從初始局面移到參考局面步數+目标局面移到參考局面步數+1；

5 需要寫一個函數f(P,i,final),表示已知個盤子的初始柱面編号數組為P，把1到i移動到final的步數，本題答案是f(start,k-1,6-start[k]-finish[k])+f(finish,k-1,6-start[k]-finish[k])+1;

6 計算f(P,i,final),若p[i]=final，則f(P,i,final)=f(P,i-1,final);

   否則需要把前i-1個盤子挪到中轉盤去，将盤子i移到柱子final去，做後把前i-1個盤子從中轉盤移到柱子final.。

   最後一步是把i-1個盤子從一個柱子移到另一個柱子，根據舊漢諾塔問題，這個步驟需要2^(i-1)-1步，加上移動盤子i那一步，一共需要2^(i-1)步。f(P,i,final)=f(P,i-1,6-p[i]-final)+2^(i-1);

代碼：

<a target="_blank" href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;category=456&amp;page=show_problem&amp;problem=1736"></a>