棋盘覆盖。大数

棋盘覆盖

描述

在一个2^k×2^k（1<=k<=100）的棋盘中恰有一方格被覆盖，如图1（k=2时），现用一缺角的2×2方格（图2为其中缺右下角的一个），去覆盖2^k×2^k未被覆盖过的方格，求需要类似图2方格总的个数s。如k=1时，s=1;k=2时，s=5

????????????????????????????????????????????????????????????????????????????????????

图1 ??????????????????????????????????????????????图2??????????????????? ? ?

输入

第一行m表示有m组测试数据；
每一组测试数据的第一行有一个整数数k;

输出

输出所需个数s;

样例输入

3123

样例输出

1521

来源

《算法设计》题

上传者

李剑锋

这道题，与大数有关，与4有关。观察一下，n=1时，为4^0，n=2时，为4^0+4^1,n=3时，为4^0+4^1+4^2;以此类推。

贴上代码

 
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
int a[100][65];
int main()
{
    int T,k=1,c=0,i,j;
    memset(a,sizeof(a));
    a[1][1]=1;
    for(i=2,k=1; i<=100; i++)
    {
        for(j=1,c=0; j<=k; j++)
        {
            a[i][j]=a[i-1][j]*4+c;
            c=a[i][j]/10;
            a[i][j]%=10;
        }
        while(c)
        {
            a[i][++k]=c;
            c/=10;
        }
    }
    for(i=2; i<=100; i++)
    {
        for(int j=1,c=0; j<=k; j++)
        {
            a[i][j]+=a[i-1][j]+c;
            c=a[i][j]/10;
            a[i][j]%=10;
        }
        while(c)
        {
            a[i][++k]=c;
            c/=10;
        }
    }
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(i=k;!a[n][i];i--);
        for(j=i;j>0;j--)
            printf("%d",a[n][j]);
        printf("n");



    }
}
        

（编辑：淮安站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!