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

1、 高等教育出版社高等教育出版社 第第 9 单元单元 基本算法基本算法作者：林厚从作者：林厚从信息学奥赛课课通信息学奥赛课课通(C+)(C+)高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)第第 1 课课 进制转换进制转换学习目标学习目标1.理解二进制计数原理。理解二进制计数原理。2.掌握不同进制数之间的转换原理和实现方法。掌握不同进制数之间的转换原理和实现方法。3.学会使用进制转换的原理解决一些实际问题。学会使用进制转换的原理解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)进制进制实际生活中，人们使用十进制计数。但是，任何信息在实际生活

2、中，人们使用十进制计数。但是，任何信息在计算机中都是采用二进制编码表示的，有时还会用到十六计算机中都是采用二进制编码表示的，有时还会用到十六进制。进制。十进制计数原理采用十进制计数原理采用“0”“9”十个符号，运算规则为十个符号，运算规则为“逢十进一逢十进一”，基数是十。，基数是十。二进制计数原理采用二进制计数原理采用“0”和和“1”两个符号，运算规则两个符号，运算规则是是“逢二进一逢二进一”，基数是二。，基数是二。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)进制进制 显然，十进制中的数显然，十进制中的数“10”和二进制中的和二进制中的“10”、十六、十六进制中的进制中

3、的“10”是不一样的。为了区分，我们分别表示成是不一样的。为了区分，我们分别表示成（10）10、（、（10）2、（、（10）16。有时也会在一个数的后面加。有时也会在一个数的后面加上英文字母上英文字母D、B、H来分别表示该数是十进制数、二进制来分别表示该数是十进制数、二进制数或者十六进制数，如数或者十六进制数，如96D、110B、2B3FH等。等。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)1.进制转换的基本原理进制转换的基本原理不同进制数之间转换的基本原理就是依据其不同进制数之间转换的基本原理就是依据其“运算规则运算规则”和和“权权”的含义进行乘除运算。的含义进行乘除

4、运算。(1)二进制数转换成十进制数二进制数转换成十进制数一个二进制数转换成十进制数的方法是将其表示成一个二进制数转换成十进制数的方法是将其表示成“按按权展开式权展开式”，再按十进制运算规则求和。这种方法可以扩，再按十进制运算规则求和。这种方法可以扩展到任意展到任意 n 进制。进制。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)进制进制(2)二进制数与十六进制数之间的相互转换二进制数与十六进制数之间的相互转换二进制数转换成十六进制数的方法是以小数点为准，往二进制数转换成十六进制数的方法是以小数点为准，往前、往后前、往后“四位一段四位一段”分别转换成十六进制数再求和，不分别转

5、换成十六进制数再求和，不满四位要补齐。满四位要补齐。(3)十进制数转换成二进制十进制数转换成二进制十进制数转换成二进制要将整数和小数分开转换，最后十进制数转换成二进制要将整数和小数分开转换，最后再求和。整数的转换方法是：不断除以再求和。整数的转换方法是：不断除以 2 求余数，最后反求余数，最后反序输出；小数的转换方法是：不断乘以序输出；小数的转换方法是：不断乘以 2，将每次得到的整，将每次得到的整数部分依次输出，并且每次都将整数部分恢复为数部分依次输出，并且每次都将整数部分恢复为 0。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)2.进制转换的应用举例进制转换的应用举例例

6、例 1、进制转换、进制转换【问题描述问题描述】将任意一个将任意一个 n 进制整数进制整数 x 转换成十进制。转换成十进制。【输入格式输入格式】第第 1 行行 1 个正整数个正整数 n，1n10；第第 2 行行 1 个整数个整数 x。【输出格式输出格式】一行一个数，表示转换得到的十进制数，保证答案不超过一行一个数，表示转换得到的十进制数，保证答案不超过 2147483647。【输入样例输入样例】2100110【输出样例输出样例】38高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】读入读入 n 和和 x，根据，根据 n 和和 x 的位数，分别求出的位数，分别

