OcrosoftDescription
“汉诺塔”，是一个众所周知的古老游戏。现在我们把问题稍微改变一下：如果一共有4根柱子，而不是3根，那么至少需要移动盘子多少次，才能把所有的盘子从第1根柱子移动到第4根柱子上呢？
为了编程方便，您只需要输出这个结果mod 10000的值。
Input
该题含有多组测试数据，每组一个正整数n。(0<n<=50000)
Output
一个正整数，表示把n个盘子从第1根柱子移动到第4根柱子需要的最少移动次数mod 10000的值。
Sample Input
15
Sample Output
129
Solution
找规律，移动次数是递增的，规律为+2 +2 +4 +4 +4 +8 +8 +8 +8 ...是等差(组)和等比(值)数列的结合，下一组就是5个16了。
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define strend string::npos
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define repe(a,v,b) for(int a=v;a<=b;a++)
typedef long long LL;
const LL LINF = LLONG_MAX / 2;
const int INF = INT_MAX / 2;
const int MAXN = 300000+ 10;
const int MOD = 1000000009;
int gcd(int a, int b)
{
if (!b)return a;
return gcd(b, a%b);
}
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕) 签订契约，成为马猴烧酒吧! (◕‿‿◕)*/
/*(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
using namespace std;
LL a[50010]={1};
void init()
{
LL bound=2,num=2;
int i=1;
while(i<50000)
{
for(int j=0;j<bound;j++)
{
a[i]=a[i-1]+num;
a[i]%=10000;
i++;
}
bound++;
num*=2;
num%=10000;
}
}
int main()
{
init();
int n;
while(cin>>n)
{
n--;
printf("%I64d\n",a[n]);//
}
return 0;
}
欢迎转载，请保留出处与链接。Ocrosoft » FZU 1036 四塔问题