4 条题解

  • 6
    @ 2023-6-2 21:03:21

    《斐波那契数列七解》 希望对你有帮助哦😄

  • 0
    @ 2025-3-30 17:09:39 
    fi=[1,1,2]
for i in range(3,1000):
    fi.append(fi[i-1]+fi[i-2])
print(sum(fi[:int(input())]))

    py的 不用写高精度真是太爽辣

    • -1
      @ 2023-6-4 15:40:12

      大整数类真的太棒了！

      #include<bits/stdc++.h>
using namespace std;
struct BigInteger
{
	static const int BASE=100000000;
	static const int WIDTH=8;
	bool sign;
	size_t length;
	vector<int> num;
	BigInteger(long long x=0) 
	{ 
		*this=x;
	}
	BigInteger(const string &x) 
	{
		*this=x;
	}
	BigInteger(const BigInteger &x) 
	{
		*this=x;
	}
	void cutLeadingZero()
	{
		while(num.back()==0&&num.size()!=1)
		{
			num.pop_back();
		}
		int tmp=num.back();
		if(tmp==0) length=1;
		else
		{
			length=(num.size()-1)*WIDTH;
			while(tmp>0)
			{
				length++;
				tmp/=10;
			}
		}
	}
	BigInteger &operator=(long long x)
	{
		num.clear();
		if(x>=0) sign=true;
		else
		{
			sign=false;
			x=-x;
		}
		do
		{
			num.push_back(x%BASE);
			x/=BASE;
		}while(x>0);
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const string &str)
	{
		num.clear();
		sign=(str[0]!='-');
		int x,len=(str.size()-1-(!sign))/WIDTH+1;
		for(int i=0;i<len;i++)
		{
			int End=str.size()-i*WIDTH;
			int start=max((int)(!sign),End-WIDTH);
			sscanf(str.substr(start,End-start).c_str(),"%d",&x);
			num.push_back(x);
		}
		cutLeadingZero();
		return *this;
	}
	BigInteger &operator=(const BigInteger &tmp)
	{
		num=tmp.num;
		sign=tmp.sign;
		length=tmp.length;
		return *this;
	}
	BigInteger abs() const
	{
		BigInteger ans(*this);
		ans.sign=true;
		return ans;
	}
	const BigInteger &operator+() const 
	{
		return *this; 	
	}
	BigInteger operator-() const
	{
		BigInteger ans(*this);
		if (ans!=0) ans.sign=!ans.sign;           
		return ans;
	}
	BigInteger operator+(const BigInteger &b) const
	{
		if(!b.sign)
		{
			return *this-(-b);
		}
		if(!sign)
		{
			return b-(-*this);
		}
		BigInteger ans;
		ans.num.clear();
		for(int i=0,g=0;;i++)
		{
			if(g==0&&i>=num.size()&&i>=b.num.size()) break;              
			int x=g;
			if(i<num.size()) x+=num[i];               
			if(i<b.num.size()) x+=b.num[i];               
			ans.num.push_back(x%BASE);
			g=x/BASE;
		}
		ans.cutLeadingZero();
		return ans;
	}
	BigInteger operator-(const BigInteger &b) const
	{
		if(!b.sign)
		{
			return *this+(-b);
		}
		if(!sign)
		{
			return -((-*this)+b);
		}
		if(*this<b)
		{
			return -(b-*this);
		}
		BigInteger ans;
		ans.num.clear();
		for(int i=0,g=0;;i++)
		{
			if (g==0&&i>=num.size()&&i>=b.num.size()) break;             
			int x=g;
			g=0;
			if(i<num.size())
				x+=num[i];
			if(i<b.num.size())
				x-=b.num[i];
			if (x<0)
			{
				x+=BASE;
				g=-1;
			}
			ans.num.push_back(x);
		}
		ans.cutLeadingZero();
		return ans;
	}
	BigInteger operator*(const BigInteger &b) const
	{
		int lena=num.size(),lenb=b.num.size();
		BigInteger ans;
		for(int i=0;i<lena+lenb;i++) ans.num.push_back(0);          
		for (int i=0,g=0;i<lena;i++)
		{
			g=0;
			for (int j=0;j<lenb;j++)
			{
				long long x=ans.num[i+j];
				x+=(long long)num[i]*(long long)b.num[j];
				ans.num[i+j]=x%BASE;
				g=x/BASE;
				ans.num[i+j+1]+=g;
			}
		}
		ans.cutLeadingZero();
		ans.sign=(ans.length==1&&ans.num[0]==0)||(sign==b.sign);
		return ans;
	}
	BigInteger e(size_t n) const
	{
		int tmp=n%WIDTH;
		BigInteger ans;
		ans.length=n+1;
		n/=WIDTH;
		while(ans.num.size()<=n) ans.num.push_back(0);           
		ans.num[n]=1;
		while(tmp--) ans.num[n]*=10;           
		return ans*(*this);
	}
	BigInteger operator/(const BigInteger &b) const
	{
		BigInteger aa((*this).abs());
		BigInteger bb(b.abs());
		if (aa<bb) return 0;            
		char *str=new char[aa.length+1];
		memset(str,0,sizeof(char)*(aa.length+1));
		BigInteger tmp;
		int lena=aa.length,lenb=bb.length;
		for (int i=0;i<= lena-lenb;i++)
		{
			tmp=bb.e(lena-lenb-i);
			while(aa>=tmp)
			{
				str[i]++;
				aa=aa-tmp;
			}
			str[i]+='0';
		}
		BigInteger ans(str);
		delete[] str;
		ans.sign=(ans==0||sign==b.sign);
		return ans;
	}
	BigInteger operator%(const BigInteger &b) const
	{
		return *this-*this/b*b;
	}
	BigInteger &operator++()
	{
		*this=*this+1;
		return *this;
	}
	BigInteger &operator--()
	{
		*this=*this-1;
		return *this;
	}
	BigInteger &operator+=(const BigInteger &b)
	{
		*this=*this+b;
		return *this;
	}
	BigInteger &operator-=(const BigInteger &b)
	{
		*this=*this-b;
		return *this;
	}
	BigInteger &operator*=(const BigInteger &b)
	{
		*this=*this*b;
		return *this;
	}
	BigInteger &operator/=(const BigInteger &b)
	{
		*this=*this/b;
		return *this;
	}
	BigInteger &operator%=(const BigInteger &b)
	{
		*this=*this % b;
		return *this;
	}
	bool operator<(const BigInteger &b) const
	{
		if(sign!=b.sign)
		{
			return !sign;
		}
		else if(!sign&&!b.sign)
		{
			return -b<-*this;
		}
		if (num.size()!=b.num.size())
			return num.size()<b.num.size();
		for (int i=num.size()-1;i>=0;i--)
		{
			if (num[i]!=b.num[i]) return num[i]<b.num[i];               
		}           
		return false;
	}
	bool operator>(const BigInteger &b) const 
	{
		return b<*this;
	}
	bool operator<=(const BigInteger &b) const 
	{ 
		return !(b<*this); 
	}
	bool operator>=(const BigInteger &b) const 
	{ 
		return !(*this<b); 
	}
	bool operator!=(const BigInteger &b) const 
	{
		return b<*this||*this<b; 
	}
	bool operator==(const BigInteger &b) const 
	{
			return !(b<*this)&&!(*this<b); 
	}
	bool operator||(const BigInteger &b) const 
	{
		return *this!=0||b!=0;
	}
	bool operator&&(const BigInteger &b) const 
	{
		return *this!=0&&b!=0; 
	}
	bool operator!() 
	{
		return (bool)(*this==0); 
	}
	friend ostream &operator<<(ostream &out,const BigInteger &x)
	{
		if (!x.sign) out<<'-';           
		out<<x.num.back();
		for (int i=x.num.size()-2;i>=0;i--)
		{
			char buf[10];
			sprintf(buf,"%08d",x.num[i]);
			int _=strlen(buf);
			for (int j=0;j<_;j++) out<<buf[j]; 
		}
		return out;
	}
	friend istream &operator>>(istream &in,BigInteger &x)
	{
		string str;
		in>>str;
		size_t len=str.size();
		int start=0;
		if (str[0]=='-') start=1;           
		if (str[start]=='\0') return in;           
		for (int i=start;i<len;i++)
		{
			if (str[i]<'0'||str[i]>'9') return in;                
		}
		x.sign=!start;
		x=str.c_str();
		return in;
	}
};

