ACM程序设计课内实验（6）高精度

我会带着你远行 2024-04-17 13:46 74阅读 0赞

### 高精度算法 ###

stirling公式：n！~ (n/e)n(2\*pai\*n)1/2^ （n趋向正无穷成立 当n大于100时可用

### 初等算术 ###

> #### Description ####
> 
>     小学生在学多位数的加法时，是将两个数右对齐，然后从右往左一位一位地加。多位数的加法经常会有进位。如果对齐的位相加结果大于或等于十就给左边一位进一。对小学生来说，进位的判断是比较难的。你的任务是：给定两个加数，统计进位的次数，从而帮助老师评估加法的难度。
> 
> #### Input ####
> 
>     输入文件中的每一行为两个无符号整数，少于10位。最后一行位两个0，表示输入结束。
> 
> #### Output ####
> 
>     对输入文件(最后一行除外)每一行的两个加数，计算它们进行加法运算时进位的次数并输出。具体输出格式详见样例输出。
> 
> #### Sample Input ####
> 
>     123 456
>     555 555
>     123 594
>     0 0
> 
> #### Sample Output ####
> 
>     No carry operation.
>     3 carry operations.
>     1 carry operation.
> 
> #### Hint ####
> 
>     0时，输出No carry operation.   1时，输出1 carry operation.  大于1时，输出N carry operations.,注意：operations.和operation.

#include <iostream>
    
    using namespace std;
    
    long long a,b,c,res;
    int main()
    {
        while(cin>>a>>b&&a&&b){
           res = c = 0;
           for(int i = 0; i < 10;i++){
              if(a % 10 + b % 10 + c >= 10){
                    res++;
                    c = 1;
              }
              else
                    c = 0;
             a /= 10;
             b /= 10;
           }
    
            if(res==0)
                cout<<"No carry operation."<<endl;
            else if(res==1)
                cout<<"1 carry operation."<<endl;
            else
                cout<<res<<" carry operations."<<endl;
        }
        return 0;
    }

优化

#include <iostream>
    #include <string>
    
    using namespace std;
    
    int countCarry(string& num1, const std::string& num2) {
        int carry = 0;
        int count = 0;
        int len1 = num1.length();
        int len2 = num2.length();
        int i = len1 - 1, j = len2 - 1;
        while (i >= 0 || j >= 0) {
            int digit1 = (i >= 0) ? num1[i] - '0' : 0;
            int digit2 = (j >= 0) ? num2[j] - '0' : 0;
            int sum = digit1 + digit2 + carry;
            carry = sum >= 10 ? 1 : 0;
            if (carry > 0) {
                count++;
            }
            i--;
            j--;
        }
    
        return count;
    }
    
    int main() {
        string num1, num2;
        while (cin >> num1 >> num2) {
            if (num1 == "0" && num2 == "0") {
                break;
            }
            int result = countCarry(num1, num2);
            cout << result << endl;
        }
        return 0;
    }

### 计算N! ###

> #### Description ####
> 
>     Given an integer N(0 ≤ N ≤ 10000), your task is to calculate N!
> 
> #### Input ####
> 
>     One N in one line, process to the end of file.
> 
> #### Output ####
> 
>     For each N, output N! in one line.
> 
> #### Sample Input ####
> 
>     1
>     2
>     3
> 
> #### Sample Output ####
> 
>     1
>     2
>     6
> 
> #### Hint ####
> 
>     输入的N小于10000，可以输入，用INT型的大数就行，用数值型的高精度！

> 分析：
> 
> 10000！的有多大？ 用计算器算=5\*1035658，可以用50000个元素的数组f来保存，为了防止进位溢出，我们让f\[0\]保存结果的个位，f\[1\]表示十位，等等。输出的时候，数组高位上的0要忽略。
> 
> n例如：11！=39916800
> 
> n则，12！=11！\*12，也就是39916800的每位都乘12，再进位，从低到高，所以数组要用f\[0\]表示低位，输出时再逆序输出！

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=50000;
    int n,c,k;
    int f[maxn+1];
    int main()
    {
        int n;
        while(cin>>n)
        {
            memset(f,0,sizeof(f));
            f[0]=1;
            for (int i=1; i<=n; i++)
            {
                c=0;
                for(int j=0; j<=maxn; j++)
                {
                    int s=f[j]*i+c;
                    f[j]=s%10;
                    c=s/10;
                }
            }
            for(k=maxn; k>=0; k--)
                if (f[k]!=0)
                    break;
            for(int j=k; j>=0; j--)
                cout<<f[j];
            cout<<endl;
        }
        return 0;
    }

### 不能白学高精度 ###

> #### Description ####
> 
>     兴安黑熊在学习数学时，特别喜欢斐波那契数列,它的表示如下：
>      f(0)=1,f(1)=1, f(n)=f(n-1)+f(n-2);现在他想知道该数列的每个确切的值是多少，学过高精度的你能帮助他吗？
> 
> #### Input ####
> 
>     输入数据有多组，每组一个数n. (1<=n <=200).
> 
> #### Output ####
> 
>     输出f(n)的值。
> 
> #### Sample Input ####
> 
>     3
>     5
> 
> #### Sample Output ####
> 
>     3
>     8

#include<bits/stdc++.h>
    using namespace std;
    vector<int>add(vector<int> &A,vector<int> &B)//vector高精板子
    {
        if(A.size()<B.size())return add(B,A);
        vector<int>c;
        int t=0;
        for(int i=0;i<A.size();i++)//A+B+t
        {
            t+=A[i];
            if(i<B.size())t+=B[i];
            c.push_back(t%10);
            t/=10;
        }
        if(t)c.push_back(t);
        return c;
    }
    int main()
    {
        vector<int>A,B,c;
        int n;
        while(cin>>n)
        {
            A.clear();
            B.clear();
            c.clear();
            A.push_back(0);
            B.push_back(1);
            if(n==1||n==0)cout<<"1"<<endl;
            else
            {
                for(int i=1;i<=n;i++)
                {
                    c=add(A,B);
                    A=B;
                    B=c;
                }
                for(int i=c.size()-1;i>=0;i--)cout<<c[i];
                cout<<endl;    
            }
        }
        return 0;
    }