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

高等教育出版社 为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第 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，再加上下一位xi高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能/p9-1-1#includeusing namespace 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 最近发现街上的汽车越来越多了，作为汽车的重要标志汽车牌照也是越来越不够用了，已经从以前的十进制发展到三十六进制了，以前的一个汽车牌照“苏 D88888”，现在的牌照“苏 D0YY11”。

小 Y 突发其想，想知道他看到的大量汽车牌照中最近的两个汽车牌照相差多少？【输入格式】若干行(不超过 500000 行)，每行为一个汽车牌照每个汽车牌照为一个 7 位的字符串，格式为 SD，其中一个 表示一个 09 或AZ，所涉及的字母均为大写输出格式】一行一个数，表示最接近的两个汽车牌照之间的差值，要求为十进制数输入样例】SD12345SD88888SD22222SD99999【输出样例】1678245高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例3、数列【问题描述】给定一个正整数 k，把所有 k 的方幂及所有有限个互不相等的 k 的方幂之和构成一个递增的序列例如，当 k=3 时，这个序列是：1，3，4，9，10，12，13，请求出这个序列的第 n 项的值(用十进制数表示)输入格式】一行两个正整数 k 和 n，之间用一个空格隔开，且 3k15，10n1000输出格式】一行一个正整数输入样例】3 100【输出样例】981高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能实践巩固高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能第 2 课 高精度运算学习目标1. 体会高精度运算的应用场合。

2. 熟练掌握高精度加法和乘法运算高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能高精度运算在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值这种情况下，就需要进行“高精度运算”高精度运算首先要处理好数据的接收和存储问题，其次要处理好运算过程中的“进位”和“借位”问题高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例1、高精度加法【问题描述】输入两个 1000 位以内的正整数，输出它们的和输入样例】123456789987654321【输出样例】1111111110高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【问题分析】用字符串的方式读入两个高精度数，转存到两个整型数组 a 和 b 中，如图 9.2-1 所示，模拟加法的过程，从低位(第 0 位)开始对应位 ai 和 bi 相加，同时处理进位，结果存储到另一个数组 c 中。

最后，从高位到低位输出 ci参考程序见教材329页高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例2、高精度乘法【问题描述】输入两个 100 位以内的正整数，输出它们的乘积输入样例】123456789987654321【输出样例】121932631112635269高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【问题分析】 如图 9.2-2 所示，模拟“竖式”乘法的过程，用一个数的每一位 ai (从低位开始)逐位与另一个数的每一位 bj 相乘，结果存储到 ci+j 位，同时处理好进位参考程序见教材330页高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例3、n! 的精确值【问题描述】输入 n，输出 n! 的精确值，n!=123n，1n2 时，存在递推关系：f (n) = f(n-1) + f(n-2)。

在递推问题模型中，每个数据项都与它前面的若干个数据项（或后面的若干个数据项）存在一定的关联，这种关联一般是通过一个“递推关系式”来描述的求解问题时，需要从初始的一个或若干数据项出发，通过递推关系式逐步推进，从而推导计算出最终结果这种求解问题的方法叫“递推法”其中，初始的若干数据项称为“递推边界”高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能递推解决递推问题有三个重点：建立正确的递推关系式；分析递推关系式的性质；根据递推关系式编程求解递推法分为“顺推”和“倒推”两类模型所谓顺推，就是从问题的边界条件(初始状态)出发，通过递推关系式依次从前往后递推出问题的解；所谓倒推，就是在不知道问题的边界条件(初始状态)下，从问题的最终解(目标状态或某个中间状态)出发，反过来推导问题的初始状态高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能例1、铺瓷砖【问题描述】用红色的 11 和黑色的 22 两种规格的瓷砖不重叠地铺满 n3 的路面，求出有多少种不同的铺设方案。

输入格式】一行一个整数 n，0n1000输出格式】一行一个整数，为铺设方案的数量模12345的结果输入样例】2【输出样例】3高等教育出版社信息学奥赛课课通(C+)为深入学习习近平新时代中国特色社会主义思想和党的十九大精神,贯彻全国教育大会精神,充分发挥中小学图书室育人功能【问题分析】用 f(n) 表示 n3 的路面有多少种不同的铺设方案把路面看成 n 行 3 列，则问题可以分成两种情况考虑，一种是最后一行用 3 块 11 的瓷砖铺设；另一种是最后两行用 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、彩带【问题描述】 一中 90 周年校庆，小林准备用一些白色、蓝色和红色的彩带来装饰学校超市的橱窗，他希望满足以下两个条件：(1) 相同颜色的彩带不能放在相邻的位置；(2) 一条蓝色的彩带必须放在一条白色的彩带和一条红色的彩带中间。

现在，他想知道满足要求的。