首页 > 代码库 > ural 2029 Towers of Hanoi Strike Back (数学找规律)
ural 2029 Towers of Hanoi Strike Back (数学找规律)
ural 2029 Towers of Hanoi Strike Back
链接：http://acm.timus.ru/problem.aspx?space=1&num=2029
题意：汉诺塔问题，给定一串只有（A, B, C）的字符串（A代表在第一根柱子，B代表在第二根柱子，C代表在第三根柱子），从前往后代表盘子的大小，第 i 个字母代表di i 个盘子在某个柱子上。问移动给定字母状态的盘子最少需要多少步。
思路：首先，从后往前看（最大的盘子），如果不在当前柱子上，那么移动到目标柱子需要 2^(n-1) 步，其余的盘子都移动到剩下的柱子上；若目标柱子与当前柱子相同，则不需要移动。当移动到目标柱子，该盘子不需要再考虑，依次类推，就可求出移动步数。
代码：
1 #include <climits> 2 #include <cstdio> 3 #include <cstring> 4 #include <cctype> 5 #include <cmath> 6 #include <ctime> 7 #include <cstdlib> 8 #include <cstdarg> 9 #include <iostream>10 #include <fstream>11 #include <iomanip>12 #include <sstream>13 #include <exception>14 #include <stdexcept>15 #include <memory>16 #include <locale>17 #include <bitset>18 #include <deque>19 #include <list>20 #include <map>21 #include <set>22 #include <queue>23 #include <stack>24 #include <vector>25 #include <algorithm>26 #include <iterator>27 #include <functional>28 #include <string>29 #include <complex>30 #include <valarray>31 32 using namespace std;33 34 typedef long long ll;35 const int N = 55;36 ll bit[N];37 char s[N];38 39 inline void init() {40 bit[0] = 1LL;41 for(int i = 1; i < N; ++i) bit[i] = (bit[i-1] * 2LL);42 return ;43 }44 45 int n;46 int pos, nxt;47 48 void solve(){49 pos = nxt = 1;50 ll ans = 0LL;51 for(int i = n-1; i > -1; --i) {52 int k = s[i] - ‘A‘ + 1; // A : 1 ; B : 2 ; C : 3;53 if(k == nxt) continue;54 nxt = 6 - nxt - k, pos = k; // nxt 代表第i个盘子除当前位置柱子和目标柱子，剩下的那根55 //printf("nxt = %d pos = %d\n", nxt, pos);56 ans += bit[i];57 }58 printf("%I64d\n", ans);59 return ;60 }61 62 int main()63 {64 init();65 66 while(~scanf("%d", &n)) {67 scanf("%s", s);68 solve();69 }70 return 0;71 }
ural 2029 Towers of Hanoi Strike Back (数学找规律)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。