第二章 高精度

高精度加法：

1 怎么表示
2 怎么做加法

1002 A+B for Polynomials (25 分)

#include <iostream>
using namespace std;
const int N =1010;
double a[N],b[N],c[N];
int main(){
    int k;
    //读入数组a
    cin >> k;
    while(k --){
        int n;
        double v;
        cin >> n >> v;
        a[n] = v;
    }
    //读入数组a
    cin >> k;
    while(k --){
        int n;
        double v;
        cin >> n >> v;
        b[n] = v;
    }
    //求和
    for(int i =0 ; i < N; i++){
        c[i]=a[i] + b[i];
    }
    //求不为0项的项数
    k =0;
    for(int i =0 ; i < N; i ++){
        if(c[i]) k ++;
    }
    //输出
    cout << k;
    for( int i =N -1; i >= 0; i --){
        if(c[i] > 0){
            printf(" %d %.1lf", i, c[i]);
        }
    }
    return 0;
}

1009 Product of Polynomials (25 分)

#include <iostream>
using namespace std;
const int N = 1010, M = 2020;
double a[N], b[N];
double c[M];
int main(){
    int k;
    cin >> k;
    while (k --){
        int n;
        double v;
        cin >> n >> v;
        a[n] = v;
    }
    cin >> k;
    while (k --){
        int n;
        double v;
        cin >> n >> v;
        b[n] = v;
    }
    for (int i = 0; i < N; i ++){
        for (int j = 0; j < N; j ++){
            c[i +j]  += a[i]* b[j];
        }
    }
    k = 0;
    for (int i = 0 ; i < M ; i ++){
        if(c[i]) k ++;
    }
    cout << k;
    for (int i = M- 1; i  >= 0; i --){
       if(c[i]){
           printf(" %d %.1lf", i ,c[i]);
       }
    }
}

1023 Have Fun with Numbers (20 分)

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(){
    string A;
    cin >> A;
    vector<int> a;
    //将A中的元素push到vector里面
    for(int i = A.size()-1; i >= 0; i --){
        a.push_back(A[i]-'0');
    }
    vector<int> b;
    //高精度加法
    int t =0;
    for(int i = 0; i < a.size(); i ++){
        int s  = a[i] + a[i] +t;
        b.push_back(s % 10);
        t = s /10;
    }
    if(t) b.push_back(t);//最后的t也要push进去
    vector<int> c = b;
    //两个队列直接sort后进行比较
    sort(a.begin(), a.end());
    sort(c.begin(), c.end());
    if(a == c ) puts("Yes");
    else puts("No");
    for(int i = b.size() -1; i >= 0; i --) cout << b[i];
    return 0;
}

1024 Palindromic Number (25 分)

#include <iostream>
#include <vector>
using namespace std;
//check是否是回文数，利用双指针
bool check(vector<int>& num){
    for(int i = 0, j=num.size()-1; i <j; i ++, j -- ){
        if(num[i] !=num[j]) return false;
    }
    return true;
}
//高精度加法思想进行相加
vector<int> add(vector<int>& a, vector<int>& b){
    vector<int> c;
    for(int i =0, t =0 ; i <a.size() || i < b.size() || t; i ++){
        int s = t;
        if (i < a.size()) s += a[i];
        if (i < b.size()) s += b[i];
        c.push_back(s % 10);
        t = s / 10;
    }
    return c;
}
int main(){
    string n;
    int k; 
    cin >> n >> k;
    vector<int> a;
    for(int i =n.size()-1; i >= 0; i --){
        a.push_back(n[i]-'0');
    }
    int cnt =0;
    if(!check(a)){
        while(cnt < k){
            //b倒序存a
            vector<int> b(a.rbegin(),a.rend());
            a = add(a, b);
            cnt ++;
            if(check(a)) break;
        }
    }
    for(int i =a.size()-1; i >= 0; i --){
        cout << a[i];
    }
    cout << endl << cnt << endl;
    return 0;
}

1058 A+B in Hogwarts (20 分)

#include <iostream>
using namespace std;
int main(){
    int a, b, c, d, e, f;
    scanf("%d.%d.%d %d.%d.%d", &a, &b, &c, &d, &e, &f);
    a += d;
    b += e;
    c += f;
    b += c / 29;
    c %= 29;
    a += b /17;
    b %= 17;
    printf("%d.%d.%d", a, b, c);
}

#include <iostream>
#include <vector>
using namespace std;

//高精度加法，模板，要背
vector<int> add(vector<int> a, vector<int> b){
    vector<int> c;
    for( int i =0, t =0; i < a.size() || i <b.size() ||t; i ++){
        if( i < a.size()) t += a[i];
        if( i < b.size()) t += b[i];
        c.push_back(t % 10);
        t = t / 10; 
    }

    return c;

}

bool check(vector<int> num){
    for(int i =0, j = num.size()-1; i < j; i ++, j --){
        if (num[i] != num[j]) return false;
    }
    return true;

}
//输出比较多，统一写一个函数
void print(vector<int> num){
    for(int i = num.size()-1; i >= 0; i --){
        cout << num[i];
    }
}

int main(){
    string n;
    cin >> n;
    vector<int> a;
    for( int i =n.size()-1; i >= 0; i --) a.push_back(n[i]-'0');
    for( int i = 1 ; i <= 10; i ++){
        if(check(a)) break;
        vector<int> b(a.rbegin(), a.rend());
        print(a), cout << " + " , print(b), cout << " = ";
        a = add(a, b);
        print(a),cout << endl;
    }
    if(check(a)) print(a), cout << " is a palindromic number.";
    else puts("Not found in 10 iterations.");
}