分享内容

  1. 高精度除法
  2. 高精度应用

浮点数的精度

C++提供了float和double 两种浮点数类型,用于存储和操作小数。浮点数的精度,即小数部分的长度。C++中的浮点数采用IEEE 754 标准进行存储和表示。尾数位存储浮点数的小数部分,所以浮点数的精度主要由尾数的位数决定的。在IEEE 754标准中,单精度浮点数(float)的尾数有23位,其精度约为7位十进制数字;而双精度浮点数(double)的尾数有52位,精度则提升至约15位十进制数字。

高精度除法(一)

a、b不是高精度整数

问题1:a,b为10^8范围内的非负整数,求a/b保留n位小数的商。(n <= 100)

但是题目要求的商的小数位数非常大,超出了C++浮点型能表示的精度范围。

浮点数的精度主要由尾数的位数决定的。
在这里插入图片描述
输出超出浮点数精度的小数位会导致舍入和精度损失。所以不能直接用浮点类型计算和输出本题要求的商。
在这里插入图片描述

86÷25

(求小数商)

相当于余数*10

·1、先按照整数除法的法则去除。
·2、除到被除数的末尾仍有余数时,就在余数后面添0,
再继续除。

初始余数是11,
1110=110,110除以25,商4余10(即商的十分位是4,余数
继续参与运算);
1010=100,100除以25,商4余0;(即商的百分位是4)

模拟整数除法求高精度的商

int a,b,n ;

商由整数和小数部分组成。

  1. 商的整数部分=a/b(整除)。
  2. 小数部分:
    初始余数t=a%b
    ①那么对应小数位的商为t10/b,输出这个值
    ②更新余数t=t    10%b,余数进行下一轮计算循环执行步骤n次,就可以得到所需的精度


int t = a%b;
for(int i=1;i <= n; i++) {
	t *= 10;
	cout << t/b;
	t %= b;
}

高精度除法(二)

问题2:高精度整数a除以单精度整数b,求商c和余数d。

观察竖式运算

163÷7= 23 … 2
在这里插入图片描述
从高位开始 前一位除法的余数10+当前位上的数字
第一步 最高位1:不够除(商0余1);
第二步 前面的余110+6=16,16除以7商2余2
第二步 前面的余2*10+3=23,23除以7商3余2
高精度算法思路:从高精度数的最高位开始,逐位与单精度数进行除法运算。
除法是从高位开始除。所有高精除法的数据存储要正序存放,最高位在最左边。
被除数a是高精度数,需要将a中的每一位数字分别存储在整数数组中。
b是单精度数,可以用一般的整数变量来接收和存储。

int a[MAX];// 整型数组存储商

int b ;//整型变量存储除数

同时定义一个整型数组来存储商,余数一定小于b,所以可以用整型变量保存。

int c[MAX];// 整型数组存储商
int d;//整型变量存储余数

在这里插入图片描述

从高位开始逐位进行除法运算:

第i轮运算:

  1. 将当前处理的位与前一位的余数组合成一个新的数,即t=t*10+a[i]
  2. t/b即商的当前位,存储在ci
  3. 将余数存储在t(t=t%b)

伪代码:alen指被除数a的长度

int t=0;// 逐位除法的余数
for(int i=1;i <= alen;i++) {
	t = t*10 + a[i];
	c[i]= t/b;// 对应位的商
	t = t%b;// 更新余数
}
d = t;// 余数

求高精度商

单精度整数,求高精度的商
已知a,b为10^8范围内的非负整数(b != 0),求a除以b保留前n位小数商的结果。(n <= 100)
【输入描述】abn
【输出描述】a除以b保留前n位小数的商
【输入样例】

97 61 50

【输出样例】
1.59016393442622950819672131147540983606557377049180

int a,b,n ;

基本步骤:

  1. 输出商的整数部分 (a/b)。

  2. 小数部分:

    初始余数t=a%b

① 对应小数位的商为t10/b,输出这个值
② 更新余数t=t10%b,余数进行下一轮计算
循环执行步骤①②n次,就可以得到所需的精度。
在这里插入图片描述

完整代码

#include<iostream>
using namespace std;
int main() {
	int a,b,n;
	cin >> a >> b >> n;
	cout << a/b << ".";
	int t = a%b;
	for(int i=1;i <= n;i++) {
		t *= 10;
		cout << t/b;
		t %= b;
	}
	return 0;

}

在这里插入图片描述

高精度除以单精度

输入一个高精度整数a(不超过100位),和另一个单精度整数b(b不超过
8位),请求出a除以b得到的商和余数各是多少?
【输入描述】输入有2行,第一行有一个正整数a(不超过100位),第二
行有一个正整数b。
【输出描述】输出2行。第一行a除以b的商,第二行余数。
【输入样例】
8162148605591693302243
20136
【输出样例】
405351043185920406