7、求出 x 的每一位对应的的每一位对应的“权值权值”，然后穷举每一位，将它乘以该位对应的权值，累加，然后穷举每一位，将它乘以该位对应的权值，累加便可得到结果。便可得到结果。更高效、更简洁的算法是采用更高效、更简洁的算法是采用“秦九韶公式秦九韶公式”。对于样例对于样例输入，可以这样计算：输入，可以这样计算：(1*2)0)*2+0)*2+1)*2+1)*2+0=38 具体实现采用具体实现采用“迭代法迭代法”，用一个变量不断乘以，用一个变量不断乘以n，再加，再加上下一位上下一位xi。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)/p9-1-1#includeusing names

8、pace std;int main()freopen(”change.in”,”r”,stdin);freopen(”change.out”,”w”,stdout);int n,ans=0,i=0;char s32;scanf(”%dn”,&n);while(si=getchar()!=n)ans=ans*n+(si-48);i+;printf(”%dn”,ans);return 0;高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例2、汽车牌照、汽车牌照【问题描述问题描述】小小 Y 最近发现街上的汽车越来越多了，作为汽车的重要标志最近发现街上的汽车越来越多了，作为汽车的

9、重要标志汽车汽车牌照也是越来越不够用了，已经从以前的十进制发展到三十六进制了，牌照也是越来越不够用了，已经从以前的十进制发展到三十六进制了，以前的一个汽车牌照以前的一个汽车牌照“苏苏 D88888”，现在的牌照，现在的牌照“苏苏 D0YY11”。小小 Y 突发其想，想知道他看到的大量汽车牌照中最近的两个汽车牌照突发其想，想知道他看到的大量汽车牌照中最近的两个汽车牌照相差多少？相差多少？【输入格式输入格式】若干行若干行(不超过不超过 500000 行行)，每行为一个汽车牌照。，每行为一个汽车牌照。每个汽车牌照为一个每个汽车牌照为一个 7 位的字符串，格式为位的字符串，格式为 SD，其中一个，其中

10、一个 表示一个表示一个 09 或或AZ，所涉及的字母均为大写。，所涉及的字母均为大写。【输出格式输出格式】一行一个数，表示最接近的两个汽车牌照之间的差值，要求为十进制数。一行一个数，表示最接近的两个汽车牌照之间的差值，要求为十进制数。【输入样例输入样例】SD12345SD88888SD22222SD99999【输出样例输出样例】1678245高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例3、数列数列【问题描述问题描述】给定一个正整数给定一个正整数 k，把所有，把所有 k 的方幂及所有有限个互不相等的方幂及所有有限个互不相等的的 k 的方幂之和构成一个递增的序列。例如，

11、当的方幂之和构成一个递增的序列。例如，当 k=3 时，时，这个序列是：这个序列是：1，3，4，9，10，12，13，请求出这个序列的第请求出这个序列的第 n 项的值项的值(用十进制数表示用十进制数表示)。【输入格式输入格式】一行两个正整数一行两个正整数 k 和和 n，之间用一个空格隔开，且，之间用一个空格隔开，且 3k15，10n1000。【输出格式输出格式】一行一个正整数。一行一个正整数。【输入样例输入样例】3 100【输出样例输出样例】981高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+

12、)第第 2 课课 高精度运算高精度运算学习目标学习目标1.体会高精度运算的应用场合。体会高精度运算的应用场合。2.熟练掌握高精度加法和乘法运算。熟练掌握高精度加法和乘法运算。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)高精度运算高精度运算在编程进行数值运算时，有时会遇到运算的精度要求特在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值。这种情况下，就别大，远远超过各种数据类型的极限值。这种情况下，就需要进行需要进行“高精度运算高精度运算”。

13、高精度运算首先要处理好数据的接收和存储问题，其次高精度运算首先要处理好数据的接收和存储问题，其次要处理好运算过程中的要处理好运算过程中的“进位进位”和和“借位借位”问题。问题。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例1、高精度、高精度加法加法【问题描述问题描述】输入两个输入两个 1000 位以内的正整数，输出它们的和。位以内的正整数，输出它们的和。【输入样例输入样例】123456789987654321【输出样例输出样例】1111111110高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】用字符串的方式读入两个高精度数，转

14、存到两个整型数组用字符串的方式读入两个高精度数，转存到两个整型数组 a 和和 b 中，如图中，如图 9.2-1 所示，模拟加法的过程，从低位所示，模拟加法的过程，从低位(第第 0 位位)开始对应位开始对应位 ai 和和 bi 相加，同时处理进位，结果存储到另相加，同时处理进位，结果存储到另一个数组一个数组 c 中。最后，从高位到低位输出中。最后，从高位到低位输出 ci。参考程序见教材参考程序见教材329页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例2、高精度乘法高精度乘法【问题描述问题描述】输入两个输入两个 100 位以内的正整数，输出它们的乘积。位以内的正整

