c++ 大数模板及例题

布满荆棘的人生 2022-08-25 08:08 132阅读 0赞

比较好的一个大数模板 贴在这里备用

string sum(string s1,string s2)
    {
    	if(s1.length()<s2.length())
    	{
    		string temp=s1;
    		s1=s2;
    		s2=temp;
    	}
    	int i,j;
    	for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
    	{
    		s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节
    		if(s1[i]-'0'>=10)
    		{
    			s1[i]=char((s1[i]-'0')%10+'0');
    			if(i) s1[i-1]++;
    			else s1='1'+s1;
    		}
    	}
    	return s1;
    }

顺便在来个例题，用大数模板求大斐波那契数 nyoj655 光棍的yy

题目[http://acm.nyist.net/JudgeOnline/problem.php?pid=655][http_acm.nyist.net_JudgeOnline_problem.php_pid_655]

直接套用模板没有任何技巧代码：

#include <iostream>
    #include <string>
    #include <cstdio>
    using namespace std;
    string sum(string s1,string s2)
    {
    	if(s1.length()<s2.length())
    	{
    		string temp=s1;
    		s1=s2;
    		s2=temp;
    	}
    	int i,j;
    	for(i=s1.length()-1,j=s2.length()-1;i>=0;i--,j--)
    	{
    		s1[i]=char(s1[i]+(j>=0?s2[j]-'0':0));   //注意细节
    		if(s1[i]-'0'>=10)
    		{
    			s1[i]=char((s1[i]-'0')%10+'0');
    			if(i) s1[i-1]++;
    			else s1='1'+s1;
    		}
    	}
    	return s1;
    }
    int main()
    {
        int n,T;
        scanf("%d",&T);
        while(T--)
        {
            string s;cin>>s;
            if(s.size()==1){
                    printf("1\n");continue;
            }
            else if(s.size()==2)
            {
                printf("2\n");continue;
            }
            string ans,a="1",b="2";
            for(int i=3;i<=s.size();i++)
            {
                ans=sum(a,b);
                a=b;
                b=ans;
            }
            cout<<b<<endl;
        }
        return 0;
    }

[http_acm.nyist.net_JudgeOnline_problem.php_pid_655]: http://acm.nyist.net/JudgeOnline/problem.php?pid=655