3076. 斐波那契数列

10175102262 LarsPendragon

标准的大数运算题,附C代码

#include <stdio.h>
int main(void)
{
    int T;
    scanf("%d",&T);
    int i, j, fib[121][27], n;
    for(i=0; i<121; i++) for(j=0; j<27; j++) fib[i][j]=0;
    fib[1][0]=1;
    for(i=2; i<121; i++)
        for(j=0; j<26; j++)
        {
            fib[i][j]+=(fib[i-1][j]+fib[i-2][j]);
            fib[i][j+1]=fib[i][j]/10;
            fib[i][j]%=10;
        }
        for(i=0; i<T; i++)
        {
            scanf("%d",&n);
            printf("case #%d:\n",i);
            for(j=26; j+1; j--)
                if(fib[n][j]) break;
            for(;j+1; j--)
                printf("%d",fib[n][j]);
            if(n==0) printf("0");
            printf("\n");
        }
    return 0;
}
Li Dao

高精度+高精度,封装的好一点,另外,可以先全部算好,要什么输出什么(离线计算)

include

using namespace std;
typedef vector BIG;
vector V;
int T;

BIG create(int aa)
{
BIG ret;
ret.push_back(aa);
while(ret[ret.size()-1]>=10)
{
int top=ret.size()-1;
ret.push_back(ret[top]/10);
ret[top]%=10;
}
return ret;
}
BIG operator+(const BIG& aa,const BIG& bb)
{
BIG ret;
for(int i=0;ibb.size())
for(int i=bb.size();i=10)
{
int top=ret.size()-1;
ret.push_back(ret[top]/10);
ret[top]%=10;
}
return ret;
}
void print(const BIG& aa)
{
for(int i=aa.size()-1;i>=0;i–) cout<>n;
print(V[n]);
return;
}
int main()
{
scanf(“%d”,&T);
init();
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

Master X

基本的大数题,做法很多,来个巨傻的字符串打法……

include

using namespace std;
int plu(char s1[],char s2[],char s3[],int l1,int l2)
{
int cnt=0;
int jin=0;

while(l1>=0&&l2>=0)
{
   int num=s1[l1]-'0'+s2[l2]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l1--,l2--;
}
while(l1>=0)
{
     int num=s1[l1]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l1--;
}
  while(l2>=0)
{
     int num=s2[l2]-'0'+jin;
   jin=num/10;
   num=num%10;
   s3[cnt]=num+'0';
   cnt++;
   l2--;
}
if(jin!=0) s3[cnt++]=jin+'0';

return cnt-1;

}
void solve()
{
char s1[50],s2[50],s3[50];
strcpy(s1,”0”);
strcpy(s2,”1”);
int l1=strlen(s1)-1,l2=strlen(s2)-1;
int l3;
int n;
cin>>n;
if(n==0) cout<=0;l3–) cout<>T;
for(int i=0;i<T;i++)
{
printf(“case #%d:\n”,i);
solve();
}
}

13627999316

这么裸的大数+斐波那契,直接用python实现吧,使用记忆化搜索降低时间复杂度:

dp = [-1 for i in range(125)]
def F(n):
    if(n == 0): return 0
    if(n == 1 or n == 2): return 1
    if(dp[n] != -1): 
        return dp[n]
    else:
        dp[n] = F(n-1) + F(n-2)
        return dp[n]

T = int(input())
for i in range(T):
    n = int(input())
    print("case #%d:"%i)
    print(F(n))
你当前正在回复 博客/题目
存在问题!