15、数，输出它们的乘积。【输入样例输入样例】123456789987654321【输出样例输出样例】121932631112635269高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】如图如图 9.2-2 所示，模拟所示，模拟“竖式竖式”乘法的过程，用一个数乘法的过程，用一个数的每一位的每一位 ai(从低位开始从低位开始)逐位与另一个数的每一位逐位与另一个数的每一位 bj 相相乘，结果存储到乘，结果存储到 ci+j 位，同时处理好进位。位，同时处理好进位。参考程序见教材参考程序见教材330页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(

16、C+)例例3、n!的精确值的精确值【问题描述问题描述】输入输入 n，输出，输出 n!的精确值，的精确值，n!=123n，1n2 时，存在递推关系：时，存在递推关系：f(n)=f(n-1)+f(n-2)。在递推问题模型中，每个数据项都与它前面的若干个在递推问题模型中，每个数据项都与它前面的若干个数据项（或后面的若干个数据项）存在一定的关联，这种关数据项（或后面的若干个数据项）存在一定的关联，这种关联一般是通过一个联一般是通过一个“递推关系式递推关系式”来描述的。求解问题时，来描述的。求解问题时，需要从初始的一个或若干数据项出发，通过递推关系式逐步需要从初始的一个或若干数据项出发，通过递推关系式逐

17、步推进，从而推导计算出最终结果。这种求解问题的方法叫推进，从而推导计算出最终结果。这种求解问题的方法叫“递推法递推法”。其中，初始的若干数据项称为。其中，初始的若干数据项称为“递推边界递推边界”。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)递推递推解决递推问题有三个重点：建立正确的递推关系式；分解决递推问题有三个重点：建立正确的递推关系式；分析递推关系式的性质；根据递推关系式编程求解。析递推关系式的性质；根据递推关系式编程求解。递推法分为递推法分为“顺推顺推”和和“倒推倒推”两类模型。所谓顺推，两类模型。所谓顺推，就是从问题的边界条件就是从问题的边界条件(初始状态初始状

18、态)出发，通过递推关系式依出发，通过递推关系式依次从前往后递推出问题的解；所谓倒推，就是在不知道问题次从前往后递推出问题的解；所谓倒推，就是在不知道问题的边界条件的边界条件(初始状态初始状态)下，从问题的最终解下，从问题的最终解(目标状态或某个目标状态或某个中间状态中间状态)出发，反过来推导问题的初始状态。出发，反过来推导问题的初始状态。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例1、铺瓷砖、铺瓷砖【问题描述问题描述】用红色的用红色的 11 和黑色的和黑色的 22 两种规格的瓷砖不重叠地铺满两种规格的瓷砖不重叠地铺满 n3 的路面，求出有多少种不同的铺设方案。的路面

19、，求出有多少种不同的铺设方案。【输入格式输入格式】一行一个整数一行一个整数 n，0n1000。【输出格式输出格式】一行一个整数，为铺设方案的数量模一行一个整数，为铺设方案的数量模12345的结果。的结果。【输入样例输入样例】2【输出样例输出样例】3高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】用用 f(n)表示表示 n3 的路面有多少种不同的铺设方案。把路面的路面有多少种不同的铺设方案。把路面看成看成 n 行行 3 列，则问题可以分成两种情况考虑，一种是最列，则问题可以分成两种情况考虑，一种是最后一行用后一行用 3 块块 11 的瓷砖铺设；另一种是最后

20、两行用的瓷砖铺设；另一种是最后两行用 1 块块 22 和和 2 块块 11 的瓷砖铺设的瓷砖铺设(最后两行就有两种铺法最后两行就有两种铺法)，第，第一种铺法就转换为一种铺法就转换为 f(i-1)的问题了，第二种铺法就转换成的问题了，第二种铺法就转换成 f(i-2)的问题了。根据加法原理，得到的递推关系式为的问题了。根据加法原理，得到的递推关系式为 f(i)=f(i-1)+f(i-2)2，边界为，边界为 f(0)=1，f(1)=1。参考程序见教材参考程序见教材350-351页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例2、彩带、彩带【问题描述问题描述】一中一中

