NOIP2011普及组初赛 完善程序 第2题《大整数》

Keywords: 高精度计算

分析：鉴于题目过于长，140行代码，不截图放原题了，直接贴上代码和注释。

#include <cstring>
#include <iostream>

using namespace std;

const int N = 200;

struct hugeint
{
    int len, num[N];
};

hugeint times(hugeint a, hugeint b)  // ab乘积 
{
    int i, j;
    hugeint ans;                     //ans存放乘积 
    memset(ans.num, 0, sizeof ans.num);

    for (i = 1; i <= a.len; i++)
        for (j = 1; j <= b.len; j++)
            ans.num[i + j - 1] += a.num[i] * b.num[j];  // 高精度乘法  1空 

    for (i = 1; i <= a.len + b.len; i++)
    {
        ans.num[i+1] += ans.num[i] / 10;  //处理乘法进位 
        ans.num[i] %= 10;                 // 2空 
    } 

    //判断乘积是否比ab中的最大数，还要多1位   123 * 3 = 369 (位数 3 + 1 - 1)
    //789 * 3 = 2367 (位数 3 + 1)
    if (ans.num[a.len + b.len] > 0) ans.len = a.len + b.len;
    else ans.len = a.len + b.len - 1;  

    return ans;   
}

hugeint add(hugeint a, hugeint b)  // ab和 
{
    int i;
    hugeint ans;
    memset(ans.num, 0, sizeof ans.num);

    if (a.len > b.len) ans.len = a.len;  //看哪个位数长，用在ans 
    else ans.len = b.len;

    for (i = 1; i <= ans.len; i++)
    {
        ans.num[i] += a.num[i] + b.num[i];  //3空
        ans.num[i + 1] += ans.num[i] / 10;  //处理进位问题 
        ans.num[i] %= 10;                   //这个地方其实也是一个第2空的参考，可以仿照写 
    } 

    if (ans.num[ans.len + 1] > 0) ans.len++;  //最后相加后，多了一位 

    return ans;
}

hugeint average(hugeint a, hugeint b) // 求ab平均数的整数部分 求middle 
{
    int i;
    hugeint ans;
    ans = add(a, b);                 //ans存ab的和 

    for (i = ans.len; i >= 2; i--)
    {
        ans.num[i - 1] += (ans.num[i] % 2) * 10;         //从高位开始模拟除以2的动作  // 4空
        ans.num[i] /= 2;                                 //高一位除2的余数，*10加给下一位 
    }

    ans.num[1] /= 2;
    if (ans.num[ans.len] == 0) ans.len--;

    return ans;
}

hugeint plustwo(hugeint a)  // a加2之后的结果   
{
    int i;
    hugeint ans;
    ans = a;
    ans.num[1] += 2;   //num[1]是最后一位  倒序存的 

    i = 1; 
    while ((i <= ans.len) && (ans.num[i] >= 10))  //从最后一位往前捋 看有无进位
    {
        ans.num[i + 1] += ans.num[i] / 10;
        ans.num[i] %= 10;
        i++;
    }

    if (ans.num[ans.len + 1] > 0) ans.len++;      // 5空  加2后总位数多了一位

    return ans; 
} 

bool over(hugeint a, hugeint b) //a是否大于b 
{
    int i;
    if (a.len < b.len) return false;  //用数的位数长短来区分大小 
    if (a.len > b.len) return true;

    for (i = a.len; i >= 1; i--)       //当位数相同时，从高位开始逐位比较 
    {
        if (a.num[i] < b.num[i]) return false;
        if (a.num[i] > b.num[i]) return true;
    }

    return false;
}

int main()
{
    int i;
    string s;
    cin >> s;
    hugeint target, left, middle, right;
    memset(target.num, 0, sizeof target.num);

    //初始化数组，倒序，存放n的每一位 
    target.len = s.length();
    for (i = 1; i <= target.len; i++)            //下标从1开始 
        target.num[i] = s[target.len - i] - '0'; // s字符数组，转化成数组，倒序存入   7空 

    //二分法，求mid 
    memset(left.num, 0, sizeof left.num);
    left.len = 1, left.num[1] = 1, right = target;
    do
    {
        middle = average(left, right); 
        if (over(times(middle, middle), target))   // check middle的平方是否大于target 8空 
            right = middle;                        // 大于 就是middle取大了 
        else
            left = middle;
    }
    while (!over(plustwo(left), right));   //left右移两步，还是小于right，就继续while循环 

    //输出结果 
    for (i = left.len; i >= 1; i--) cout << left.num[i];  //正序输出 

    return 0;
}