计算基础教程 8

授课内容简单算法学时2教学目标知识目标掌握整除、模除运算的规则与用法理解数字分离、数字合成的算法原理掌握素数判断、埃氏筛法基本思路掌握辗转相除法、数组下标巧用与桶排序原理能力目标提升数值类问题规律观察与归纳建模能力强化简单算法流程拆解与逻辑分析能力培养多类基础算法对比择优与应用实践能力重点与难点重点数字分离与数字合成基础算法流程素数判断思路与埃氏筛选法操作步骤辗转相除法求解最大公约数流程数组下标巧用思想及桶排序实现方法难点结合循环，实现多位数字自动分离统计理解筛法优化逻辑与桶排序适用边界教学内容第一部分：课程导入1、点名与签到2、课程重要性阐述本章承接算法基础理论，转入实操简单算法训练数值拆分、合成是编程刷题的通用底层基本功素数、公约数题型，是考试与竞赛高频考点内容巧用数组下标、桶排序，培养高效解题思维方式本章易上手、见效快，增强学生算法学习信心第二部分：新课讲解一、数字分离与合成1、分离原理所谓的数字分离，就是将一个整数，分解出其中的每一位。在C++中，数字分离依赖于二个除法运算符：整除和模除。实例inti=123,a,b,c;a=i%10; //得到个位数：3c=i/100; //得到百位数：1b=i%100/10; //得到十位数：2cout<<a<<""<<b<<""<<c<<endl;2、合成原理所谓的数字合成，就是已有整数的各位数字，将其合并成为一个整数。例如：已知百位数字为1，十位数字为2，个位数字为3，要求将其合成为一个整数123。算法原理为：((0*10+1)*10+2)*10+3。实例已有二个数字字符串，例如：“1234”和“5678”，试输出其和。chars1[]="1234";chars2[]="5678";intp1=0,p2=0; for(inti=0;s1[i]!='\0';i++) p1=p1*10+s1[i]-'0';for(inti=0;s2[i]!='\0';i++) p2=p2*10+s2[i]-'0';cout<<p1+p2<<endl;3、例题：计数问题【题目描述】试计算在区间1到n的所有整数中，数字x(0≤x≤9)共出现了多少次？例如，在1到11中，即在1，2，3，4，5，6，7，8，9，10，11中，数字1出现了4次。【程序】详见课本二、素数判断1、素数及其判断要判断n是否为素数，可以根据定义，让n除以2～n-1之间的每一个数，如果均不能整除，n就是素数。上述方案还可以优化为：让n除以2～n/2或者2～之间的每一个数。2、批量求素数概述所谓批量求素数，就是要找出某个范围之内的全部素数。比如：求2～100之间的全部素数。批量求素数的主要方法有：埃氏筛选法（埃拉托斯特尼筛法）和线性筛选法。实例用筛选法求出100以内的全部素数，并按每行五个数显示。为了使用埃氏筛选法求素数，我们要先定义一个数组：boola[101];在此数组中，我们使用a[i]的值表示i是否为素数。原理见课本介绍，整个求解过程如下图所示：三、最大公约数求最大公约数有很多种方法，最常用的是辗转相除法，也称为欧几里德算法。辗转相除法的具体步骤如下：①输入两个正整数m和n。②求出m除以n的余数r，即r=m%n。③如果余数r=0，则n就是最大公约数，结束。如果r≠0，则令m=n，n=r。转到第②步重新执行。④重复上述步骤，直到余数为0，此时的除数n就是最大公约数。四、桶排序1、概述对于正整数的排序，有一种很简单的排序方法：桶排序。2、桶排序原理第1步：准备“桶”如果要排序的这批数据范围在1～100之间，我们需要先准备100个桶（就是定义相应容量的数组），并且将其编号为1～100。第2步：将数据放入“桶”内检查待排序的数据，如果某个数据值为x，就将其放入编号为x的桶中。例如：如果某个数据值为1，就将其放入1号桶内；如果值为2，就将其放入2号桶内；依次类推。第3步：按从小到大（或从大到小）的顺序，依次将“桶”内数据输出。先检查1号桶：如果里面没有数据，则不输出；如果里面有一个数据，则输出则输出一个“1”；如果里面有二个数据，则输出二个“1”；依次类推。处理完1号桶后，按同样的规则依次处理2～100号桶。3、例题：考