12——1715,1041,1047

今天做了三道高精度的题目,感觉棒棒哒12——1715,1041,1047 - 蜗牛 - 追梦少年12——1715,1041,1047 - 蜗牛 - 追梦少年12——1715,1041,1047 - 蜗牛 - 追梦少年

http://acm.hdu.edu.cn/showproblem.php?pid=1715

//1715大斐波拉契数

#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
#define N 1000+10
string s[N];
string add(string s1,string s2)//高精度加法
{
string temp;
if(s1.length()<s2.length())
{
temp=s1;
s1=s2;
s2=temp;
}
for(int i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
{
s1[i]=s1[i]+(j>=0?(s2[j]-'0'):0);
if(s1[i]-'0'>=10)
{
s1[i]=(s1[i]-'0')%10+'0';
if(i)
s1[i-1]++;
else
s1="1"+s1; //string类型的加法,就是把两个字符串连接起来
}
}
return s1;
}
int main()
{
int n,x;
s[1]="1";s[2]="1";s[3]="2";
for(int i=4;i<=1005;i++)
s[i]=add(s[i-1],s[i-2]);
cin>>n;
getchar(); //关键的语句,用来吸收回车键,否则会出现意想不到的错误
while(n--)
{
cin>>x;
cout<<s[x]<<endl;
}
return 0;
}


http://acm.hdu.edu.cn/showproblem.php?pid=1041

//此题关键在于找规律+高精度加法
//a[n]=2^(n-3)+a[n-2];
//另外看了网上的代码,发现他们中的规律是a[n]=a[n-1]+2*a[n-2];
//经检验都是对的
#include<iostream>
#include<string>
using namespace std;
#define N 1010
string addition(string a,string b)
{
string temp;
if(a.size()<b.size())
{
temp=a;
a=b;
b=temp;
}
for(int i=a.size()-1,j=b.size()-1;i>=0;i--,j--)
{
a[i]=a[i]+(j>=0?(b[j]-'0'):0);
if(a[i]-'0'>=10)
{
a[i]=char ((a[i]-'0')%10+'0');
if(i)
a[i-1]++;
else
a="1"+a;
}
}
return a;
}
string s1[N],s2[N];
int main()
{
int n;
s1[1]="0";s1[2]="1";s1[3]="1";
s2[1]="1";s2[2]="2";s2[3]="4";
for(int i=4;i<=1005;i++)
{
s2[i]=addition(s2[i-1],s2[i-1]);
s1[i]=addition(s1[i-2],s2[i-2]);
}
while(cin>>n)
cout<<s1[n]<<endl;
// string a,b;
// while(cin>>a>>b)
// cout<<addition(a,b)<<endl;
return 0;
}
/*
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
#define N 1010
string add(string s,string r)
{
string temp;
if(s.length()<r.length())
{
temp=s;
s=r;
r=temp;
}
for(int i=s.length()-1,j=r.length()-1;i>=0;i--,j--)
{
s[i]=char (s[i]+(j>=0?(r[j]-'0'):0));
if(s[i]-'0'>=10)
{
s[i]=char((s[i]-'0')%10+'0');
if(i)
s[i-1]++;
else
s="1"+s;
}
}
return s;
}
string a[N];
int main()
{
int n,i;
a[1]="0";a[2]="1";a[3]="1";a[4]="3";a[5]="5";a[6]="11";
a[7]="21";
for(i=8;i<1005;i++)
a[i]=add(add(a[i-2],a[i-2]),a[i-1]);
while(scanf("%d",&n)!=EOF)
cout<<a[n]<<endl;
}
*/


http://acm.hdu.edu.cn/showproblem.php?pid=1047

//此题也是高精度加法的运用,只不过是多组数据,用循环处理即可
//此题有个坑点就是格式问题,注意最后一组数据后没有空行,输出的结果之间有空行
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
#define N 100+10
string a[N],b;
string addition(string s1,string s2)
{
string temp;
if(s1.length()<s2.length())
{
temp=s1;
s1=s2;
s2=temp;
}
for(int i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
{
s1[i]=s1[i]+(j>=0?(s2[j]-'0'):0);
if(s1[i]-'0'>=10)
{
s1[i]=(s1[i]-'0')%10+'0';
if(i)
s1[i-1]++;
else
s1="1"+s1;
}
}
return s1;
}
int main()
{
int n,i,num;
cin>>n;
getchar();//加上这条语句,吸收回车键
while(n--)
{
for(i=0;i<=105;i++)
{
cin>>a[i];
if(a[i]=="0")
{
num=i-1;
break;
}
}
b=a[0];
for(i=1;i<=num;i++)
b=addition(b,a[i]);
cout<<b<<endl;
if(n)
cout<<endl;
}
}



评论

© 现实给了梦想多少时间 | Powered by LOFTER