首页 > 其他分享 >高精度加减乘除小数详解

高精度加减乘除小数详解

时间：2023-08-15 20:35:14浏览次数：35  
标签：加减乘除 10 int back -- vector size 详解 小数

高精度

简介

众所周知，在计算机中，每个数据类型都是有存储上限的，那么当数字特别大时应该怎么办呢？这时高精度就产生了。高精度的主要思想就是模拟手算，然后将结果存储到数组中去，相同的，小数也有精度问题，也可以使用相同的思路

存储

这里使用vector 来进行存储，因为这样不需要去管结果有多少位，直接使用push_back() 函数就行了，虽然和数组比起来会慢一些，不过差别也仅仅是常数而已

输入：定义一个字符串，然后将字符串的每位转数字存储起来就行了

string a; vector <int> A; 
cin>>a;
for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');

输出：请注意，输入的时候我是反过来的，这样做是为了添加元素比较方便，那么输出的时候也要注意倒着输出

for (int i = C.size() - 1; i >= 0; i--) printf("%d", C[i]);

高精度加法

上文中已经提到，在进行高精度运算是模拟手算的，那么接下来就来回忆一下，我们是怎么手动做加法的

图为用竖式做加法的示例，我们可以发现主要组成部分有两个加数、结果、还有进位，于是我们的变量就可以呼之欲出了

vector <int> A; vector <int> B; vector <int> C; int t;

然后我们再使用循环遍历（从0开始）来进行计算，循环位数较大的那个加数的每一位，然后加到 \(t\) 里面就行了

那么 \(C_i\) 就等于 \(A_i+B_i\) 再 \(mod~10\)，进位 \(t\) 就等于 \((A_i+B_i)/10\)

注意在循环完之后，如果 \(t\neq 0\) 的话，还要加上一位

代码模板

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