21、90 周年校庆，小林准备用一些白色、蓝色和红色周年校庆，小林准备用一些白色、蓝色和红色的彩带来装饰学校超市的橱窗，他希望满足以下两个条件：的彩带来装饰学校超市的橱窗，他希望满足以下两个条件：(1)相同颜色的彩带不能放在相邻的位置；相同颜色的彩带不能放在相邻的位置；(2)一条蓝色的彩带必须放在一条白色的彩带和一条红色的一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。彩带中间。现在，他想知道满足要求的放置彩带的方案数有多少种。现在，他想知道满足要求的放置彩带的方案数有多少种。例如，如图例如，如图 9.4-1 所示为橱窗宽度所示为橱窗宽度n=3 的所有放置方案，共的所有放置方案，共 4 种

22、。种。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【输入格式输入格式】一行一个整数一行一个整数 n，表示橱窗宽度，表示橱窗宽度(或者说彩带数目或者说彩带数目)。【输出格式输出格式】一行一个整数，表示装饰橱窗的彩带放置方案数。一行一个整数，表示装饰橱窗的彩带放置方案数。【样例输入样例输入】3【样例输出样例输出】4【数据规模数据规模】对对 30%的数据满足：的数据满足：1n15。对对 100%的数据满足：的数据满足：1n45。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】用用 f(i)表示宽度为表示宽度为 i 的橱窗的橱窗(或或 i

23、 条彩带条彩带)的合法放置方案的合法放置方案数，则数，则 f(1)=2，f(2)=2，f(3)=4，f(4)=6，f(5)=10，不不难发现，答案就是初始值不一样的斐波那契数列，所以，用难发现，答案就是初始值不一样的斐波那契数列，所以，用递推法就可以很方便地求出递推法就可以很方便地求出 f(n)。参考程序见教材参考程序见教材352页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例3、城市路径城市路径【问题描述问题描述】地图上有地图上有 n 个城市，一只奶牛要从个城市，一只奶牛要从 1 号城市开始依次经号城市开始依次经过这些城市，最终到达过这些城市，最终到达 n 号

24、城市。但是这只奶牛觉得这样太号城市。但是这只奶牛觉得这样太无聊了，所以它决定跳过其中的一个城市无聊了，所以它决定跳过其中的一个城市(但是不能跳过但是不能跳过 1 号号和和 n 号城市号城市)，使得它从，使得它从 1 号城市开始，到达号城市开始，到达 n 号城市所经过号城市所经过的总距离最小。假设每一个城市的总距离最小。假设每一个城市 i 都有一个坐标都有一个坐标(x i，y i)，从从(x 1，y 1)的城市的城市 1 到到(x 2，y 2)的城市的城市 2 之间的距离为之间的距离为|x 1-x 2|+|y 1-y 2|。【输入格式输入格式】第第 1 行行 1 个正整数个正整数 n，表示城市个

25、数。，表示城市个数。接下来的接下来的 n 行，每行行，每行 2 个数个数 x i 和和 y i，表示城市，表示城市 i 的坐标。的坐标。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【输出格式输出格式】一行一个数，使得它从一行一个数，使得它从1号城市开始，跳过某一个城市，到达号城市开始，跳过某一个城市，到达n号城市所经过的最小总距离。号城市所经过的最小总距离。【输入样例输入样例】40 08 311-110 0【输出样例输出样例】14【样例说明样例说明】跳过跳过 2 号城市。号城市。【数据规模数据规模】对于对于 40%的数据满足：的数据满足：n1000。对于对于 100%的

26、数据满足：的数据满足：3n100000，-1000 x i，y i 1000。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】设设f(i)为从城市为从城市1依次跳到城市依次跳到城市i的距离之和，设的距离之和，设g(i)为从城市为从城市i依次跳到城市依次跳到城市n的距离之和，则问题的答案为的距离之和，则问题的答案为 minf(i-1)+g(i+1)+disi-1,i+1。其中，。其中，dis i-1,i+1表示城市表示城市 i-1 到城市到城市 i+1的曼哈顿距离，的曼哈顿距离，f(i)和和 g(i)都可以用递推来预处理求出：都可以用递推来预处理求出：f(

27、i)=f(i-1)+disi-1,i，g(i)=g(i+1)+disI,i+1。也可以设也可以设 f(i)表示从城市表示从城市 1 依次跳到城市依次跳到城市 n，且跳过城市，且跳过城市 i 的的距离之和，距离之和，sum 表示表示从城市表示表示从城市 1 依次跳到城市依次跳到城市 n 的距离之的距离之和，则和，则 f(i)=minsumdisI,i-1-disi+1.i+disi-1,i+1。参考程序见教材参考程序见教材353页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例4、穿越沙、穿越沙漠漠【问题描述问题描述】一辆卡车欲穿过一辆卡车欲穿过 1000 千米的沙

