东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn ACM程序设计 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn.

Presentation on theme: "东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn ACM程序设计 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn."— Presentation transcript:

1 东北林业大学 陈宇 Lg_chenyu@yahoo.com.cn
ACM程序设计 东北林业大学 陈宇

2 今天你AC 了吗？ 2018/11/19

3 第二讲 高精度 2018/11/19

4 我校的ACM在线评测系统 acm.nefu.edu.cn 课件下载地址： acm.nefu.edu.cn/kj/acm03.ppt
2018/11/19

5 还看N!的位数这题 Hdu 1018 Big Number Pku 1423 Big Number
用1+lg(1)+lg(2)+..+lg(n)的方法，在PKU上TLE 了，超时了 2018/11/19

6 原因！ 1 <= m <= 10^7 规模很大 这道题目给出的限时是1000ms。假如对于给出的每一个数据，我们都慢慢地将它从log10(1) 慢慢加到log10(N)，绝对会超时。因为里面有大量重复的运算，例如log10(1)，如果有100组数据，那么它的值就会被计算100次。于是，我们想到，能否把所有计算过的log10值保存起来，然后若遇到重复的，就从这个结果数组里面提取就可以了，不用再计算。这个方法很好，但是题目给出的数据规模比较大，开一个10^7大的double数组，绝对会Memory Excceed Limit。那么，既然如此，我们应该用什么方法来计算呢？ 2018/11/19