vector<int> add(vector<int>& A,vector<int>& B)
{
	vector<int> C; 
	int t=0;
	for(int i=0;i<max(A.size(),B.size());i++)
	{
		if(i<A.size()) 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()
{
	string a,b;
	cin>>a;
	cin>>b;
	vector<int> A;
	vector<int> B;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	vector<int> C=add(A,B);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	return 0;
}

高精度减法

不带负数

首先，先回忆一下我们是怎么用竖式进行减法的

与加法不同，我们在列减法的竖式时会把大数放在上面，小数放在下面，因为减法涉及到借位的问题

所以说在计算机计算的时候，我们要先判断 \(A\) 是否 \(\geq B\)，如果 \(<B\)，为了避免增加代码量我们直接计算 \(-(A-B)\) 就行了

那么因为数字特别大，所以我们也需要手写一个比较函数，那么我们是怎么比较两个数的呢？

先比较哪个位数大，位数多的大，如果位数一样，那么分别比较每一位

bool cmp(vector<int>& A, vector<int>& B)
{
	if (A.size() != B.size())return A.size() > B.size();
	for (int i = A.size()-1; i>=0; i--)
	{
		if (A[i] != B[i]) return A[i] > B[i];
	}
	return true;
}

类似加法，变量分别为被减数，减数，结果，借位

使用循环遍历（从0开始）被减数的每一位

借位 \(t\) = \(A_i-(B_i)-t\)，如果说最终结果小于0，就要借一位，将 \(t+10\) 最后再 \(mod~10\) 便是 \(C_i\)

如果借位了 \(t=1\) 否则 \(t=0\)

注意：为了方便，我们直接不管结果是否小于0，每次都加10，因为如果结果不小于0的话 \(+10\) \(mod~10\) 就抵消了对结果不影响

最后还要去除前导0

while (C.size() > 1 && C.back() == 0)
{
	C.pop_back();
}

代码模板

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool cmp(vector<int>& A,vector<int>& B)
{
	if(A.size()!=B.size()) return A.size()>B.size();
	for(int i=A.size()-1;i>=0;i--)
	{
		if(A[i]!=B[i]) return A[i]>B[i];
	}
	return true;
}
vector<int> sub(vector<int>& A,vector<int>& B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t=A[i]-t;
		if(i<B.size()) t-=B[i];
		C.push_back((t+10)%10);
		if(t<0) t=1;
		else t=0;
	}
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}
int main()
{
	string a,b;
	vector<int> A,B;
	cin>>a;
	cin>>b;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	if(cmp(A,B)) 
	{
		vector<int> C=sub(A,B);
		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	}
	else 
	{
		vector<int> C=sub(B,A);
		cout<<'-';
		for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	}
	return 0;
}

带有负数

  • 自然数 \(A\) 减负数 \(B\) 等于 $A+\vert B\vert $
  • 负数 \(A\) 减自然数 \(B\) 等于 \(-(\vert A \vert+B)\)
  • 自然数 \(A\) 减负数 \(B\) 等于 \(\vert A\vert+B\)
  • 负数 \(A\) 减负数 \(B\) 当 \(\vert A\vert\leq\vert B\vert\) 时，等于\(\vert B\vert -\vert A\vert\) 当 \(\vert A \vert>\vert B\vert\) 时，等于 \(-(\vert A\vert-\vert B\vert)\)

代码模板

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
bool cmp(vector<int>& A,vector<int>& B)
{
	if(A.size()!=B.size()) return A.size()>B.size();
	for(int i=A.size()-1;i>=0;i--)
	{
		if(A[i]!=B[i]) return A[i]>B[i];
	}
	return true;
}
bool cmp1(vector<int>& A,vector<int>& B)
{
    if(A.size()!=B.size()) return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
	{
		if(A[i]!=B[i]) return A[i]>B[i];
	}
	return false;
}
vector<int> add(vector<int>A,vector<int>B)
{
	vector<int> C; 
	int t=0;
	for(int i=0;i<max(A.size(),B.size());i++)
	{
		if(i<A.size()) 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;
}
vector<int> sub(vector<int>& A,vector<int>& B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t=A[i]-t;
		if(i<B.size()) t-=B[i];
		C.push_back((t+10)%10);
		if(t<0) t=1;
		else t=0;
	}
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}
int main()
{
	string a,b;
	vector<int> A,B;
	cin>>a;
	cin>>b;
    if(a[0]!='-'&&b[0]!='-')
    {
        for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
        for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
        if(cmp(A,B)) 
	    {
		    vector<int> C=sub(A,B);
		    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	    }
	    else 
	    {
		    vector<int> C=sub(B,A);
		    cout<<'-';
		    for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	    }
    }
	else if(a[0]=='-'&&b[0]!='-')
	{
        for(int i=a.size()-1;i>=1;i--) A.push_back(a[i]-'0');
        for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
        vector<int> C=add(A,B);
        cout<<'-';
        for(int i=C.size()-1;i>=0;i--) cout<<C[i];
    }
	else if(a[0]!='-'&&b[0]=='-')
	{
		for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
        for(int i=b.size()-1;i>=1;i--) B.push_back(b[i]-'0');
        vector<int> C=add(A,B);
        for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	}
	else if(a[0]=='-'&&b[0]=='-')
    {
        for(int i=a.size()-1;i>=1;i--) A.push_back(a[i]-'0');
        for(int i=b.size()-1;i>=1;i--) B.push_back(b[i]-'0');
        if(cmp1(A,B))
        {
            cout<<'-';
            vector<int> C=sub(A,B);
            for(int i=C.size()-1;i>=0;i--) cout<<C[i];
        }
        else
        {
            vector<int> C=sub(B,A);
            for(int i=C.size()-1;i>=0;i--) cout<<C[i];
        }
    }
	return 0;
}

高精度乘法

高精度乘低精度

高精度乘法与前面有所不同，在我们用竖式计算乘法时，都是一位对一位的，而在这里因为 \(b\) 比较小，所以我们直接拿大数的每一位去乘上 \(b\) 就行了，那么我们还是拿一个竖式举例：

先模拟一下这个例子：

\(C_0=(3×12)~mod~10=6\) \(t_1=3×12/10=3\) \(C_1=(2×12+t_1)~mod~10=7\) \(t_2=2×12/10=2\)

\(C_2=(1×12+2)~mod~10=4\) \(t_3=1×12/10=1\) \(C_3=t_3=1\)

那么最终的结果就是 1476

我们用循环遍历 \(A\) 的每一位就行了

如果最后 \(t\neq0\)，那么就添上 \(t~mod~10\)，注意因为我们是直接乘上 \(b\) 所以进位不一定是个位数，要用一个循环来做

代码模板

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A,int B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t+=A[i]*B;
		C.push_back(t%10);
		t/=10;
	}
	while(t) 
	{
		C.push_back(t%10);
		t/=10;
	}
	return C;
}
int main()
{
	string a;
	int B;
	cin>>a;
	cin>>B;
	vector<int> A;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	vector<int> C=mul(A,B);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}