28、漠，卡车耗油为千米的沙漠，卡车耗油为 1 升升/千米，千米，卡车总载油能力为卡车总载油能力为 500 升。显然，卡车装一次油是过不了沙升。显然，卡车装一次油是过不了沙漠的。因此，司机必须设法在沿途建立几个贮油点，使卡车漠的。因此，司机必须设法在沿途建立几个贮油点，使卡车能顺利穿越沙漠。试问：司机如何建立这些贮油点？每一贮能顺利穿越沙漠。试问：司机如何建立这些贮油点？每一贮油点应存多少油，才能使卡车以消耗最少油点应存多少油，才能使卡车以消耗最少汽油的代价通过沙漠？结果保留小数点后两位。汽油的代价通过沙漠？结果保留小数点后两位。编程计算及打印建立的贮油点序号，各贮油点距沙漠边沿出编程计算及打印建立

29、的贮油点序号，各贮油点距沙漠边沿出发的距离以及存油量，格式如下：发的距离以及存油量，格式如下：No.Distance(km)Oil(litre)1 .2 .3 .高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】因为从起始点出发无法确定第因为从起始点出发无法确定第 1 个贮油点的位置及贮油量，个贮油点的位置及贮油量，所以顺推行不通。下面换个思路倒推试试看。先从终点出发所以顺推行不通。下面换个思路倒推试试看。先从终点出发倒推最后一个贮油点的位置及贮油量，然后再把最后一个贮倒推最后一个贮油点的位置及贮油量，然后再把最后一个贮油点作为终点，倒推倒数第油点作为终点

30、，倒推倒数第 2 个贮油点的位置及贮油个贮油点的位置及贮油量，量，设设 dis(i)表示第表示第 i 个贮油点至终点个贮油点至终点(i=0)的距离，的距离，oil(i)表示第表示第 i 个贮油点的贮油量。从终点向起始点倒推，逐一求个贮油点的贮油量。从终点向起始点倒推，逐一求出每个贮油点的位置及存油量，如图出每个贮油点的位置及存油量，如图 9.4-2 所示。所示。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)从贮油点从贮油点 i 向贮油点向贮油点 i+1 倒推的策略是，卡车在点倒推的策略是，卡车在点 i 和点和点 i+1 间往返若干次。卡车每次返回间往返若干次。卡车每次返回

31、i+1 处时正好耗尽处时正好耗尽 500 升汽升汽油，而每次从油，而每次从 i+1 处出发时又必须装满处出发时又必须装满 500 升汽油。两点之间升汽油。两点之间的距离必须满足在耗油最少的条件下使的距离必须满足在耗油最少的条件下使 i 点贮存点贮存 i500 升汽升汽油的要求油的要求(0in-1)，根据贪心思想，第一个贮油点，根据贪心思想，第一个贮油点 i=1 应距终应距终点点 i=0 处处 500 千米且在该处贮藏千米且在该处贮藏 500 升汽油，这样才能保证卡升汽油，这样才能保证卡车能由车能由 i=1 处到达终点处到达终点 i=0 处，这就是说，处，这就是说，dis(1)=500，oil(

32、1)=500。而为了在。而为了在 i=1 处贮藏处贮藏 500升汽油，卡车至少从升汽油，卡车至少从 i=2 处开两趟满载油的车至处开两趟满载油的车至 i=1 处，所以处，所以 i=2 处至少存贮处至少存贮 2500 升汽油，即升汽油，即 oil(2)=5002=1000，另外再加上从，另外再加上从 i=1 返回至返回至 i=2 处的一趟空载，合计往返处的一趟空载，合计往返 3 次，往返路程的耗油量按最省次，往返路程的耗油量按最省要求只能为要求只能为500升，即升，即d 1，2 =500/3，所以，所以dis(2)=dis(1)+d 1，2 =dis(1)+500/3。高等教育出版社高等教育出版