7 假设问题给出的C组数据，是从小往大排列的，例如，给出三个数据，10，20，30，那么我们可以想到，计算log10(20
假设问题给出的C组数据，是从小往大排列的，例如，给出三个数据，10，20，30，那么我们可以想到，计算log10(20!)的时候，我们是可以利用long10(10!)的结果。因为： log10(10!) = log10(1) + log10(2) + log10(3) log10(9) +log10(10) log10(20!) = log10(1) + log10(2) + log10(3) log10(9) +log10(10) + log10(11) + log10(12) log10(19) + log10(20) 容易看出： log10(20!) = log10(10!) + log10(11) + log10(12) log10(19) + log10(20) ; 同理： log10(30!) = log10(10!) + log10(21) + log10(22) log10(29) + log10(30) ; 2018/11/19

8 也就是说，我们只需要保存之前的那个数的运算结果。这种方法，有人就说是DP，但是我觉得这算是记忆化搜索吧。
题目没有说给出的数据是有序的，但是我们可以通过排序使之有序。至于排序，那么当然是系统的sort()函数了。我解题时定义了一个结构体： typedef struct { int num; int id; double result; } data; 2018/11/19

9 【Stirling公式】 利用斯特林(Stirling)公式求解n!的位数:
易知整数n的位数为[lg10(n)]+1. 用Stirling公式计算n!结果的位数时，可以两边取对数，得： log10(n!) = log10(2*PI*n)/2+n*log10(n/E); 故n!的位数为 res=log10(2*PI*n)/2+n*log10(n/E)+1 2018/11/19

10 #include <iostream> #include <math.h>
using namespace std; //注意 e和pi的值要精确 const double , pi = ; double str_ling(int n) { return 0.5*log10(2*pi*n)+n*log10(n/e); } int main() int t,m; cin>>t; while(t--) cin>> m; cout<<(int)str_ling(m)+1<<endl; system("pause"); return 1; 2018/11/19

11 另外，超过浮点数取值范围的数据，比如一个1000位的整数，无法用常规方法来处理。 这些精度很高的数据通常称为高精度数，或称为大数。
在32位机器里，有符号整数(int)的取值范围是 ~ ，无符号整数(unsigned int) 的取值范围是0 ~ 。超过这个范围的数据可以用浮点型(double)来表示，如50!。但用浮点数来表示整数通常不便于整数的运算，比如整数除法跟浮点数除法含义不一样，浮点数也无法实现取余运算等等。 另外，超过浮点数取值范围的数据，比如一个1000位的整数，无法用常规方法来处理。 这些精度很高的数据通常称为高精度数，或称为大数。 高精度数的运算只能用本章介绍的高精度数计算方法来处理。 现在谈谈大整数 2018/11/19

12 Primary Arithmetic(初等算术） pku2562， nefu也有
题目描述： 小学生在学多位数的加法时，是将两个数右对齐，然后从右往左一位一位地加。多位数的加法经常会有进位。如果对齐的位相加结果大于或等于十就给左边一位进一。对小学生来说，进位的判断是比较难的。你的任务是：给定两个加数，统计进位的次数，从而帮助老师评估加法的难度。 2018/11/19

13 输入文件中的每一行为两个无符号整数，少于10位。最后一行位两个0，表示输入结束。
输入描述： 输入文件中的每一行为两个无符号整数，少于10位。最后一行位两个0，表示输入结束。 第二种输入方式!!!!! 输出描述： 对输入文件(最后一行除外)每一行的两个加数，计算它们进行加法运算时进位的次数并输出。具体输出格式详见样例输出。 样例输入： 0 0 样例输出： No carry operation. 3 carry operations. 1 carry operation. 2018/11/19

14 分析 Int 型的上限是2000000000，可以保存9位整数，因此本题可以用整数来保存输入，每次把a和b分别模10，就能获取他们的位数。
2018/11/19

15 while(cin>>a>>b) { if (a==0&&b==0) break; c=0;sum=0;
long long a,b,c,sum; while(cin>>a>>b) { if (a==0&&b==0) break; c=0;sum=0; for(int i=0;i<=9;i++) if ((a%10+b%10+c)>=10) {sum++; c=1; } else c=0; a=a/10;b=b/10; 2018/11/19

16 计算N! 72题 输入不超过10000的正整数n,计算n!的具体值？ 输入：30
输出： 2018/11/19

17 分析： 10000！的有多大？ 用计算器算=5* ，可以用50000个元素的数组f来保存，为了防止进位溢出，我们让f[0]保存结果的个位，f[1]表示十位，等等。输出的时候，数组高位上的0要忽略。 例如：11！= 则，12！=11！*12，也就是 的每位都乘12，再进位，从低到高，所以数组要用f[0]表示低位，输出时再逆序输出！ 2018/11/19

18 先定义变量 const int maxn=50000; int n,c,k; int f[maxn+1];
如果不知道10000！的阶乘有多少位，那肯定WA! 2018/11/19

19 for (int i=1;i<=n;i++) c=0;//代表进位 for(int j=0;j<=maxn;j++)
while(cin>>n) { memset(f,0,sizeof(f)); f[0]=1; for (int i=1;i<=n;i++) c=0;//代表进位 for(int j=0;j<=maxn;j++) int s=f[j]*i+c; f[j]=s%10; c=s/10; } 2018/11/19

20 看输出部分 运行时间4578ms，本题时间是5S for(k=maxn;k>=0;k--) if (f[k]!=0) break;
for(int j=k;j>=0;j--) cout<<f[j]; cout<<endl; } 运行时间4578ms，本题时间是5S 2018/11/19

21 能不能再快点？ 思考 发现f[i]里面的值只有1个数字，但f[i]是INT型啊，能存9位数啊，利用一下。 int s=f[j]*i+c;
f[j]=s%100000;//好好看看 c=s/100000;//每5位数字再进位 这回数组f开20000就够了，时间也快了~ 运行时间是1778ms！ 2018/11/19

22 如何打印输出？ 12！=479001600，后5位01600，输出是1600，要处理好这个问题就行了！
for(k=maxn;k>=0;k--) if (f[k]!=0) break; printf("%d",f[k]); for(int j=k-1;j>=0;j--) printf(“%05d”,f[j]);//5位的数字，不足前面添0 printf("\n"); 2018/11/19

23 还 能不能更快，一定能！先计算N!的位数 int a[40000]; int main() { int n,k,l; double wei;
for(int i=1;i<=n;i++) { int c=0; wei+=log10(i); k=((int)wei+1)/5; for(int j=0;j<=k;j++) int s=a[j]*i+c; a[j]=s%100000; c=s/100000; } int a[40000]; int main() { int n,k,l; double wei; while(cin>>n) memset(a,0,sizeof(a)); a[0]=1; wei=0;

24 时间 690MS for(k=wei;k>=0;k--) if(a[k]!=0) break; printf("%d",a[k]);
for(k;k>=0;k--) printf("%05d",a[k]); printf("\n"); }

25 当输入的数很大时，则必须用字符串来处理 再来看“初等算术”这道题~~ strcmp(a,b) a 和b相同时返回0！ 2018/11/19

26 正如前面分析的那样，本题可以采用字符数组来存储读入的两个加数。对两个加数进行加法运算时，要注意以下两点：
还可以用字符数组来做！ 正如前面分析的那样，本题可以采用字符数组来存储读入的两个加数。对两个加数进行加法运算时，要注意以下两点： 在进行加法时，要得到数字字符对应的数值，方法是将数字字符减去数字字符“0”； 从两个加数的最低位开始按位求和，如果和大于9，则会向前一位进位。要注意某一个加数的每一位都运算完毕，但另一个加数还有若干位没有运算完毕的情形。如图所示， ，这两个加数分为有6位和3位数。当第2个加数的最低3位数都运算完毕时，还会向前面进位，这时第1个加数还有3位没有运算完毕，由于进位的存在，这3位在运算时都还会产生进位。 2018/11/19

27 #include <stdio.h> #include <string.h> int main( ) {
char add1[11], add2[11]; //读入的两个加数 while( scanf("%s%s", add1, add2) ) if( !strcmp(add1,"0") && !strcmp(add2,"0") ) break; int carry = 0; //进位次数 int i1 = strlen(add1) - 1; int i2 = strlen(add2) - 1; int C = 0; //进位 while( i1>=0 && i2>=0 ) //从两加数右边开始对每位相加 if( add1[i1]-'0'+add2[i2]-'0'+C>9 ) carry++; C = 1; } else C = 0; i1--; i2--; 2018/11/19

28 while( i1>=0 ) //如果第1个加数还有若干位没有运算完 { if( add1[i1]-'0'+C>9 )
carry++; C = 1; } else C = 0; i1--; while( i2>=0 ) //如果第1个加数还有若干位没有运算完 if( add2[i2]-'0'+C>9 ) i2--; if( carry>1 ) printf( "%d carry operations.\n", carry ); else if( carry==1 ) printf( "%d carry operation.\n", carry ); else printf( "No carry operation.\n" ); return 0; 2018/11/19

29 另外，本题并不需要存储加法运算的结果，如果需要存储，通常需要将两个加数逆序后再进行运算。
注意：本题中告诉了读入的无符号整数少于10位，因此可以用unsigned int变量(其取值范围是0~ )来保存读入的整数。本题也可以将读入的整数取出各位存放到整型数组中，再按整型数组进行运算，统计进位的次数。读者不妨试试。 另外，本题并不需要存储加法运算的结果，如果需要存储，通常需要将两个加数逆序后再进行运算。 2018/11/19

30 高精度计算的基本思路 高精度计算的基本思路是：用数组存储参与运算的数的每一位，在运算时以数组元素所表示的位为单位进行运算。可以采用字符数组，也可以采用整数数组，到底采用字符数组还是整数数组更方便，应试具体题目而定。 2018/11/19

31 skew二进制(Skew Binary) 题目来源：Mid-Central USA 1997 题号：ZOJ1712，POJ1565
题目描述： 在十进制里，第k位数字的权值是10k。(每位数字的顺序是从右到左的，最低位，也就是最右边的位，称为第0位)。例如： 81307(10) = 8 * * * * * 100 = = 而在二进制里，第k位的权值为2k。例如： 10011(2) = 1 * * * * * 20 = = 19. 2018/11/19

32 在skew二进制里，第k位的权值为2(k+1) - 1，skew二进制的数码为0和1，最低的非0位可以取2。例如： 10120(skew2)
题目描述(continue)： 在skew二进制里，第k位的权值为2(k+1) - 1，skew二进制的数码为0和1，最低的非0位可以取2。例如： 10120(skew2) = 1 * (25 - 1) + 0 * (24 - 1) + 1 * (23 - 1) + 2 * (22 - 1) + 0 * (21 - 1) = = 44. skew二进制的前10个数为0，1，2，10，11，12，20，100，101和102。 2018/11/19

33 输入文件包含若干行，每行为一个整数n。n = 0代表输入结束。除此之外，n是skew二进制下的一个非负整数。
输入描述： 输入文件包含若干行，每行为一个整数n。n = 0代表输入结束。除此之外，n是skew二进制下的一个非负整数。 第二种输入方式!!!!! 输出描述： 对输入文件中的每个skew二进制数，输出对应的十进制数。输入文件中n最大值对应到十进制为231 – 1 = 。 样例输入： 10120 10 样例输出： 44 3 2018/11/19

34 很明显，对输入文件中的skew二进制数，不能采用整数形式(int)读入，必须采用字符数组。那么需要定义多长的字符数组？
分析： 很明显，对输入文件中的skew二进制数，不能采用整数形式(int)读入，必须采用字符数组。那么需要定义多长的字符数组？ 题目中提到“输入文件中的skew二进制数最大值对应到十进制为231 – 1 = ”，正如样例输入数据所示，十进制数 对应的skew二进制数为： 。 因此存储输入文件中的skew二进制数可以采用长度为40的字符数组。 在把skew二进制数转换成十进制时，只需把每位按权值展开求和即可。 采用字符数组存储高精度数，要求高精度数的总位数及取出每位上的数码都是很方便的。 2018/11/19

35 #include <stdio.h> #include <string.h>
#include <math.h> int main( ) { char str[40]; //读入的每个skew二进制数，用字符数组存放 while( scanf( "%s", str )!=EOF ) int len = strlen(str); //高精度数的总位数就是字符串的长度 int num = 0; //对应的十进制数 if( len==1 && str[0]==‘0’ ) break;//输入0，就退出 for( int i=len-1; i>=0; i-- ) //高精度数的每位：str[i]-'0' num += (str[i]-‘0’)*( pow(2,len-i) - 1 );//注意 printf( "%d\n", num ); } return 0; 2018/11/19

36 高精度数的基本运算 本节以几道竞赛题目为例讲解高精度数的加法、乘法和除法运算的实现方法。 2018/11/19

37 高精度数的加法 例整数探究(Integer Inquiry) 题目来源：Central Europe 2000
题号：pku1503 hdu1047 题目描述： 十进制大数的加法运算。 输入描述： 输入文件的第1行为一个整数N，表示输入文件中接下来有N组数据。每组数据最多包含100行。每一行由一个非常长的十进制整数组成，这个整数的长度不会超过100个字符而且只包含数字，每组数据的最后一行为0，表示这组数据结束。 每组数据之间有一个空行。 第一种输入方式!!!!! 2018/11/19

38 对输入文件中的每组数据，输出它们的和。每两组数据的输出之间有一个空行。
输出描述： 对输入文件中的每组数据，输出它们的和。每两组数据的输出之间有一个空行。 样例输入： 1 23 样例输出： 2018/11/19

39 首先，题目中提到，整数的长度不会超过100位，所以这些整数只能采用字符数组读入。但在对每位进行求和时，可以采用字符形式，也可以采用整数形式。
分析： 首先，题目中提到，整数的长度不会超过100位，所以这些整数只能采用字符数组读入。但在对每位进行求和时，可以采用字符形式，也可以采用整数形式。 本题用整数形式处理更方便。 2018/11/19

40 样例输入： 1 23 方法：对读入的字符数组，以逆序的方式将各字符转换成对应的数值存放到整数数组(整数数组中剩余元素的值为0)，然后再以整数方式求和，最后将求和的结果以相反的顺序输出各位。 2018/11/19

41 1)计算每位和时，得到的进位可能大于1，如图7.4所示。
在本题中，求和时要注意以下两点： 1)计算每位和时，得到的进位可能大于1，如图7.4所示。 2)累加各大数得到的和，其位数可能会比参与运算的大数的位数还要多。稍加分析即可得出结论，如果参与求和运算的大数最大长度为maxlen，因为参加求和运算的大数个数不超过100个，所以求和结果长度不超过maxlen+2。因此求和时可以一直求和到maxlen+2位，然后去掉后面的0，再以相反的顺序输出各位整数即可。 2018/11/19

42 #include <stdio.h> #include <string.h> int main( ) {
char buffer[200]; //存储(以字符形式)读入的每个整数 int array[200][200]; //逆序后的大数(每位是整数形式) int answer[200]; //及求得的和 int i, j, k; //循环变量 int num_integers; //读入整数的个数 int len, maxlen; //每个整数的长度，及这些整数的最大长度 int sum, carry, digit;//每位求和运算后得到的总和, 进位, 及该位的结果 int N; //测试数据的个数 scanf( "%d", &N ); 2018/11/19

43 memset( array, 0, sizeof(array) );
for( k=1; k<=N; k++ ) { maxlen = -1; memset( array, 0, sizeof(array) ); memset( answer, 0, sizeof(answer) ); for( num_integers = 0; num_integers < 200; num_integers++ ) gets( buffer ); if( strcmp(buffer, "0") == 0 ) break; len = strlen(buffer); if( len>maxlen ) maxlen = len; for( i = 0; i < len; i++ )//逆序存放大数的每位(整数形式) array[num_integers][i] = buffer[len i] - '0'; } 2018/11/19

44 for( i = 0; i < maxlen+2; i++ ) //对这些整数的每位进行求和 { sum = carry;
for( j = 0; j < num_integers; j++ ) sum += array[j][i]; digit = sum % 10; carry = sum / 10; answer[i] = digit; } for( i = maxlen+2; i >= 0; i-- ) //统计求和结果的位数 if( answer[i] != 0 ) break; while( i >= 0 ) printf( "%d", answer[i--] ); //逆序输出求和结果 printf( "\n" ); if( k<N ) printf( "\n" ); //两个输出块之间有一个空行 return 0; 2018/11/19

45 How Many Fibs? Hdu 1316 Recall the definition of the Fibonacci numbers: f1 := 1 f2 := 2 fn := fn-1 + fn-2 (n >= 3) Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a, b]. Input The input contains several test cases. Each test case consists of two non-negative integer numbers a and b. Input is terminated by a = b = 0. Otherwise, a <= b <= 10^100. The numbers a and b are given with no superfluous leading zeros. 2018/11/19