typedef BigInteger Big;

const int N = 1e3+10;
Big fi[N];


int main()
{
	fi[1] = 1;
	fi[2] = 1;
	int n;
	Big sum = 2;
	cin >> n;
	if(n == 1) sum = 1;
	else if(n == 2) sum = 2;
	else for(int i=3;i<=n;i++)
	{
		fi[i] = fi[i-1]+fi[i-2];
		sum+=fi[i];
	}
	cout << sum;
	return 0;
}
      • -2
        @ 2023-8-1 16:10:11

        我太喜欢C++啦

        😕 😕 😕

        #include<bits/stdc++.h>

using namespace std;

int a[10000];
int b[10000];
int c[10000];
int d[10000];

int main()
{

    int n;
    cin >>n;
    a[1]=1;
    b[1]=1;
    if(n==1){cout<<"1";}
    if(n==2){cout<<"2";}
    int la=1;
    int lb=1;
    int lc=1;
    int ld=1;
    if(n!=1 && n!=2){
        for(int i=1; i<=n; i++){
            if(i==2){
                d[1]=2;
            }
            if(i>2){
                for(int j=1000; j>=1; j--){
                    if(d[j]!=0){
                        ld=j;
                        break;
                    }
                }
                if(i%3==0){
                    for(int j=lc; j>=1; j--){
                        c[j]=0;
                    }
                    lc=max(la,lb)+1;
                    for(int j=1; j<=max(la,lb); j++){
                        c[j]=a[j]+b[j]+c[j];
                        c[j+1]=c[j+1]+c[j]/10;
                        c[j]=c[j]%10;
                    }
                    if(c[lc]==0){lc--;}
                    for(int j=1; j<=max(ld,lc); j++){
                        d[j]=d[j]+c[j];
                        d[j+1]=d[j+1]+d[j]/10;
                        d[j]=d[j]%10;
                    }
                }
                if(i%3==1){
                    for(int j=la; j>=1; j--){
                        a[j]=0;
                    }
                    la=max(lc,lb)+1;
                    for(int j=1; j<=max(lc,lb); j++){
                        a[j]=a[j]+b[j]+c[j];
                        a[j+1]=a[j+1]+a[j]/10;
                        a[j]=a[j]%10;
                    }
                    if(a[la]==0){la--;}
                    for(int j=1; j<=max(ld,la); j++){
                        d[j]=d[j]+a[j];
                        d[j+1]=d[j+1]+d[j]/10;
                        d[j]=d[j]%10;
                    }
                }
                if(i%3==2){
                    for(int j=lb; j>=1; j--){
                        b[j]=0;
                    }
                    lb=max(lc,la)+1;
                    for(int j=1; j<=max(lc,la); j++){
                        b[j]=a[j]+b[j]+c[j];
                        b[j+1]=b[j+1]+b[j]/10;
                        b[j]=b[j]%10;
                    }
                    if(b[lb]==0){lb--;}
                    for(int j=1; j<=max(ld,lb); j++){
                        d[j]=d[j]+b[j];
                        d[j+1]=d[j+1]+d[j]/10;
                        d[j]=d[j]%10;
                    }
                }
            }
        }
        if(d[ld+1]!=0){ld++;}
        for(int j=ld; j>=1; j--){
            cout<<d[j];
        }
    }

	return 0;
}
        • 1

        [F001]斐波那契前n项和

        信息

        ID
        837
        时间
        1000ms
        内存
        256MiB
        难度
        4
        标签
        递交数
        54
        已通过
        25
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        2. By 北师大台州附中
        3. Worker 0, 87ms
        4. Powered by Hydro v4.18.2 Community