当前位置：文档之家 › 高精度计算(C++版)

高精度计算(C++版)

  • 格式：ppt
  • 大小：318.00 KB
  • 文档页数：30

下载文档原格式

  / 30

合集下载

高精度计算

高精度计算

高精度计算由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，一般计算机实数表示的范围为1038，如果超过这个范围，计算机就无法表示了。

但是我们可以通过一些简单的办法来解决这个问题。

这就是我们要说的高精度计算机。

基本方法加法减法乘法精确值除法多精度除以单精度多精度除以多精度求e一、基本方法：在计算机上进行高精度计算，首先要处理好以下几个基本问题：1、数据的接收与存储；2、计算结果位数的确定；3、进位处理和借位处理；4、商和余数的求法；下面我们逐一介绍一下这几个问题的解决方法。

1、数据的接收与存储：要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。

通常：①、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。

②、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。

③、分离各位数字。

接收数据子模块(字符型变量接收数据)：QBASICPASCALINPUT a$l = LEN(a$)DIM a(l)FOR i = 1 TO la(i) = VAL(MID$(a$, i, 1))NEXTprucedure readdata(var in:array[1..100] of integer);var ch:char;i,k:integer;beginread(ch);k:=0;while ch in['0'..'9'] do begininc(k);int[k]:=ord(ch)-48;read(ch);end;end;2、计算结果位数的确定①、两数之和的位数最大为较大的数的位数加1。

②、乘积的位数最大为两个因子的位数之和。

③、阶乘与乘方的位数可以采用对数运算来确定计算结果的位数。

3、进位处理和借位处理①、加法的进位处理进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。

c语言高精度计算n的阶乘

c语言高精度计算n的阶乘

c语言高精度计算n的阶乘高精度计算是指在计算机中进行大数运算时，能够精确表示和计算超过计算机位数范围的整数或小数。

在计算n的阶乘时，如果n很大，传统的计算方法可能会导致溢出或精度丢失，因此需要使用高精度计算的方法。

C语言是一种广泛应用于系统软件和应用软件开发的高级程序设计语言。

它支持对内存的直接访问，并提供了丰富的库函数，可以方便地进行高精度计算。

本文将介绍如何使用C语言实现高精度计算n的阶乘。

我们需要明确阶乘的定义。

阶乘是指从1到n的连续整数的乘积，表示为n!。

例如，5的阶乘为5! = 5 ×4 × 3 × 2 × 1 = 120。

传统的计算n的阶乘的方法是使用循环结构，从1到n依次相乘。

但是，当n很大时，结果可能会超出计算机能够表示的范围。

为了避免这个问题，我们可以使用数组来表示大数，并模拟手工计算的过程。

具体实现时，我们可以使用一个整型数组来存储大数的每一位。

数组的每个元素表示一个位数，例如，数组的第一个元素表示最低位，最后一个元素表示最高位。

为了方便计算，我们可以将大数按照逆序存储，即最低位存储在数组的最后一个元素中。

我们需要定义一个函数来实现大数的乘法。

该函数接受两个大数作为参数，并返回它们的乘积。

具体实现时，我们可以使用两层循环遍历两个大数的每一位，并将结果保存在一个新的大数中。

在计算过程中，需要注意进位的处理。

接下来，我们可以定义一个函数来计算n的阶乘。

该函数接受一个整数n作为参数，并返回n的阶乘。

具体实现时，我们可以使用一个循环从2到n，依次计算每个数的阶乘，并将结果与之前的乘积相乘。

在计算过程中，为了避免溢出，我们可以使用前面提到的大数乘法函数。

我们可以在主函数中调用阶乘函数，并输出结果。

为了方便观察，我们可以将大数按照正常顺序输出，即从最高位到最低位。

具体实现时，可以使用一个循环从最高位到最低位遍历大数数组，并将每一位转换为字符型后输出。

高精度模板(算法必备)

高精度模板(算法必备)