46 Output For each test case output on a single line the number of Fibonacci numbers fi with a <= fi <= b. Sample Input 10 100 Sample Output 5 4 2018/11/19

47 代码 2分+高精度 #include <iostream> #include <cstdlib>
代码 2分+高精度 #include <iostream> #include <cstdlib> #include <cstring> #define M 105 using namespace std; char data[1000][M+2]; char a[M+2],b[M+2]; int cmp_ab(char *s1,char *s2) { for(int k=0;k<=105;k++) if (k==105) return s1[k]-s2[k]; if (s1[k]!=s2[k]) return s1[k]-s2[k]; }

48 int find1(int i,char *x) { int low=0,high=i,mid; while(low<=high) mid=(low+high)/2; int value=cmp_ab(x,data[mid]); if (value>0) low=mid+1; if (value==0) return mid-1; if (value<0) high=mid-1; } return high; //这时候high小于low int find2(int i,char *x) if (value==0) return mid+1; return low; //这时候 low大于high

49 int main() { int i,j,p; //memset(data,0,sizeof(data)); data[0][105]=1; data[1][105]=2; i=2;p=105; while(data[i-1][5]<=1) for(j=105;j>=p;j--) data[i][j]=data[i-1][j]+data[i-2][j]; int c=data[i][j]/10; if (c>=1) data[i][j]=data[i][j]%10; data[i][j-1]=data[i][j-1]+c; } if (data[i][p-1]>0) p--; i++;

50 while(cin>>a>>b)
{ if (a[0]=='0'&&b[0]=='0') break; int len1=strlen(a)-1; int len2=strlen(b)-1; int k; for(int d=len1,k=105;d>=0;d--,k--) a[k]=a[d]-'0'; a[d]=0; } for(int d=len2,k=105;d>=0;d--,k--) b[k]=b[d]-'0'; b[d]=0; /*for(int i=0;i<=105;i++) cout<<(int)b[i]; cout<<endl; */ int lt=find1(i-1,a); int rt=find2(i-1,b); cout<<rt-lt-1<<endl; memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); return 0;