33、社信息学奥赛课课通信息学奥赛课课通(C+)同理，为了在同理，为了在i=2处贮存处贮存1000升汽油，卡车至少从升汽油，卡车至少从i=3处处开开3趟满载油的车至趟满载油的车至i=2处。所以，处。所以，i=3 处至少存贮处至少存贮 3500 升升汽油，即汽油，即 oil(3)=5003=1500，加上，加上 i=2 至至 i=3 处的处的 2 趟返趟返程空车，合计程空车，合计 5 次，路途耗油量也应该是次，路途耗油量也应该是 500 升，即升，即 d 2，3 =500/5，所以，所以 dis(3)=dis(2)+d 2，3 =dis(2)+500/5。依次类推，为了在依次类推，为了在 i=k 处贮

34、藏处贮藏 k500 升汽油，卡车至升汽油，卡车至少从少从 i=k+1 处开处开 k 趟满载车至趟满载车至 i=k 处，即处，即oil(k+1)=(k+1)500=oil(k)+500，加上从，加上从 i=k 返回返回 i=k+1 的的 k-1 趟返程空车，合计趟返程空车，合计 2*k-1 次，总耗油量按最省要求为次，总耗油量按最省要求为 500 升，即升，即 d k，k+1 =500/(2k-1)，所以，所以 dis(k+1)=dis(k)+d k，k+1 =dis(k)+500/(2k-1)。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)最后一个贮油点的位置如图最后一个

35、贮油点的位置如图 9.4-4 所示。所示。最后，最后，i=n至起始点的距离为至起始点的距离为1000-dis(n)，oil(n)=500n。为了在为了在i=n处取得处取得n500升汽油，卡车至少从始点开升汽油，卡车至少从始点开n+1次满次满载车至载车至i=n，加上从，加上从i=n返回起始点的返回起始点的n趟返程空车，合计趟返程空车，合计2n+1次，总耗油量应正好为次，总耗油量应正好为(1000-dis(n)(2n+1)，即起，即起始点藏油为始点藏油为 oil(n)+(1000-dis(n)(2n+1)。参考程序见教材参考程序见教材355页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学

36、奥赛课课通(C+)例例5、偶数个、偶数个3【问题描述问题描述】编程求出所有的编程求出所有的 n 位数中，有多少个数中有偶数个数字位数中，有多少个数中有偶数个数字 3。【输入格式输入格式】一行一个正整数一行一个正整数 n，0n1的宫殿，将其分解的宫殿，将其分解成成4个个k/2大小的宫殿，先看一下公主站的位置是属于哪一块，大小的宫殿，先看一下公主站的位置是属于哪一块，因为根据公主所在的位置，我们可以确定中间位置所放的因为根据公主所在的位置，我们可以确定中间位置所放的毯子类型，再递归处理公主所站的那一块，直到出现边界毯子类型，再递归处理公主所站的那一块，直到出现边界条件条件k=1的情况，然后在公主边

37、上铺上一块合适的地毯，递的情况，然后在公主边上铺上一块合适的地毯，递归结束。归结束。参考程序见教材参考程序见教材368-370页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)3.分治与递归的应用举例分治与递归的应用举例分治与递归的思想简单易懂，但是如果采用直接递归来分治与递归的思想简单易懂，但是如果采用直接递归来实现，存在着大量实现，存在着大量“冗余冗余”计算，效率比较低。一般可以计算，效率比较低。一般可以采用以下几种思路进行优化，一是将递归公式转化成递推采用以下几种思路进行优化，一是将递归公式转化成递推算法实现；二是采用所谓的算法实现；二是采用所谓的“记忆化记忆化

38、”方法，设置一个数方法，设置一个数组组 f 记录每一项的值，第一次计算出第记录每一项的值，第一次计算出第 i 项的值项的值 f（i），就），就同时存储到数组同时存储到数组 fi中，避免以后再次递归调用中，避免以后再次递归调用 f（i），），从而减少冗余计算；三是定义一个手工栈保存和恢复递归从而减少冗余计算；三是定义一个手工栈保存和恢复递归过程中的现场信息，模拟递归调用，其缺点是减低了程序过程中的现场信息，模拟递归调用，其缺点是减低了程序的可读性。的可读性。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例6、平面、平面分割分割【问题描述问题描述】平面上有平面上有 n 条封

39、闭曲线，其中任何两条封闭曲线恰好相交条封闭曲线，其中任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，计算这些于两点，且任何三条封闭曲线不相交于同一点，计算这些封闭曲线把平面分割成的区域个数。封闭曲线把平面分割成的区域个数。【输入样例输入样例】3【输出样例输出样例】8高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【问题分析问题分析】设设 f(n)为为 n 条封闭曲线把平面分割成的区域个数。如图条封闭曲线把平面分割成的区域个数。如图 9.5-4 所示，所示，f(1)=2，f(2)=4，f(3)=8，F(4)=14，f(5)数起来比较困难，但是也能数得出数起来

40、比较困难，但是也能数得出 f(5)=22。找规律发现，找规律发现，f(2)-f(1)=2，f(3)-f(2)=4，f(4)f(3)=6，f(5)-f(4)=8猜想结论：猜想结论：f(n)-f(n-1)=2(n-1)，即递归公式为，即递归公式为 f(n)=f(n-1)+2(n-1)，边界条件为，边界条件为 f(1)=2。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)可以简单证明以上猜想：当平面上已有可以简单证明以上猜想：当平面上已有 n-1 条封闭曲线将平面分割条封闭曲线将平面分割成成 f（n-1）个区域后，第）个区域后，第n 条封闭曲线每与曲线相交一次，就会增加条封闭曲线

