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

高精度算法

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;
}