大数相乘，大数相加

大数相乘，大数相加的具体运用！

以杭电的BigNums的7题（1002，1042,1047,1063,1316,1715,1753）为例作为练习！如下：

1002

算法分析：

源码实现：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

#define max 1010

char* cal(char *s1,int l1,char *s2,int l2);
int main()
{

    int m,l1,l2,count=1;
    char a[max],b[max];
    char *result;
    cin>>m;
        while(count<=m)
       {
        memset(a,sizeof(a));
        memset(b,sizeof(b));
        cin>>a>>b;
        l1=strlen(a);
        l2=strlen(b);
        printf("Case %d:n",count);
        printf("%s + %s = ",a,b);
        result=cal(a,b,l2);
        printf("%sn",result);
        if(count<m)
        printf("n");

        count++;

       }

    return 0;
}

char* cal(char *s1,int l2)
{
    int array[max];
    char *result = new char[max];
    memset(result,'',sizeof(result));
    memset(array,-1,sizeof(array));
    int i,j,t,temp;
    for(i=0;i<l1/2;i++)
    {
       temp=s1[i];
       s1[i]=s1[l1-1-i];
       s1[l1-1-i]=temp;
    }

    for(i=0;i<l2/2;i++)
    {
       temp=s2[i];
       s2[i]=s2[l2-1-i];
       s2[l2-1-i]=temp;
    }



    for(i=0;i<l1&&i<l2;i++)
        array[i]=s1[i]-48+s2[i]-48;
    while(i<l2)
    {
        array[i]=s2[i]-48;
        i++;
    }

    while(i<l1)
    {
        array[i]=s1[i]-48;
        i++;
    }


    j=0;
    do{
            if(array[j]/10 > 0)
            {
                temp=array[j]/10;
                array[j]=array[j]%10;
                j++;
                if(array[j]==-1)
                {
                    array[j]++;
                    array[j]+=temp;
                }

                else
                array[j]+=temp;
            }
            else
            {
                j++;
            }

    }while(array[j] != -1);

    t=--j;
    for(i=t,j=0;i>=0;i--,j++)
    {
        result[j]=array[i]+48;
    }
    result[j]='';
       return result;
}

1042

算法分析：

源码实现：

?????????

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#define MAX 30000
using namespace std;
int array[MAX];
char result[MAX];
char number[MAX];
char *p;
char * multyplus(char *s1,int l2)
{
               int k;
               int i,j;
               memset(result,sizeof(result));
               memset(array,sizeof(array));
               for(i=0;i<l1;i++)
               {
                         k=i;
                         for(j=0;j<l2;j++)
                         {
                                 if(array[k]==-1)
                                    array[k++]=(s1[i]-48)*(s2[j]-48);
                                 else
                                 array[k++]+=(s1[i]-48)*(s2[j]-48);
                         }
               }
               for(k=0;;k++)
               {
                       if((array[k+1]==-1)&&(array[k]/10!=0))
                       {
                            array[k+1]++;
                       }
                       array[k+1]+=array[k]/10;
                       array[k]=array[k]%10;
                       if(array[k+1]==-1)
                        break;
               }
               for(i=k,j++)
               {
                       result[j]=array[i]+48;
               }

               result[j]='';
               strcpy(number,result);
               return number;
}
char *itos(int m)
{
    int i;
    char *res = new char[10];
    memset(res,10);
    for(i=0;;i++)
    {
        res[i]=m%10+48;
        m=m/10;
        if(0==m)
            break;
    }
    res[++i]='';
    return res;
}
void transverse(char *temp,int len)
{
    int i,t;
    for(i=0;i<len/2;i++)
    {
        t=temp[i];
        temp[i]=temp[len-1-i];
        temp[len-1-i]=t;
    }
}
char *multi(int m)
{
    int i;
    int len1,len2;
    char *count = new char[10];
    char *temp;
    memset(count,sizeof(count));
    count[0]='1';
    for(i=1;i<=m;i++)
    {
        temp = itos(i);
        len1 = strlen(count);
        len2 = strlen(temp);
        transverse(count,len1);

        if(len1>len2)
            count = multyplus(count,temp,len1,len2);
        else
            count = multyplus(temp,count,len2,len1);

    }
    return count;
}
int main()
{
    int m;
    char *num;
    while(scanf("%d",&m)!=-1)
    {
        num = multi(m);
        cout<<num<<endl;
    }
    return 0;
}

1047

算法分析：

???? 和1002差不多，只是这里是多位连续相加，1002只是两个数相加

源码实现：

????

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAX 1000
char *result = new char[MAX];
char *input = new char[MAX];
char *res = new char[MAX];
int array[MAX];