41、每与曲线相交一次，就会增加 2 个区域，因为平面上已有了个区域，因为平面上已有了 n-1 条封闭曲线，且第条封闭曲线，且第n 条曲线与已有的每条曲线与已有的每一条封闭曲线恰好相交于两点，且不会与任何两条曲线交于同一点，故一条封闭曲线恰好相交于两点，且不会与任何两条曲线交于同一点，故平面上一共增加平面上一共增加 2（n-1）个区域，加上已有的）个区域，加上已有的 f（n-1）个区域，一共）个区域，一共有有 f（n-1）+2（n-1）个区域。）个区域。如果不满足于以上递推算法，可以进一步推出其如果不满足于以上递推算法，可以进一步推出其“通项公式通项公式”：f（n）=f（n-1）+2（n-1）f（n

42、-1）=f（n-2）+2（n-2）f（n-2）=f（n-3）+2（n-3）f（2）=f（1）+2把以上把以上 n-1 个等式的左边和右边分别累加，再约去相同项，得到：个等式的左边和右边分别累加，再约去相同项，得到：f（n）=f（1）+2（1+2+3+（n-1）=n2-n+2。参考程序见教材参考程序见教材371页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例7、斐波那契、斐波那契数列数列【问题描述问题描述】输入输入 n，1n1000，输出斐波那契数列第，输出斐波那契数列第 n 项模项模 9997 的值。的值。【输入样例输入样例】10【输出样例输出样例】55【问题分

43、析问题分析】直接递归求解存在着大量的冗余计算，利用数学知识可以直接递归求解存在着大量的冗余计算，利用数学知识可以计算出时间复杂度为计算出时间复杂度为 O(1+sqrt(5)/2)n)，显然超时严重。，显然超时严重。因此，可以采用因此，可以采用“记忆化记忆化”的方法进行算法优化。的方法进行算法优化。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)/p9-5-7#includeusing namespace std;int n,a1001;int f(int x)if(x=1|x=2)return 1;if(ax!=-1)return ax;else return ax=(f(

44、x-1)+f(x-2)%9997);int main()freopen(“fib.in“,“r“,stdin);freopen(“fib.out“,“w“,stdout);cin n;for(int i=1;i=n;i+)ai=-1;cout f(n)B，一般情况，一般情况下有下有 A+BB+A。但是，当。但是，当 A=B+C 时，按字符串的大小定时，按字符串的大小定义有义有 AB，此时有可能出现，此时有可能出现 A+BB+A 的情况。如的情况。如 A=121 ，B=12 ，则，则 A+B=12112 ，B+A=12121 ，所以所以A+BB。按这一定义将所有的数字字符串从大到小排序后连接起来