高精度乘高精度

因为两个数都很大，所以我们按照手算的方式进行计算，首先先举个例子：

我们可以发现 \(A_0×B_0\) 对应 \(C_0\) \(A_1×B_0\) 对应 \(C_1\) \(A_2×B_0\) 对应 \(C_2\) 以此类推……

我们可以得出 \(A_i×B_j\) 对应 \(C_i\)\(_+\)\(_j\)

那么进位 \(t\) 就等于\(C_i\)\(_+\)\(_j\)\(/10\)

与大数乘小数一样，最后还要添上 \(t\)，不过这里是模拟手算，不需要再循环了

因为不能直接往后添数，所以我们的答案先初始化长一点，否则无法存储 vector<int> C(A.size() + B.size() + 7, 0);

最后记得去除前导0

代码模板

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A,vector<int>& B)
{
	vector<int> C(A.size()+B.size()+7,0);
	for(int i=0;i<A.size();i++)
	{
		int t=0;
		for(int j=0;j<B.size();j++)
		{
			C[i + j] += A[i] * B[j] + t;
			t = C[i + j] / 10;
			C[i + j] %= 10;
		}
		if(t) C[i+B.size()]+=t;
	}
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}
int main()
{
	string a,b;
	cin>>a; cin>>b;
	vector<int> A,B;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');
	vector<int> C=mul(A,B);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
}

注意：\(t\) 在一轮用完后要及时初始化为0，另外 \(t\) 一定要赋值为 \(C_i\)\(_+\)\(_j/10\)，因为当重叠时可能加法上又有进位。

高精度除法

大数除小数

首先，回想一下我们是怎么用竖式算除法的

我们可以发现几个变量分别是被除数、除数、商、余数

我们使用一个变量 \(r\) 来存储余数

因为计算机不像人那么聪明，所以一位一位来

首先看1，1除11不够，商0，余1

再看2，因为现在余1，所以变成10+2，12除11够，商1，余1，结束

我们就可以得到 \(r=r×10+A_i~mod~B\)，\(C_i=r×10+A_i~/B\)

注意因为我们除法是从前往后的，所以去除前导0的时候要先进行翻转

代码模板

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> div(vector<int>& A, int& B,int& r)
{
	r=0; vector<int> C;
	for(int i=A.size()-1;i>=0;i--)
	{
		r=r*10+A[i];
		C.push_back(r/B);
		r%=B;
	}
	reverse(C.begin(),C.end());
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}
int main()
{
	string a;
	cin>>a;
	vector<int> A; int B;
	cin>>B;
	for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
	int r;
	vector<int> C=div(A,B,r);
	for(int i=C.size()-1;i>=0;i--) cout<<C[i];
	cout<<endl;
	cout<<r;
}

压位

因为数组一个位置可以存很大的数，所以我们只存一个数有点浪费，所以我们可以使用压位这个技巧

我们先开两个全局变量 \(N=x\) \(M=10^x\) （x为你想压的位数）

输入的时候改成

int st=max(0,1-N+1),len=i-st+1;
A.push_back(a.substr(st,len)-'0');

注意所有 \(/10~mod~10\) 的操作均要修改成 \(/M~mod~M\)
输出的时候要先输出首位，因为输出的时候有可能不一定正好是 \(x\) 位数，要使用 printf("%04d",C[i])（以4位举例）
所以当输出完首位后，从C.size()-2开始

高精度小数

保留？位

首先，我们先算出整数部分，因为计算机不像手算，直接算出就可以了，不需要像手算一样一位一位算

然后我们回想一下手算是怎么算小数部分的，我们将上一位算得的余数乘10再除以除数就行了

示意图

代码模板

//c是位数
digit[0]=a/b;
a%=b;
for(int i=1;i<=c+1;i++)
{
	a*=10;
    digit[i]=a/b;
   	a%=b;
}
cout<<digit[0]<<'.';
for(int i=1;i<=c;i++) cout<<digit[i];

四舍五入

由于小数会出现循环，所以题目一般会给出一些要求，例如最后一位四舍五入

四舍五入即为 当数 \(>=5\) 进一位，\(<5\) 时舍去

不过我们需要注意，进位的时候可能会出现“多米诺骨牌”

