[ZJ][遞迴] d734. 另类Hanoi＠Morris' Blog｜PChome Online 個人新聞台

2014-01-30 15:07:37| 人氣1,742| 回應0 | 上一篇 | 下一篇

[ZJ][遞迴] d734. 另类Hanoi

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

设有n个大小不同的中空圆盘，按从小到大的顺序从1到n编号。将这n个圆盘任意的迭套在三根立柱上，立柱的编号依次为 a、b、c ，这个状态称为初始状态。

现在要求找到一种步数最少的移动方案，使得从初始状态转变为目标状态。

移动时有如下要求：

* 一次只能移动一个盘。

* 不允许把大盘移到小盘上面。

輸入說明：

第一行数字n(1<=n<=20)，表示状态中圆盘总数。

第二行表示初始状态，有n个数字，第i个数字a[i]表示第i个圆盘放在第a[i]个立柱上。

第三行表示目标状态，有n个数字，第i个数字b[i]表示第i个圆盘放在第b[i]个立柱上。

不必EOF判断。

輸出說明：

输出移动步骤时，需按照 ring x : y -> z 的格式，其中x为整数，y、z为a、b、c其中一个。
最后在输出最少步数。

範例輸入：

5
1 1 1 2 2
3 1 2 2 2

範例輸出：

ring 1 : a -> b
ring 2 : a -> c
ring 1 : b -> c
ring 3 : a -> b
ring 1 : c -> b
ring 2 : c -> a
ring 1 : b -> c
7

將問題拆成 "隨便一個狀態集中到某一個目標柱上" 和 "某一個狀態到另一個狀態"

#include <stdio.h>
#define mod 1000000007
int init[25], goal[25], n;
int ret = 0;
char label[] = " abc";
void hanoiArbitrarily(int n, int goal) {
   if(n == 0)
       return;
   if(init[n] != goal) {
       int target = 6;//temp buffer.
       target -= init[n];
       target -= goal;
       hanoiArbitrarily(n-1, target);// move others into buffer.
       printf("ring %d : %c -> %c\n", n, label[init[n]], label[goal]);
       init[n] = goal;//move n-th disk to goal.
       ret++;
       hanoiArbitrarily(n-1, goal);
   } else {
       hanoiArbitrarily(n-1, goal);
   }
}
void hanoi(int n) {
   if(n == 0)   return;
   if(init[n] != goal[n]) {
       int target = 6;
       target -= init[n];
       target -= goal[n];
       hanoiArbitrarily(n-1, target);
       for(int i = 1; i < n; i++)
           init[i] = target;
       printf("ring %d : %c -> %c\n", n, label[init[n]], label[goal[n]]);
       ret++;
       init[n] = goal[n];//move n-th disk to goal.
   }
   hanoi(n-1);
}
int main() {
   int i;
   while(scanf("%d", &n) == 1 && n) {
       for(i = 1; i <= n; i++)
           scanf("%d", &init[i]);
       for(i = 1; i <= n; i++)
           scanf("%d", &goal[i]);
       ret = 0;
       hanoi(n);
       printf("%d\n", ret%mod);
   }
   return 0;
}

我要檢舉

#d734#另类Hanoi#遞迴

台長： Morris

您可能對以下文章有興趣

[ZJ] a473. 外援計畫

[ZJ][0/1背包] a587. 祖靈好孝順 ˋˇˊ

[ITSA桂冠][n維堆] a574. ITSA2012 桂冠 n維區間查詢

[ZJ][2DST][zkw] d800. ST版区间MAX

人氣(1,742) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: ZeroJudge |
此分類下一篇:[ZJ][中線定理] d408. 我要最小值 (Part 2)
此分類上一篇:[ZJ][大數除法] a667. 可怕的除法

回應(0)