高精度算法和链表

高精度算法

前言

计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特别高,远远超过各种数据类型的精度范围;有时数据又特别大,远远超过各种数据类型的极限值。这种情况下,就需要进行“高精度运算”。

高精度算法(High Accuracy Algorithm)是处理大数字的数学计算方法。在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开方等运算。对于非常庞大的数字无法在计算机中正常存储,于是,将这个数字拆开,拆成一位一位的,或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字,这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法,但又因其特殊性,故从普通数的算法中分离,自成一家。 —-百度百科

加法

用字符串输入两个数,再导入数组,然后每位相加,如果某位数字>10,则此位模10,下一位加一,最后用while循环去除前导零再输出即可。
先上最喜欢的AC代码

cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    int a[10010] = {0},b[10010] = {0},c[10010] = {0};
    int la = 0,lb = 0,lc = 0;
    string s1,s2;
    cin >> s1 >> s2;
    la = s1.size();
    lb = s2.size();
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0';
    lc = max(la,lb);
    for (int i = 1;i <= lc;i++)
    {
        c[i] += a[i] + b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    if (c[lc + 1] > 0)  lc++;
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i = lc;i >= 1;i--) cout >> c[i];
    return 0;
}

没啥难度,主要就是数太大,超范围,要用string存储。

这时候,冥场面 start:

g老师:…霹雳扒拉一大堆…
某某同学:老师,你刚刚说加法在加时进了1位,还是只可能进一位,我觉得能进2位,什么时候进2位?

全班寂静…ing

g老师/myq同学/zzy同学:乘法啊,你加法不管再怎么大,也只进一位,举个栗子:最大9+9也才进一位

全班无语…ing

减法

用字符串输入两个数,再导入数组,判断是否后数比前数,如果是则输出负号再交换数组。然后按位相减不够借1,最后用while循环去除前导零再输出即可。
AC代码

cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    int a[10010] = {0},b[10010] = {0},c[10010] = {0};
    int la = 0,lb = 0,lc = 0;
    string s1,s2;
    cin >> s1 >> s2;
    la = s1.size();
    lb = s2.size();
    if (la < lb || la == lb && s1 < s2)
    {
        cout << "-";
        swap(s1,s2);
        swap(la,lb);
    }
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0'; 
    lc = la;
    for (int i = 1;i <= lc;i++)
    {
        if (a[i] < b[i])
        {
            a[i] += 10;
            a[i + 1]--;
        }
        c[i] = a[i] - b[i];
    }
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i  = lc;i >= 1;i--)    cout << c[i];
    return 0;
}

也是没有可说的,记得,减法最重要的是删掉前导0(其实每个好像都要)

乘法

导入方法与前面一样,导入后按乘法竖式思路相乘,再按常规思路进位。最后去除前导零就行了。
AC代码

cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    string s1,s2;
    int b[1010] = {0},la = 0,lb = 0,a[1010] = {},lc = 0,c[1010] = {};
    cin >> s1 >>  s2;
    la = s1.size();
    lb = s2.size();
    for (int i = 0;i < la;i++)  a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++)  b[lb - i] = s2[i] - '0';
    lc = la + lb;
    for (int i = 1;i <= la;i++)
    {
        for (int j = 1;j <= lb;j++)
        {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i = lc;i >= 1;i--) cout << c[i];
    return 0;
}

细心的同学估计发现了,3个好像没有区别,都是模版,只改了一点点东西,所以是可以背背模版的。

除法

cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int a[N],b,c[N];
int main()
{
    string s1;
    cin >> s1 >> b;
    int la = s1.size();
    for(int i = 0;i < la;i++) a[i] = s1[i] - '0';
    long long x = 0;
    for (int i = 0;i < la;i++)
    {
        x *= 10;
        x += a[i];
        c[i] = x / b;
        x %= b;
    }
    int lc = 0;
    while(c[lc] == 0 && lc < la - 1) lc++;
    for (int i = lc;i < la;i++) cout << c[i];
    cout << " " << x;
}

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构,操作复杂。
由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,
但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

优点

  1. 不必预估空间大小
  2. 插入和删除很方便

优点有多强多好,缺点就有多明显多恶心。

缺点

不可随意访问任意元素

它的删除和插入到底有多简单呢,看↓
插入

原表: 1 -> 2 -> 4
指令:插入3
做法: p -> next = s->next;
s -> next = p;
就是直接将第2项指向下一项的指针指向插入的元素(将2 -> 4 改为 2 -> 3)
再将插入的元素指向后面那一个元素(将2 -> 4 改为 3 -> 4)
表就变为: 1 -> 2 -> 3 -> 4

删除

原表:1 -> 2 -> 3 – > 4
指令:删除2
做法:
s->next=p->next
就是将 删除的数的上一项直接指向 删除的数的下一项(将 1 -> 2 -> 3 直接改为 1 -> 3)

课上最Amzing的是老师讲的遍历二叉树的投机小技巧,可惜这在这上面我不知道如何表达

emmmmmmmmmmmmmm…
下课好吧,点个赞再走!!!

那年 • 今日
发布于2023-08-08 20:16
没有伞的孩子,必须学会努力奔跑。

赞助 点赞 0

指南不是个艺术家等人对本文发表了1条热情洋溢的评论。
  • 指南不是个艺术家说道: 0
    感觉没图就特别快,有图的页面就慢些了
  • 发表回复

    您的电子邮箱地址不会被公开。 必填项已用 * 标注