51 高精度数的乘法 初等数学里乘法的运算过程，如图所示。该运算过程有如下特点：
多位数的乘法是转换成1位数的乘法及加法来实现的，即把第二个乘数的每位数乘以第一个乘数，把得到的中间结果累加起来。 第二个乘数的每位数进行乘法运算的中间结果，是与第二个乘数参与运算的位右对齐的。如图(a)所示，第二个程序的第2位为7，参与乘法运算得到的中间结果“8638”是和7对齐的。 2018/11/19

52 在初等数学里，乘法运算得到的每个中间结果都是处理了进位的：在中间结果里，一出现进位马上累加到高一位，如图(a)中的中间结果“11106”是已经处理了进位的结果。
但是，为方便程序实现，对中间结果的进位处理更方便的做法是等全部中间结果运算完后再统一处理。如图(b)所示，每个中间结果，“ ”、“ ”、“ ”、“ ”都是没有处理进位的，都是第二个乘数的每位乘以第一个乘数每位的原始乘积。这些中间结果累加后，再一位一位的处理进位。 2018/11/19

53 例 高精度数的乘法 输出描述： 对输入文件中的每个测试数据，输出其中两个正整数的乘积。 样例输入： 样例输出： 981567
题目描述： 给定两个位数不超过100位的正整数，求它们的乘积。 第三种输入方式!!!!! 输入描述： 输入文件中包含多个测试数据。每个测试数据占两行，分别为一个正整数，每个正整数的位数不超过100位。输入数据一直到文件尾。 输出描述： 对输入文件中的每个测试数据，输出其中两个正整数的乘积。 样例输入： 981567 样例输出： 2018/11/19