45、按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是问题的解。排序时先将所有字符所得到的数字字符串即是问题的解。排序时先将所有字符串中的最大值选出来存在数组的第一个元素中，再从第二串中的最大值选出来存在数组的第一个元素中，再从第二至最后一个元素中最大的字符串选出来存在数组的第二个至最后一个元素中最大的字符串选出来存在数组的第二个元素中，直到从最后两个元素中选出最大的字符串存在数元素中，直到从最后两个元素中选出最大的字符串存在数组的倒数第二个元素中为止。组的倒数第二个元素中为止。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)需要说明的是，按本题定义的字符

46、串的大小定义是有序需要说明的是，按本题定义的字符串的大小定义是有序的，即如果的，即如果 A+BB+A，B+CC+B，则一定有，则一定有 A+CC+A。证明方法如下：证明方法如下：引理：记引理：记 nA 为为 n 个字符串个字符串 A 按字符串加法运算规则相加之按字符串加法运算规则相加之和，则由和，则由 A+BB+A 可推导出可推导出nA+mBmB+nA，其中，其中 m，n 为任意的自然数。用反证法可证明反过来也成立。为任意的自然数。用反证法可证明反过来也成立。设设 la 为字符串为字符串 A 的长度，的长度，lb 为字符串为字符串 B 的长度，的长度，lc 为字符为字符串串 C 的长度，再设的

47、长度，再设 n=lb*lc，m=la*lc，k=la*lb，则，则 nA，mB，kC 三三 个个 字字 符符 串串 等等 长，根长，根 据据 引引 理理 有：有：nA+mBmB+nA，mB+kCkC+mB，从而得到，从而得到 nAmBkC，所以所以 nA+kCkC+nA，A+CC+A。要使要使 n 个字符串拼接起来后得到一个最大的字符串和式，个字符串拼接起来后得到一个最大的字符串和式，则一定要将按上述定义最大的字符串放在第一个，否则必则一定要将按上述定义最大的字符串放在第一个，否则必可通过将最大的字符串与它左侧的字符串交换得到更大的可通过将最大的字符串与它左侧的字符串交换得到更大的字符串和式。

48、参考程序见教材字符串和式。参考程序见教材386页。页。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)（2）构造法构造法根据描述的算法，用贪心的策略依次构造出一个解，可根据描述的算法，用贪心的策略依次构造出一个解，可证明一定是合法的解。即用贪心法找可行解。证明一定是合法的解。即用贪心法找可行解。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例例5、取火柴游戏、取火柴游戏【问题描述问题描述】输入输入 k 及及 k 个整数个整数 n 1，n 2，n k，表示有，表示有 k 堆火柴堆火柴棒，第棒，第 i 堆火柴棒的根数为堆火柴棒的根数为 n i。接着便是和计

49、算机对弈游。接着便是和计算机对弈游戏，取火柴的规则如下：每次可以从一堆中取走若干根火戏，取火柴的规则如下：每次可以从一堆中取走若干根火柴，也可以将一堆全部取走，但不允许跨堆取，也不允许柴，也可以将一堆全部取走，但不允许跨堆取，也不允许不取。不取。谁取走最后一根火柴算谁胜利。谁取走最后一根火柴算谁胜利。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)例如，例如，k=2，n 1=n 2=2，A 代表你，代表你，P 代表计算机，若代表计算机，若决定决定 A 先取：先取：A：（2，2）（1，2）/从一堆中取一根从一堆中取一根P：（1，2）（1，1）/从另一堆中取一根从另一堆中取一根

50、A：（1，1）（1，0）P：（1，0）（0，0）/P 胜利胜利如果决定如果决定 A 后取：后取：P：（2，2）（2，0）A：（2，0）（0，0）/A 胜利胜利又如又如 k=3，n 1=1，n 2=2，n 3=3，A 决定后取：决定后取：P：（1，2，3）（0，2，3）A：（0，2，3）（0，2，2）A 已将游戏归结为（已将游戏归结为（2，2）的情况，不管）的情况，不管 P 如何取如何取 A 都都必胜。必胜。高等教育出版社高等教育出版社信息学奥赛课课通信息学奥赛课课通(C+)【输入样例输入样例】33 6 9【输出样例输出样例】4 3/表示第表示第 1 次从第次从第 3 堆取堆取 4 个出来必胜个