算法扩展2-高精度

高精度:

首先,我们知道,在计算机中,是以2进制存储数字的。

一个int型整数占四个字节,能表示的最大数字为2^31-1。

那么,如果我要表示一个几百位、甚至上千位的数字,我需要多大的空间呢?

以一千位数为例,一千位数字最小为10^1000。

以2为底10^1000的对数

等于1000被以2为底10的对数

约等于3.32。

也就是说,这大约需要3320个字节。

如果说,计算机中有这样的类型,我们叫它超超超超超长整型,我们就可直接用来计算了

不幸的是,计算机中最大的整数类型,long long int,也只能占用了八个字节。

那么,如果实际生活中,我们需要计算几百位甚至几千位的长整数,我们应该怎么办呢?

这就是所谓的高精度问题。

无论多长的整数,都是由每一位的数码组成。

我们可以用一个数组,来存储这个长整数的每一位:

利用字符串输入,把字符串的每一位存储在数组里;

在计算中,当第X位大于10时,则使第X+1位增加第X位除十的倍数,使第X变为自己对十取余的余数;

然后再依次输出。

下面我们先来处理第一个问题:输入。

在计算的时候,我们要从后向前计算,从个位开始向十位计算。

所以,我们应该尽可能的把低位存储在数组的低位里。

一个好的习惯,开辟数组前宏定义一个最大值:

#define MAXN 1000

然后定义一个字符数组

char temp[MAXN + 5];

进行输入

cin >> temp;

然后将字符数组的每一位存储在数组中。

在这里,我们有一个小问题:

循环从1开始,可是到几结束?

所以,我们需要先获取一下temp数组的长度。

int length = strlen(temp);

这个函数在头文件string.h中,别忘了加到前面!

#include <string.h>

然后我们声明一个数组,用来存储数字。

int a[MAXN + 5];

进行每一位的提取:

for(int i = 1; i <= length; i++){
    a[i] = temp [length - i] - '0';//倒着提取,最高位(第一位)存储在最大的地方(最后一位)
    //但是注意,利用cin输入字符串时,第一位为0。所以a[1]应该为a[length - 1]
}

OK,到了这里,我们已经能完整的表示一个高精度数字。

请你以此类推,完成第二个数组的存储。

然后,下面我们进行一下高精度的加法。

在小学阶段,我们学习了竖式这个神奇的东西来帮助我们计算,而计算机的高精度计算与竖式同理。

1234567

+7654321

8888888


我们对每一位进行加法,然后存储在ans数组中,并且随时判断ans数组的每一位是否大于10。

下面是高精度加法的实现代码:

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
#define MAXN 105
int m[MAXN],n[MAXN];//m,n存储两个数字
int ans[MAXN];//ans存储答案
int main() {
    char str1[MAXN],str2[MAXN];//两个字符数组用来输入
    cin >> str1 >> str2;
    
    //注:以下的很多注释的作用是用来调试,找bug用。
    
    for (int i = 1; i <= strlen(str1); i++) {
        //cout << i << ":";
        m[i] = str1[strlen(str1) - i] - '0';
        //cout << m[i] << " ";
    }
    for (int i = 1; i <= strlen(str2); i++) {
        n[i] = str2[strlen(str2) - i] - '0';//转存
    }


    int maxn = max(strlen(str1), strlen(str2));


    for (int i = 1; i <= maxn; i++) {
        //cout << i << ":" << endl;
        ans[i] += (m[i] + n[i]);//计算
        //printf("ans[i]=%d,ans[i+1]=%d\n", ans[i], ans[i + 1]);
        while (ans[i] >= 10) {//进位
            ans[i] -= 10;
            ans[i + 1]++;
            //printf("ans[i]=%d,ans[i+1]=%d\n", ans[i], ans[i + 1]);
        }
    }

    bool first = false;//第一个正整数前的0不要

    for (int i = maxn+5; i >= 1; i--) {
        if (!first && ans[i] == 0)continue;
        else first = true;
        cout << ans[i];
    }
    //cout << endl << 1234567 + 7654999;

    return 0;
}
最近的文章

算法扩展1-素数筛

如果你想要判断一个数字是否是质数,你该怎么办呢?首先,我们要先知道质数的定义是什么:质数是指,在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。那么我们很简单就能编辑出我们的最初版判断素数函数:【我们以欧拉第七题举例,输出第10001个素数】#include <iostream&g…

继续阅读
更早的文章

扩展算法3-二分法

在编程中,查找是很重要的一环。比方说,有一个一百万位的、单调递增的数组,需要你找到某个值在第几位;比方说,有一个不规则函数,要你求出一个零点的位置;等等等。在这个时候,你总不能把这一百万都查找一遍吧?这个时候二分就派上用场了。那么二分是什么呢?你可以和同学做一个游戏,我们来模拟一下最基础的二分:让你…

继续阅读