汉诺塔

 1 #include <iostream>
 2 using namespace std;
 3 int main()
 4 {
 5   int T, n, i;
 6   cin >> T;
 7   int x[100];
 8   while (T--)
 9   {
10     cin >> n;
11     for (i = 1; i <= n; i++)
12       cin >> x[i];
13     int cur = 3; //表示当前 金片应该在的针的编号 ，初始时表示最大的那个应当在3上
14     int ans = 0;
15     for (i = n; i > 0; i--) //从最大的开始
16     {
17       if (x[i] != cur) // 如果第i个金片的不在cur上 ，最好的情况下把它移到cur上需要 2^(n-1) 步
18       {
19         cur = 6 - cur - x[i];  // 根据第i个金片的位置确定第i-1个金片应该在的位置
20         ans += 1 << (i - 1);
21       }
22     }
23     cout << ans << endl;
24   }
25   return 0;
26 }