例如 9.99999... 进位后会变成10.00000....，所以我们需要使用循环来处理

注意进位到整数位如果变成10不用管，因为我们是直接输出整数位的

代码模板

if(digit[c+1]>=5) digit[c]++;
for(int i=c;i>0;i--)
{
	if(digit[i]>=10)
    {
       	digit[i]-=10;
        digit[i-1]++;
    }
}

8进制转10进制

因为8进制小数能完美转换成10进制小数，所以我们就不用管保留几位的问题

举个例子，0.75如何转换成10进制呢?

\(7/8^1+7/8^2=0.953125\) 这样就转换完成了，不会的去补初一数学

于是我们就可以模拟手算(见上文保留？位)，再用数组进行存储就行了，因为题目也给出了范围 \(0<k<15\)，因为所有小数点后位数为n的八进制小数都可以表示成小数点后位数不多于3n的十进制小数。所以我们数组长度开个50就行了

还要注意进位的问题，与之前一样都是”多米诺骨牌“，所以要用循环

还要开一个变量，记录数组里面一共有多少位了方便输出

坑点：

pow返回的是double类型，所以要进行强转，因为 \(3^1\)\(^5\) 非常大，使用long long，所以 与它进行计算的 \(x\) 也必须是long long类型

答案有可能变成1点几，例如当输入为 0.898 时，网上很多人都没有注意到这一点，为此我们从数组的第一位开始，第0位专门留着防止进位变1

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
int digit[50];
int main() {
    string a;
    cin >> a;
    int t = 0;
    for (int i = 2; i <= a.size() - 1; i++) {
        ll x = a[i] - '0';
        int j = 0;
        while (x) {
            x *= 10;
            digit[++j] += x / (ll)pow(8, i - 1);
            int k = j;
            while (digit[k] >= 10) {
                digit[k] -= 10;
                digit[--k]++;
            }
            x %= (ll)pow(8, i - 1);
        }
        t = max(t, j);
    }
    cout << a << " [8] = " << digit[0] << '.';
    for (int i = 1; i <= t; i++) cout << digit[i];
    cout << " [10]";
    return 0;
}

棋盘放米

首先我们分析一下题目是什么意思，相信大家在上幂这一课，老师都讲过这个故事

第一个格子有 \(2^0\) 粒米，第二个格子有 \(2^1\) 粒米，……

我们在这里直接从1开始，不然全是0，第20个格子就遍历19次

注意这题的说法略微有些歧义，从第 \(n\) 个到第 \(m\) 个，应该第一次从 1 遍历到 \(n-1\) 第二次从 1 遍历到 \(m\)，然后将两次结果一减就行了，注意也要使用高精

接下来就是三位一撇的问题了，我是先将正序的结果存储下来，然后再根据位数对3进行取模，注意最后一位不要有逗号

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A,int B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t+=A[i]*B;
		C.push_back(t%10);
		t/=10;
	}
	while(t) 
	{
		C.push_back(t%10);
		t/=10;
	}
	return C;
}
vector<int> sub(vector<int>& A,vector<int>& B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t=A[i]-t;
		if(i<B.size()) t-=B[i];
		C.push_back((t+10)%10);
		if(t<0) t=1;
		else t=0;
	}
	while(C.size()>1&&C.back()==0) C.pop_back();
	return C;
}
int main()
{
	int n,m;
    cin>>n>>m;
    vector<int> C,D,E,F;
    C.push_back(1); D.push_back(1);
    for(int i=1;i<n;i++) C=mul(C,2);
    for(int i=1;i<=m;i++) D=mul(D,2);
    E=sub(D,C);
	for(int i=E.size()-1;i>=0;i--) F.push_back(E[i]);
	int cnt=0;
	if(E.size()%3==0) cnt=3;
	else cnt=E.size()%3;
	for(int i=0;i<F.size();i++) 
	{
		cout<<F[i];
		if(i==cnt-1&&i!=F.size()-1) cout<<',',cnt+=3;
	}
    return 0;
}

n的阶乘

我们可以发现这题就是高精度乘低精度
我们直接将上一次得到的结果再乘当前的数就行了

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> mul(vector<int>& A,int B)
{
	int t=0;
	vector<int> C;
	for(int i=0;i<A.size();i++)
	{
		t+=A[i]*B;
		C.push_back(t%10);
		t/=10;
	}
	while(t) 
	{
		C.push_back(t%10);
		t/=10;
	}
	return C;
}

