信息学奥赛课课通(C++)第9单元-电子课件

高等教育出版社第9单元基本算法作者：林厚从信息学奥赛课课通(C++)高等教育出版社信息学奥赛课课通(C++)第1课进制转换学习目标1.理解二进制计数原理。2.掌握不同进制数之间的转换原理和实现方法。3.学会使用进制转换的原理解决一些实际问题。高等教育出版社信息学奥赛课课通(C++)进制实际生活中，人们使用十进制计数。但是，任何信息在计算机中都是采用二进制编码表示的，有时还会用到十六进制。十进制计数原理采用“0”~“9”十个符号，运算规则为“逢十进一”，基数是十。二进制计数原理采用“0”和“1”两个符号，运算规则是“逢二进一”，基数是二。高等教育出版社信息学奥赛课课通(C++)进制显然，十进制中的数“10”和二进制中的“10”、十六进制中的“10”是不一样的。为了区分，我们分别表示成（10）10、（10）2、（10）16。有时也会在一个数的后面加上英文字母D、B、H来分别表示该数是十进制数、二进制数或者十六进制数，如96D、110B、2B3FH等。高等教育出版社信息学奥赛课课通(C++)1.进制转换的基本原理不同进制数之间转换的基本原理就是依据其“运算规则”和“权”的含义进行乘除运算。(1)二进制数转换成十进制数一个二进制数转换成十进制数的方法是将其表示成“按权展开式”，再按十进制运算规则求和。这种方法可以扩展到任意n进制。高等教育出版社信息学奥赛课课通(C++)进制(2)二进制数与十六进制数之间的相互转换二进制数转换成十六进制数的方法是以小数点为准，往前、往后“四位一段”分别转换成十六进制数再求和，不满四位要补齐。(3)十进制数转换成二进制十进制数转换成二进制要将整数和小数分开转换，最后再求和。整数的转换方法是：不断除以2求余数，最后反序输出；小数的转换方法是：不断乘以2，将每次得到的整数部分依次输出，并且每次都将整数部分恢复为0。高等教育出版社信息学奥赛课课通(C++)2.进制转换的应用举例例1、进制转换【问题描述】将任意一个n进制整数x转换成十进制。【输入格式】第1行1个正整数n，1n10；第2行1个整数x。【输出格式】一行一个数，表示转换得到的十进制数，保证答案不超过2147483647。【输入样例】2100110【输出样例】38高等教育出版社信息学奥赛课课通(C++)【问题分析】读入n和x，根据n和x的位数，分别求出x的每一位对应的“权值”，然后穷举每一位，将它乘以该位对应的权值，累加便可得到结果。更高效、更简洁的算法是采用“秦九韶公式”。对于样例输入，可以这样计算：(((((1*2)＋0)*2+0)*2+1)*2+1)*2+0=38具体实现采用“迭代法”，用一个变量不断乘以n，再加上下一位x[i]。高等教育出版社信息学奥赛课课通(C++)//p9-1-1#includebits/stdc++.husingnamespacestd;intmain(){freopen(”change.in”,”r”,stdin);freopen(”change.out”,”w”,stdout);intn,ans=0,i=0;chars[32];scanf(”%d\n”,&n);while((s[i]=getchar())!='\n'){ans=ans*n+(s[i]-48);i++;}printf(”%d\n”,ans);return0;}高等教育出版社信息学奥赛课课通(C++)例2、汽车牌照【问题描述】小Y最近发现街上的汽车越来越多了，作为汽车的重要标志——汽车牌照也是越来越不够用了，已经从以前的十进制发展到三十六进制了，以前的一个汽车牌照“苏D88888”，现在的牌照“苏D0YY11”。小Y突发其想，想知道他看到的大量汽车牌照中最近的两个汽车牌照相差多少？【输入格式】若干行(不超过500000行)，每行为一个汽车牌照。每个汽车牌照为一个7位的字符串，格式为SD×××××，其中一个×表示一个0~9或A~Z，所涉及的字母均为大写。【输出格式】一行一个数，表示最接近的两个汽车牌照之间的差值，要求为十进制数。【输入样例】SD12345SD88888SD22222SD99999【输出样例】1678245高等教育出版社信息学奥赛课课通(C++)例3、数列【问题描述】给定一个正整数k，把所有k的方幂及所有有限个互不相等的k的方幂之和构成一个递增的序列。例如，当k=3时，这个序列是：1，3，4，9，10，12，13，…请求出这个序列的第n项的值(用十进制数表示)。【输入格式】一行两个正整数k和n，之间用一个空格隔开，且3≤k≤15，10≤n≤1000。【输出格式】一行一个正整数。【输入样例】3100【输出样例】981高等教育出版社信息学奥赛课课通(C++)实践巩固高等教育出版社信息学奥赛课课通(C++)第2课高精度运算学习目标1.体会高精度运算的应用场合。2.熟练掌握高精度加法和乘法运算。高等教育出版社信息学奥赛课课通(C++)高精度运算在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值。这种情况下，就需要进行“高精度运算”。高精度运算首先要处理好数据的接收和存储问题，其次要处理好运算过程中的“进位”和“借位”问题。高等教育出版社信息学奥赛课课通(C++)例1、高精度加法【问题描述】输入两个1000位以内的正整数，输出它们的和。【输入样例】123456789987654321【输出样例】1111111110高等教育出版社信息学奥赛课课通(C++)【问题分析】用字符串的方式读入两个高精度数，转存到两个整型数组a和b中，如图9.2-1所示，模拟加法的过程，从低位(第0位)开始对应位a[i]和b[i]相加，同时处理进位，结果存储到另一个数组c中。最后，从高位到低位输出c[i]。参考程序见教材329页。高等教育出版社信息学奥赛课课通(C++)例2、高精度乘法【问题描述】输入两个100位以内的正整数，输出它们的乘积。【输入样例】123456789987654321【输出样例】121932631112635269高等教育出版社信息学奥赛课课通(C++)【问题分析】如图9.2-2所示，模拟“竖式”乘法的过程，用一个数的每一位a[i](从低位开始)逐位与另一个数的每一位b[j]相乘，结果存储到c[i+j]位，同时处理好进位。参考程序见教材330页。高等教育出版社信息学奥赛课课通(C++)例3、n!的精确值【问题描述】输入n，输出n!的精确值，n!=1×2×3×…×n，1n1000。【输入样例】100【输出样例】93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000高等教育出版社信息学奥赛课课通(C++)【问题分析】假设已经计算好(n-1)!，那么，对于求n!，就是用一个整数去乘以一个高精度数。只要用n乘以(n-1)!的每一位(从低位开始)，同时不断处理进位。参考程序见教材331页。高等教育出版社信息学奥赛课课通(C++)例4、n/m的精确值【问题描述】输入n和m，输出n除以m的精确值。假设n和m在int范围以内，结果精确到小数点后100位。【输入样例】355113【输出样例】3.1415929203539823008849557522123893805309734513274336283185840707964601769911504424778761061946902654高等教育出版社信息学奥赛课课通(C++)【问题分析】如图9.2-3所示，模拟数学中的“短除法”。由数学知识可知，除法运算中被除数、除数和商、余数的关系为：新的被除数=10×余数商=被除数／除数余数=被除数%除数参考程序见教材332页。高等教育出版社信息学奥赛课课通(C++)实践巩固高等教育出版社信息学奥赛课课通(C++)第3课模拟学习目标1.熟练应用模拟法解决一些实际问题。2.体验模拟法的审题分析和细节测试。高等教育出版社信息学奥赛课课通(C++)模拟在信息学奥赛中，有一类问题是模拟一个游戏的对弈过程，或者模拟一项任务的操作过程，进行统计计分、判断输赢等。这些问题很难建立数学模型用特定算法解决，一般只能采用“模拟”法。用模拟法解题必须关注以下几个问题：审题要仔细，游戏规则不能错；分析要全面，各种特例不能漏；编程要细心，测试运行要到位。高等教育出版社信息学奥赛课课通(C++)例1、蚱蜢【问题描述】有一天，一只蚱蜢像往常一样在草地上愉快地跳跃，它发现了一条写满了英文字母的纸带。蚱蜢只能在元音字母(A、E、I、O、U、Y)间跳跃，一次跳跃所需的能力是两个位置的差。纸带所需的能力值为蚱蜢从纸带开头的前一个位置根据规则跳到纸带结尾的后一个位置的过程中能力的最大值。蚱蜢想知道跳跃纸带所需的能力值(最小)是多少。如图9.3-1所示的纸带所需的能力值(最小)是4。高等教育出版社信息学奥赛课课通(C++)【输入格式】一行一个字符串，字符串长不超过100。【输出格式】一行一个整数，代表(最小)能力值。【输入样例】KMLPTGFHNBVCDRFGHNMBVXWSQFDCVBNHTJKLPMNFVCKMLPTGFHNBVCDRF-GHNMBVXWSQFDCVBNHTJKLPMNFVC【输出样例】85高等教育出版社信息学奥赛课课通(C++)【问题分析】从头到尾枚举纸带的每一个字母，按照规则模拟蚱蜢在元音字母之间跳跃的过程，打擂台记录能力值。参考程序见教材336页。高等教育出版社信息学奥赛课课通(C++)例2、遭遇战【问题描述】小林和小华在一个n×n的矩形方格里玩游戏，矩形左上角为(0，0)，右下角为(n-1，n-1)。两人同时进入地图的随机位置，并以相同速度进行走位。为了隐蔽性，两人都不会再走自己走过的格子。如果两人向某一方向前进，那么他们会跑到不能跑为止，当不能跑的时候，小林会向右转，小华则会向左转，如果不能跑，则不再动。现在已知两人进入地图的初始位置和方向，请算出两人遭遇的位置。【输入格式】第1行1个正整数t，表示测试数据组数，1≤t≤10。接下来的t组数据，每组数据的第1行包含1个整数n，1≤n≤1000。高等教育出版社信息学奥赛课课通(C++)第2行包含3个整数x、y和d，表示小林的初始位置和一开始跑的方向。其中，d=0表示东；d=1表示南；d=2表示西；d=3表示北。第3行与第2行格式相同，但描述的是小华。【输出格式】输出t行，若会遭遇，则包含两个整数，表示他们第一次相遇格子的坐标，否则输出“-1”。【输入样例】220000124010320【输出样例】-113高等教育出版社信息学奥赛课课通(C++)【问题分析】设置两个布尔型数组，分别记录模拟每个人走过的格子。如果两人没有相遇并且还可以跑，就让他们按照规则一直跑下去。参考程序见教材337-338页。高等教育出版社信息学奥赛课课通(C++)例3、乒乓球【问题描述】国际乒联立志推行一系列改革，以推动乒乓球运动在全球的普及。其中11分制改革引起了很大的争议，有一部分球员因为无法适应新规则只能选择退役。华华就是其中一位，他退役之后走上了乒乓球研究工作，意图弄明白11分制和21分制对选手的不同影响。在开展研究之前，他首先需要对自己多年比赛的统计数据进行一些分析，所以需要一些帮忙。华华通过以下方式进行分析，首先将比赛每个球的胜负列成一张表，然后分别计算在11分制和21分制下，双方的比赛结果(截至记录末尾)。高等教育出版社信息学奥赛课课通(C++)比如，现在有这么一份记录，(其中W表示华华获得一分，L表示华华对手获得一分)：。在11分制下，此时比赛的结果是华华第一局11比0获胜，第二局11比0获胜，正在进行第三局，当前比分1比1。而在21分制下，此时比赛结果