#include <iostream>

#include <string>

using namespace std;

string add(string a,string b)

{

    int len1=a.length();

    int len2=b.length();

    int i;

    if(len1>len2)

    {

        for(i=;i<=len1-len2;i++)

            b=""+b;

    }

    else

    {

        for(i=;i<=len2-len1;i++)

            a=""+a;

    }

    string str;

    int cf=,t;

    len1=a.length();

    for(i=len1-;i>=;i--)

    {

        t=a[i]-''+b[i]-''+cf;

        cf=t/;

        t%=;

        str=char(t+'')+str;

    }

    if(cf!=)

        str=char(cf+'')+str;

    return str;

}

string fun(int n)

{

    string f[];

    f[]="";

    f[]="";

    f[]="";

    f[]="";

    int i;

    string a,b,c;

    for(i=;i<=n;i++)

    {

        a=add(f[i-],f[i-]);

        b=add(f[i-],f[i-]);

        f[i]=add(a,b);

    }

    return f[n];

}

int main()

{

    int n;

    while(cin>>n)

    {

        string str;

        str=fun(n);

        cout<<str<<endl;

        cout<<endl;

    }

    return ;

}

方法一：

利用二维数组和亿进制。

#include<cstdio>

#include <iostream>

#include<cstring>

using namespace std;

int str[][];                //必须为int类型。

int main()

{

    memset(str,,sizeof(str));

    str[][]=;

    str[][]=;

    str[][]=;

    str[][]=;

    int i,j,ans=,c,n;

    for(i=;i<;i++)

    {

        for(j=,c=;j<;j++)          //循环，来将j个数组的8位数字的情况全部列举出。

        {

            ans=str[i-][j]+str[i-][j]+str[i-][j]+str[i-][j]+c;

            c=ans/;

            str[i][j]=ans%;           //每一个数组存8位数字，c来判定是否进位。

    }

    }

    while(cin>>n)

    {

        j=;

        while(!str[n][j])       //首位有0，清除掉0。

        j--;

        cout<<str[n][j];           //开头的首0清除掉后的x位数字，可能小于8位。

        for(i=j-;i>=;i--)

        printf("%08d",str[n][i]);            //每8位数字输出一组，不足的自动部0。

        printf("\n");

    }

    return ;

}

方法二：

利用滚动数组求解

#include <iostream>

#include <cstdio>

#include <cstring>  

using namespace std;  

int t[][];  

int main()

{

    int n;

    while(scanf("%d",&n) != EOF)

    {

        memset(t,,sizeof(t));

        t[][] = ;

        t[][] = ;

        t[][] = ;

        t[][] = ;

        for(int i = ;i < n;i++)

        {

            int carry = ;

            int k = i % ;

            for(int j = ;j < ;j++)

            {

                int x = t[][j] + t[][j] + t[][j] + t[][j];

                t[k][j] = x + carry;

                carry = t[k][j] / ;

                t[k][j] %= ;

            }

        }

        int k = ;

        while(t[(n - ) % ][--k] == );

        for(int i = k;i >= ;i--)

        {

            printf("%d",t[(n - ) % ][i]);

        }  

        printf("\n");  

    }  

    return ;

}

import java.math.BigInteger;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner (System.in);

        BigInteger a[]=new BigInteger[10001];

        int n;

        while(in.hasNextInt()) {

            n=in.nextInt();

            a[1]=BigInteger.ONE;

            a[2]=BigInteger.ONE;

            a[3]=BigInteger.ONE;

            a[4]=BigInteger.ONE;

            for(int i=5;i<=10000;i++) {

                a[i]=BigInteger.ZERO;

                a[i]=a[i].add(a[i-1]);

                a[i]=a[i].add(a[i-2]);

                a[i]=a[i].add(a[i-3]);

                a[i]=a[i].add(a[i-4]);

            }

            System.out.println(a[n]);

        }

    }

}