《高精度与字符串》PPT课件.ppt

主讲人： 张波 ID： AC_mm 信息工程学院ACM团队,高精度运算,字符串,AND,主要内容： 高精度加法 高精度乘法 字符串中空格的处理 字符串处理函数,高精度篇,C/C+中的int类型能表示的范围是： -231到231-1; unsigned类型能表示的范围是： 0到232-1; 即：0 - 4294967295 所以int和unsigned类型变量，都不能保存超过10位的整数。,又如long long和_int64能表示的范围是：-263到263-1 即：-9223372036854775808到 9223372036854775807 所以即便是long long和_int64最多也只能保存19位的数字。,有时我们需要参与运算的数，可能会远远不止10位或19位。 例如，可能需要保留小数点后面100位（比如pi值）。那么，即便使用能表示很大数值范围的double变量（double变量只有64位），仍然不能到达精确到小数点后面100位这样的精度。,一般我们称这种基本数据类型无法表示的整数为大整数。那么如何表示和存放大整数呢？基本思想就是：用数组存放和表示大整数。一个数组元素存放大整数中的一位。 那么，如何解决类似大整数这样的高精度计算问题呢？ 这就是我们今天学习的内容。,例题1分析,首先给一个最简单的例子。 问题描述： 求两个不超过200位的正整数的和。 输入数据： 有两行，每行是一个不超过200位的正整数，并且没有多余的前导0.,输出要求： 输出相加后的结果。结果里面不能有多余的前导0，即如果结果是342，那么就不能输出0342。,例题1分析,例题1分析,输入样例： 22222222222222222222 33333333333333333333 输出样例： 55555555555555555555,例题1分析,首先要解决的就是存储200位整数的问题。显然，任何C/C+固有类型的变量都无法保存它。最直观的想法就是可以用一个字符串来保存它。字符串本质上就是一个字符数组，因此为了编程更方便，我们也可以用数组A200来保存一个200位的整数。,例题1分析,让A0存放个位数，A1存放十位数，A2存放百位数，依次类推。 那么如何实现两个大整数相加呢？方法很简单，就是模拟小学生列竖式做加法，从个位开始逐位相加，超过或达到10则进位。,比如计算4567+9135 4 5 6 7 + 9 1 3 5 - = 13 6 9 12,= 13 6 9 12 - = 13 6 10 2 - = 13 7 0 2 - = 1 3 7 0 2,现在我们来写例题1的代码。 首先开2个数组来保存2个大数 分别为数组A210, B210; 然后再开一个数组ans210来保存相加的结果。 这里为了让大家更容易理解，我们最后统一进位。,例题1分析,1 #include 2 #include 3 #define M 210 4 int main() 5 6 char str1M,str2M; 7 int AM,BM,ansM,i,j; 8 while(scanf(“%s%s“,str1,str2)!=EOF),9 10 memset(A,0,sizeof(A); 11 memset(B,0,sizeof(B); 12 memset(ans,0,sizeof(ans); 13 int len1=strlen(str1); 14 int len2=strlen(str2); 15 for(j=0,i=len1-1;i=0;i-) 16 Aj+=str1i-0; 17 for(j=0,i=len2-1;i=0;i-) 18 Bj+=str2i-0;,19 for(i=0;i=10) 24 25 ansi+1+=ansi/10; 26 ansi%=10; 27 28 ,29 for(i=M-1;i=0;i-) 30 if(ansi) break; 31 for(j=i;j=0;j-) 32 printf(“%d“,ansj); 33 printf(“n“); 34 35 return 0; 36 ,高精度乘法,例题2： 题目描述： 计算2个不超过40位的正整数的积. 输入数据： 输入为2行,每一行代表一个数 输出数据： 输出一行,为2个数的乘积.,高精度乘法,输入样例： 11111111111111 1111111111 输出样例： 12345679011110987654321,例题2分析,有了刚才的高精度加法，现在我们应该比较容易想到怎样处理。 我们用一个简单的例子来推断。 我们来模拟835*49的过程。 这个过程和小学生列竖式做乘法相同。,8 3 5 4 9 - 72 27 45 32 12 20 - 32 84 47 45 - 4 0 9 1 5,数组ans来保存运算结果。 我们对上面的竖式乘法过程进行分析。 先计算835*9。 5*9得到45个1,3*9得到27个10,8*9得到72个100。那么ans的结果为： 下标： 5 4 3 2 1 0 ans 0 0 0 72 27 45,例题2分析,接下来再计算835*4 4*5得到20个10，因此ans1+=20, 下标： 5 4 3 2 1 0 ans 0 0 0 72 47 45,例题2分析,再接下来算4*3，得到12个100，因此ans2+=12. 下标： 5 4 3 2 1 0 ans 0 0 0 84 47 45,例题2分析,最后算4*8，得到32个1000，因此ans3+=32. 下标： 5 4 3 2 1 0 ans 0 0 32 84 47 45,例题2分析,最后我们统一进位得到： 下标： 5 4 3 2 1 0 ans 0 4 0 9 1 5,例题2分析,我们从上式不难看出某种规律。 即一个数的第i位和另一个数的第j位相乘所得的数，一定是要累加到结果的第i+j位上。这里i，j都是自右往左从0开始数。,例题2分析,有了上面的分析我们就可以敲代码了。,例题2分析,1 #include 2 #include 3 #define M 45 4 int main() 5 6 char str1M,str2M; 7 int AM,BM,ans2*M,i,j; 8 while(scanf(“%s%s“,str1,str2)!=EOF) 9 ,10 memset(A,0,sizeof(A); 11 memset(B,0,sizeof(B); 12 memset(ans,0,sizeof(ans); 13 int len1=strlen(str1); 14 int len2=strlen(str2); 15 for(j=0,i=len1-1;i=0;i-) 16 Aj+=str1i-0; 17 for(j=0,i=len2-1;i=0;i-) 18 Bj+=str2i-0;,19 for(i=0;i=10) 25 26 ansi+1+=ansi/10; 27 ansi%=10; 28 29 ,30 for(i=2*M-1;i=0;i-) 31 if(ansi) break; 32 for(j=i;j=0;j-) 33 printf(“%d“,ansj); 34 printf(“n“); 35 36 return 0; 37 ,高精度课后习题,都是我们OJ上的： 1202 ：最基本的高精度加法 1011 ：高精度加法（二维的） 1019 ：高精度乘法 1529 ：高精度减法 1521 ：高精度除法 饭可三日不吃，水可一日不喝，然题不可一日不做。,字符串篇,字符串的定义,字符串：由零个或多个字符组成且通过双引号括起来的有限序列就叫字符串。 例如: “Hello world！“ , “我爱ACM“, “123456“ 等等都是字符串. 字符串存储在字符数组中。且以空字符（0）结尾。（通常由系统自己添加）,当我们刚接触编程，在处理一些简单字符串题目时，经常会遇到一系列的问题（比如数据无法按预期目标输入等等），但归根结底，大多数都是因为不会处理字符串中的空格而引起。 特别是输入输出中的空格处理尤为重要。,scanf会在开始读入字符串之前跳过空白符，但是不允许在输入中存在空白符。 比如：当输入“ ACM AC_mm“的时候,只有“ ACM “会被存储在内存中，而空格字符后的其他剩余字符将被丢弃。,scanf和gets的区别,gets 函数不会在开始读字符串之前跳过空白字符。 gets 函数会持续读入直到找到换行符才停止(scanf 函数会在任意空白字符处停止)。 常常要在scanf后面添加getchar() 才能进行gets输入,scanf和gets的区别,例题分析,62/oj/showproblem?problem_id=1142 题目大意： 有t组测试数据，每组测试数据有多个数字（不超过50个）。输出排序后的序列。,输入样例： 2 5 1 3 1 8 2 4 输出样例： 1 3 5 1 2 4 8,例题分析,例题分析,由于我们不知道输入的数到第有多少个，所以我们只能进行字符的读入，将读入的字符转换为int型的整数，并且在换行（n）时结束输入。,1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 int main() 7 8 char ch; 9 int i,t,d55;,10 scanf(“%d“,19 if(ch=n|ch=EOF) break; 20 while(ch= ) ch=getchar(); 21 while(isdigit(ch) 22 di=di*10+ch-0,ch=getchar(); 23 i+; 24 25 if(ch=EOF) break; 26 sort(d,d+i);,27 for(int j=0;ji-1;j+) 28 printf(“%d “,dj); 29 printf(“%dn“,di-1); 30 31 return 0; 32 ,字符串中的函数,在处理字符或字符串的相关问题时，我们经常被要求去判断字符ch是否为数字，求字符串str的长度，将字符串s1复制给字符串s2等等。虽然这些问题都很简单，都可以用简单的C语句表示。,字符串中的函数,例如： 判断字符ch是否为数字：if(ch=0,字符串中的函数,既然我们能够在不调用函数的情况下处理好这些问题，那为什么我们还要用函数呢？用函数表达的优势又在哪里呢？ 优势：使程序更简洁、可读性更强、方便代码的调试等等。,字符串中的函数,处理字符和字符串的函数主要分成三大类，其分别包含在ctype.h、string.h、stdlib.h三个头文件中。 这里只给出部分函数。感兴趣的同学可以查阅相关资料,isdigit: int isdigit(int ch) 如果参数是0到9之间的数字字符，函数返回非零值，否则返回零。 isalpha: int isalpha(int ch) 如果参数是字母字符，函数返回非零值，否则返回零。 isalnum: int isalnum(int ch) 如果参数是数字或字母字符，函数返回非零值，否则返回零。,islower: int islower(int ch) 如果参数是小写字母字符，函数返回非零值，否则返回零值。 isupper: int isupper(int ch) 如果参数是大写字母字符，函数返回非零值，否则返回零值。 另外还有这个头文件里还包含了isxdigit, tolower, toupper,isspace，isctrl, ispunct, isprint, isalpha等函数。,strcpy: char *strcpy(char *s1,char *s2); 将字符串s2的内容复制给字符串s1 strncpy: char *strncpy(char *s1,char *s2,int n); 将s2中的前n个字符复制到s1中，如果s2的长度小于n，其余部分用0填补。返回处理完成的字符串 strcat: char *strcat(char *s1,char *s2); 将字符串s2接在字符串s1后面。,strcmp: int strcmp(char *s1,char *s2); 比较字符串s1和s2，小于、等于、大于分别返回负值、0、正值。 strlen: int strlen(char *str); 返回字符串str的长度。 类似函数有strchr，strstr，strncmp , strspn,strcspn,strpbrk,strtok等等。,itoa: char *itoa( int n, char *str, int radix) 将n按radix进制转化为一个字符串,并将值保存在str中。 atoi：int atoi (char *st