高精度计算模板注意：减法、除法要用到compare函数乘法需要加法的部分，加法需要减法部分#include <iostream>#include <string>using namespace std;int compare(string str1, string str2){if(str1.size() > str2.size())return 1;else if(str1.size() < str2.size())return -1;elsereturn pare(str2);}int main(){char ch;string s1, s2, res;while(cin >> ch) {cin >> s1>> s2;switch(ch) {case '+': res = ADD_INT(s1, s2); break; //高精度加法case '-': res = MINUS_INT(s1, s2); break; //高精度减法case '*': res = MULTIPLY_INT(s1, s2); break; //高精度乘法case '/': res = DIV_INT(s1, s2); break; //高精度除法,返回商case 'm': res = MOD_INT(s1, s2); break; //高精度除法,返回余数 default : break;}cout << res<< endl;}return(0);}string ADD_INT(string str1, string str2){string MINUS_INT(string str1, string str2);int sign = 1;string str;if(str1[0] == '-') {if(str2[0] == '-') {sign = -1;str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));}else {str = MINUS_INT(str2, str1.erase(0, 1));}}else {if(str2[0] == '-')str = MINUS_INT(str1, str2.erase(0, 1));else {string::size_type l1, l2;int i;l1 = str1.size(); l2 = str2.size();if(l1 < l2) {for(i = 1; i <= (int)(l2 - l1); i++)str1 = "0" + str1;}else {for(i = 1; i <= (int)(l1 - l2); i++)str2 = "0" + str2;}int int1 = 0, int2 = 0;for(i = str1.size() - 1; i >= 0; i--) {int1 = (int(str1[i]) - 48 + int(str2[i]) - 48 + int2) %10; int2 = (int(str1[i]) - 48 + int(str2[i]) - 48 +int2) / 10; str = char(int1 + 48) + str;}if(int2 != 0) str = char(int2 + 48) + str;}}//运算后处理符号位if((sign == -1) && (str[0] !='0'))str = "-" + str;return str;}string MINUS_INT(string str1, string str2){string MULTIPLY_INT(string str1, string str2);int i,sign = 1;string str;if(str2[0] == '-')str = ADD_INT(str1, str2.erase(0, 1));else {int res = compare(str1, str2);if(res == 0) return "0";if(res < 0) {sign = -1;string temp = str1;str1 = str2;str2 = temp;}string::size_type tempint;tempint = str1.size() - str2.size();for(int i = str2.size() - 1; i >= 0; i--) {if(str1[i + tempint] < str2[i]) {str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1); str = char(str1[i + tempint] - str2[i] + 58) + str;}elsestr = char(str1[i + tempint] - str2[i] + 48) + str;}for(i = tempint - 1; i >= 0; i--)str = str1[i] + str;}//去除结果中多余的前导0str.erase(0, str.find_first_not_of('0'));if(str.empty()) str = "0";if((sign == -1) && (str[0] !='0'))str = "-" + str;return str;}string MULTIPLY_INT(string str1, string str2){int sign = 1;string str;if(str1[0] == '-') {sign *= -1;str1 = str1.erase(0, 1);}if(str2[0] == '-') {sign *= -1;str2 = str2.erase(0, 1);}int i, j;string::size_type l1, l2;l1 = str1.size(); l2 = str2.size();for(i = l2 - 1; i >= 0; i --) {//实现手工乘法string tempstr;int int1 = 0, int2 = 0, int3 = int(str2[i]) - 48;if(int3 != 0) {for(j = 1; j <= (int)(l2 - 1 - i); j++)tempstr = "0" + tempstr;for(j = l1 - 1; j >= 0; j--) {int1 = (int3 * (int(str1[j]) - 48) + int2) % 10; int2 = (int3 * (int(str1[j]) - 48) + int2) / 10;tempstr = char(int1 + 48) + tempstr;}if(int2 != 0) tempstr = char(int2 + 48) + tempstr;}str = ADD_INT(str, tempstr);}//去除结果中的前导0str.erase(0, str.find_first_not_of('0'));if(str.empty()) str = "0";if((sign == -1) && (str[0] !='0'))str = "-" + str;return str;}string DIVIDE_INT(string str1, string str2, int flag){//flag = 1时,返回商; flag = 0时,返回余数string quotient, residue;int sign1 = 1, sign2 = 1, i;if(str2 == "0") { //判断除数是否为0quotient = "ERROR!";residue = "ERROR!";if(flag == 1) return quotient;else return residue;}if(str1 == "0") { //判断被除数是否为0quotient = "0";residue = "0";}if(str1[0] == '-') {str1 = str1.erase(0, 1);sign1 *= -1;sign2 = -1;}if(str2[0] == '-') {str2 = str2.erase(0, 1);sign1 *= -1;}int res = compare(str1, str2);if(res < 0) {quotient = "0";residue = str1;}else if(res == 0) {quotient = "1";residue = "0";}else {string::size_type l1, l2;l1 = str1.size(); l2 = str2.size();string tempstr;tempstr.append(str1, 0, l2 - 1);//模拟手工除法for(i = l2 - 1; i < l1; i++) {tempstr = tempstr + str1[i];for(char ch = '9'; ch >= '0'; ch --) {string str;str = str + ch;if(compare(MULTIPLY_INT(str2, str), tempstr) <= 0){quotient = quotient + ch;tempstr = MINUS_INT(tempstr, MULTIPLY_INT(str2, str));break;}}}residue = tempstr;}//去除结果中的前导0quotient.erase(0, quotient.find_first_not_of('0'));if(quotient.empty()) quotient = "0";if((sign1 == -1) && (quotient[0] !='0'))quotient = "-" + quotient;if((sign2 == -1) && (residue[0] !='0'))residue = "-" + residue;if(flag == 1) return quotient;else return residue;}//高精度除法,返回商string DIV_INT(string str1, string str2){return DIVIDE_INT(str1, str2, 1);}//高精度除法,返回余数string MOD_INT(string str1, string str2){return DIVIDE_INT(str1, str2, 0);}。

c语言定义双精度浮点数

c语言定义双精度浮点数

C语言定义双精度浮点数双精度浮点数是一种C语言中用于表示大范围和高精度的浮点数类型。

在C语言中，双精度浮点数类型被定义为double，它占据8个字节（64位）的存储空间。

1. 双精度浮点数的表示方式双精度浮点数采用IEEE 754标准来表示，它使用一种科学计数法的形式，包含三个部分：符号位、指数位和尾数位。

符号位双精度浮点数的符号位用于表示数值的正负，它占据1个比特位。

0表示正数，1表示负数。

指数位双精度浮点数的指数位用于表示数值的大小，它占据11个比特位。

指数位使用偏移的二进制表示，即实际存储的值减去一个偏移量。

这个偏移量是2的指数位数减1后的结果。

尾数位双精度浮点数的尾数位用于表示数值的精度，它占据52个比特位。

尾数位使用二进制小数的形式表示。

2. C语言中定义双精度浮点数在C语言中，可以使用double关键字来定义双精度浮点数变量。

例如：double num1 = 3.14159;double num2 = 2.71828;上述代码中，num1和num2分别被定义为双精度浮点数变量，并且分别被赋值为π和自然对数的底数e。

3. 双精度浮点数的精度和范围双精度浮点数的精度比单精度浮点数更高，可以表示更大范围和更高精度的数值。

双精度浮点数的精度约为15到16位有效数字。

双精度浮点数的范围由指数位的取值范围决定。

指数位的取值范围为-1022到1023，表示的指数范围为-1022到1023。

根据指数位的取值范围，双精度浮点数可以表示的数值范围约为10的-308次方到10的308次方。

4. 双精度浮点数的运算C语言提供了一系列的运算符和函数来进行双精度浮点数的运算。

常见的运算符包括加法、减法、乘法和除法。

例如：double result = num1 + num2; // 加法double result = num1 - num2; // 减法double result = num1 * num2; // 乘法double result = num1 / num2; // 除法此外，C语言还提供了一些数学函数来进行更复杂的双精度浮点数运算，如求平方根、求幂、求对数等。

高精度计算

高精度计算

输出时注意跳过高位时多余的0 输出时注意跳过高位时多余的0 数组需要稍微大一些，避免运算时溢出
程序实现
交给大家解决！谢谢老师们！
高精度乘法: 高精度乘法: 高精度乘单精度大体算法 单精度大体算法: 高精度乘单精度大体算法: 由低位到高位逐位乘以单精度数b 由低位到高位逐位乘以单精度数b，把 a[i]*b的除 的余数作为更新 的值 a[i]*b的除10的余数作为更新a[i]的值， 的除10的余数作为更新a[i]的值， 而对10取整赋值给 作为进位。 取整赋值给g 而对10取整赋值给g作为进位。
三、高精度要处理的几个问题： 高精度要处理的几个问题： ）、数据的读入和存贮方法 数据的读入和存贮方法。 （1）、数据的读入和存贮方法。 如果所处理的数据小于或等于255位 如果所处理的数据小于或等于255位，可直接使用字符串 读入，利用字符串操作把它们存贮在数组中。 读入，利用字符串操作把它们存贮在数组中。如果超过 255位，可使用字符数组逐位读入并存贮。 255位 可使用字符数组逐位读入并存贮。 ）、计算结果位数的确定 （2）、计算结果位数的确定。 ）、计算结果位数的确定。 位数的确定： 位数的确定：利用对数函数 L=trunc(log(x)/log(10))+1来确定位数。定义 A（L） 来确定位数。 来确定位数 （ ） （3）进位和借位处理。 ）进位和借位处理。 加法进位： 加法进位：a[i]:=a[i]+b[i],若a[i]>=10则a[i]:=a[i]若 则 10;a[i+1]:=a[i+1]+1 减法借位： 减法借位：若a[i]<b[i]则a[i+1]:=a[i+1]则 1;a[i]:=a[i+10];a[i]:=a[i]-b[i] 乘法进位： 乘法进位：y:=a[i]*b[i]+c;c:=y div 10;a[i]:=y-c*10