char* cal(char *s1,int l2)
{

    memset(array,j++)
    {
        result[j]=array[i]+48;
    }
    result[j]='';

       return result;
}
int main()
{
    int m;
    int i;
    int len1,len2;
    cin>>m;
        for(i=1;i<=m;i++)
        {
                memset(result,sizeof(result));
                result[0]='0';
                memset(input,sizeof(input));
                while(scanf("%s",input)!=-1)
                {
                       if(input[0]=='0')
                         break;
                       strcpy(res,input);
                       len1 = strlen(result);
                       len2 = strlen(res);
                       result = cal(result,res,len2);

                }
                cout<<result<<endl;
                if(i<m)
                    cout<<endl;
        }
    return 0;
}

1063

算法分析：

???

源码实现：

????

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAX 1000
char result[MAX];
int array[MAX];
char number[MAX];
void multyplus(char *s1,result);
               return;
}
int FindPointPosition(char *s)
{
    int i,len=strlen(s);
    for(i=0;i<len;i++)
    {
        if(s[i]=='.')
        {
            for(j=i;j<len-1;j++)
                s[j]=s[j+1];
                s[len-1]='';

            return 5-i;
        }

    }
    if(i>=len)
        return 0;
}
void transverse(char *s)
{
    int len=strlen(s);
    int i,t;
    for(i=0;i<len/2;i++)
    {
        t=s[i];
        s[i]=s[len-1-i];
        s[len-1-i]=t;
    }
}

void killzero(char *s)
{
    int len=strlen(s);
    int i,j;
    for(i=0;i<len;i++)
    {
        if(s[i]!='0')
        {
            j=i;
            break;
        }
    }
    for(i=0;j<=len-1;)
    {
        s[i++]=s[j++];
    }
    for(;i<=len-1;)
    {
        s[i++]='';
    }
}
int main()
{
    char a[7];
    int m,i,k,l,flag,label,f;
    int point;
    int len;
    while(scanf("%s%d",&a,&m)!=-1)
    {
        flag=1;
        point=m*FindPointPosition(a);
        killzero(a);//kill the pre zero
        if(a[0]=='')
        {
            cout<<"0"<<endl;
            flag=0;
        }
        else if(m==0)
        {
            cout<<"1"<<endl;
            flag=0;
        }

        if(flag!=0)
        {
            memset(number,sizeof(number));
            strcpy(number,a);

            if(m!=1)
            {
                transverse(a);
                for(i=1;i<=m-1;i++)
                {
                    transverse(number);

                    multyplus(number,strlen(number),strlen(a));
                }
            }



        memset(result,sizeof(result));
        len=strlen(number);
        j=len-point;//确定小数点的位置，
        for(i=len-1;i>=0;i--)
            if(number[i]!='0'||i==(j-1))
            break;
        len=i;
        if(j>0)
        {
            for(i=len,k=0;i>j-1;)
            {
                result[k++]=number[i--];
            }
            label=k;
            result[k++]='.';
            for(;i>=0;)
                result[k++]=number[i--];
            k--;
        }
        else
        {
            for(i=len,k=0;i>=0;)
            {
                result[k++]=number[i--];
            }
            for(;i>=j;i--)
                result[k++]='0';
            label=k;
            result[k]='.';
        }

        for(f=0;f<=label;f++)
        {
            if(f==0&&result[f]=='.')
            {
                l=1;
                break;
            }

            if(result[f]!='0'&&result[f]!='.')
            {
                l=f;
                break;
            }

        }
        if(f>label)
            l=f;
        for(;k>=l;k--)
        {
            cout<<result[k];
        }

        cout<<endl;
        }
    }

    return 0;
}

1316

算法分析：

???? 主要就是计算斐波那契数列，和大数加法类型的类似！

源码实现：

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAX 150
int array[MAX];
char s1[MAX],s2[MAX];
char f1[MAX],f2[MAX];
char temp1[MAX],temp2[MAX];
char *f3 = new char[MAX];
char* Fibonacci(char *s1,j++)
    {
        f3[j]=array[i]+48;
    }
    f3[j]='';

       return f3;
}
int Strcmp(char *s1,char *s2)
{
    int len1=strlen(s1);
    int len2=strlen(s2);
    if(len1>len2)
        return 1;
    else if(len1<len2)
         return -1;
         else
         return strcmp(s1,s2);
}
int main()
{
    int count,l2;
    while(scanf("%s%s",s1,s2),s1[0]!='0'||s2[0]!='0')
    {
        memset(f1,sizeof(f1));
        memset(f2,sizeof(f2));
        memset(temp1,sizeof(temp1));
        memset(temp2,sizeof(temp2));
        f1[0]='1';
        f2[0]='2';
        count = 0;
        l1=Strcmp(f1,s1);
        l2=Strcmp(f1,s2);
        if(l1>=0 && l2<=0)
            count++;
        l1=Strcmp(f2,s1);
        l2=Strcmp(f2,s2);
        if(l1>=0 && l2<=0)
            count++;
        f3=Fibonacci(f1,strlen(f1),f2,strlen(f2));
        l1=Strcmp(f3,s2);
        while(l1<=0)
        {
             l2=Strcmp(f3,s1);
             if(l2>=0)
             count++;
             memset(f1,sizeof(f1));
             memset(temp1,sizeof(temp1));
             strcpy(f1,f2);
             strcpy(temp1,f1);
             memset(temp2,sizeof(temp2));
             memset(f2,sizeof(f2));
             strcpy(f2,f3);
             strcpy(temp2,f2);
             memset(f3,sizeof(f3));
             f3=Fibonacci(temp1,strlen(temp1),temp2,strlen(temp2));
             l1=Strcmp(f3,s2);
        }
       cout<<count<<endl;
    }
    return 0;
}