7027
被除数a是高精度数,需要将a中的每一位数字分别存储在整数数组中。
b是单精度数,可以用一般的整数变量来接收和存储。

int a [MAX];// 整型数组存储商

int b ;//整型变量存储除数

同时定义一个整型数组来存储商,余数一定小于b,所以可以用整型变量保存。

int c[MAX];// 整型数组存储商

int d;//整型变量存储余数

1、输入a、b;
初始化c、d;

输入高精度数,正序保存到数组a,输入单精度数,保
存到整数变量b。初始化商数组c所有元素值为0,余数d为0。

2、逐位模拟除
法运算

逐位处理:从高精度数的最高位开始,逐位与单精度数
进行除法运算。

3、输出c、d

输出商(数组c去除前导0后的所有值)和余数d。

1~被除数长度,逐位模拟除法运算的具体步骤:

第i位的运算:

  1. 将当前处理的位与前一位的余数组合成一个新的数,即t=t*10+a[i]
  2. t/b即商的当前位,存储在ci
  3. 将余数存储在t(t=t%b)
    a[0]中保存被除数的长度
void div() {
	int t=0;//逐位除法的余*
	for(int i=1;i <= a[0];i++) {
		t=t*10+ a[i];//将当前处理的位与前一位的余数组合成一个新的数
		c[i]= t/b;// 商的当前位
		t = t%b;// 更新余数
	}
	d = t;
}	

#include<iostream>
#include<cstring>
using namespace std;
int a[110];//被除数
int b;//除数
int c[110];//商
int d;//余数

void init() {
	char ac[110];
	cin >> ac >> b;
	a[0]= strlen(ac);//a高精度数的位数存在a[0]中
	for(int i=0;i<a[0];i++)
		a[i+1]=ac[i]-'0';//将数字字符串ac转换成数组a,顺序存储数字
}	
void div() {
	int t=0;
	for(int i=1;i <= a[0];i++){//从高位开始逐位进行除法运算
		t = t*10 + a[i] ;
		c[i] = t/b;
		t = tb;
	}
	d=t;//余数
}
int main() {
	init();
	div();
	c[0]=a[0];//获取最大位数
	int i=1;
	while(c[i] == 0)//去前导0
		i++:
	if(i>c[0])//当a<b时,c[]数组全部是0,此时直接输出0
		cout << 0;
	else
		while(i <= c[0]) // 输出商
			cout << c[i++];
	cout << endl << d << endl;//输出余数
	return 0;
}

在这里插入图片描述
【注意】当a<b时,商0余数b。
高精度除以单精度-扩展

如果问题变成:高精度数a除以单精度b,求保留n位小数的商。

1、高精度数a除以单精度b,先算出商c,余数d
2、根据余数d继续计算出商的n位小数,此时d是被除数,b是除数
cout << ".";// 先输出小数点
int t = d%b;
for(int i=1;i <= n;i++){//逐位计算输出商的小数位上的值
	t *= 10;
	cout << t/b;
	t %= b;
}

n的阶乘

计算n的阶乘,(1 <= n <= 100)。
【输入描述】只有一行输入,整数n。
【输出描述】输出一行,即n!的值。
【输入样例】

100

【输出样例】

933262154439441526816992388562667004907159682643816214685929638

952175999932299156089414639761565182862536979208272237582511852

10916864000000000000000000000000
【分析】如果手动进行计算,20!大约为2.4*10^18,还可以用long long保存。但是当n>20,n!计算
结果long long就保存不了。所以需要用高精度算法。

100的阶乘有多少位,需要多大的数组?我们可以使用对数的性质来估算。
在这里插入图片描述
我们可以使用计算器或编程语言来计算这个和。计算得到:log1o(100!)=157.97
因此,100的阶乘的位数是:157.97向上取整得158。所以,100的阶乘有158位。



#define MAXN 160
int a[MAXN]={0};// 保存阶乘结果

在这里插入图片描述

n!的高精度计算的算法步骤

1、初始化a[0]=1,其他元素值=0。

2、输入n。

3、循环进行累乘计算:k=2~n,
初始进位=0;
从低位到高位(i=0~MAXN-1)逐位*k,并处理进位:
① 计算t=a[i]*k+进位。
② 将计算结果t的个位更新到a[i]中,同时更新进位。
4、输出结果:先去除数组a中的前导0,再逆序输出a中的结果。

#define MAXN 160
int a[MAXN]={0};// 保存阶乘结果
int n;

#include<iostream>
using namespace std;

