高精度运算(C++)
万进制高精度运算（C++语言）
目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种，除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数）
主要的解题思想是利用在小学就曾学习过的坚式加减乘除法则，用程序语言实现存在的问题主要有如何存储高精度数的值，如何实现计算等问题。 一. 高精度数字的存储
我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry ）或借位（borrow ）导致高位增长或减少，因此我们定义一个整型数组（int bignum[maxlen]）从低位向高位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示）
高精度数 3（高位）
…… 7 9 4（低位）
int bignum[i]
n
……
2
1
显然，在C++语言中，int 类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。）
在实际编写程序代码过程中常作如下定义： const int base=10000; const int maxlen=1000+1; int bignum[maxlen];
说明：base 表示进制为万进制，maxlen 表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。 二. 各种运算的程序实现 （一）加法：
首先回顾一下小学中曾学习的坚式加法，见图一：
bignum1[] 9475 46 1243 bignum2[]
918 1324
341 carry
1 0 0 0 bignum_ans[]
1
393
1370
1584
图一 加法的计算过程
从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry 进行存储，程序实现的过程如图二所示：
图二 加法的实现过程
初始化
进位carry 赋初始值0，结果的位数为两个加数的最大位数。
当前位超过最高位了？
处理当前位和进位
N
Y
还有进位么？
N
结束
处理进位
Y
高精度加法程序代码（bignum1+bignum2→bignum_ans ）：
void addition(int *bignum1, int *bignum2, int *bignum_ans){ int carry=0; memset( bignum_ans, 0, sizeof(bignum_ans) ); *bignum_ans=*bignum1>*bignu2?*bignum1:*bignum2; for(int pos=1; pos<=*bignum_ans; pos++){ carry+=bignum1[pos]+bignum2[pos]; bignum_ans[pos]=carry%base; carry/=base; } while(carry){ bignum_ans[++*bignum_ans]=carry%base; carry/=base; } }
说明：函数中的数组是引用传递，传递的是数组的首元素的地址，可用指针来代替，当前指针所指向的为0元素，后面的代码相同。
有的同学可能提出，在加法运算中的进位不管进制是多少，进位只可能出现1，用while 循环没有意义，在这里说明一下，为了跟后面乘法中出现的代码相匹配才采用这种处理方法，实现代码的统一性。 （二）减法：
bignum1[] 132 9475 46 1243 bignum2[]
132 918 1324
341 borrow
0 1 0 0 bignum_ans[]
8556
8722
902
图三 减法的计算过程
图三表示出了减法的计算过程，与加法不同的地方是进位变成了借位，另外就是计算结果的位数可能会比被减数的位数少，因此在处理过程中要更要注意结果到底是多少位的。
其次，日常我们做减法时，如果被减数小于减数，我们是把两数反过来进行相减，在前面添加负号标识。因此，我们在编写减法子函数时是约定bignum1大于bignum2的，调用时首先判断两个高精度数的大小，然后根据两数的大小决定如何调用。减法的实现过程如图四所示：
图四 减法的实现过程
高精度数比较程序代码：
int bignumcmp( int *bignum1, int *bignum2 ){ if (*bignum1-*bignum2) return *bignum1-*bignum2; for (int pos=*bignum1; pos>0; pos--) if ( bignum1[pos]-bignum2[pos] ) return bignum1[pos]-bignum2[pos]; return 0; }
初始化
借位borrow 赋初始值0，结果的位数为被减数的位数。
当前位超过最高位了？
处理当前位和借位
N
Y
结果高位为0？
N
结束
结果位数减1
Y
说明：bignum1>bignum2返回正整数，bignum1＝＝bignum2返回0，bignum1＜bignum2返回负整数。 解释：首先进行两数的位数的比较，如果位数相同再从高位向低位比较。
高精度减法程序代码（bignum1-bignum2→bignum_ans ）：
void subtract( int *bignum1, int *bignum2, int *bignum_ans ){ int borrow=0; memset( bignum_ans, 0, sizeof(bignum_ans) ); *bignum_ans=*bignum1; for(int pos=1; pos<=*bignum_ans; pos++){ bignum_ans[pos]=bignum1[pos]-borrow-bignum2[pos]; if(bignum_ans[pos]<0){ bignum_ans[pos]+=base; borrow=1; }else{ borrow=0; } } while( !bignum_ans[*bignum_ans] ) --*bignum_ans; }
（三）乘法：
乘法的计算过程正如图五所示的从乘数的最低位起枚举每一位与被乘数相乘，累加到结果当中。高精度乘高精度实际是多次调用单精度数乘高精高数运算。
1 2 3 4 X 4 3 2 1 (1) 1 2 3 4 (2) 2 4 6 8 (3) 3 7 0 2 (4) 4 9 3 6
5
3
3
2
1
1
4
图五 乘法的计算过程
首先看一下单精度数乘高精度数的实现过程，如图六所示：
图六 单精度乘高精度实现过程
初始化
进位carry 赋初始值0，结果的位数被乘数的位数。
当前位超过最高位了？
处理当前位和进位
N
Y
还有进位么？
N
结束
处理进位
Y
单精度乘高精度程序代码（n*bignum→bignum_ans）：
void SingleMultiply(int n, int *bignum, int *bignum_ans){
int carry=0;
memset(bignum_ans, 0, sizeof(bignum_ans);
*bignum_ans=*bignum;
for(int pos=1; pos<=*bignum_ans; pos++){
carry+=n*bignum[pos];
bignum_ans[pos]=carry%base;
carry/=base;
}
while(carry){
bignum_ans[++*bignum_ans]=carry%base;
carry/=base;
}
}
高精度数乘高精度数，实质就是在单精度数乘高精度数的基础上枚举各个乘数位与被乘数相乘，累计到结果当中。其中乘数中的第J位与被乘数中的第I位相乘时，结果应该保存到结果的第I＋J－1位中，因为如果存在进位的问题结果的位数可能为乘数与被乘数的位数和，也可能为两者位数和减一，这一点也应该单独处理。过程就不再展示了，具体的请阅读下面的程序代码：
高精度乘高精度程序代码（bignum1*bignum2→bignum_ans）：
void BignumMultiply( int *bignum1, int *bignum2, int *bignum_ans){
int carry=0, i, j;
memset(bignum_ans, 0, sizeof(bignum_ans) );
for (j=1; j<=*bignum2; j++){
for(i=1; i<=*bignum1; i++){
bignum_ans[i+j-1]+=carry+bignum1[i]*bignum2[j];
carry=bignum_ans[i+j-1]/base;
bignum_ans[i+j-1]%=base;
}
i=j+*bignum1;
while(carry){
bignum_ans[i++]=carry%base;
carry/=base;
}
}
*bignum_ans=*bignum1+*bignum2;
while( !bignum_ans[*bignum_ans] ) --*bignum_ans;
}
（四）除法：
除法在高精度计算中是最为特殊的，在近几年联赛中并没有出现类似的题目，除法类的高精度题目会涉及到精度和循环节问题，在这里首先用表格分析两个例子：
例一：3除以8，结果为0.375
被除数 3 30 60 40
商0 . 3 7 5
余数 3 6 4 0
例二：45除以56，结果为0.803(571428)
被除数45 450 20 200 320 400 80 240 160 480
商0 . 8 0 3 5 7 1 4 2 8
余数45 2 20 32 40 8 24 16 48 32
在例一中展示的为能被除尽的情形，能被除尽的条件是余数为0，而在例二中56并不能除尽45，出
现571428这个循环节，出现循环节的条件是当前的余数曾经出现在前面求得的余数序列中。 直接模拟除法操作进行程序设计的过程如图七所示：
图七 高精度除法实现过程
根据上述处理过程编写代码如下： void divide(int x, int y){ int remainder[maxlen], quotient[maxlen], repeat_pos=-1, pos=0; quotient[0]=x/y; remainder[0]=x%y; while( remainder[pos] ){ for(int i=0; i 说明：maxlen 为指定的精度或最大的小数位数加一，根据程序需要而定义。 从上面的程序可以看出，在求得每一个余数后，都要到前面的余数序列中查找是否已存在，来判定是否出现循环节，这种方法即费时又浪费空间。有没有更好的方法来解决这个问题呢？ 我们从数学上的自然数找一下规律。任何一个自然数都可拆分为若干质数的幂的形式 （n=p 1K1*p 2K2…p n Kn ），在所有的质数中，只有2和5才能被除尽，其他的均出现循环节。我们是否可以从 初始化 商存储数组quotient[]清零，余数数组remainder[]清零。 余数为0？ 处理当前位 N Y 结束 输出整除值，存储余数 余数序列中出现过么？ 处理循环节 Y N 2和5上找出解决方法来呢？ 将被除数和除数转化为互质的两个数，从除数中统计出2和5的个数n2和n5，且一个2和一个5都仅产生一位小数，这些小数是肯定不出现在循环节中的。反过来说，在小数点后面，循环节前面小数的位数就是n2和n5中的较大者。如果求解出循环节前的小数以后，余数仍不为0，那就存在着循环节了，循环节的长度为再次得到的这个余数。 请看下面的代码： 小数点后循环节前的位数程序代码： int numBeforeRepeat(int x, int y){ int n2=0, n5=0; while(y%2==0){n2++; y/=2;} while(y%5==0){n5++; y/=5;} while(x%2==0){n2--; x/=2;} while(x%5==0){n5--; x/=2;} if(n2 return n2>0?n2:0; } 高精度除法程序代码： void divide(int x, int y){ int BeforeRepeat=numBeforeRepeat(x, y); cout< x%=y; if(x){ cout<<'.'; for(int i=0; i x*=10; cout< x%=y; } if(x){ cout<<'('; int remainder=x; do{ remainder*=10; cout< remainder%=y; }while(remainder != x); cout<<')'; } } cout< } 利用这种解法一方面省去了余数和商的存储空间，另一方面也无需再到余数序列中查找余数是否出现过，即节省空间，又提高了程序的执行效率。所以遇到高精度除法问题时，可以优选第二种解法。 三. 万进制高精度数的输出问题： 采用万进制来进行高精的加、减、乘三种运算，虽然提高了程序的执行效率，但在输出时却带来了问题，如在加法示例中的结果从高位到低位分别为1，393，1370，1584，如果我们仍按照平常的输出一样直接输出时，结果为139313701584，但我们定义万进制时明确过每一位是占十进制的四位，393这一位应该输出0393而不是393。因此我们在输出时应首先输出最高位（因最高位前面是不补0的），然后再输出其他位，如果不足四位，用0补充。 万进制输出程序代码： void printbignum(int *n){ int *p=*n+n; cout<<*p--; cout.fill('0'); //定义填充字符'0' while(p>n){ cout.width(4); cout<<*p--; } cout< } 至此，有关万进制的相关内容已全部介绍完毕，在本文中的示例代码仍可根据个人的习惯进行精简，在熟练使用以后，在解题的过程中，就不需要再为如何解决高精度问题浪费宝贵的时间啦。相关练习题可参考“编程实战”中的高精度专项练习题。 附一：C＋＋语言输出控制语句： cout.fill(char ch) 设置输出留空位置的填充字符（作用于所有的输出）只调用一次 cout.width(int n) 设置输出域的宽度（只作用于下一次输出）每次都要调用 附二：相关英文单词 carry['k?r?]: 进位borrow['b?r??]: 借位addition[?'di??n]: 加subtra ct[s?b'tr?kt]: 减multiply['m?lt?pla?]: 乘divide[di'vaid]: 除 quotient['kw?u??nt]: 商remainder[r?'me?nd?(r)]: 余数decimal['des?ml]: 小数 附三：编程实战URL https://www.sodocs.net/doc/287706107.html,/bbs/forumdisplay.php?fid=163 关于圆周率的计算 祖冲之在数学方面的突出贡献是关于圆周率的计算，确定了相当精确的圆周率值。中国古代最初采用的圆周率是“周三径一”，也就是说，π＝3。这个数值与当时文化发达的其他国家所用的圆周率相同。但这个数值非常粗疏，用它计算会造成很大的误差。随着生产和科学的发展，π＝3 就越来越不能满足精确计算的要求。因此，中外数学家都开始探索圆周率的算法和推求比较精确的圆周率值。在中国，据公元一世纪初制造的新莽嘉量斛（亦称律嘉量斛，王莽铜斛，是一种圆柱形标准量器，现存）推算，它所取的圆周率是3.1547 。二世纪初，东汉天文学家张衡在《灵宪》中取用π＝≈3.1466，又在球体积计算中取用π≈3.1622。三国时东吴天文学家王蕃在浑仪论说中取用π≈3.1556。以上这些圆周率近似值，比起古率“周三径一”，精确度有所提高，其中π＝ 10还是世界上最早的记录。但这些数值大多是经验结果，并没有可靠的理论依据。 在这方面最先取得突破性进展的是魏晋之际的数学家刘徽，他在《九章算术注》中创立了“割圆术”，为计算圆周率建立起相当严密的理论和完善的算法。他所得到的圆周率值π＝3.14 与π＝＝3.1416，都很精确，在当时世界上是很先进的，至今仍在经常使用。继刘徽之后，祖冲之则将圆周率推算到更加精确的程度。据《隋书·律历志》记载，祖冲之确定了π的不足近似值 3.1415926 和过剩近似值 3.1415927，π的真值在这两个近似值之间，即 3.1415926＜π＜3.1415927 精确到小数 7 位。这是当时世界上最先进的数学成果，直到约一千年后，才为 15 世纪中亚数学家阿尔·卡西（Al—? kash1）和16世纪法国数学家韦达（F.Vièta，1540—1603）所超过。 关于他得到这两个数值的方法，史无明载，一般认为是基于刘徽割圆术。通过现代计算验证，如果按照割圆术计算，要得到小数 7 位准确的圆周率值，必须求出圆内接正12288 边形的边长和 24576边形的面积，这样，就要对9位数进行上百次加减乘除和开方运算，还要选择适当的有效数字，保证准确的误差范围。对于用算筹计算的古代数学家来说，这绝不是一件轻而易举的事情，只有掌握纯熟的理论和技巧，并具备踏踏实实和一丝不苟的研究精神，才能取得这样的杰出成就。祖冲之的这项记录在中国也保持了一千多年。 中国古代数学家和天文学家还往往用分数表示常量的近似值。为此，祖冲之确定了π的两个分数形式的近似值：约率π＝22/7≈3.14 ，密率π＝355/113 ≈3.1415929。这两个数值都是π的渐近分数。刘宋天文学家何承天及古希腊阿基米德等都已用到过。密率355/113 是π的分母小于10000的最佳近似分数，则为祖冲之首创。关于密率355/113是如何得到的，今人有“调日法”术，连分数法，解同余式或不定方程，割圆术等种种推测，迄今尚无定论。在欧洲，π＝ 355/113 是16世纪由德国数学家奥托（V.Otto，1550（？）—1605）和荷兰工程师安托尼兹（A.Anthonisz，1527—1607）分别得到，后通称“安托尼兹率”，但这已是祖冲之以后一千多年的事情了。自从我国古代灿烂的科学文化逐渐得到世界公认以来，一些学者就建议把π＝ 355 称为“祖率”，以纪念祖冲之的杰出贡献。 关于球的体积公式及其证明： 祖冲之的另一项重要数学成就是关于球的体积公式及其证明。各种几何体的体积计算是古代几何学中的基本内容。《九章算术》商功章已经正确地解决了 运算符重载基础概念练习题 1、下列运算符中, （）运算符在C++中不能重载。 A = B () C :: D delete 2、下列运算符中, （）运算符在C++中不能重载。 A ?: B [] C new D && 3、下列关于C++运算符函数的返回类型的描述中,错误的是（）。 A 可以是类类型 B 可以是int类型 C 可以是void类型 D 可以是float类型 4、下列运算符不能用友元函数重载的是（）。 A + B = C * D << 5、在重载运算符函数时,下面（）运算符必须重载为类成员函数形式。 A + B - C ++ D -> 6、下列关于运算符重载的描述中,正确的是（）。 A 运算符重载可以改变运算符的操作数的个数 B 运算符重载可以改变优先级 C 运算符重载可以改变结合性 D 运算符重载不可以改变语法结构 7、友元运算符obj>obj2被C++编译器解释为（）。 A operator>(obj1,obj2) B >(obj1,obj2) C obj2.operator>(obj1) D obj1.oprator>(obj2) 8、在表达式x+y*z中，+是作为成员函数重载的运算符，*是作为非成员函数重载的运算符。下列叙述中正确的是（）。 A operator+有两个参数，operator*有两个参数 B operator+有两个参数，operator*有一个参数 C operator+有一个参数，operator*有两个参数 D operator+有一个参数，operator*有一个参数 9、重载赋值操作符时,应声明为（）函数。 A 友元 B 虚 C 成员 D 多态 10、在一个类中可以对一个操作符进行（）重载。 A 1种 B 2种以下 C 3种以下 D 多种 11、在重载一个运算符时，其参数表中没有任何参数，这表明该运算符是（）。 高精度计算 由于计算机具有运算速度快，计算精度高的特点，许多过去由人来完成的烦琐、复杂的数学计算，现在都可以由计算机来代替。 计算机计算结果的精度，通常要受到计算机硬件环境的限制。例如，pascal 要计算的数字超过19位，计算机将按浮点形式输出；另一方面，计算机又有数的表示范围的限制，在一般的微型计算机上，实数的表示范围为l0-38 -l038。例如，在计算N!时，当N=21时计算结果就超过了这个范围，无法计算了。这是由计算机的硬件性质决定的，但是，我们可以通过程序设计的方法进行高精度计算（多位数计算）。 学习重点 1、掌握高精度加、减、乘、除法。 3、理解高精度除法运算中被除数、除数、商和余数之间的关系。 4、能编写相应的程序，解决生活中高精度问题。 学习过程 一、高精度计算的基本方法 用free pascal程序进行高精度计算，首先要处理好以下几个基本问题：【数据的输入与保存】 （1）一般采用字符串变量存储数据，然后用length函数测量字符串长度确定其位数。 （2）分离各位数位上的数字 分离各数位上的数通常采用正向存储的方法。以“163848192”为例，见下表：A[9] A[8] A[7] A[6] A[5] A[4] A[3] A[2] A[1] 1 6 3 8 4 8 1 9 2 基本原理是A[1]存放个位上的数字，A[2]存放十位上的数字，……依此类推。即下标小的元素存低位上的数字，下标大的元素存高位上的数字，这叫“下标与位权一致”原则。 【计算结果位数的确定】 （1）高精度加法：和的位数为两个加数中较大数的位数+1。 （2）高精度减法：差的位数为被减数和减数中较大数的位数。 （3）高精度乘法：积的位数为两个相乘的数的位数之和。 （4）高精度除法：商的位数按题目的要求确定。 【计算顺序与结果的输出】 高精度加、减、乘法，都是从低位到高位算起，而除法相反。输出结果都是从高位到低位的顺序，注意：高位上的零不输出（整数部分是零除外）。 高精度加法 【参考程序】 var a,b:array[1..10000] of byte; i,w,la,lb:integer; 常用数学公式大全 1、每份数×份数＝总数总数÷每份数＝份数总数÷份数＝每份数 2、1倍数×倍数＝几倍数几倍数÷1倍数＝倍数几倍数÷倍数＝1倍数 3、速度×时间＝路程路程÷速度＝时间路程÷时间＝速度 4、单价×数量＝总价总价÷单价＝数量总价÷数量＝单价 5、工作效率×工作时间＝工作总量工作总量÷工作效率＝工作时间工作总量÷工作时间＝工作效率 6、加数＋加数＝和和－一个加数＝另一个加数 7、被减数－减数＝差被减数－差＝减数差＋减数＝被减数 8、因数×因数＝积积÷一个因数＝另一个因数 9、被除数÷除数＝商被除数÷商＝除数商×除数＝被除数 小学数学图形计算公式 1、正方形C周长S面积a边长周长＝边长×4C=4a面积=边长×边长S=a×a 2、正方体V:体积a:棱长表面积=棱长×棱长×6S表=a×a×6体积=棱长×棱长×棱长V=a×a×a 3、长方形 C周长S面积a边长 周长=(长+宽)×2C=2(a+b) 面积=长×宽S=ab 4、长方体 V:体积s:面积a:长b:宽h:高 (1)表面积(长×宽+长×高+宽×高)×2S=2(ab+ah+bh) (2)体积=长×宽×高V=abh 5三角形s面积a底h高 面积=底×高÷2s=ah÷2 三角形高=面积×2÷底 三角形底=面积×2÷高 6平行四边形 s面积a底h高 面积=底×高s=ah 7梯形 s面积a上底b下底h高 面积=(上底+下底)×高÷2s=(a+b)×h÷2 8圆形 S面积C周长∏d=直径r=半径 (1)周长=直径×∏=2×∏×半径C=∏d=2∏r (2)面积=半径×半径×∏ 9圆柱体 v:体积h:高s;底面积r:底面半径c:底面周长 (1)侧面积=底面周长×高 (2)表面积=侧面积+底面积×2 (3)体积=底面积×高 （4）体积＝侧面积÷2×半径 10圆锥体 v:体积h:高s;底面积r:底面半径 体积=底面积×高÷3 总数÷总份数＝平均数 运算符重载 一．单项选择题 1．下列运算符中，运算符在C++中不能重载。 A．?： B．+ C． D．<= 解：C++中不能被重载的运算符有：·，一，：：，?：。本题答案为A。 2．下列运算符中，运算符在C++中不能重载。 A．&& B．[] C．：： D．new 解：c++中不能被重载的运算符有：·，·+，：：，?：。本题答案为c。 3．下列关于运算符重载的描述中，是正确的。 A．运算符重载可以改变操作数的个数 B．运算符重载可以改变优先级 C．运算符重载可以改变结合性 D．运算符重载不可以改变语法结构 解：运算符重载不能改变操作数的个数、运算符的优先级、运算符的结合性和运算程的语法结构。本题答案为D。 4．友元运算符objl>obj2被C++编译器解释为。 A．operator>(objl，obj2) B．>(obj1，obj2) C．obj2．operator：>(obj1) D．objl．operator>(obj2) 解：重载为友元函数的运算符的调用形式如下： operator<运算符>(<参数1>，<参数2>) 等价于：<参数1><运算符><参数2> 本题答案为A。 5．现需要对list类对象使用的逻辑运算符“==”重载，以下函数声明是正确的。 A、list & list：：operator==(const list &a)； B、list list：：operator==(const list &a)； C、bool & list：：operator==(const list &a)； D、bool list：：operator==(const list &a)； 6. 以下类中分别说明了“+=”和“++”运算符重载函数的原型。如果主函数中有定义： fun m,c,d;，那么，执行语句c=m++; 时，编译器把m++解释为： (33) A) c.operator++(m); B) m=operator++(m); C) m.operator++(m); D) operator++(m); class fun { public: .. .. .. fun operator +=(fun ); friend fun operator ++(fun &,int); }; 答案：D 7. 在第33题中，当执行语句d+=m; 时，C++编译器对语句作如下解释： (34) A. d=operator+=(m); B. m=operator+=(d); C. d.operator+=(m); D. m.operator+=(d); 答案：C 8. 设有以下类定义，其中说明了“+”运算符重载函数的原型。这是一个友元函数，当类 C语言课程设计-高精度数计算 源代码： #include { printf("%d",Numa[i]); } printf("\n"); printf("随机产生的加数b为：\n"); for(i=0;i 圆周率计算公式Revised on November 25, 2020 12 π= 22 π= 32 π= 42 π= 52 π= 62 π= 72 π= 82 π= 92 π= 102 π=314 112 π= 122 π= 132 π= 142 π= 152 π= 162 π= 172 π= 182 π= 192 π= 202 π=1256 212 π= 222 π= 232 π= 242 π= 252 π= 262 π= 272 π= 282 π= 292 π= 302 π=2826 312 π= 322 π= 332 π= 342 π= 352 π= 362 π= 372 π= 382 π= 392 π= 402 π=5024 412 π= 422 π= 432 π= 442 π= 452 π= 462 π= 472 π= 482 π= 492 π= 502 π=7850 512 π= 522 π= 532 π= 542 π= 552 π= 562 π= 572 π= 582 π= 592 π= 602 π=11304 612 π= 622 π= 632 π= 642 π= 652 π= 662 π= 672 π= 682 π= 692 π= 702 π=15386 712 π= 722 π= 732 π= 742 π= 752 π= 762 π= 772 π= 782 π= 792 π= 802 π= 812 π= 822 π= 832 π= 842 π= 852 π= 862 π= 872 π= 882 π= 892 π= 902 π=25434 912 π= 922 π= 932 π= 942 π= 952 π= 962 π= 972 π= 982 π= 992 π= 1002 π=31400 12~1002 12=1 22=4 32=9 42=16 52=25 62=36 72=49 82=64 92=81 102=100 112=121 122=144 132=169 142=196 152=225 162=256 172=289 182=324 192=361 202=400 212=441 222=484 232=529 242=576 252=625 262=676 272=729 282=784 292=841 302=900 312=961 322=1024 332=1089 342=1156 352=1225 362=1296 372=1396 382=1444 392=1521 402=1600 412=1681 422=1764 432=1849 442=1936 452=2025 圆周率的计算方法 古人计算圆周率，一般是用割圆法。即用圆的内接或外切正多边形来逼近圆的周长。Archimedes用正96边形得到圆周率小数点后3位的精度；刘徽用正3072边形得到5位精度；Ludolph Van Ceulen用正262边形得到了35位精度。这种基于几何的算法计算量大，速度慢，吃力不讨好。随着数学的发展，数学家们在进行数学研究时有意无意地发现了许多计算圆周率的公式。下面挑选一些经典的常用公式加以介绍。除了这些经典公式外，还有很多其他公式和由这些经典公式衍生出来的公式，就不一一列举了。 ?Machin公式 这个公式由英国天文学教授John Machin于1706年发现。他利用这个公式计算到了100位的圆周率。Machin公式每计算一项可以得到1.4位的十进制精度。因为它的计算过程中被乘数和被除数都不大于长整数，所以可以很容易地在计算机上编程实现。 Machin.c 源程序 还有很多类似于Machin公式的反正切公式。在所有这些公式中，Machin公式似乎是最快的了。虽然如此，如果要计算更多的位数，比如几千万位，Machin 公式就力不从心了。下面介绍的算法，在PC机上计算大约一天时间，就可以得到圆周率的过亿位的精度。这些算法用程序实现起来比较复杂。因为计算过程中涉及两个大数的乘除运算，要用FFT(Fast Fourier Transform)算法。FFT可以将两个大数的乘除运算时间由O(n2)缩短为O(nlog(n))。 关于FFT算法的具体实现和源程序，请参考Xavier Gourdon的主页 ?Ramanujan公式 1914年，印度数学家Srinivasa Ramanujan在他的论文里发表了一系列共14条圆周率的计算公式，这是其中之一。这个公式每计算一项可以得到8位的十进制精度。1985年Gosper用这个公式计算到了圆周率的17,500,000位。 书籍是人类知识的总结,书籍是全世界的营养品。——莎士比亚 万进制高精度运算（C++语言） 目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种，除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数） 主要的解题思想是利用在小学就曾学习过的竖式加减乘除法则，用程序语言实现存在的问题主要有如何存储高精度数的值，如何实现计算等问题。 一. 高精度数字的存储 我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry ）或借位（borrow ）导致高位增长或减少，因此我们定义一个整型数组（int bignum[maxlen]）从低位向高位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示） 高精度数 3（高位） …… 7 9 4（低位） int bignum[i] n …… 2 1 显然，在C++语言中，int 类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。） 在实际编写程序代码过程中常作如下定义： const int base=10000; const int maxlen=1000+1; int bignum[maxlen]; 说明：base 表示进制为万进制，maxlen 表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。 二. 各种运算的程序实现 （一）加法： 首先回顾一下小学中曾学习的竖式加法，见图一： bignum1[] 9475 46 1243 bignum2[] 918 1324 341 carry 1 0 0 0 bignum_ans[] 1 393 1370 1584 图一 加法的计算过程 从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry 进行存储，程序实现的过程如图二所示： 初始化 进位carry 赋初始值0，结果的位数为两个加数的最大位数。 当前位超过最高位了？ 处理当前位和进位 N Y 还有进位么？ N 结束 处理进位 Y 圆周率π的计算历程及意义 李毫伟 数学科学学院数学与应用数学学号:080412047 指导老师:王众杰 摘要: 圆周率π这个数,从有文字记载的历史开始,就引起了人们的兴趣.作为一个非常重要的常数,圆周率π最早是出于解决有关圆的计算问题.仅凭这一点,求出它的尽量准确的近似值,就是一个极其迫切的问题了.几千年来作为数学家们的奋斗目标,古今中外的数学家为此献出了自己的智慧和劳动.回顾历史,人类对π的认识过程,反映了数学和计算技术发展情形的一个侧面.π的研究在一定程度上反映这个地区或时代的数学水平. 关键词: 圆周率; 几何法; 分析法; 程序 1、实验时期 通过实验对π值进行估算,这是计算π的第一个阶段.这种对π值的估算基本上都是以观察或实验为根据,是基于对一个圆的周长和直径的实际测量而得出来 π=这个数据,最早见于有文字记载的基督教《圣经》的.在古代,实际上长期使用3 中的章节,其上取圆周率π为3.这一段描述的事大约发生在公元前950年前后.其他如巴比伦、印度、中国等也长期使用3这个粗略而简单实用的数值.在我国刘徽之前“圆径一而周三”曾广泛流传.我国第一部《周髀算经》中,就记载有“圆周三径一”这一结论.在我国,木工师傅有两句从古流传下来的口诀:叫做:“周三径一,方五斜七,”意思是说,直径为1的圆,周长大约是3,边长为5的正方形,对角线之长约为7,这正反应了人们早期对π和2这两个无理数的粗略估计.东汉时期,官方还明文规定圆周率取3为计算圆的面积的标准,后人称之为古率. 早期的人们还使用了其它的粗糙方法.如古埃及、古希腊人曾用谷粒摆在圆形上,以数粒数与方形对比的方法取得数值.或用匀重木板锯成圆形和方形以秤量对比取值……由此,得到圆周率π的稍好些的值.如古埃及人应用了约四千年的()≈2984 3.1605.在印度,公元前六世纪,曾取π≈10≈3.162.在我国东、西汉之 运算符重载 【学习要点】 1．理解多态性的概念和实现。 ①编译时多态性是通过函数重载、运算符重载实现的。 ②运行时多态性是通过类的继承+虚函数实现的。 2．掌握运算符重载的作用和规则。 ①在C++中可根据需要对运算符赋予多种含义，以配合用户自定义的类类型。 ②运算符重载是通过定义运算符重载函数 operator运算符(实现的。 3．掌握双目、单目运算符重载为成员函数的方法。 4．掌握双目、单目运算符重载为友元函数的方法。 5．掌握重载为成员函数、重载为友元函数的区别： ①友元函数与成员函数不同，它不是类的成员，没有this指针。 ②运算符 =、（）、[ ]、—> 不能重载为友元函数，只能重载为成员函数。 ③运算符插入”<<”、提取”>>” 只能重载为友元函数。 6．掌握几个特殊运算符“++”、“--”、“=”、“[ ]”、“<<”、“>>”的重载。 7．掌握类型转换函数。 8．掌握自定义字符串类。 9．掌握C++标准库中的string类的使用。 ------------------------------------------------------------------------------------------------------------------------------------------------ 【例题分析】 1．下面程序中的错误有几处? #include class C { int x , y ; public: C ( { } C ( int a , int b : x( a , y( b { } C operator@ ( C a { C temp ; temp.x=x+a.x ; temp.y=y+a.y ; return temp ; } int operator# ( C a { return ( x * y ; } friend C operator= ( C a { x=a.x ; y=b.y ; return *this ; } void show( { cout << "x=" << x <<"\ty=" << y << endl ; } }; void main( { C a( 2 , 3 , b( 2 , 3 , c ; (a+b.show( ; c=a ; c.show( ; } 【答案】3 【解析】 ①函数C operator@ (C a ; 运算符重载是允许用户重新定义运算符的含义，但此运算符必须是C++系统预定义的，而“@”不是C++预定义的运算符，应换成“+”。 ②函数int operator# (C a ; 符号#不允许重载，应换成“*”，另外形参C a也不需要。 ③函数friend C operator = (C a ; 赋值运算符“=”只能重载为成员函数，不能重载为友元函数，故将friend删去。其次，返回类型最好是 C & 。 2．编写程序：存放在my Vector.cpp文件中，包含内容如下： ①定义向量类Vector。私有成员数据有：存放向量在三条坐标轴上投影值的x、y、z。公有成员函数有：可设置向量中x、y、z值的成员函数void set( float a=0, float b=0, float c=0 ；可输出向量中x、y、z值的成员函数void show( ；构造函数Vector ( float a=0 , float b=0 , float c=0 ；构造函数Vector( float v[ 3 ] ；两个赋值运算符“=”重载成员函数Vector & operator=( Vector v 、Vector & operator=( float v[ 3 ] 。 ②将实现两个向量之间加、减、乘运算的三个独立函数声明为Vector类的友元函数： 运算符重载复习题1 1.概念填空题 1.1运算符重载是对已有的运算符赋予 含义，使同一个运算符在作 用于 对象时导致不同的行为。运算符重载的实质是 ，是类的 特征。 1.2可以定义一种特殊的类型转换函数，将类的对象转换成基本数据类 型的数据。但是这种类型转换函数只能定义为一个类的 函数而不 能定义为类的友元函数。类类型转换函数既没有 ，也不显式给出 。类类型函数中必须有 的语句返回函数值。一个类可以定义 类类型转换函数。 1.3运算符重载时其函数名由构成。成员函数重载双目运算符时,左操 作数是,右操作数是。 2.简答题 2.2简述运算符重载的规则。 2.2简述重载单目运算符++、--，前置和后置时的差别。 2.3 C++中重运算符是否都可以重载?是否都可以重载成类的成员函数? 是否都可以重载成类的友元函数? 2.4 构造函数作为类型转换函数的条件是什么。 3．选择题 3.1在下列运算符中,不能重载的是( ) A.！ B. sizeof C. new D. delete 3.2 不能用友员函数重载的是( )。 A.= B.== C.<= D.++ 3.3下列函数中,不能重载运算符的函数是( )。 A.成员函数 B.构造函数 C.普通函数 D.友员函数 3.4如果表达式++i*k时中的”++”和”*”都是重载的友元运算符，则 采用运算符函数调用格式，该表达式还可表示为（ ）。 A．operator*(i.operator++(),k) B．operator* (operator++(i),k) C．i.operator++().operator*(k) D．k.operator* (operator++(i)) 3.5已知在一个类体中包含如下函数原型：VOLUME operator-(VOLUME)const；下列关于这个函数的叙述中，错误的是（ ）。 A．这是运算符-的重载运算符函数 B．这个函数所重载的运算符是一个一元运算符 C．这是一个成员函数 D．这个函数不改变数据成员的值 3.6在表达式x＋y*z中，+是作为成员函数重载的运算符，*是作为非成员函数重载的运算符。下列叙述中正确的是（ ）。 A．operator+有两个参数，operator*有两个参数 B．operator+有两个参数，operator*有一个参数 C．operator+有一个参数，operator*有两个参数 D．operator+有一个参数，operator*有一个参数 4.写出下列程序运行结果 4.1#include 怎样计算 姓名： 学号 班级：数学与应用数学4班 实验报告 实验目的：自己尝试利用Mathematica软件计算的近似值，并学会计算的近似值的方法。 实验环境：Mathematica软件 实验基本理论和方法： 方法一：数值积分法（单位圆的面积是，只要计算出单位圆的面积也就计算出了的值） 其具体内容是：以单位圆的圆心为原点建立直角坐标系，则单位圆在第一象限内的部分G是一个扇形， 由曲线（）及坐标轴围成，它的面积是，算出了S的近似值，它的4倍就是的近似值。而怎样计算扇形G的面积S的近似值呢?如图 图一 扇形G中，作平行于y轴的直线将x轴上的区间[0，1]（也就是扇形在x轴上的半径）分成n等份（n=20），相应的将扇形G分成n个同样宽度1/n的部分（）。每部分是一个曲边梯形：它的左方、右方的边界是相互平行的直线段，类似于梯形的两底；上方边界是一段曲线，因此称为曲边梯形。如果n很大，每个曲边梯形的上边界可以近似的看成直线段，从而将近似的看成一个梯形来计算它的面积；梯形的高（也就是它的宽度）h=1/n，两条底边的长分别是和，于是这个梯形面积可以作为曲边梯形面积的近似值。所有这些梯形面积的和T就可以作为扇形面积S的近似值： n越大，计算出来的梯形面积之和T就越接近扇形面积S，而4T就越接近的准确值。 方法二：泰勒级数法 其具体内容是：利用反正切函数的泰勒级数 计算。 方法三：蒙特卡罗法 其具体内容是：单位正方形的面积=1，只要能够求出扇形G 的面积S在正方形的面积中所占的比例，就能立即得到S，从而得到的值。而求扇形面积在正方形面积中所占的比例k的值，方法是在正方形中随机地投入很多点，使所投的每个点落在正方形中每一个位置的机会均等，看其中有多少个点落在扇形内。将落在扇形内的点的个数m与所投的点的总数n的比可以作为k的近似值。能够产生在区间[0，1]内均匀分布的随机数，在Mathematica中语句是 Random[ ] 产生两个这样的随机数x，y，则以（x，y）为坐标的点就是单位正方形内的一点P，它落在正方形内每一个位置的机会均等。P落在扇形内的充分必要条件是。这样利用随机数来解决数学问题的方法叫蒙特卡罗法。 实验内容、步骤及其结果分析： 问题1：在方法一中，取n=1000，通过计算图一中扇形面积计算的的近似值。 分析：图一中的扇形面积S实际上就是定积分。 与有关的定积分很多，比如的定积分 万进制高精度运算（C++语言） 目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种，除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数） 主要的解题思想是利用在小学就曾学习过的坚式加减乘除法则，用程序语言实现存在的问题主要有如何存储高精度数的值，如何实现计算等问题。 一. 高精度数字的存储 我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry ）或借位（borrow ）导致高位增长或减少，因此我们定义一个整型数组（int bignum[maxlen]）从低位向高位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示） 高精度数 3（高位） …… 7 9 4（低位） int bignum[i] n …… 2 1 显然，在C++语言中，int 类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。） 在实际编写程序代码过程中常作如下定义： const int base=10000; const int maxlen=1000+1; int bignum[maxlen]; 说明：base 表示进制为万进制，maxlen 表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。 二. 各种运算的程序实现 （一）加法： 首先回顾一下小学中曾学习的坚式加法，见图一： bignum1[] 9475 46 1243 bignum2[] 918 1324 341 carry 1 0 0 0 bignum_ans[] 1 393 1370 1584 图一 加法的计算过程 从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry 进行存储，程序实现的过程如图二所示： 图二 加法的实现过程 初始化 进位carry 赋初始值0，结果的位数为两个加数的最大位数。 当前位超过最高位了？ 处理当前位和进位 N Y 还有进位么？ N 结束 处理进位 Y 圆周率的来源和2000位 “圆周率”即圆的周长与其直径之间的比率。关于它的计算问题，历 来是中外数学家极感兴趣、孜孜以求的问题。德国的一位数学家曾经说过：“历史上一个国家所算得的圆周率的准确程度，可以作为衡量这个国家当时数学发展的一个标志。”我国古代在圆周率的计算方面长期领先于世界水平，这应当归功于魏晋时期数学家刘徽所创立的新方法一一“割圆术”。 所谓“割圆术”，是用圆内接正多边形的周长去无限逼近圆周并以此求取圆周率的方法。这个方法，是刘徽在批判总结了数学史上各种旧的计算方法之后，经过深思熟虑才创造出来的一种崭新的方法。 中国古代从先秦时期开始，一直是取“周三径一”（即）的数值来进行有关圆的计算。但用这个数值进行计算的结果，往往误差很大。正如刘徽所说，用“周三径一”计算出来的圆周长，实际上不是圆的周长而是圆内接正六边形的周长，其数值要比实际的圆周长小得多。东汉的张衡不满足于这个结果，他从研究圆与它的外切正方形的关系着手得到圆周率。这个数值比“周三径一”要好些，但刘徽认为其计算出来的圆周长必然要大于实际的圆周长，也不精确。刘徽以极限思想为指导，提出用“割圆术”来求圆周率，既大胆创新，又严密论证, 从而为圆周率的计算指出了一条科学的道路。 在刘徽看来，既然用“周三径一”计算出来的圆周长实际上是圆内接正六边形的周长，与圆周长相差很多；那么我们可以在圆内接正六边形把圆周等分为六条弧的基础上，再继续等分，把每段弧再分割为二， 做出一个圆内接正十二边形，这个正十二边形的周长不就要比正六边形的周长更接近圆周了吗？如果把圆周再继续分割，做成一个圆内接正二十四边形，那么这个正二十四边形的周长必然又比正十二边形的周长更接近圆周。这就表明，越是把圆周分割得细，误差就越少，其内接正多边形的周长就越是接近圆周。如此不断地分割下去，一直到圆周无法再分割为止，也就是到了圆内接正多边形的边数无限多的时候，它的周长就与圆周“合体”而完全一致了。 按照这样的思路，刘徽把圆内接正多边形的面积一直算到了正3072 边形，并由此而求得了圆周率为3.14和3.1416这两个近似数值。这个结果是当时世界上圆周率计算的最精确的数据。刘徽对自己创造的这个“割圆术”新方法非常自信，把它推广到有关圆形计算的各个方面，从而使汉代以来的数学发展大大向前推进了一步。 以后到了南北朝时期，祖冲之在刘徽的这一基础上继续努力，终于求得了圆周率：精确到了小数点以后的第七位。在西方，这个成绩是由法国数学家韦达于1593年取得的，比祖冲之要晚了一千一百多年。祖冲之还求得了圆周率的两个分数值，一个是“约率”22/7 ,另一个 是“密率” 355/113 ,其中355/113 这个值，在西方是由德国的奥托和荷兰的安东尼兹在16世纪末才得到的，都比祖冲之晚了一千一一百年。刘徽所创立的“割圆术”新方法对中国古代数学发展的重大贡献，历史是永远不会忘记的。 答应了大宝，教她点东西，才知道自己才疏学浅，不知道教她什么。偶尔看到巧计圆周率，就截图下来和她一起背，呵呵还真的有效，花三 高精度算法 #include 历史上一些圆周率计算方法 从古至今，计算圆周率一直挑战着人类的探索能力极限，人们为此提出了效率越来越高的计算方法。可是，你知道多少圆周率的另类计算法呢？今天我们就来和大家分享一下，历史上出现的几个最奇怪的圆周率计算法。 功亏一篑的人肉计算记录 电脑计算圆周率屡破记录，但新时代对机器的信任和依赖使得人们已经主动放弃了自己手动演算的能力。为了打破手算圆周率的记录，让人们重新拾回对自己演算能力的信心，澳大利亚一个 16 岁的小伙子决定人肉计算圆周率的前 100 位。他挑选了圆周率的一个广义连分数公式，准备了 2000 张草稿纸，并精心地规划了一番。从此开始，他总是把这厚厚的一叠草稿纸带在身边。不管是在家还是在学校，他都端坐在草稿纸面前，不停地挥动着手中的笔。他很快成为了学校的一道风景线——无视上下课铃声，雷打不动地做着枯燥的加法和除法。 2 年后的某堂历史课上，就在他书写最后一个除法竖式时，悲剧发生了：新来的代课老师发现他有小动作，点名叫他起来回答问题。当他无视老师继续埋头苦算时，不明真相的代课老师一怒之下抢过草稿纸，并撕成了无数碎片。 最辗转的计算方法 在一本统计学读物中，为了告诉读者在日常生活中数字无处不在，作者统计出了自家厕所的卷筒纸平均每多少天换一次，乘以平均每天的大便次数，乘以平均每次大便需要扯下来的卫生纸张数，乘以每一截卫生纸的长度，乘以把一长截卫生纸对折 10 次的厚度，除以 1024 ，除以自动切割机从卷筒纸最外层切到最里层（厚度为 R-r ）的时间，除以切完整个卷筒纸（剩余的 R+r ）还需要的时间，除以切割机移动的速度，得出了圆周率近似值。 作者顺便指出，若读者愿意，还可以在末尾乘以平均每个男人拥有的 jj 根数。 用生命换来的圆周率 这个多少有些标题党了，但实际情况就是如此——这个 3.14 真的是由无数人的鲜血换来的。 2003 年，美国纽约警方搜集了 30 年来发生在斑马线上的车祸，从里面抽取了所有身高在 5 英尺 6 英寸到 8 英寸之间（大概从 1.68 米到 1.73 米）的遇难行人，统计了他们的尸体与斑马线相交的概率，并应用Buffon 投针实验理论得到了圆周率的近似值。纽约警方还专门发表了文章，称由此他们得出，行人被撞事故是完全随机的，一切都是遵循大自然的规律的。文章末尾请求出行人看开一些，生命在规律面前弱不禁风，该发生的总会发生。 凶案现场也有圆周率关于圆周率的计算
运算符重载基础概念练习题
高精度计算
常用数学公式
运算符重载练习题.
高精度数计算
圆周率计算公式
圆周率的计算方法
高精度运算(C++)
圆周率的计算历程及意义
作业━━第 5 章(4)━━运算符重载.
4运算符重载复习题1
数学实验：怎样计算圆周率
高精度运算(C++)
圆周率200位记忆口诀
高精度算法(c语言版)
历史上一些圆周率计算方法