題目鏈接

簡介：新漢諾塔問題（給出了初始狀態和目標狀態）

分析：
我們考慮最大的盤子，如果這個盤子初始狀態和中止狀態在一個柱子上，說明我們根本不用移動ta
那么我們找到編號最大的需要移動是盤子k（初始狀態所在的柱子和終止狀態不一樣）
假設k要從x—>y，那么在移動k之前三根柱子的狀態一定是（我們可以忽略那些編號大于k且不需要移動的柱子）：
x：k
y：空
z：1~k-1有序擺放
我們稱這種狀態為中間狀態

由于盤子的移動是可逆的，根據對稱性，
問題所需要的步數就是：（初始狀態到達中間狀態的步數）+（終止狀態到達中間狀態的步數）+1

漢諾塔問題有一個經典結論，不得不提一下：

把n個有序的盤子由一根柱子全部移動到另一根柱子上，所需的步數是：2^n-1

這就是一個遞歸的過程，
遞歸的柿子就可以表示為：f(start,i,final)=f(start,i-1,6-final-start[i])+f(finish,i-1,6-final-start[i])+1
start表示初始狀態，finish表示終止狀態，final表示需要移動到的柱子
我們把柱子依次編號1,2,3，那么除了初始狀態和終止狀態，剩下的那根柱子的編號就是6-final-finish[i]

f(P,now,final)表示當前的狀態是P，我們需要把1~now個盤子全都移動到final上

怎么計算f(P,now,final)呢
如果當前的盤子now已經在目標柱子final上了，那f(P,now,final)=f(P,now-1,final)
如果不在目標柱子上，我們就要分成三步：

• 把now-1個盤子移動到（6-final-P[now]）
• 把第now個盤子移動到final，需要一步
• 把now-1個盤子從（6-final-P[now]）移動到final，注意這里是把now-1個盤子全部按順序移動到final
  根據漢諾塔問題的經典結論，這需要（2^（now-1）-1）步

所以f(P,now,final)=f(P,now-1,6-final-P[now])+2^（now-1）

//這里寫代碼片 #include<cstdio> #include<cstring> #include<iostream> #define ll long longusing namespace std;int n; int start[103],finish[103];ll f(int *P,int now,int final) {if (!now) return 0;if (P[now]==final)return f(P,now-1,final);return f(P,now-1,6-final-P[now])+(1LL << (now-1)); }int main() {int cnt=0;while (scanf("%d",&n)!=EOF&&n){for (int i=1;i<=n;i++) scanf("%d",&start[i]);for (int i=1;i<=n;i++) scanf("%d",&finish[i]);int i=n;while (i>=1&&finish[i]==start[i]) i--;ll ans=0;if (i>=1){ int t=6-start[i]-finish[i];ans=f(start,i-1,t)+f(finish,i-1,t)+1;}printf("Case %d: %lld\n",++cnt,ans);}return 0; }

轉載于:https://www.cnblogs.com/wutongtong3117/p/7673021.html

總結

以上是生活随笔為你收集整理的UVa10795 - A Different Task（递归）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。