#define MAXN 160
int a[MAXN]={0};
int n;
int main() {
	cin >> n;
	a[0] = 1;
	for(int k = 2;k <= n;k++) {
		int up=0;//进位初始为0
		for(int i = 0;i<MAXN;i++){//从个位到最高位,处理进位
		int t = a[i]*k + up;//逐位*k +进位
		a[i] = t%10;// 保存个位
		up = t/10;// 留下进位部分
		}	
	}
	int i = MAXN-1;
	while(a[i] == 0) // 去前导0
		i --;
	while(i>=0)//输出阶乘结果
		cout << a[i -- ];
	return 0;
}

在这里插入图片描述

阶乘之和

计算阶乘和:1!+2!+3!+4!+ … +n!,(1 <= n <= 50)。
【输入描述】只有一行输入,整数n。

【输出描述】输出一行,即1!+2!+3!+4!+ … +n!的值。

【输入样例】

5

【输出样例】

153
【分析】同样的,当n>20,n!计算结果long long保存不了,阶乘以及阶乘和都需要用高精度计算法
进行处理。

需要定义两个整数数组存放阶乘、阶乘和的高精度计算结果:

#define MAXN 160
int a[MAXN]={0};// 保存阶乘结果
int s[MAXN]={0};// 保存阶乘和的结果

阶乘和的高精度计算的算法步骤

n=1时,阶乘=1,阶乘和=1
1、初始化a[0]=1,s[0]=1。

2、输入n。
3、循环进行计算:k=2~n,
① 计算阶乘k !: 逐位*k,并处理进位,结果保存在a[];
② 计算阶乘和1!+ …. +K !: 逐位累加 s[i]+a[i],并处理进位,结果保存在s[];
4、输出结果:去前导0,逆序输出s中的值。

#define MAXN 160

int a[MAXN]={0};// 保存阶乘结果
int s[MAXN]={0};//保存阶乘和的结果
int n;

完整代码

#include<iostream>
using namespace std;

#define MAXN 160
int a[MAXN]={0};// 保存阶乘
int s[MAXN]={0};//保存阶乘和

int main() {
	int n;
	cin >> n;
	a[0]=1;//初始化 1 != 1
	s[0]=1;//n=1的阶乘和=1
	for(int k = 2;k <= n;k++) {
		// 1.计算阶乘k!
		int up= 0;//进位初始为0
		for(int i=0;i <MAXN;i++){//从个位到最高位,处理进位
			int t= a[i]*k+ up;//逐位*k+进位
			a[i] = t$10;// 保存个位
			up = t/10;// 留下进位部分
		}
		//2.累加到s[],得到1!+…+K!
		up=0;//进位初始为0
		for(int i=0;i <MAXN;i++){//从个位到最高位,处理进位
			int t=s[i] + a[i] + up;//逐位累加t=s[i]+a[i]+进位
			s[i] = t$10;// 保存个位
			up = t/10;// 留下进位部分
		}
	 }
	int i = MAXN-1;
	while(s[i] == 0) //去前导0
		i --;
	while(i>=0)//输出阶乘和结果
		cout << s[i -- ];
	
	return 0;
}

在这里插入图片描述

本次课程的知识点

  1. 实现高精度除法
  2. 其他高精度应用:高精度阶乘,高精度阶乘和
    在这里插入图片描述
    【提示】B选项函数缺少返回类型,因此不正确。C选项,返回类型定义为void,这意味着函数不返回任何值,代码尝试将
    square(2.0)的结果赋值给area,这会导致编译错误。D选项,return没有返回任何值。A选项,正确定义了一个返回类型为
    float的函数square,它接受一个float类型的参数x并返回x的平方。而且调用square(2)并将结果赋值给area是正确的。
    2、C++表达式(6>2)*2的值是(B)?

A, 1

B、2

C, true

D. false

【提示】先执行小括号内的运算,6>2这个逻辑比较结果是true,布尔值true等于1,1*2结果为2,所以整个表达式结果为2。

2的n次方

任意给定一个正整数n(n <= 100),计算2的n次方的值。
输入描述】输入一个正整数n。

输出描述】输出2的n次方的值。
【输入样例】

100

(输出样例】

1267650600228229401496703205376

#include<iostream>
using namespace std;

#define MAXN 160
int a[MAXN]={0};
int n;
int main() {
	cin >> n;
	a[0] = 1;
	for(int i = 1;i <= n;i++) {
		int up=0;//进位初始为0
		for(int j=0;j<MAXN;j++){//从个位到最高位,处理进位
			int t=a[j]*2+up;//逐位*2+进位
			a[j] = t%10;// 保存个位
			up = t/10;// 留下进位部分
		}
	}
	int i = MAXN-1;
	while(a[i] == 0) // 去前导0
		i --;
	while(i>=0)// 输出商
		cout << a[i -- ];
	return 0;
}

在这里插入图片描述

# c++ # 开发语言
Logo
亚马逊云科技技术品牌专区

更多推荐

cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！人工智能的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区
cover

别再只聊大模型！AI的下一场革命，藏在“身体”里

avatar 亚马逊云科技技术品牌专区