gw4_HighComputing.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,程序设计实习第四讲,高精度计算,程序设计实习第四讲,高精度计算,新课程网址：,an1201,保存第一个数，用,unsigned an2200,表示第二个数，然后逐位相加，相加的结果直接存放在,an1,中。要注意处理进位。,#include,#include,#define MAX_LEN 201,int,an1MAX_LEN+10;,int,an2MAX_LEN+10;,char szLine1MAX_LEN+10;,char szLine2MAX_LEN+10;,int,Add(int,nMaxLen,int,*an1,int,*an2),/,将长度最多为,nMaxLen,的大整数,an1,和,an2,相加，结果放在,an1,/an10,an20,对应于个位,int,nHighestPos,=0;,for(int,i=0;i=10)/,看是否要进位,an1i-=10;,an1i+1+;/,进位,if(an1i),nHighestPos,=i;/,记录最高位的位置,return,nHighestPos,;,int,main(),scanf(%s,szLine1);,scanf(%s,szLine2);,int,i,j;,/,库函数,memeset,将地址,an1,开始的,sizeof(an1),字节内容置成,0,/sizeof(an1),的值就是,an1,的长度,/,memset,函数在,string.h,中声明,memset,(an1,0,sizeof(an1);,memset,(an2,0,sizeof(an2);,/,下面将,szLine1,中存储的字符串形式的整数转换到,an1,中去，,/an10,对应于个位,int,nLen1=,strlen,(szLine1);,for(j,=0,i=nLen1-1;i=0;i-),an1j+=szLine1i-0;,int,nLen2=strlen(szLine2);,for(j,=0,i=nLen2-1;i=0;i-),an2j+=szLine2i-0;,int,nHighestPos,=Add(MAX_LEN,an1,an2);,for(i=,nHighestPos,;i=0;i-),printf(%d,an1i);,return 0;,例题：,ai2736,大整数减法,问题描述,求,2,个大的正整数相减的差,输入数据,第,1,行是测试数据的组数,n,，每组测试数据占,2,行，第,1,行是被减数,a,，第,2,行是减数,b(a,b),。每组测试数据之间有一个空行，每行数据不超过,100,个字符,输出要求,n,行，每组测试数据有一行输出是相应的整数差,例题：,ai2736,大整数减法,输入样例,2,9999999999999999999999999999999999999,9999999999999,5409656775097850895687056798068970934546546575676768678435435345,1,输出样例,9999999999999999999999990000000000000,5409656775097850895687056798068970934546546575676768678435435344,#include,#include,#define MAX_LEN 110,int,an1MAX_LEN;,int,an2MAX_LEN;,char szLine1MAX_LEN;,char szLine2MAX_LEN;,int,Substract,(,int,nMaxLen,int,*an1,int,*an2),/,两个最多,nMaxLen,位的大整数,an1,减去,an2,an1,保证大于,an2,int,nStartPos,=0;,for(,int,i=0;i,nMaxLen,;i+),an1i-=an2i;/,逐位减,if(an1i=0;i-),an1j+=szLine1i-0;,int,nLen2=strlen(szLine2);,for(j=0,i=nLen2-1;i=0;i-),an2j+=szLine2i-0;,int,nStartPos,=,Substract,(MAX_LEN,an1,an2);,for(i=,nStartPos,;i=0;i-),printf(%d,an1i);,printf(n,);,return 0;,例题：,ai2980,大整数乘法,问题描述,求两个不超过,200,位的非负整数的积。,输入数据,有两行，每行是一个不超过,200,位的非负整数，没有多余的前导,0,。,输出要求,一行，即相乘后的结果。结果里不能有多余的前导,0,，即如果结果是,342,，那么就不能输出为,0342,。,输入样例,12345678900,98765432100,输出样例,1219326311126352690000,解题思路,用,unsigned an1200,和,unsigned an2200,分别存放两个乘数，用,aResult400,来存放积。计算的中间结果也都存在,aResult,中。,aResult,长度取,400,是因为两个,200,位的数相乘，积最多会有,400,位。,an10,an20,aResult0,都表示个位。,一个数的第,i,位和另一个数的第,j,位相乘所得的数，一定是要累加到结果的第,i+j,位上。这里,i,j,都是从右往左，从,0,开始数。,计算的过程基本上和小学生列竖式做乘法相同。为编程方便，并不急于处理进位，而将进位问题留待最后统一处理。,现以,83549,为例来说明程序的计算过程。,先算,8359,。,59,得到,45,个,1,，,39,得到,27,个,10,，,89,得到,72,个,100,。由于不急于处理进位，所以,8359,算完后，,aResult,如下：,接下来算,45,。此处,45,的结果代表,20,个,10,，因此要,aResult1+=20,，变为：,再下来算,43,。此处,43,的结果代表,12,个,100,，因此要,aResult2+=12,，变为：,最后算,48,。此处,48,的结果代表,32,个,1000,，因此要,aResult3+=32,，变为：,乘法过程完毕。接下来从,aResult0,开始向高位逐位处理进位问题。,aResult0,留下,5,，把,4,加到,aResult1,上，,aResult1,变为,51,后，应留下,1,，把,5,加到,aResult2,上,最终使得,aResult,里的每个元素都是,1,位数，结果就算出来了：,#include,#include,#define MAX_LEN 200,unsigned an1MAX_LEN+10;,unsigned an2MAX_LEN+10;,unsigned,aResultMAX_LEN,*2+10;,char szLine1MAX_LEN+10;,char szLine2MAX_LEN+10;,int,main(),gets(szLine1);/gets,函数读取一行,gets(szLine2);,int,i,j;,int,nLen1=,strlen,(szLine1);,memset,(an1,0,sizeof(an1);,memset,(an2,0,sizeof(an2);,memset,(,aResult,0,sizeof(aResult,);,j=0;,for(i=nLen1-1;i=0;i-),an1j+=szLine1i-0;,int,nLen2=strlen(szLine2);,j=0;,for(i=nLen2-1;i=0;i-),an2j+=szLine2i-0;,/,每一轮都用,an2,的一位，去和,an1,各位相乘，从,an1,的个位开始,for(i=0;i nLen2;i+),/,用选定的,an2,的那一位，去乘,an1,的各位,for(j=0;j nLen1;j+),/,两数第,i,j,位相乘，累加到结果的第,i+j,位,aResulti+j,+=an2i*an1j;,/,下面的循环统一处理进位问题,int,nHighestPos,=0;,for(i=0;i=10),aResulti+1+=,aResulti,/10;,aResulti,%=10;,if(,aResulti,),nHighestPos,=i;,for(i=,nHighestPos,;i=0;i-),printf(%d,aResulti,);,return 0;,求,2,个大的正整数相除的商,Input,第,1,行是测试数据的组数,n,，每组测试数据占,2,行，第,1,行是被除数，第,2,行是除数。每组测试数据之间有一个空行，每行数据不超过,100,个字符,Output,n,行，每组测试数据有一行输出是相应的整数商,Sample Input,3,2405337312963373359009260457742057439230496493930355595797660791082739646 2987192585318701752584429931160870372907079248971095012509790550883793197894,10000000000000000000000000000000000000000,10000000000,5409656775097850895687056798068970934546546575676768678435435345,1,Sample Output,0,1000000000000000000000000000000 5409656775097850895687056798068970934546546575676768678435435345,例题：,ai2737,大整数除法,(P165),例题：,ai2737,大整数除法,(P165),基本的思想是反复做减法，看看从被除数里最多能减去多少个除数，商就是多少。一个一个减显然太慢，如何减得更快一些呢？以,7546,除以,23,为例来看一下：开始商为,0,。先减去,23,的,100,倍，就是,2300,，发现够减,3,次，余下,646,。于是商的值就增加,300,。然后用,646,减去,230,，发现够减,2,次，余下,186,，于是商的值增加,20,。最后用,186,减去,23,，够减,8,次，因此最终商就是,328,。,所以本题的核心是要写一个大整数的减法函数，然后反复调用该函数进行减法操作。,#include,#include,#define MAX_LEN 110,int,an1MAX_LEN;,int,an2MAX_LEN;,int,tmpAn2MAX_LEN;,int,anResultMAX_LEN,;,char szLine1MAX_LEN;,char szLine2MAX_LEN;,char,szNouseMAX_LEN,;,int,Substract,(,int,nMaxLen,int,*an1,int,*an2),/,大整数,an1,减去,an2,。两者最多,nMaxLen,位，,an1,必须不小于,an2,差放在,an1,里,/,返回差的最高非,0,位的位置,int,nStartPos,=0;,for(,int,i=0;i,nMaxLen,;i+),an1i-=an2i;/,逐位相减,if(an1i=0),return i+1;,return 0;,void,ShiftLeft,(,int,nMaxLen,int,*an1,int,*an2,int,n),/,将大整数,an1,左移,n,位，即乘以,10,的,n,次方，结果放到,an2,里,memcpy,(an2,an1,nMaxLen*,sizeof(int,);,if(n=0;i-),if(i-n=0),an2i=an1i-n;,else,an2i=0;,int,*,Max(int,nMaxLen,int,*an1,int,*an2),/,求大整数,an1,和,an2,里面大的那个,/,如果都是,0,，则返回,NULL,bool,bBothZero,=true;,for(,int,i=,nMaxLen,-1;i=0;i-),if(an1i an2i),return an1;,else if(an1i=0;i-),an1j+=szLine1i-0;,int,nLen2=strlen(szLine2);,for(j=0,i=nLen2-1;i=0;i-),an2j+=szLine2i-0;,int,nHighestPos,=0;,memset(anResult,0,sizeof(anResult);,int,nShiftLen,=Length(MAX_LEN,an1)-Length(MAX_LEN,an2,);,/,只要,an1,大于,an2,，就不停相减,while(Max(MAX_LEN,an1,an2)=an1),/,算出,an1,的,10,的,nShiftLen,次方倍,ShiftLeft(MAX_LEN,an2,tmpAn2,nShiftLen);,/,重复减去,an2,的,10,的,nShiftLen,次方倍，看能减几次,while(Max(MAX_LEN,an1,tmpAn2)=an1),Substract(MAX_LEN,an1,tmpAn2);,/,记录商对应位,anResultnShiftLen,+;,/,记录结果最高位的位置,if(,nHighestPos,=0&,anResultnShiftLen,),nHighestPos,=,nShiftLen,;,nShiftLen,-;,for(i=,nHighestPos,;i=0;i-),printf(%d,anResulti,);,printf(n,);,return 0;,例题：,ai2952,循环数,问题描述,当一个,N,位的整数,X,满足下列条件时，称其为循环数：,X,与任意一个整数,1,Y,N,相乘时，都将产生一个,X,的“循环”。即：分别将这两个整数的第,1,位数字与最后,1,位数字连在一起，可以得到一个相同的数字循环；当然两个整数在该数字循环中的起始位置不同。例如，,142857,是一个循环数,142857*1=142857,142857,*2=285714 142857*3=428571 142857*4=571428 142857*5=714285 142857*6=857142,输入,写一个程序判断一个整数是否是循环数。输入文件是一个整数序列，每个整数长度为,260,。注意：每个整数前面的零被看作是该整数的一部分，在计算,N,时要统计。例如“,01”,是一个,2,位的整数，而“,1”,是一个,1,位的整数。,输出,对每个输入整数，输出一行，说明该整数是否是循环数。,样例输入,142857,142856,142858,01,0588235294117647,样例输出,142857 is cyclic,142856 is not cyclic,142858 is not cyclic,01 is not cyclic,0588235294117647 is,cycl,解题思路,高精度的乘法：整数可能达,60,位,X*1:Y,0,=X;,X*2:Y,1,=Y,0,+X,X*3:Y,2,=Y,1,+X,Y,i,是否是,X,的“循环”？,解题思路,:Y,i,是否是,X,的“循环”？,穷举：,N,位整数，循环移位可以有,N,种可能,循环移位方法：,Y,i,是否是“,XX”,的子串？,1,2,3,4,5,6,7,1,2,3,4,5,6,7,0,#include,#include,#define MAX_LEN 201,int,an1MAX_LEN+10;,int,an2MAX_LEN+10;,char szLine1MAX_LEN+10;,char szLine2MAX_LEN+10;,char szDouble2*MAX_LEN+10;,int,Add(int,nMaxLen,int,*an1,int,*an2),/,将长度最多为,nMaxLen,的大整数,an1,和,an2,相加，结果放在,an1,/an10,an20,对应于个位,int,nHighestPos,=0;,for(int,i=0;i=10)/,看是否要进位,an1i-=10;,an1i+1+;/,进位,if(an1i),nHighestPos,=i;/,记录最高位的位置,return,nHighestPos,;,int,main(),while(gets(szLine1)&szLine10),int,i,j;,/,库函数,memeset,将地址,an1,开始的,sizeof(an1),字节内容置成,0,/sizeof(an1),的值就是,an1,的长度,/,memset,函数在,string.h,中声明,memset,(an1,0,sizeof(an1);,memset,(an2,0,sizeof(an1);,/,下面将,szLine1,中存储的字符串形式的整数转换到,an1,中去，,/an10,对应于个位,int,nLen1=,strlen,(szLine1);,for(j,=0,i=nLen1-1;i=0;i-),an1j=szLine1i-0;,an2j+=szLine1i-0;,strcpy,(,szDouble,szLine1);,strcat,(,szDouble,szLine1);,bool,bOk,=true;,for(i=1;i=nLen1)/,长度超出了,bOk,=false;,break;,for(,int,k=0;k nLen1;k+)/,转换成字符串,szLine2nLen1-k-1=an1k+0;szLine2nLen1=0;,if(,strstr,(,szDouble,szLine2)=NULL),bOk,=false;,break;,if(,bOk,),printf,(%s is cyclicn,szLine1);,else,printf,(%s is not cyclicn,szLine1);,return 0;,