信息学奥赛系列课程(三阶段)-2019_02_21_第3版

信息学奥赛系列课程(三阶段)-2019_02_21_第3版

信息学奥赛NOIP系列课程（三阶段）第一阶段C++语言及数据结构与算法基础课本:1、信息学奥赛一本通+训练指导教程C++版第五版--2017年出版(两本）第1部分C++语言（50课时）适于：零基础的初中或高中的学生，当然有C语言或scratch、Python语言基础更好授课：相关内容讲授+实例+题目现堂训练（每次课2-3题，题目较大可能是1题）第1章C++语言入门（2－3课时）第2章顺序结构程序设计（6课时）第3章程序控制结构（3课时）NOIP2017复赛普及组第1题成绩https:///problem-12334.htmlNOIP2018复赛普及组第1题标题统计方法一https:///problem-12393.htmlNOIP1996普及组第1题https:///WDAJSNHC/article/details/83513564https:///yuyanggo/article/details/47311665第4章循环结构（5课时）NOIP2018复赛普及组第1题标题统计方法二https:///problem-12393.htmlNOIP2016复赛普及组第1题买铅笔https:///problem-12121.htmlNOIP2015复赛普及组第1题金币/ch0105/45/NOIP2002复赛普及组第1题级数求和/ch0105/27/NOIP2013复赛普及组第1题计数问题https:///problem-11005.html?tdsourcetag=s_pcqq_aiomsgNOIP2012复赛普及组第1题质因数分解/ch0105/43/NOIP2011复赛普及组第1题数字反转/ch0105/29/NOIP2010复赛普及组第1题数字统计https:///problem-10012.htmlNOIP1999普及组第1题Cantor表/ch0201/8760/https:///problemnew/show/P1014NOIP1997普及组第1题棋盘问题https:///problemnew/show/P1548NOIP1995普及组复赛第1题https:///secret_zz/article/details/76862335https:///WDAJSNHC/article/details/83513896NOIP1997普及组第2题数字三角形https:///ber_bai/article/details/76722379第5章数组（9－10课时）NOIP2014复赛普及组第1题珠心算测验https:///problem-12091.htmlNOIP2009复赛普及组第1题多项式输出/ch0113/39/NOIP2006复赛普及组第1题明明的随机数/ch0110/09/NOIP2005复赛普及组第1题陶陶摘苹果/ch0106/02/NOIP2004复赛普及组第1题不高兴的津津/ch0109/03/NOIP2003年普及组第1题乒乓球/ch0113/37/NOIP1998年普及组第1题三连击（枚举）https:///problemnew/show/P1008NOIP1995普及组复赛第2题方阵填数https:///WDAJSNHC/article/details/79381876NOIP1996普及组第2题格子问题https:///WDAJSNHC/article/details/79381843?utm_source=blogxgwz5NOIP2016复赛普及组第2题回文日期https:///problem-12122.htmlhttps:///problemnew/show/P2010NOIP2015普及组第2题P2670扫雷游戏/ch0108/14/https:///problemnew/show/P2670https:///problem-12105.htmlNOIP2012普及组第2题_P1076寻宝/ch0112/06/https:///problemnew/show/P1076第6章函数（5课时）NOIP2008复赛普及组第1题ISBN号码/ch0107/29/NOIP2000提高组第1题P1017进制转换https:///problemnew/show/P1017NOIP2000普及组第1题计算器的改良https:///problemnew/show/P1022https:///yuyanggo/article/details/47856785https:///u012773338/article/details/41749421NOIP2018普及组第2题龙虎斗https:///problemnew/show/P5016https:///problem-12394.html机器翻译【1.12编程基础之函数与过程抽象07】Noip2010提高组第1题/ch0112/07/Vigenère密码【1.12编程基础之函数与过程抽象08】Noip2012提高组第1题/ch0112/08/笨小猴【1.9编程基础之顺序查找06】NOIP2008提高组第1题/ch0109/06/第7章文件和结构体（5课时）NOIP2011复赛提高组第1题铺地毯/ch0109/14/NOIp2008提高组第2题火柴棒等式https:///problemnew/show/P1149https:///Mr_Doublerun/article/details/52589778第8章指针及其应用（8课时）第9章C++实用技巧与模版库（5课时）NOIP2007复赛普及组第1题奖学金/ch0110/04/NOIP2017复赛普及组第2题图书管理员（STL、排序）https:///problem-12335.htmlhttps:///problemnew/show/P3955NOIP1999普及组第2题回文数https:///problemnew/show/P1015***模拟NOIP2017年提高组第2题时间复杂度（模拟）https:///problem-12333.htmlhttps:///problemnew/show/P3952NOIP2011普及组第3题P1309瑞士轮（模拟、快拍、归并排序）/ch0401/4363/https:///problemnew/show/P1309NOIP2018复赛普及组第3题摆渡车(模拟)https:///problem-12395.htmlhttps:///problemnew/show/P5017NOIP2016普及组第3题海港（port）--枚举https:///problemnew/show/P2058NOIP2006年提高组第3题P1065作业调度方案(模拟)https:///problemnew/show/P1065NOIP2013提高组第4题P1969积木大赛（模拟贪心）https:///problem-12071.htmlhttps:///problemnew/show/P1969NOIP2014提高组第4题P2038无线网络发射器选址（模拟）https:///problemnew/show/P2038第2部分NOIP基础算法（39课时）第1章高精度计算（2-3课时）【例1.6】回文数(Noip1999):8088/problem_show.php?pid=1309NOIP2003普及组第4题P1045麦森数(分治、高精度运算)https:///problemnew/show/P1045NOIP2005普及组第4题P1050循环(高精度运算、数论、快速幂) https:///problemnew/show/P1050第2章数据排序（3课时）NOIP2014复赛普及组第1题珠心算测验https:///problem-12091.html第3章递推算法（2-3课时）1314：【例3.6】过河卒(Noip2002):8088/problem_show.php?pid=1314NOIP2011普及组第4题P1310表达式的值(栈、表达式计算、递推) https:///problemnew/show/P1310NOIP2011提高组第6题P1315观光公交(递推分析、贪心)https:///problemnew/show/P1315第4章递归算法（2-3课时）【例4.6】数的计数(Noip2001普及组第1题):8088/problem_show.php?pid=1316第5章搜索与回溯算法（2-3课时）NOIP2015day1T3_斗地主P2668斗地主https:///problemnew/show/P2668NOIP2017年普及组第3题棋盘https:///problemnew/show/P3956https:///problem-12336.htmlNOIP2015年提高组第2题P2661信息传递（Tarjen bfs/dfs（图论））https:///problem-12107.htmlhttps:///problemnew/show/P2661NOIP2016年提高组第2题天天爱跑步（Lca/dfs（图论）树结构最近公共祖先）https:///problem-12208.htmlhttps:///problemnew/show/P1600NOIP2000普及组第4题P1019单词接龙(深搜)https:///problemnew/show/P1019NOIP2000年提高组第3题单词接龙(DFS,字符串,模拟)https:///problemnew/show/P1019NOIP2014普及组第4题P2258子矩阵(搜索或dp)https:///problemnew/show/P2258NOIP2018年提高组第3题P5021赛道修建(搜索深度优先搜索)https:///problem-12392.htmlhttps:///problemnew/show/P5021第6章贪心算法（3课时）删数问题（NOIP1994）P1106删数问题https:///problemnew/show/P1106:8088/problem_show.php?pid=1321NOIP2010复赛普及组第2题接水问题/ch0109/15/NOIP1999年提高组第1题导弹拦截https:///problemnew/show/P1020https:///huashanqingzhu/p/6728652.html https:///qq_33927580/article/details/51853345 https:///Darost/article/details/52086240https:///yuyanggo/article/details/48739029NOIP2002提高组第1题均分纸牌P1031均分纸牌https:///problemnew/show/P1031NOIP2007普及组第2题_P1094纪念品分组https:///problem-12007.htmlhttps:///problemnew/show/P1094NOIP2008普及组第2题_P1056排座椅https:///problem-12008.htmlhttps:///problemnew/show/P1056NOIP2012年提高组第2题国王游戏（贪心、排序后列出）https:///problemnew/show/P1080NOIP2013年提高组第2题P1966火柴排队(逆序对、贪心、排序) https:///problem-12083.htmlhttps:///problemnew/show/P1966NOIP2010普及组第4题P1199三国游戏(贪心)https:///problemnew/show/P1199第7章分治算法（3课时）NOIP2001提高组第1题P1024一元三次方程求解/ch0204/7891/https:///problemnew/show/P1024NOIP2011年提高组第2题P1311选择客栈(二分查找)https:///problemnew/show/P1311NOIP2003普及组第4题P1045麦森数(分治、高精度运算)https:///problemnew/show/P1045第8章广度优先搜索算法（2-3课时）NOIP2002年提高组第2题P1032字串变换(BFS,字符串)https:///problemnew/show/P1032NOIP2013提高组第6题P1979华容道(广搜\最短路:图论)https:///problem-12212.htmlhttps:///problemnew/show/P1979第9章动态规划（15课时）第一节动态规划的基本模型1260：【例9.4】拦截导弹(NOIP1999):8088/problem_show.php?pid=1260NOIP2013普及组第3题P1982小朋友的数字https:///problemnew/show/P1982NOIP2003复赛普及组第2题_P1043数字游戏数字游戏（Game.cpp）https:///problemnew/show/P1043NOIP2006年提高组第2题P1064金明的预算方案(资源分配DP,构造) https:///problemnew/show/P1064NOIP2013普及组第3题P1982小朋友的数字（动态规划、子段和）https:///problemnew/show/P1982NOIP2007普及组第3题P1095守望者的逃离(动态规划或枚举）https:///problemnew/show/P1095NOIP2009普及组第4题P1070道路游戏(动态规划)https:///problemnew/show/P1070NOIP2004年提高组第3题P1091合唱队形(子序列DP)https:///problemnew/show/P1091第二节背包问题NOIP2018提高组第2题货币系统https:///problem-12391.htmlNOIP2006普及组第2题_P1060开心的金明题解https:///problemnew/show/P1060NOIP2005普及组第3题P1048采药(0/1背包)/ch0206/1775/https:///problem-12062.htmlhttps:///problemnew/show/P1048NOIP2001普及组第4题P1049装箱问题(0/1背包或枚举)https:///problemnew/show/P1049NOIP2014年提高组第3题P1941飞扬的小鸟(背包DP)https:///problem-12087.htmlhttps:///problemnew/show/P1941第三节动态规划经典题NOIP2000年提高组第2题P1018乘积最大（资源分配DP）https:///problemnew/show/P1018NOIP2000普及组第3题P1018乘积最大(划分动态规划)https:///problemnew/show/P1018NOIP2001年提高组第2题P1025数的划分（资源分配DP,多维状态DP）/ch0206/8787/https:///problemnew/show/P1025NOIP2001年提高组第3题统计单词个数(资源分配DP,字符串) https:///problemnew/show/P1026NOIP2005年提高组第2题P1052过河(子序列DP,贪心优化)https:///problemnew/show/P1052NOIP2010年提高组第2题P1541乌龟棋(动态规划优化)https:///problemnew/show/P1541NOIP2014年提高组第2题P1351联合权值（动态规划搜索图结构树形DP图的遍历遍历（图论）,二次展开式）https:///problem-12086.htmlhttps:///problem-12210.htmlhttps:///problemnew/show/P1351NOIP2008普及组第3题P1057传球游戏（动态规划）https:///problemnew/show/P1057NOIP2012普及组第3题摆花（动态规划）https:///problem-12366.htmlhttps:///problemnew/show/P1077NOIP2002普及组第4题P1002过河卒(棋盘动态规划)https:///problemnew/show/P1002NOIP2008年提高组第3题P1006传纸条(多维状态DP动态规划图结构最短路网络流)https:///problem-12110.htmlhttps:///problemnew/show/P1006NOIP2000提高组第4题方格取数(多维状态DP)/ch0206/8786/https:///problem-12186.htmlhttps:///problemnew/show/P1004NOIP2002提高组第4题P1034矩形覆盖(动态规划/贪心/搜索剪枝) /ch0405/1793/https:///problemnew/show/P1034第3部分NOIP数据结构（19课时）第1章栈（3课时）NOIP2011普及组第4题P1310表达式的值(栈、表达式计算、递推) https:///problemnew/show/P1310第2章队列（3-5课时）NOIP2016普及组第3题海港（port）https:///problemnew/show/P2058第3章树（3课时）第一节树的概念第二节二叉树第三节堆及其应用NOIP2015普及组第4题P2672推销员(枚举、堆)https:///problemnew/show/P2672NOIP2001普及组第3题P1030求先序排列(树的遍历)https:///problemnew/show/P1030NOIP2004普及组第3题P1087FBI树(二叉树的遍历)https:///problemnew/show/P1087第4章图论算法（8课时）第一节基本概念第二节图的遍历第三节最短路径算法NOIP2002普及组第3题P1037产生数(最短路、高精度)https:///problemnew/show/P1037NOIP2012普及组第4题P1078文化之旅(搜索、最短路(图论)、动规) https:///problemnew/show/P1078NOIP2009年提高组第3题P1073最优贸易(最短路:图论）https:///problemnew/show/P1073NOIP2001提高组第4题P1027Car的旅行路线(最短路,实数处理)https:///problemnew/show/P1027NOIP2007提高组第4题P1099树网的核(最短路,树的直径)https:///problemnew/show/P1099第四节图的连通性问题第五节并查集NOIP2010年提高组第3题P1525关押罪犯(二分答案或并查集)https:///problemnew/show/P1525NOIP2017提高组第4题P3958奶酪（数据结构树结构并查集）https:///problem-12205.htmlhttps:///problemnew/show/P3958第六节最小生成树第七节拓朴排序与关键路径NOIP2013普及组第4题P1983车站分级(图论、拓扑排序) https:///problemnew/show/P19831390：食物链【NOI2001】:8088/problem_show.php?pid=1390NOIP2004年提高组第2题P1090合并果子(最优哈夫曼树，排序，贪心)https:///problemnew/show/P1090NOIP2013年提高组第3题P1967货车运输(最大生成树,最近公共祖先)https:///problemnew/show/P1967NOIP2018提高组第4题P5022旅行（搜索图结构）https:///problem-12397.htmlhttps:///problemnew/show/P5022NOIP2018提高组第6题P5024保卫王国(图结构)https:///problem-12399.htmlhttps:///problemnew/show/P50242、啊哈！算法--2014-06（35-50小时）第二阶段算法与数据结构提高1、《信息学奥赛一本通·提高篇》（80-100课时，不一定一次都讲完）第一部分基础算法第1章贪心算法NOIP2002提高组第1题P1031均分纸牌(贪心,模拟)https:///problemnew/show/P1031NOIP2010普及组第3题P1158导弹拦截（排序+枚举，贪心）https:///problemnew/show/P1158NOIP2012提高组第6题P1084疫情控制(二分答案，贪心，倍增)https:///problemnew/show/P1084第2章二分与三分NOIP2010年提高组第3题P1525关押罪犯(二分答案或并查集)https:///problemnew/show/P1525NOIP2008提高组第4题P1155双栈排序(枚举,贪心/二分图)https:///problemnew/show/P1155NOIP2015提高组第4题P2678跳石头（二分查找、二分答案）https:///problem-12198.htmlhttps:///problemnew/show/P2678第3章深搜的剪枝技巧NOIP2018普及组第4题对称二叉树（搜索树结构深度优先搜索）https:///problem-12396.htmlhttps:///problemnew/show/P5018NOIP2011年提高组第3题P1312Mayan游戏(深搜、剪支)https:///problemnew/show/P1312NOIP2015年提高组第3题P2668斗地主(分情况,剪枝)https:///problemnew/show/P2668NOIP2003提高组第4题P1041传染病控制(随机贪心/搜索剪枝)https:///problemnew/show/P1041NOIP2004提高组第4题P1092虫食算（搜索搜索与剪枝）https:///problem-12414.htmlhttps:///problemnew/show/P1092第4章广搜的优化技巧NOIP2017年普及组第3题棋盘（搜索搜索与剪枝广度优先搜索）https:///problemnew/show/P3956https:///problem-12336.htmlNOIP2009提高组第4题P1074靶形数独(搜索优化)https:///problemnew/show/P1074NOIP2010提高组第4题P1514引入水域（广搜+动态规划，判断有解和无解）https:///problemnew/show/P1514第二部分字符串算法第1章哈希表第2章KMP算法第3章Trie字典树第4章AC自动机NOIP2005提高组第4题P1054等价表达式(字符串,抽样检测,表达式) /practice/1686/https:///problemnew/show/P1054NOIP2008普及组第4题P1058立体图(字符输出)https:///problemnew/show/P1058NOIP2006普及组第3题P1061Jam的计数法(数学、字符串)https:///problemnew/show/P1061NOIP2007年提高组第2题字符串的展开（字符串模拟）https:///problem-11016.htmlhttps:///problemnew/show/P1098NOIP2003年提高组第2题P1039侦探推理(枚举,模拟,字符串)https:///problemnew/show/P1039NOIP2011普及组第2题_P1308统计单词数/ch0112/05/https:///problemnew/show/P1308第三部分图论第1章最小生成树第2章最短路径NOIP2016年提高组第3题P1850换教室(最短路/Dp)https:///problemnew/show/P1850NOIP2017年提高组第3题P3953逛公园(搜索图结构记忆化搜索最短路)https:///problem-12337.htmlhttps:///problemnew/show/P3953NOIP2014提高组第5题P1351联合权值(遍历,二次展开式)https:///problem-12086.htmlhttps:///problemnew/show/P1351第3章SPFA算法的优化第4章差分约束系统第5章强连通分量第6章割点和桥第7章欧拉回路第四部分数据结构第1章树状数组第2章RMQ问题第3章线段树NOIP2012提高组第5题P1083借教室(枚举、线段树、树状数组、二分) https:///problem-12069.htmlhttps:///problemnew/show/P1083NOIP2017提高组第6题P3960列队(数据结构平衡树线段树)https:///problem-12339.htmlhttps:///problemnew/show/P3960第4章倍增求LCANOIP2015提高组第6题P2680运输计划(Lca或线段树)https:///problem-12213.htmlhttps:///problemnew/show/P2680第5章树链剖分第6章平衡树Treap第五部分动态规划第1章区间类型动态规划NOIP2007年提高组第3题P1005矩阵取数游戏(区间DP,高精度)https:///problemnew/show/P1005第2章树型动态规划NOIP2003年提高组第3题P1040加分二叉树(树,区间DP)https:///problemnew/show/P1040第3章数位动态规划第4章状态压缩类动态规划NOIP2017提高组第5题P3959宝藏(动态规划搜索贪心状态压缩DP枚举)https:///problem-12340.htmlhttps:///problemnew/show/P3959NOIP2016提高组第6题愤怒的小鸟(状态压缩动态规划)https:///problemnew/show/P2831第5章单调队列优化动态规划NOIP2016提高组第5题蚯蚓(单调队列)https:///Mrsrz/p/7517155.htmlhttps:///m0_38083668/article/details/82557281NOIP2017普及组第4题P3957跳房子（数据结构动态规划单调队列队列）https:///problem-12338.htmlhttps:///problemnew/show/P3957第6章利用斜率优化动态规划NOIP2012年提高组第3题P1081开车旅行(离线深搜，动态规划、倍增)https:///problemnew/show/P1081NOIP2015提高组第5题P2679子串(Dp+滚动数组)https:///problemnew/show/P2679第六部分数学基础第1章快速幂第2章素数第3章约数第4章同余问题第5章矩阵乘法第6章组合数学NOIP2009年提高组第2题P1072Hankson的趣味题(初等数论,质因数,组合数学)https:///problemnew/show/P1072NOIP2006提高组第4题P10662^k进制数(动态规划/组合数学,高精度) https:///problemnew/show/P1066NOIP2011提高组第4题P1313计算系数（组合、二项式系数）/practice/4036/https:///problemnew/show/P1313NOIP2016提高组第4题P2822组合数问题（杨辉三角）https:///problemnew/show/P2822第7章博弈论NOIP2004普及组第4题P1088火星人(数学:排列、stl)https:///problemnew/show/P1088NOIP2009普及组第3题P1069细胞分裂（数论）https:///problemnew/show/P1069NOIP2000提高组第1题P1017进制转换(初等代数,找规律)https:///problemnew/show/P1017NOIP2001提高组第1题P1024一元三次方程求解(数学,枚举,实数处理) /ch0204/7891/https:///problemnew/show/P1024NOIP2003普及组第3题P1044栈(数学:卡特兰数）https:///problemnew/show/P1044NOIP2018年提高组第2题货币系统(数论)https:///problem-12391.htmlhttps:///problemnew/show/P5020NOIP2014年普及组复赛第3题螺旋矩阵（数学分析）https:///problem-12341.htmlhttps:///problemnew/show/P2239NOIP2015年普及组第3题求和（数学：数列）https:///problemnew/show/P2671NOIP2004普及组第4题P1088火星人(数学:排列、stl)https:///problemnew/show/P1088NOIP2005普及组第4题P1050循环(高精度运算、数论、快速幂) https:///problemnew/show/P1050NOIP2006普及组第4题P1062数列(数学:进制转换)https:///problemnew/show/P1062NOIP2007普及组第4题P1096$Hanoi$双塔问题(数学、高精度) https:///problemnew/show/P1096NOIP2016普及组第4题P2119魔法阵(数学分析、枚举)https:///problemnew/show/P2119NOIP2002年提高组第3题P1033自由落体(数学,物理,模拟,实数处理) https:///problemnew/show/P1033NOIP2005年提高组第3题P1053篝火晚会(置换群,贪心)https:///problemnew/show/P1053NOIP2012提高组第4题P1082同余方程（数论、递归，扩展欧几里得）https:///problemnew/show/P1082NOIP2011提高组第5题P1314聪明的质监员(部分和优化)/practice/4037/https:///problemnew/show/P1314NOIP2013提高组第5题P1970花匠(序列)https:///problem-12072.htmlhttps:///problemnew/show/P1970NOIP2018提高组第5题P5023填数游戏（DP）https:///problem-12398.htmlhttps:///problemnew/show/P50232、NOIP历年真题讲解（30-50小时）---包括初赛和复赛3、《骗分导论》（推荐指数：5颗星）--电子书（可以作为学习的参考资料）第三阶段算法与数据结构高级专题（选择性学习）1、信息学奥赛之数学专题2、高级数据结构(C++版)3、动态规划专题注：上面的内容也可能要交叉的进行讲解在线题库：1、OpenJudge在线题库/2、信息学奥赛一本通在线评测系统:8088/3、洛谷https:///4、啊哈编程/tiku/5、《信息学奥赛一本通（提高篇）》在线评测OJhttps://loj.ac/注：本系列课程将根据行业发展状况，及时优化调整课程内容，具体课程设置以实际为准。

高精度计算c++加法

高精度计算c++加法在计算机科学中，高精度计算是经常需要用到的一种技术，尤其是在处理大数运算时。

C语言是一种常用的编程语言，它提供了许多内置函数来处理整数，包括高精度计算。

在C语言中，可以使用长整型数据类型来进行高精度计算。

本文将介绍如何使用C语言进行高精度加法运算。

一、高精度加法原理高精度加法运算与普通的加法运算有一些不同。

在普通加法中，我们需要考虑进位的问题，而在高精度加法中，我们需要考虑的是位的数量。

也就是说，我们需要将两个大数分别表示成一位一位的形式，然后逐位相加，如果有进位，则要向上一位加。

最终得到的结果就是两个大数和的最高位以及剩下的位。

二、实现高精度加法下面是一个简单的C语言程序，用于实现高精度加法：```c#include <stdio.h>#include <stdlib.h>#define MAX_DIGITS 1000 // 定义最大位数// 高精度加法函数long long add(long long a, long long b) {long long carry = 0; // 进位初始化为0long long result[MAX_DIGITS+1]; // 结果数组，长度为最大位数+1int i, k; // i表示当前处理的位数，k表示当前位的值for (i = 0; i < MAX_DIGITS; i++) { // 处理每一位k = (int)a % 10 + (int)b % 10; // 当前位的值result[i] = k + carry; // 加上进位carry = result[i] / 10; // 计算进位result[i+1] += carry * 10; // 将进位写入下一个位置}if (carry > 0) { // 如果有进位result[MAX_DIGITS] += carry; // 将最高位的进位写入结果数组的最后一位}// 将结果数组逆序输出即可得到结果for (i = MAX_DIGITS-1; i >= 0; i--) {printf("%lld ", result[i]);}printf("\n");return result[0]; // 返回结果数组的第一个值}int main() {long long a, b, result;printf("Enter two large numbers: \n");scanf("%lld %lld", &a, &b); // 读入两个大数result = add(a, b); // 对两个数进行高精度加法运算printf("Result: %lld\n", result); // 输出结果return 0;}```这个程序中，我们首先定义了一个常量MAX_DIGITS来表示最大位数。

03.高精度计算(C++版)

第八页，编辑于星期三：五点 四十二分。
printf("Input minuend:"); gets(n1); //输入被减数
printf("Input subtrahend:"); gets(n2); //输入减数
if (strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0))
gets(a1); //scanf geti
gets(b1);
//输入加数与被加数
lena=strlen(a1);
lenb=strlen(b1);
for (i=0;i<=lena-1;i++) a[lena-i]=a1[i]-48; a1[i] - ‘0’ //加数放入a数组
for (i=0;i<=lenb-1;i++) b[lenb-i]=b1[i]-48; //加数放入b数组
856 + 255 1111
图1
A3 A2 A1 + B3 B2 B1 C4 C3 C2 C1
图2
如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有 A[1]=6，A[2]=5， A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1，C[3]=1，C[2]=1， C[1]=1，两数相加如图2所示。
using namespace std;
int main()
{
int a[256],b[256],c[256],lena,lenb,lenc,i;
char n[256],n1[256],n2[256];
memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c));