54 两个长度不超过100位的正整数必须用字符数组a和b来读入，其乘积不超过200位。大整数的乘法运算过程可分为几个步骤：
分析： 两个长度不超过100位的正整数必须用字符数组a和b来读入，其乘积不超过200位。大整数的乘法运算过程可分为几个步骤： 2018/11/19

55 对读入的字符形式的大整数，把其各位上的数值以整数形式取出来，以相反的顺序存放到一个整型数组里。如下图所示。
把第二个乘数中的每个数乘以第一个乘数，把得到的中间结果累加起来，注意对齐方式，以及累加每位的中间结果时不进位。 把累加的中间结果，由低位向高位进位。再把得到的最终结果按相反的顺序转换成字符输出。 2018/11/19

56 #include <stdio.h> #include <string.h>
char a[101], b[101]; //输入的两个正整数(字符形式) int len_a, len_b; //输入的正整数长度 int ai[101], bi[101]; //输入的两个正整数(以整数形式存储每一位) int temp[202]; //每一位乘法的中间结果 char product[201]; //乘积 void reverse( char s[ ], int si[] ) //以逆序顺序存放大数中的各位数(整数形式) { int len = strlen(s); for( int i=0; i<len; i++ ) si[len-1-i] = s[i]-'0'; } int main( ) int i, j; while( scanf( "%s", a ) != EOF ) scanf( "%s", b ); len_a = strlen(a); len_b = strlen(b); reverse(a, ai); reverse(b, bi); memset( temp, 0, sizeof(temp) ); memset( product, 0, sizeof(product) ); 2018/11/19

57 for( i=0; i<len_b; i++ ) //用大整数b的每位去乘大整数a {
int start = i;//得到的中间结果跟大整数b中的位对齐 for( j=0; j<len_a; j++ ) temp[start++] += ai[j]*bi[i]; } for( i=0; i<202; i++ ) //低位向高位进位 if( temp[i]>9 ) temp[i+1] += temp[i]/10; temp[i] = temp[i]%10; for( i=201; i>=0; i-- ) //求乘积的长度 { if( temp[i] ) break; } int lenp = i+1; //乘积的长度 for( i=0; i<lenp; i++ ) //将乘积各位转换成字符形式 product[lenp-1-i] = temp[i]+'0'; product[lenp] = 0; //串结束符标志 printf( "%s\n", product ); return 0; 2018/11/19

58 Welcome to HDOJ Thank You ~ 2018/11/19