UVA oj 练习水题算法入门经典（大数系列）

逃离我推掉我的手 2022-10-02 06:47 245阅读 0赞

最近做了很多白皮书（算法入门经典）上面的很多水题，但是考验编程的细心还是很考验的，把一些题记录在这儿

[424 - Integer Inquiry][] 大数加法，代码改的很烂，很不容易的过了：

#include <iostream>
    #include <string>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    
    int main()
    {
        string a,b,c;
        int la,lb,lc;
        int ta[120],tb[120],tc[120];
        cin>>a;
        if(a[0]=='0')
        { return 0;}
        reverse(a.begin(),a.end());
        la=a.size();
        for(int i=0;i<la;i++)
            ta[i]=a[i]-'0';
        while(cin>>b)
        {
            memset(tc,0,sizeof(tc));
            memset(tb,0,sizeof(tb));
            bool ok=false;
            if(b[0]=='0'){
                for(int i=la-1;i>=0;i--)
                    cout<<ta[i];
                cout<<endl;
                break;
            }
            reverse(b.begin(),b.end());
            lb=b.size();
            for(int i=0;i<lb;i++)
                tb[i]=b[i]-'0';
            int l=la>lb?la:lb;
            if(la<l)
            {
                for(int i=la;i<l;i++)
                    ta[i]=0;
            }
            if(lb<l)
            {
                for(int i=lb;i<l;i++)
                    tb[i]=0;
            }
            for(int i=0;i<l;i++){
                if(ta[i]+tb[i]>9){
                    if(i==l-1){
                        tc[i]=(ta[i]+tb[i])%10;
                        tc[i+1]=1;ok=true;
                    }
                    else{
                        tc[i]=(ta[i]+tb[i])%10;
                        tb[i+1]++;
                    }
                }
                else{
                    tc[i]=tb[i]+ta[i];
                }
            }
            if(ok) l++;
            ok=false;
            la=l;
            for(int i=0;i<la;i++)
                ta[i]=tc[i];
        }
        return 0;
    }

### [10106 - Product][] 简单大数乘法，刚开始没有考虑到05\*05这样输出为0025的。wa了、、、后面输出加了判断之后0\*0却不输出了，特殊处理过了。 ###

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    void multiply(const vector<int>& t, const vector<int>& d, vector<int>& result)
    {
        int i,j,k,tmp;
        for(int i=0;i<t.size();i++){
            k=i;
            for (j = 0; j < d.size(); ++j)
             {
                 result[k++] += t[i] * d[j];
             }
        }
        for(k=result.size()-1;k>=0;--k){
            if(result[k]>9){
                if(k!=0){
                    result[k-1]+=result[k]/10;
                    result[k]%=10;
                }
                else{
                    tmp=result[k]/10;
                    result[k]%=10;
                    result.insert(result.begin(),tmp);
                }
            }
        }
    }
    int main()
    {
        string s1,s2;
        while(cin>>s1>>s2)
        {
            if(s1=="0"||s2=="0")
                {cout<<"0"<<endl;continue;}
            vector<int> vs1,vs2;
            vs1.reserve(s1.size());
            vs2.reserve(s2.size());
            for(int i=0;i<s1.size();i++)
                vs1.push_back(s1[i]-'0');
            for(int i=0;i<s2.size();i++)
                vs2.push_back(s2[i]-'0');
            vector<int> vs3(s1.size()+s2.size()-1,0);
            multiply(vs1,vs2,vs3);
            bool ok=true;
            for(int i=0;i<vs3.size();i++)
            {
                if(vs3[i]==0)
                {
                    if(!ok)
                        cout<<vs3[i];
                }
                else{
                    cout<<vs3[i];
                    ok=false;
                }
            }
            cout<<endl;
        }
        return 0;
    }

### [10494 - If We Were a Child Again][] 大数除以高精度数，很简单的模拟，但是大牛看看23行到35行注释掉的代码，为什么那样写会出错，没搞懂。代码： ###

#include <stdio.h>
    #include <string.h>
    int main()
    {   char s[1000],lable;
        long num,i,l,temp,a[1000],sum,pos;
        while (scanf("%s %c %ld",&s,&lable,&num)!=EOF)
        {
            l=strlen(s); sum=0;
                temp=0;
                for (i=0;i<l;i++)
                {
                    temp=temp*10+s[i]-'0';
                    if (temp>=num)
                    {
                        a[++sum]=temp/num;
                        temp=temp%num;
                    }
                    else
                    { a[++sum]=0;}
                }
                if(lable=='/')
                {
                    /*bool ok=true;
                    for(int i=1;i<=sum;i++)
                    {
                        if(a[i]==0)
                        {
                            if(!ok)
                                printf("0");
                        }
                        else{
                            printf("%d",a[i]);
                            ok=false;
                        }
                    }*/
                    pos=1;
                    while ((a[pos]==0)&&(pos<sum)){
                        ++pos;
                    }
                    for (i=pos;i<=sum;i++)
                    printf("%ld",a[i]);
                    printf("\n");
                }
                else
                    printf("%d\n",temp);
        }
        return 0;
    }

### [Uva113 - Power of Cryptography][] 求大数开n次方的结果。但是用double水过了、、但是long long 过不了。 ###

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    
    int main()
    {
        long mid,left,right;
        double p;
        int n;
        while(~scanf("%d%lf",&n,&p)){
            left=0,right=1000000000;
            while(left<right)
            {
                mid=(left+right)/2;
                if(pow(mid,n)==p) break;
                if(pow(mid,n)<p)left=mid;
                if(pow(mid,n)>p)
                    right=mid;
            }
            //printf("%lf\n",p);
            printf("%ld\n",mid);
        }
        return 0;
    }

[424 - Integer Inquiry]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=365
[10106 - Product]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1047
[10494 - If We Were a Child Again]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1435
[Uva113 - Power of Cryptography]: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=49