1715

算法分析：

???? 同上题；

源码实现：

#include <iostream>
#include <string.h>
using namespace std;
#define MAX1 1002
#define MAX2 300
char s[MAX1][MAX2];
char temp1[MAX2],temp2[MAX2];
int array[MAX2];

void Fibonacci(char *s1,int l2,int m)
{

    memset(array,j++)
    {
        s[m][j]=array[i]+48;
    }
    s[m][j]='';

    return;
}
void init(char s[][MAX2])
{
    memset(s,sizeof(s));
    memset(temp1,sizeof(temp1));
    memset(temp1,sizeof(temp2));
    s[1][0]='1';
    s[2][0]='1';
    for(int i=3;i<=1000;i++)
    {
        memset(temp1,sizeof(temp1));
        memset(temp1,sizeof(temp2));
        strcpy(temp1,s[i-1]);
        strcpy(temp2,s[i-2]);
        Fibonacci(temp1,strlen(temp2),i);
    }

}
int main()
{
    int m,n;
    init(s);
    cin>>m;
    while(m--)
    {
          cin>>n;
          cout<<s[n]<<endl;
    }
    return 0;
}

1753

算法流程：

????

源码实现：

??????

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define MAX 440
char s1[MAX],s2[MAX];
char result[MAX];
void multiflus(char *s1,int len1,int len2,int point1,int point2)
{

    int i,k=0,l=0;
    int len,temp;
    memset(result,sizeof(result));
    for(i=point1,j=point2;i<len1 && j<len2;i++,j++)
    {
        result[k++]+=s1[i]-'0'+s2[j]-'0';
        result[k-1]+=48;
    }
    while(i<len1)
    {
        result[k++]+=s1[i++]-'0';
        result[k-1]+=48;
    }
    while(j<len2)
    {
        result[k++]+=s2[j++]-'0';
        result[k-1]+=48;
    }

    len = strlen(result);
    for(i=0;i<len/2;i++)
    {
        temp=result[i];
        result[i]=result[len-1-i];
        result[len-1-i]=temp;
    }

    for(i=0;;i++)
    {
        if((result[i]-48)/10 > 0)
        {
            result[i+1]+=1;
            result[i]-=48;
            result[i]%=10;
            result[i]+=48;
        }

        if(result[i+1]=='')
                break;


    }
    if(k==i&&k!=0)//有小数位进位
    {
        result[k++]='.';
        result[k]+=1;
    }
    else//没有小数进位
    {
        result[k++]='.';
    }

    //除掉末尾的0,和全为0的小数点,以及末尾为0的小数点
    i=0;
    while(i<k-1)
    {
        if(result[i]!='0')
            break;
        i++;
    }

    if(i<k-1)
        l=i;
    else
        l=k;
    //
    for(i=point1-2,j=point2-2;i>=0 && j>=0;i--,j--)
    {
        result[k++]+=s1[i]-'0'+s2[j]-'0';
        if(result[k-1]/10 > 0)
        {
            result[k]+=result[k-1]/10;
            result[k-1]=result[k-1]%10;
        }
        result[k-1]+=48;
    }

    while(i>=0)
    {
        result[k++]+=s1[i--]-'0';
        if(result[k-1]/10 > 0)
        {
            result[k]+=result[k-1]/10;
            result[k-1]=result[k-1]%10;
        }
        result[k-1]+=48;
    }
    while(j>=0)
    {
        result[k++]+=s2[j--]-'0';
        if(result[k-1]/10 > 0)
        {
            result[k]+=result[k-1]/10;
            result[k-1]=result[k-1]%10;
        }
        result[k-1]+=48;
    }
    if(result[k]!='')
        result[k++]+=48;
    result[k]='';

    for(i=k-1;i>=l;i--)
        cout<<result[i];
    cout<<endl;
}
int FindPointPosition(char *s)
{
    int i,len=strlen(s);
    for(i=0;i<len;i++)
    {
        if(s[i]=='.')
            return i+1;
    }
    if(i>=len)
        return i+1;
}
int main()
{
    int point1,point2;
    int len1,len2;
    while(scanf("%s%s",s2)!=-1)
    {
        len1=strlen(s1);
        len2=strlen(s2);
        point1=FindPointPosition(s1);
        point2=FindPointPosition(s2);
        multiflus(s1,s2,point1,point2);
        memset(s1,sizeof(s1));
        memset(s2,sizeof(s2));
    }
    return 0;
}