在NOJ上遇到關于漢諾塔步數的求解問題
開始讀時一臉懵逼，甚至不知道輸入的資料是什么意思
題目描述：給出漢諾塔的兩個狀態，從初始狀態移動到目的狀態所需要的最少步數
對于初級漢諾塔步數問題，我們可以直接通過公式進行求解，概括來說，從一個柱子到另一個柱子移動n個盤子，需要2的n次方-1步
下面看一下輸入的是什么資料，通過一個例子進行說明
下面看問題的求解
對題目的分析就到這，下面給出具體的程式：
#include <stdio.h> #include <stdlib.h> #include <math.h> long long fun(int *num,int i,int f) { if(i<0)return 0; if(num[i]==f)return fun(num,i-1,f); return fun(num,i-1,6-num[i]-f)+(1LL<<(i-1)); } int main() { long long ans; int n; int start[60],target[60]; while(scanf("%d",&n)) { if(n==0)break; for(int i = 1;i<=n;i++)scanf("%d",&start[i]); for(int i = 1;i<=n;i++)scanf("%d",&target[i]); int index_end = n; ans = 0; while(index_end>=1 && start[index_end]==target[index_end]){ index_end--; } if(index_end==0){ printf("0\n"); continue; }else{ int other = 6-start[index_end]-target[index_end]; ans = fun(start,index_end-1,other)+fun(target,index_end-1,other)+1; printf("%lld\n",ans); } } return 0; }
第一次博客園的總結就這到這啦
如果大家有疑問可以留言討論
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/135943.html
標籤：其他
上一篇：用書