前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数.因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算.
高精度计算通用方法:高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位(当然,在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字,暂时不讲),表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数.如数:3485(三千四百八十五),表达在数组a[10]上情况是:
下标 0 1 2 3 4 5 6 7 8 9
内容 4 5 8 4 3 0 0 0 0 0
说明:位数 个位 十位 百位 千位
具体在计算加减乘除时方法就是小学时采用的列竖式方法.
注:高精度计算时一般用正数,对于负数,通过处理符号位的修正.
一.高精度数的存储
1.如对数采用的字符串输入
#include <iostream>
#include <string>
#include<memory.h>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i;
string s1;
cin>>s1;//数s1
memset(a,0,sizeof(a)); //数组清0
a[0]=s1.length(); //位数
for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';//将字符转为数字并倒序存储.
return 0;
}
2.直接读入
#include <iostream>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i,s,key;
cin>>key;//数key
memset(a,0,sizeof(a)); //数组清0
i=0;//第0位
while(key) //当key大于0
{
a[++i]=key%10;//取第i位的数
key=key/10;
}
a[0]=i; //共i位数
return 0;
}
3.直接初始化(用a[]存储)
初始化为0: memset(a,0,sizeof(a));
初始化为1: memset(a,0,sizeof(a));a[0]=1;a[1]=1;
以下程序都只写函数,不写完整程序,所有高精度数存储都满足上述约定。
二.高精度数比较
int compare(int a[],int b[]) //比较a和b的大小关系,若a>b则为1,a<b则为-1,a=b则为0
{int i;
if (a[0]>b[0]) return 1;//a的位数大于b则a比b大
if (a[0]<b[0]) return -1;//a的位数小于b则a比b小
for(i=a[0];i>0;i--) //从高位到低位比较
{if (a[i]>b[i]) return 1;
if (a[i]<b[i]) return -1;}
return 0;//各位都相等则两数相等。
}
三、高精度加法
int plus(int a[],int b[]) //计算a=a+b
{int i,k;
k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位数最大的一个的位数
for(i=1;i<=k;i++)
{a[i+1]+=(a[i]+b[i])/10; //若有进位,则先进位
a[i]=(a[i]+b[i])%10;} //计算当前位数字,注意:这条语句与上一条不能交换。
if(a[k+1]>0) a[0]=k+1; //修正新的a的位数(a+b最多只能的一个进位)
else a[0]=k;
return 0;
}
四、高精度减法
int gminus(int a[],int b[]);//计算a=a-b,返加符号位0:正数 1:负数
{ int flag,i
flag=compare(a,b); //调用比较函数判断大小
if (falg==0)//相等
{memset(a,0,sizeof(a));return 0;} //若a=b,则a=0,也可在return前加一句a[0]=1,表示是 1位数0
if(flag==1) //大于
{ for(i=1;i<=a[0];i++)
{ if(a[i]<b[i]){ a[i+1]--;a[i]+=10;} //若不够减则向上借一位
a[i]=a[i]-b[i];}
while(a[a[0]]==0) a[0]--; //修正a的位数
return 0;}
if (flag==-1)//小于 则用a=b-a,返回-1
{ for(i=1;i<=b[0];i++) { if(b[i]<a[i]){ b[i+1]--;b[i]+=10;} //若不够减则向上借一位
a[i]=b[i]-a[i];}
a[0]=b[0];
while(a[a[0]]==0) a[0]--; //修正a的位数
return -1;}
}
五、高精度乘法1(高精度乘单精度数,单精度数是指通常的整型数)
int multi1(int a[],long key) //a=a*key,key是单精度数
{int i,k;
if (key==0){memset(a,0,sizeof(a));a[0]=1;return 0;} //单独处理key=0
for(i=1;i<=a[0];i++)a[i]=a[i]*key;//先每位乘起来
for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;} //进位
//注意上一语句退出时i=a[0]+1
while(a[i]>0) {a[i+1]=a[i]/10;a[i]=a[i]%10;i++;a[0]++];} //继续处理超过原a[0]位数的进位,修正a的位数
return 0;
}
int multi2(int a[],int b[]) //a=a*b
{
}
分享到:
相关推荐
总结来说,C++中的高精度算法需要对位操作、动态内存管理和数值计算有深入理解。通过`BigInt`类的设计和实现,我们可以扩展C++的标准整数类型,使其能够处理任意大小的整数。这个示例中的代码将提供一个基础框架,...
C++是一种通用的、面向对象的编程语言,具有强大的性能和灵活性,因此常常被用于实现高精度算法。本文将深入探讨高精度算法的核心概念以及如何使用C++进行实现。 首先,我们了解什么是高精度算法。传统的计算机硬件...
C++实现高精度计算类库,包含了FFT的乘法除法,开平方,用法类似java的bigint,实测速度比java的快很多
圆周率的高精度C++算法,可以自己输入精确的位数,个人认为算法的效率还是很高的
标题“利用高精度算法求N!”表明我们要探讨的是一种特别设计的算法,能够处理大整数N的阶乘计算,而不会受到标准整数类型限制。描述中的“输入一个数N,输出N!”进一步确认了这个算法的目标是精确计算N的阶乘,...
在C++中,由于内置的`int`、`long long`等类型有其固定的大小限制,对于需要处理大数值的情况,就需要自定义数据结构和算法来实现高精度计算。以下将详细探讨C++中的高精度实现策略、常见的库以及相关操作。 1. **...
本文将围绕“C++高精度运算代码”这一主题,详细讨论高精度加法和乘法的实现,并结合提供的压缩包文件,探讨高精度除法的实现。 一、高精度加法 在C++中,我们可以使用数组存储大整数,每一位对应数组的一个元素。...
在C++中,实现高精度幂次方计算通常有两种常见方法:**迭代法**和**快速幂算法**。迭代法是最直观的方法,通过不断地自乘来达到目标指数,但其时间复杂度为O(b)。相比之下,快速幂算法更为高效,其时间复杂度降为O...
C++竞赛高精度模板 优点:包含四则运算 抛弃传统数组,使用vector 缺点:乘法没有使用FFT算法,复杂度O(N^2) 在某些编辑器上可能无法使用资源中定义的常量,需要手动创建(CE的话可能是这个问题) 没有运算符...
支持+,-,*,/,%,幂,大小判断
高精度算法的实现可以使用 C++ 语言来完成。下面是高精度加法运算的实现步骤: 1. 将从键盘输入的两个数分别存入两个 char 型的字符数组,然后再将两个 char 数组的数据转存入两个 int 型的数组。 代码如下: ```...
e的高精度C++算法,可以自己输入精确位数,自己认为算法的效率还是很高地~~~
8.2.6组合数的高精度算法 8.2.4高精度阶乘 8.2.3分组 8.2.2高精度幂 8.2.5国债计算 8.2.7高精度数除以高精度数 全书章节 第01章 模拟算法免费 第02章 递归算法 第03章 枚举算法 第04章 递推算法 第05章 分治算法 第...
高精度算法的C++版本的实现。详情见附件,内有详细说明和使用方法。
高精度模板是程序员必须掌握的一项技能,特别是在涉及精确计算、金融计算或者算法竞赛等领域。下面将详细讨论高精度模板的基本概念、实现方法以及其在C++中的应用。 一、高精度模板基础 1. **基本概念**:高精度...
以上知识点是实现C++高精度四则运算的核心内容。在实际开发中,可能还需要结合项目需求,考虑性能、可读性、可维护性等因素进行设计和实现。通过对这些知识点的理解和应用,可以构建出自己的高精度运算库。
高精度的算法,一般的方式是用一个很长的数组去记录数据,数组的每一位记录固定位数的数字,记录顺序是低位到高位。计算方式则通常采用模拟立竖式计算。计算方式有一些优化方法,比如FFT快速傅里叶变换优化乘法,...
### 数组型高精度算法详解 ...综上所述,高精度算法是解决大数运算问题的关键技术之一,在ACM竞赛及其他需要处理大量数据的应用场景中具有重要的作用。通过对高精度算法的理解和掌握,可以有效提升解决问题的能力。
解决一个问题通常有多种方法, 我们总想找到最高效的,所以需要对比不同算法执行所用的时间。可惜的是,C++中提供的方法一般只能精确到毫秒级。
在C++编程中,设计一个长整数高精度计算器是一项挑战性的课程设计任务,它涉及到对常规整型数据类型限制的超越以及复杂算法的应用。在这个项目中,我们不仅需要理解和运用C++的基本语法,还需要深入理解数值计算和...