高精度整数加法运算(C语言)


/* * * *
******************************************************** name: add.c author: Joshua Chan description: 对二个随意长度的整数进行加法运算
以程序参数的形式输入二个随意长度整数（可为负整数） 程序会输出其加法运算的结果
高精度整数加法运算c语言c语言高精度加法c语言高精度运算c语言大数加法高精度c语言c语言运算符高精度整数加法c语言高精度计算c语言运算符优先级c语言运算c语言逻辑运算符
高精度整数加法运算
因为是任意长的二整数求和，而系统中整型数的精度有限，因此需用字符串形式存储整数，并按位逐 位进行运算，运算过程中需考虑进位和借位问题。再者，整数可以是负数，若二整数符号相同则为加法运 算，相异则实为减法运算，若是减法运算还需比较二数的绝对值大小，以确定最终结果的符号及减数与被 减数的安排顺序。 完整 result[i] = '-'; i++; } for (j = k-1; j >= 0; j--) { result[i] = c[j]; i++; } } /* * 实现二个整数字符串的减法运算，即求(num1 - num2)的值 * 要求 num1 绝对值大于 num2 */ static void _sub(const char *num1, const char *num2, char *result) { int i, j, k, n1, n2, n; int len1, len2; /* 以 num1 符号作为结果的符号 */ int sig; int sta1, sta2; /* 借位标识 */ int car; char c[MAX_LEN] = {0}; sig = (*num1 == '-') ? -1 : 1; sta1 = (*num1 == '-') ? 1 : 0; sta2 = (*num2 == '-') ? 1 : 0; len1 = strlen(num1); len2 = strlen(num2); j = len2 - 1; k = 0; car = 0; /* * 对二整数自低位起进行逐位相减，结果小于 0 则借位再减，计算结果逐位存入临时数组 */ for (i = len1-1; i >= sta1; i--) { n1 = ctoi(num1[i]); n2 = (j >= sta2) ? (ctoi(num2[j])) : 0; j--; if (car == 1) { n1 = n1 - 1; car = 0; } if (n1 < n2) { n = n1 + 10 - n2; car = 1; } else n = n1 - n2;

高精度计算(C版PPT培训课件


C语言数据类型
总结词
C语言有多种数据类型，包括基本数据类型 和派生数据类型。
详细描述
基本数据类型包括整型（int）、字符型 （char）、浮点型（float、double）等。 派生数据类型包括数组、结构体、联合、枚 举等，允许用户自定义数据结构。
C语言运算符
总结词
C语言支持多种运算符，包括算术运算符、关系运算符、逻辑运算符等。
高精度计算(C语言版)培训课 件
目录
• 高精度计算概述 • C语言基础 • 高精度计算在C语言中的实现 • 高精度计算的应用实例 • 高精度计算的性能优化 • 高精度计算的发展趋势和展望
01
高精度计算概述
高精度计算的背景和意义
高精度计算在科学计算、金融、工程 等领域具有广泛的应用，能够解决大 规模数值计算问题，提高计算精度和 可靠性。
04
高精度计算的应用实例
大数分解质因数
总结词
通过高精度计算，能够快速准确地分解大数 的质因数，有助于解决一些数学问题。
详细描述
高精度计算可以处理大整数，利用高精度算 法，可以快速地分解大数的质因数。这对于 密码学、数论等领域的研究具有重要意义， 例如在加密算法、数论检验等方面有广泛应
用。
求解高精度方程
优化
在快速幂算法中，可以通过预计算和缓存部分中间结果来减少重复计算，提高算法效率。
矩阵乘法
01
矩阵乘法
矩阵乘法是一种基本的线性代数 运算，可以通过两个矩阵相乘得 到一个新的矩阵。
02
03
算法步骤
优化
首先将两个矩阵按照对应元素相 乘，然后将得到的值相加得到新 的矩阵的元素。
在矩阵乘法中，可以采用分块处 理和压缩存储等技术来提高算法 效率。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

i=1; while (i<=lena||i<=lenb) { if (a[i]<b[i]) { a[i]+=10; //不够减，那么向高位借1当10 a[i+1]--; } c[i]=a[i]-b[i]; //对应位相减 i++; } lenc=i; while ((c[lenc]==0)&&(lenc>1)) lenc--; //最高位的0不输出 for (i=lenc;i>=1;i--) cout<<c[i]; //输出结果 cout<<endl; return 0;
for (i=1;i<=lena;i++) { c[i]=(x*10+a[i])/b; x=(x*10+a[i])%b; } lenc=1; while (c[lenc]==0&&lenc<lena) lenc++; for (i=lenc;i<=lena;i++) cout<<c[i]; cout<<endl; return 0; }
}
【例3】高精度乘法。输入两个正整数，求它们的积。 【算法分析】 类似加法，可以用竖式求乘法。在做乘法运算时，同样 也有进位，同时对每一位进行乘法运算时，必须进行错位相加， 如图3、图4。 分析c数组下标的变化规律，可以写出如下关系式：ci = c’i +c”i +…由此可见，c i跟a[i]*b[j]乘积有关，跟上次的进位有关， 还跟原c i的值有关，分析下标规律，有c[i+j-1]= a[i]*b[j]+ x + c[i+j-1]; x=c[i+j-1]/10 ; c[i+j-1]%=10; 856 × 25 4280 1712 21400 图3 A3A2A1 × B2B1 C’4C’3 C’2 C’1 C”5C”4C”3C”2 C6C 5C4C 3C2C1 图4
#include<iostream> #include<cstring> #include<cstdio> using namespace std; int main() { char a1[100],c1[100]; int a[100],c[100],lena,i,x=0,lenc,b; memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); gets(a1); cin>>b; lena=strlen(a1); for (i=0;i<=lena-1;i++) a[i+1]=a1[i]-48;
பைடு நூலகம்
【例2】高精度减法。输入两个正整数，求它们的差。
【算法分析】 类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必 须比减数大，同时需要处理借位。高精度减法的参考程序： #include<iostream> #include<cstdio> #include<cstring> using namespace std; int main() { int a[256],b[256],c[256],lena,lenb,lenc,i; char n[256],n1[256],n2[256]; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); memset(c,0,sizeof(c));
while (lenc <=lena||lenc <=lenb) { c[lenc]=a[lenc]+b[lenc]+x; //两数相加 x=c[lenc]/10; c[lenc]%=10; lenc++; } c[lenc]=x; if (c[lenc]==0) lenc--; //处理最高进位 for (i=lenc;i>=1;i--) cout<<c[i]; //输出结果 cout<<endl; return 0; }
因此，算法描述如下： int c[100]; void add(int a[],int b[]) //a,b,c都为数组，分别存储被加数、加数、结果 { int i=1,x=0; //x是进位 while ((i<=a数组长度)||(i<=b数组的长度)) { c[i]=a[i]+b[i]+x; //第i位相加并加上次的进位 x=c[i]/10; //向高位进位 c[i]%=10; //存储第i位的值 i++; //位置下标变量 } }
//按位相除
//删除前导0
实质上，在做两个高精度数运算时候，存储高精度数的 数组元素可以不仅仅只保留一个数字，而采取保留多位数 （例如一个整型或长整型数据等），这样，在做运算（特别 是乘法运算）时，可以减少很多操作次数。例如图5就是采用 4位保存的除法运算，其他运算也类似。具体程序可以修改上 述例题予以解决，程序请读者完成。 示例：123456789 ÷45 = 1’ 2345’ 6789 ÷ 45 = 274’ 3484 ∵ 1 / 45 = 0 ， 1%45=1 ∴ 取12345 / 45 = 274 ∵ 12345 % 45 = 15 ∴ 取156789/45 = 3484 ∴ 答案为2743484, 余数为156789%45 = 9 图5
【例4】高精度除法。输入两个正整数，求它们的商 （做整除）。
【算法分析】 做除法时，每一次上商的值都在０～９，每次求得的余 数连接以后的若干位得到新的被除数，继续做除法。因此， 在做高精度除法时，要涉及到乘法运算和减法运算，还有移 位处理。当然，为了程序简洁，可以避免高精度除法，用0～ 9次循环减法取代得到商的值。这里，我们讨论一下高精度数 除以单精度数的结果，采取的方法是按位相除法。
【例5】高精除以高精，求它们的商和余数。 【算法分析】 高精除以低精是对被除数的每一位（这里 的“一位”包含前面的余数，以下都是如此） 都除以除数，而高精除以高精则是用减法模 拟除法，对被除数的每一位都减去除数，一 直减到当前位置的数字（包含前面的余数） 小于除数（由于每一位的数字小于10，所以 对于每一位最多进行10次计算）具体实现程 序如下：
printf("Input minuend:"); gets(n1); //输入被减数 printf("Input subtrahend:"); gets(n2); //输入减数 if (strlen(n1)<strlen(n2)||(strlen(n1)==strlen(n2)&&strcmp(n1,n2)<0)) //strcmp()为字符串比较函数，当n1==n2, 返回0; //n1>n2时，返回正整数；n1<n2时，返回负整数 { //处理被减数和减数，交换被减数和减数 strcpy(n,n1); //将n1数组的值完全赋值给n数组 strcpy(n1,n2); strcpy(n2,n); cout<<"-"; //交换了减数和被减数，结果为负数 } lena=strlen(n1); lenb=strlen(n2); for (i=0;i<=lena-1;i++) a[lena-i]=int(n1[i]-'0'); //被减数放入a数组 for (i=0;i<=lenb-1;i++) b[lenb-i]=int(n2[i]-'0'); //减数放入b数组
856 + 255 1111 图1
A3 A2 A1 + B3 B2 B1 C4 C3 C2 C1 图2
如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。 则上例有A[1]=6，A[2]=5， A[3]=8，B[1]=5，B[2]=5，B[3]=2，C[4]=1， C[3]=1，C[2]=1，C[1]=1，两数相加如图2所示。
for (i=1;i<=lena;i++) { x=0; //用于存放进位 for (j=1;j<=lenb;j++) //对乘数的每一位进行处理 { c[i+j-1]=a[i]*b[j]+x+c[i+j-1]; //当前乘积+上次乘积进位+原数 x=c[i+j-1]/10; c[i+j-1] %= 10; } c[i+lenb]=x; //进位 } lenc=lena+lenb; while (c[lenc]==0&&lenc>1) //删除前导0 lenc--; for (i=lenc;i>=1;i--) cout<<c[i]; cout<<endl; return 0; }
(2) 高精度数位数的确定 位数的确定：接收时往往是用字符串的，所以它的位数就等于字符串的长度。 (3) 进位,借位处理 加法进位：c[i]=a[i]+b[i]; if (c[i]>=10) { c[i]%=10; ++c[i+1]; } 减法借位：if (a[i]<b[i]) { --a[i+1]; a[i]+=10; } c[i]=a[i]-b[i]; 乘法进位：c[i+j-1]= a[i]*b[j] + x + c[i+j-1]; x = c[i+j-1]/10; c[i+j-1] %= 10; (4) 商和余数的求法 商和余数处理：视被除数和除数的位数情况进行处理.
第一章 高精度计算
利用计算机进行数值计算，有时会遇到这样的问题：有些计算要求 精度高，希望计算的数的位数可达几十位甚至几百位，虽然计算机的计 算精度也算较高了，但因受到硬件的限制，往往达不到实际问题所要求 的精度。我们可以利用程序设计的方法去实现这样的高精度计算。介绍 常用的几种高精度计算的方法。 高精度计算中需要处理好以下几个问题： (1)数据的接收方法和存贮方法 数据的接收和存贮：当输入的数很长时，可采用字符串方式输入， 这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取 出，存入数组中。另一种方法是直接用循环加数组方法输入数据。 void init(int a[]) //传入一个数组 { string s; cin>>s; //读入字符串s a[0]=s.length(); //用a[0]计算字符串s的位数 for(i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0'; //将数串s转换为数组a，并倒序存储 }另一种方法是直接用循环加数组方法输入数据。