int main()
{
	int B;
	cin>>B;
	vector<int> A; A.push_back(1);
	for(int i=B;i>=1;i--) A=mul(A,i);
	for(int i=A.size()-1;i>=0;i--) cout<<A[i];
}

标签：加减乘除,10,int,back,--,vector,size,详解,小数
From： https://www.cnblogs.com/xiaozhu0602/p/17632356.html

相关文章

  • platform总线详解
    转载：手把手教Linux驱动10-platform总线详解-知乎(zhihu.com)platform总线是学习linux驱动必须要掌握的一个知识点。本文参考已发布：Linux3.14内核一、概念嵌入式系统中有很多的物理总线：I2c、SPI、USB、uart、PCIE、APB、AHBlinux从2.6起就加入了一套新的驱动管理和注册的......
  • 数据处理详解分析
    数据处理数据处理是将数据从给定形式转换为更有用和更期望的形式的任务，即使其更有意义和信息。使用机器学习算法，数学建模和统计知识，整个过程可以自动化。这个完整过程的输出可以是任何所需的形式，如图形，视频，图表，表格，图像等等，这取决于我们正在执行的任务和机器的要求。数据处理是机......
  • decimal float double小数位比较
    decimalfloatdouble小数位比较语法---2023-7-27decimal最多可以保留28位小数float最多可以保留6位小数double最多可以保留14位小数///<summary>///测试语法///</summary>publicstaticvoidTestProgrammer(){d......
  • Linux之sed命令详解
    sed是一种流编辑器，它是文本处理中非常好的工具，能够完美的配合正则表达式使用，功能不同凡响。处理时，把当前处理的行存储在临时缓冲区中，称为“模式空间”（patternspace），接着用sed命令处理缓冲区中的内容，处理完成后，把缓冲区的内容送往屏幕。接着处理下一行，这样不断重复，直到文件末尾。文......
  • CMakeLists语法详解
     https://www.jianshu.com/p/eb25baf5ca19set(Root"${CMAKE_CURRENT_SOURCE_DIR}")set(Base64${Root}/lib/libb64/src)include_directories(${OpenCV_INCLUDE_DIRS})include_directories(${Root})include_directories(${Root}/lib/libb64/include) include_dir......
  • MySQL 执行计划详解
    1.EXPLAIN详解本文基于MySQL8.0编写，理论支持MySQL5.0及更高版本。2.EXPLAIN使用2.1explain分析SQL的执行计划{EXPLAIN|DESCRIBE|DESC}tbl_name[col_name|wild]{EXPLAIN|DESCRIBE|DESC}[explain_type]{explainable_stmt|FORCONNECTIONconne......
  • Linux之sed命令详解
    sed是一种流编辑器，它是文本处理中非常好的工具，能够完美的配合正则表达式使用，功能不同凡响。处理时，把当前处理的行存储在临时缓冲区中，称为“模式空间”（patternspace），接着用sed命令处理缓冲区中的内容，处理完成后，把缓冲区的内容送往屏幕。接着处理下一行，这样不断重复，直到文件末尾。文......
  • SpringBoot 3.0日志系统设计LoggingSystem详解
    0前言SpringBoot对日志的配置和加载进行了封装，让我们可以很方便地使用一些日志框架，只需要定义对应日志框架的配置文件，如LogBack、Log4j、Log4j2等，代码内部便可以直接使用。如我们在resources目录下定义了一个logbackxml文件，文件内容是logback相关配置，然后就可以直接在代码在使用L......
  • Apipost接口自动化控制器使用详解
    测试人员在编写测试用例以及实际测试过程中，经常会遇到两个棘手的问题：稍微复杂一些的自动化测试逻辑，往往需要手动写代码才能实现，难以实现和维护测试用例编写完成后，需要手动执行，难以接入自动化体系这里，小编在Apipost自动化测试中还原了用户在电商平台购物实例，并利用这个实例来给大家......
  • 稀疏数组（五子棋）详解
    稀疏数组的介绍（五子棋）当一个数组中大部分元素为0，或者为同一值的数组时，可以使用稀疏数组来保存该数组。稀疏数组的处理方式是：记录数组一共有几行列，有多少个不同把具有不同值的元素和行列及值记录在一个小规模的数组中，从而缩小程序的规模------->packagearra......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99