§5·5妙趣横生的算法－递归
★教学目标
知识与技能：
1、理解什么是递归算法，用递归算法的思想分析问题
2、能够应用自定义函数方法实现递归算法的编程
过程与方法：参与讨论，通过思考、动手操作，体验递归算法的方法
情感态度与价值：结合实例，激发数学建模的意识，培养多维度思考问题和解决问题，激发审美情感。
★重点与难点
重点：理解什么是递归算法，会用递归算法思想分析问题；应用自定义函数方法实现递归算法的编程
难点：应用自定义函数方法实现递归算法的编程
学习思维导图：
一、认识递归：
1、小游戏：报数
2、头脑风暴：举出你身边的递归的例子
二、新知导学：
问题：有甲、乙、丙、丁四人，从甲开始到丁（甲＞乙＞丙＞丁），一个比一个大1岁，已知丁10岁，问甲几岁？
1．分析问题：这是递归法的一道非常典型的题目——因为我们可以很显然知道：假设要计算甲的年龄，那么必须知道乙的年龄；同样，算乙的必须知道丙的，算丙的必须知道丁的，因为丁已知，自然可以往前推算了。现在假设有一个数学模型（函数）可以计算出他们各自的年龄（为方便我们给他们编号—甲＝1，乙＝2，丙＝3，丁＝4），那么存在一个F(X)函数，X 表示某人的编号，其规律如下：
F(1)=F(2)+1
F(2)=F(3)+1
F(3)=F(4)+1
F(4)=10
这种按同一方法把问题的计算规模逐步变小的过程叫做“递归的展开”，然后要逐级代入直到求出结果，这一过程称为递归的返回
F(4)=10
F(3)=F(4)+1=11
F(2)=F(3)+1=12
F(1)=F(2)+1=13
2、写出递归表达式：显然，当n=4时，问题的解为10，而当n<4时，问题的解可转换为：
F(n)=f(n＋1)+1
3、编写程序：递归算法通常用自定义函数来实现，称为递归函数，如以上题可以写成如下函数：
Function f(n as integer) as integer
If n=4 then
＿＿＿
Else
＿＿＿＿＿
End if
End function
4、调试运行程序：
归结：解决递归问题的一般步骤：
1．分析问题，写出递归与返回的过程
2．建立数学模型（写出递归表达式）
X=D 返回某个常数作为结果
F（x）=
F（X’）……返回一个自身嵌套的表达式，自身调用，直到F（X”……）＝D作为条件终止。
3．编写自定义函数代码(一般形式为)
Function f(n as ____ ) as ______
If＿＿＿＿then
＿＿＿＿
Else
＿＿＿＿＿
End if
End function
4．调试运行程序
三、合作探究：小猴吃桃问题:
有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后
小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的
时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?
1．分组讨论，推算10天吃桃的过程
2、根据推算，得出的数据，填写下表：（建议先填写后四天，前六天通过调试程序，根据运行结果填写）
天数 1 2 3 4 5 6 7 8 9 10 桃子数
3、根据推算10天吃桃的数据和本题大意讨论并写出递归表达式：
假设第n天（n<10）的桃子数为tao(n)那么：
4、编写自定义函数程序：
Function tao(n as integer) as integer
If n=10then
Tao=1
Else
____________
End if
End function
5、将以上程序应用到VB中，调试运行，观察运行结果是否正确。
6、将你的程序提交给老师
四、欣赏：递归之美
五、随堂练习：
1、数列1，4，7，10，13，……的递归表达式为（ ）
(A) f(n)=n+3 ；f(1)=1 (B) f(n)=n*2-1 ；f(1)=1 (C) f(n)=n*2+1 ；f(1)=1 (D) f(n)=f(n-1)+3 ；f(1)=1 2、 一个递归算法必须包括（ ）
( A) 递归部分 (B) 终止条件和递归部分 (C ) 循环部分 (D) 终止条件和循环部分
选择算法：我们在用计算机解决问题时，常采用的算法有解析法、穷举法、递归法、冒泡排序法、选择排序法等，分析下列问题应采用哪种算法解决？
3、走台阶问题。从楼下到楼上共有n 个台阶，每一步有2种走法：走1个台阶；走2个台阶。走上这n 个台阶共有多少种走法？（提示：有n 级台阶时，走法有f(n-1)+f(n-2)种） ＿＿＿＿
4、用10元纸币（可取的面值有1元、2元或5元）组成一笔总值为24元的现金，设计一个算法输出所有不同的组成方法。
＿＿＿＿＿＿＿
5、信封问题，有N 个信封，N 封信，将N 封信装入N 个信封，全部都装错的方法有多少种数？
f(n)=(n-1)*(f(n-1)+f(n-2)) (n>2) f(1)=0 f(2)=1
＿＿＿＿＿＿＿＿＿
六、课堂小结：（及时总结、不断提高!）
七、课后作业：爱因斯坦的谜语
1、在一条街上，有5座房子，喷了5种颜色。
2、每个房里住着不同国籍的人
3、每个人喝不同的饮料，抽不同品牌的香烟，养不同的宠物 问题是：谁养鱼？ 提示：
1、英国人住红色房子
2、瑞典人养狗
3、丹麦人喝茶
4、绿色房子在白色房子左面
5、绿色房子主人喝咖啡
6、抽Pall Mall 香烟的人养鸟
7、黄色房子主人抽Dunhill 香烟
8、住在中间房子的人喝牛奶
9、 挪威人住第一间房 10、抽Blends 香烟的人住在养猫的人隔壁 11、养马的人住抽Dunhill 香烟的人隔壁 12、抽Blue Master 的人喝啤酒 13、德国人抽Prince 香烟 14、挪威人住蓝色房子隔壁 15、抽Blends 香烟的人有一个喝水的邻居
习题1 1. 图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现 在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次， 图是这条河以及河上的两个岛和七座桥的草 图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行 2， 经过七座桥，且每次只经历过一次 3， 回到起点 该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。 2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 =m-n 2.循环直到r=0 m=n n=r r=m-n 3 输出m 3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。 编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。 #include
for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"<
【最新】2019年高中数学第1章算法初步1-4算法案例教材 梳理导学案 庖丁巧解牛 知识·巧学 1．几个常用函数符号 求余函数Mod(m,n)：Mod(m,n)表示取m除以n的余数. 如：m被3除余2，可表示为Mod(m,3)=2. 取整函数Int(x) :表示取不大于x的最大整数. 如：Int(2)=2,Int(2.3)=2,Int(2.6)=2. 误区警示不要与四舍五入相混淆Int(-2.3)=-3. 可用mInt(m/n)*n表示m除以n的余数，如m被3除余2，可表示为mInt(m/3)*3=2. 2．算法典型案例 案例1：韩信点兵——孙子问题 《孙子算经》中载有“物不知数”这个问题:今有物不知其数,三三数之剩二；五五数之剩三；七七数之剩二，问物几何？答曰“二十三”.这就是著名的孙子问题(记载于中国古代约公元3世纪成书的《孙子算经》,是原书卷下第26题).
这个问题可以简单地用一句话描述，即“一个正整数，被3，5，7除，余数分别为2，3，2”.设这个数为m，则可列关于x,y,z的方程 联想发散这一类问题的解法可以推广成解一次同余式组的一般方法．秦九韶给出了理论上的证明，并将它定名为“大衍求一术”.这个问题的通用解法称为“中国剩余定理”.秦九韶（公元1202—1261年），南宋数学家，著《数书九章》十八卷．全书共81道题，分为九大类：大衍类、天时类、田域类、测望类、赋役类、钱谷类、营建类、军旅类、市易类.其中对“大衍求一术”（一次同余组解法）和“正负开方术”（高次方程的数值解法）等有十分深入的研究.“大衍求一术”，在世界数学史上占有崇高的地位. 计算机解决：从2开始，让m依次去除，直到满足要求为止.这样，只要使用循环，由小到大依次搜索，直到找出满足条件的数即可.流程图如图1-4-1： 图1-4-1 案例2：辗转相除法求最大公约数 辗转相除法又称欧几里得算法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，此时的除数就是所求两数的最大公
《算法与程序设计》考前模拟题 1、下列选项中不是字符串常量的是 ( D ) A、”ab” B、”你好” C、”2006” D、1235 2、以下不属于算法基本特征的是（ D）。 A、可执行性 B、确定性 C、有穷性 D、无限性 3、流程图是描述（B）的常用方式。 A、程序 B、算法 C、数据结构 D、计算规则 4、以下运算符中运算优先级最高的是（ D ） A、＋ B、－ C、>= D、* 5、结构化程序设计由顺序结构，选择结构和循环结构三种基本结构组成，其中某程序中 三个连续语句如下： a=1 b=2 c=b+a 它属于（A） A、顺序结构 B、选择结构 C、循环结构 D、其他三种都不是 6、在现实生活中，人工解题的过程一般分为：（ A ） A、理解分析问题->寻找解题方法->用工具计算->验证结果 B、寻找解题方法->理解分析问题->用工具计算->验证结果 C、用工具计算->验证结果->寻找解题方法->理解分析问题 D、用工具计算->验证结果->理解分析问题->寻找解题方法 7、一位同学想编程解决“韩信点兵”的问题，他制定的如下工作过程中，最恰当的是（C） A、设计算法，编写程序，提出问题，运行程序，得到答案 B、分析问题，编写程序，设计算法，运行程序，得到答案 C、分析问题，设计算法，编写程序，运行程序，得到答案 D、设计算法，提出问题，编写程序，运行程序，得到答案 8、一位爱好程序设计的同学，想通过程序设计解决“鸡兔同笼”的问题，他制定的如下工作过程中，更恰当的是（A）。 A、提出问题、设计算法、编写程序、得到答案 B、提出问题、编写程序、运行程序、得到答案 C、编写程序、设计算法、调试程序、得到答案 D、设计程序、提出问题、编写程序、运行程序 9、下列关于算法的特征描述不正确的是（C） A、有穷性：算法必须在有限步之内结束 B、确定性：算法的每一步必须有确切的含义 C、输入：算法必须至少有一个输入 D、输出：算法必须至少有一个输出 10．下面关于算法的说法错误的是（ B ）。 A．算法必须有输出B．算法就是程序 C．算法不一定有输入D．算法必须在有限步执行后能结束 11、下列哪一个不是用于程序设计的软件（C） A、BASIC B、C语言 C、Word D、Pascal 12、下列可以作为合法变量名的是（A） A、a7 B、7a C、a-3 D、8 13、流程图中表示判断框的是（B）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 14、由“上车—掏钱—投币”所描述的问题是（A）。 Ａ、无人售票车投币过程Ｂ、乘公交车过程Ｃ、上车过程Ｄ、下车过程 15、下列给出的赋值语句中正确的是（C）。
2010年高考数学一轮复习精品学案(人教版 A 版) 算法案例 一.【课标要求】 通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献。 二.【命题走向】 算法是高中数学新课程中的新增内容，本讲的重点是几种重要的算法案例思想，复习时重算法的思想轻算法和程序的构造。 预测2010年高考队本讲的考察是：以选择题或填空题的形式出现，分值在5分左右， 考察的热点是算法实例和传统数学知识的结合题目 三.【要点精讲】 1 ?求最大公约数 (1)短除法 求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得 的商是两个互质数为止，然后把所有的除数连乘起来 (2)穷举法(也叫枚举法) 穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数 (3)辗转相除法 辗转相除法求两个数的最大公约数，其算法可以描述如下： ①输入两个正整数m和n; ②求余数r：计算m除以n,将所得余数存放到变量r中； ③更新被除数和余数：m=n, n=r; ④判断余数r是否为0。若余数为0,则输出结果；否则转向第②步继续循环执行. 如此循环，直到得到结果为止。 (4)更相减损术 我国早期也有解决求最大公约数问题的算法，就是更相减损术。在《九章算术》中记载了更相减损术求最大公约数的步骤：可半者半之，不可半者，副置分母？子之数，以少减多， 更相减损，求其等也，以等数约之 步骤： 1. 任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二 步。 n.以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这操作，直到所得的数相等为止，则这个数(等数)就是所求的最大公约数。 2. 秦九韶算法 秦九韶算法的一般规则： 秦九韶算法适用一般的多项式f(x)=a n x n+a n-1x n1+….-Bnx+a0的求值问题。用秦九韶算法求一般多项式f(x)= a n x n+a n-1x n-1 +….a1X+a0当x=x0时的函数值，可把n次多项式的求值问题转化成求n个一次多项式的值的问题，即求 V 0=a n V1=a n X+a n-1 V2=V1X+a n —2
一、选择题 1、流程图是描述（）的常用方式。 A、程序 B、算法 C、数据结构 D、计算规则 2、下面不属于算法描述方式的是（）。 A、自然语言 B、伪代码 C、流程图 D、机器语言 3、以下运算符中运算优先级最高的是（）。 A、+ B、^ C、>= D、* 4、某程序中三个连续语句如下： a=1 b=2 c=b+a 它属于（） A、顺序结构 B、选择结构 C、循环结构 D、以上三种都不是 5、穷举法的适用范围是（） A、一切问题 B、解的个数极多的问题 C、解的个数有限且可一一列举 D、不适合设计算法 6、在现实生活中，人工解题的过程一般分为（） A、理解分析问题→寻找解题方法→用工具计算→验证结果 B、寻找解题方法→理解分析问题→用工具计算→验证结果 C、用工具计算→验证结果→寻找解题方法→理解分析问题 D、用工具计算→验证结果→理解分析问题→寻找解题方法 7、下列关于算法的特征描述不正确的是（） A、有穷性：算法必须在有限步之内结束 B、确定性：算法的每一步必须确切的定义 C、输入：算法必须至少有一个输入 D、输出：算法必须至少有一个输出 8、下列哪一个不是用于程序设计的软件（） A、BASIC B、C语言 C、Word D、Pascal 9、下列可以作为合作变量名的是（） A、a7 B、7a C、a-3 D、8 10、编程求1+2+3+........+1000的和，该题设计最适合使用的控制结构为（）。 A、顺序结构 B、分支结构 C、循环结构 D、选择结构 11、下列步骤不属于软件开发过程的是（） A、任务分析与系统设计 B、软件的销售 C、代码编写与测试 D、软件测试与维护12．以下程序段运行时，语句k=k+1 执行的次数为（）次。 k=-10 do k=k+1 loop while（until）k=0 A. 9 B. 10 C. 11 D. 12 13．已知x=6, y=5, 则以下运算结果为True 的是（） A．Not(x>y) B. (x<5)or(y>6) C. (x>=6)And(y>=5) D. Not(x>4) 14．模块化程序设计方法反映了结构化程序设计的（）基本思想。 A、自顶向下，逐步求精 B、面向对象 C、自定义函数、过程 D、可视化编程 15、一位同学想编程解决“韩信点兵”的问题，他制定的如下工作过程中，最恰当的是（） A、设计算法，编写程序，提出问题，运行程序，得到答案
递 归 冯文科 一、递归的基本概念。 一个函数、概念或数学结构，如果在其定义或说明内部直接或间接地出现对其本身的引 用，或者是为了描述问题的某一状态，必须要用至它的上一状态，而描述上一状态，又必须用到它的上一状态……这种用自己来定义自己的方法，称之为递归或递归定义。在程序设计中，函数直接或间接调用自己，就被称为递归调用。 二、递归的最简单应用：通过各项关系及初值求数列的某一项。 在数学中，有这样一种数列，很难求出它的通项公式，但数列中各项间关系却很简单，于是人们想出另一种办法来描述这种数列：通过初值及n a 与前面临近几项之间的关系。 要使用这样的描述方式，至少要提供两个信息：一是最前面几项的数值，一是数列间各项的关系。 比如阶乘数列 1、2、6、24、120、720…… 如果用上面的方式来描述它，应该是： ???>==-1 ,1,11n na n a n n 如果需要写一个函数来求n a 的值，那么可以很容易地写成这样：
这就是递归函数的最简单形式，从中可以明显看出递归函数都有的一个特点：先处理一 些特殊情况——这也是递归函数的第一个出口，再处理递归关系——这形成递归函数的第二个出口。 递归函数的执行过程总是先通过递归关系不断地缩小问题的规模，直到简单到可以作为 特殊情况处理而得出直接的结果，再通过递归关系逐层返回到原来的数据规模，最终得出问题的解。 以上面求阶乘数列的函数)(n f 为例。如在求)3(f 时，由于3不是特殊值，因此需要计 算)2(*3f ，但)2(f 是对它自己的调用，于是再计算)2(f ，2也不是特殊值，需要计算 )1(*2f ，需要知道)1(f 的值，再计算)1(f ，1是特殊值，于是直接得出1)1(=f ，返回上 一步，得2)1(*2)2(==f f ，再返回上一步，得62*3)2(*3)3(===f f ，从而得最终解。 用图解来说明，就是 下面再看一个稍复杂点的例子。 【例1】数列}{n a 的前几项为
递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】
基于导学案的课堂教学案例研究报告 一、核心概念界定 1?导学案 导学案是在教学过程中，教师为了引导学生学习教学内容而编写的纸质文案。导学案包括：教学目标、教学重点、教学难点、课前预习、课中研讨、课堂与反馈练习、课堂小结、作业布置等环节。导学案的编写是教师精心指导学生进行自主学习，自主探究，自主创新的材料依据，从教师备课的角度来看，编写导学案是一种创造性劳动。 2?教学案例 教学案例是真实而又典型且含有问题的事件。简单地说，一个教学案例就是一个包含有疑难问题的实际情境的描述，是一个教学实践过程中的故事，描述的是教学过程中“意料之外，情理之中的事”。 二、研究目标 1 ?探究基于导学案下课堂教学案例的特征和研究方法 2.通过案例研究，改进和完善导学案教学的方法 3.提高教师的反思能力，促进教师专业成长。 三、研究内容 1.导学案下的教学案例的特征 2.导学案下的教学案例的行动研究方法 3.提高教师的反思能力，促进教师专业成长。 四、研究过程与方法 1.准备阶段：通过参考、阅读、借鉴相关文献书籍，研究设计更符合本学科课堂教学特点的教学案例。 2.实施阶段：结合教学实际，各教研组为单位，开展课堂观察，确立主题，开展案例分析研究，整理教学案例资料，撰写论文，并把好的经验进行推广，完善“导学案”的教学设计和方法，提高教学的有效性。 3.总结成果，成果形式为论文。收集和整理研究资料，分析实验情况，总结导学案使用过程中的成功经验以及存在的问题，提炼研究成果。 研究方法：文献研究法和行动研究法 五、预期研究成果 成果名称 成果 形式完成 时间 负责人
基于导学案的课堂教学案例研究 论文 子课题六：基于以学定教理念的导学案设计的研究 一、核心概念及其界定 1 .以学定教 以学定教是依据学情确定教学的起点、方法和策略。这里的学情包括学生的知识、能力基础，学生的年段认知水准，学生课前的预习程度，学生对新知的情绪状态等学习主体的基本情况。而“定教”，就是确定教学的起点不过低或过高，在恰当的起点上选择最优的教学方法，运用高超的教学艺术，让每一位学生达到最优化的发展。 “以学定教”是以学生为本，以科学高效的学法作为确定教法的根本依据，面向每个学生，让学生生动活泼的学习，让学生主动活泼的发展。 2.导学案 导学案是在教学过程中，教师为了引导学生学习而编写的纸质文案。导学案包括：教学目标、教学重点、教学难点、课前预习、课中研讨、课堂与反馈练习、课堂小结、作业布置等环节。导学案的编写是教师精心指导学生进行自主学习，自主探究，自主创新的材料依据，从教师备课的角度来看，编写导学案是一种创造性劳动。 二、研究目标 1.提高教师导学案的设计水平； 2.促进教师工作中的创新、提高教育教学质量。 三、研究内容 1.导学案设计的基本要素和结构 基本要素：问题设计、情景设计、教法设计及多媒体使用设计 基本结构：教师寄语、学习目标、学习过程、学习评价 2.导学案设计常见流程和方法 3.依据学情确定教学的起点、方法和策略 4.课堂评价方式的转变 四、研究过程、方法 1.调查阶段。2012年1月-2月
《算法与程序设计》试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么？”，然后再确定程序“如何做？”请问“如何做？”是属于用计算机解决问题的哪一个步骤？（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的？（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、88.12345 D、1.2345E6 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式 A+B+C
穷举法算法案例《用穷举法解决问题》教学设计 教学分析 1.教学目标知识与技能：了解什么是穷举法及其特点，以及用穷举法设计算法的基本过程；能够根据具体问题的要求，使用穷举法设计算法。 过程和方法：运用观察、发现、归纳、应用的方法，发展学生的归纳思维；培养学生独立探究与自主发现的学习能力。 情感态度与价值观：了解算法和程序设计在计算机解决问题过程中的重要性；体验将算法转变为程序的过程，享受计算机解决问题的快乐。 2.教学重点和难点 重点：用穷举算法解决问题的一般步骤；能根据具体问题的要求，提高运用穷举算法解决问题的能力。 难点：通过观察、类比多种方式培养学生归纳思维。
教学过程 1.创设情境激趣引入 教师活动：某同学用自己的QQ号登录，可他记不清密码了，你能帮他找回密码吗？他的密码是一个5位数，67□□8，其中百位和十位上的数字他不记得了，但他还记得该数能够被78整除，也能被67整除。你能帮他设计一个算法求出该密码吗？希望大家能在学习完下面这个例子后就可以解决这个问题。 设计意图：成功的教学不是强制，而是激发学生的学习兴趣，该导入正是从学生感兴趣的事情着手的。 2.观察―发现―归纳―应用 (1)观察。
教师活动：逐语句调试以下程序，分析程序的执行过程，让学生填写下表，指出此程序功能。 For i=100 to 999 a=int(i /100) b=int(i /10) mod 10 C=i mod 10 If a^3+b^3+c^3=ithen Printi Endif Next i (2)发现。 教师引导：在分析上一程序过程中，你能发现什么？
算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
高一第二学期《算法与程序设计》学分认定试题 学校：_____________ 班级：____________ 学号：____________ 姓名：____________ 一、单选题（每小题3分，20小题，共60分） 1、用计算机解决问题时，首先应该确定程序“做什么”，然后再确定程序“如何做”请问“如何做”是属于用计算机解决问题的哪一个步骤（） A、分析问题 B、设计算法 C、编写程序 D、调试程序 2、在调试程序过程中，下列哪一种错误是计算机检查不出来的（） A、编译错误 B、执行错误 C、逻辑错误 D、任何错误计算机都能检查出来 3、下列关于算法的叙述中，错误的是（） A、一个算法至少有一个输入和一个输出 B、算法的每一个步骤必须确切地定义 C、一个算法在执行有穷步之后必须结束 D、算法中有待执行的运算和操作必须是相当基本的。 4、流程图中表示判断的是（）。 Ａ、矩形框Ｂ、菱形框Ｃ、圆形框Ｄ、椭圆形框 5、任何复杂的算法都可以用三种基本结构组成，下列不属于基本结构的是（） A、顺序结构 B、选择结构 C、层次结构 D、循环结构 6、能够被计算机直接识别的语言是（） A、伪代码 B、高级语言 C、机器语言 D、汇编语言 7、在VB语言中，下列数据中合法的长整型常量是（） A、08A B、2380836E C、 D、 8、求Mid(“ABCDEFG”,3,2)的结果是（） A、“ABC” B、“CD” C、“ABCDEF” D、“BCD” 9、表达式A+B+C
1．3 算法案例 1．问题导航 (1)什么叫辗转相除法？ (2)什么叫更相减损术？ (3)辗转相除法与更相减损术的区别是什么？ (4)什么是秦九韶算法？ (5)学习了十进制，知道十进制是使用0～9十个数字，那么二进制、五进制、七进制分别使用哪些数字？ 2．例题导读 通过对例1的学习，学会用更相减损术求最大公约数； 通过对例2的学习，学会用秦九韶算法求多项式的值； 通过对例3的学习，学会如何将二进制化为十进制； 通过对例4的学习，学会如何将k进制化为十进制； 通过对例5的学习，学会如何将十进制化为二进制； 通过对例6的学习，学会十进制化为k进制的方法：即“除k取余法”(k∈N，2≤k≤9)． 1．辗转相除法与更相减损术 (1)辗转相除法：又叫欧几里得算法，是一种求两个正整数的最大公约数的古老而有效的算法． (2)更相减损术：我国古代数学专著《九章算术》中介绍的一种求两个正整数的最大公约数的算法． 2．秦九韶算法 功能它是一种用于计算一元n次多项式的值的方 法 改写后的形式f(x)＝a n x n＋a n－1x n－1＋…＋a1x＋a0 ＝(a n x n－1＋a n－1x n－2＋…＋a1)x＋a0 ＝((a n x n－2＋a n－1x n－3＋…＋a2)x＋a1)x＋a0 ＝… ＝(…((a n x＋a n－1)x＋a n－2)x＋…＋a1)x＋a0 计算方法从括号最内层开始，由内向外逐层计算v1＝a n x＋a n－1， v2＝v1x＋a n－2， v3＝v2x＋a n－3， v n＝v n－1x＋a0，
… 这样，求n次多项式f(x)的值就转化为求n 个一次多项式的值. 3.进位制 (1)进位制 进位制是人们为了计数和运算方便而约定的记数系统，“满几进一”就是几进制，几进制的基数就是几． (2)其他进位制与十进制间的转化 ①其他进位制化成十进制 其他进位制的数化成十进制时，表示成不同位上数字与基数的幂的乘积之和的形式． ②十进制化成k进制的方法——“除k取余法”． 1．用更相减损术求294和84的最大公约数时，需做减法运算的次数是( ) A．2 B．3 C．4 D．5 解析：选C.294－84＝210，210－84＝126，126－84＝42，84－42＝42，共做4次减法运算． 2．用秦九韶算法计算多项式f(x)＝3x6＋4x5＋5x4＋6x3＋7x2＋8x＋1当x＝0.4时的值时，需要做乘法和加法的次数分别是( ) A．6，6 B．5，6 C．5，5 D．6，5 答案：A 3．完成下列进位制之间的转化． (1)1 034(7)＝________(10)； (2)119(10)＝________(6)． 解析：(1)1 034(7)＝1×73＋0×72＋3×7＋4×70＝368. (2) ∴119(10)＝315(6)． 答案：(1)368 (2)315 4．当所给的多项式按x的降幂排列“缺项”时，用秦九韶算法改写多项式时，应注意什么？ 解：所缺的项写成系数为零的形式，即写成0·x n的形式． 1．对于任何一个数，我们可以用不同的进位制来表示． 2．表示各种进位制数一般在数字右下角加注来表示，如111 001(2)表示二进制数，34(5)表示5进制数． 3．电子计算机一般都使用二进制． 4．利用除k取余法，可以把任何一个十进制数化为k进制数，并且操作简单、实用．5．通过k进制数与十进制数的转化，我们也可以将一个k进制数转化为另一个不同基数的M进制数．
递归算法的优缺点： ○ 1优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 ○2缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 边界条件与递归方程是递归函数的二个要素 应用分治法的两个前提是问题的可分性和解的可归并性 以比较为基础的排序算法的最坏倩况时间复杂性下界为0(n·log2n)。 回溯法以深度优先的方式搜索解空间树T ，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T 。 舍伍德算法设计的基本思想: 设A 是一个确定性算法，当它的输入实例为x 时所需的计算时间记为tA(x)。设Xn 是算法A 的输入规模为n 的实例的全体，则当问题的输入规模为n 时，算法A 所需的平均时间为 这显然不能排除存在x ∈Xn B ，使得对问题的输入规模为n 拉斯维加斯( Las Vegas )算法的基本思想: 设p(x) 是对输入x 调用拉斯维加斯算法获得问题的一个解的概率。一个正确的拉斯维加斯算法应该对所有输入x 均有p(x)>0。 设t(x)是算法obstinate 找到具体实例x 的一个解所需的平均时间 ,s(x)和e(x)分别是算法对于具体实例x 蒙特卡罗(Monte Carlo)算法的基本思想: 设p 是一个实数，且1/2 [转]递归算法详解 2009年09月05日星期六20:34 本文转至https://www.doczj.com/doc/d614501982.html,/blog/378483 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时， 2.1.3算法案例分析 【使用说明】： 1.课前认真阅读教材81—83页内容，独立完成学案所设计的问题，并在不会做或有疑问的地方用红笔做出标记。 2.限时完成，规范书写，课上小组合作探究，答疑解惑，并及时用红笔纠错、补充 【学习目标】： A 通过对例题的模仿，探索，初步掌握中点分段法，求两数的最大公因数，最小公倍数的具体算法 B 通过对具体问题的解决过程和步骤的分析，了解算法的含义体会算法的思想----在有限步内完成的、解决某一类问题的“机械”程序 C 激情投入，高效学习，踊跃展示，大胆质疑，体验自主 学习的快乐和成功的愉悦 一、自主学习： （一）阅读教材75页例1（中点分段法）， 1.假设物品价格为725元，补全下面竞猜过程： （1）参：800元！ 主: 高了!（P在0---800元之间） （2）参: 400元！ 主: 低了！（P在400---800元之间） （3）参: 600元！ 主: 低了！（P在600---800元之间） （4) 参: ＿＿＿备注：主: 低了！（P在700---800元之间） (5) 参: 750元！ 主: 高了!（P在＿＿＿元之间） (6) 参:＿＿＿！ 主: 恭喜你，打对了！ 2、如果物品价格为650元，当物品价格在800元之内时用 这种方法，参与者需要竞猜-＿＿＿次可得正确结果 （二) 阅读教材76页例2，仿照例2，补全将780分解成素因数 积的算法： 1、判断780是否为素数：否。 2、确定780的最小素因数：＿＿＿。780=＿＿＿ 3、判断＿＿＿是否为素数：否。 4、确定＿＿＿的最小素因数：2. ＿＿＿=2 ＿＿＿ 5、＿＿＿＿＿＿ 6、＿＿＿＿＿＿＿＿＿ 7、判断65是否为素数：否。 8、确定65的最小素因数：5. 65=513 9、判断13是否为素数：＿＿＿，所以分解结束。 分解结果是：780=＿＿＿＿＿＿ 阅读教材77页例3，仿照例3，补全求780和2520最大公因数 的算法： 1、先将780进行素因数分解：780=223513 一、综合处理题 1、两倍- https://www.doczj.com/doc/d614501982.html,/problem?id=2807 Description 给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。 Input 输入包括多组测试数据。每组数据包括一行，给出2到15个两两不同且小于100的正整数。每一行最后一个数是0，表示这一行的结束后，这个数不属于那2到15个给定的正整数。输入的最后一行只包括一个整数-1,这行表示输入数据的结束，不用进行处理。 Output 对每组输入数据，输出一行，给出有多少个数对满足其中一个数是另一个数的两倍。 Sample Input 1 4 3 2 9 7 18 22 0 2 4 8 10 0 7 5 11 13 1 3 0 -1 Sample Output 3 2 2、谁拿了最多奖学金 - https://www.doczj.com/doc/d614501982.html,/problem?id=2715 Description 某校的惯例是在每学期的期末考试之后发放奖学金。发放的奖学金共有五种，获取的条件各自不同： 1) 院士奖学金，每人8000元，期末平均成绩高于80分（>80），并且在本学期内发表1篇或1篇以上论文的学生均可获得； 2) 五四奖学金，每人4000元，期末平均成绩高于85分（>85），并且班级评议成绩高于80分（>80）的学生均可获得； 3) 成绩优秀奖，每人2000元，期末平均成绩高于90分（>90）的学生均可获得； 4) 西部奖学金，每人1000元，期末平均成绩高于85分（>85）的西部省份学生均可获得； 5) 班级贡献奖，每人850元，班级评议成绩高于80分（>80）的学生干部均可获得； 递归算法详解 C通过运行时堆栈支持递归函数的实现。递归函数就是直接或间接调用自身的函数。 许多教科书都把计算机阶乘和菲波那契数列用来说明递归，非常不幸我们可爱的著名的老潭老师的《C语言程序设计》一书中就是从阶乘的计算开始的函数递归。导致读过这本经书的同学们，看到阶乘计算第一个想法就是递归。但是在阶乘的计算里，递归并没有提供任何优越之处。在菲波那契数列中，它的效率更是低的非常恐怖。 这里有一个简单的程序，可用于说明递归。程序的目的是把一个整数从二进制形式转换为可打印的字符形式。例如：给出一个值4267，我们需要依次产生字符‘4’，‘2’，‘6’，和‘7’。就如在printf函数中使用了%d格式码，它就会执行类似处理。 我们采用的策略是把这个值反复除以10，并打印各个余数。例如，4267除10的余数是7，但是我们不能直接打印这个余数。我们需要打印的是机器字符集中表示数字‘7’的值。在ASCII码中，字符‘7’的值是55，所以我们需要在余数上加上48来获得正确的字符，但是，使用字符常量而不是整型常量可以提高程序的可移植性。‘0’的ASCII码是48，所以我们用余数加上‘0’，所以有下面的关系： ‘0’+ 0 =‘0’ ‘0’+ 1 =‘1’ ‘0’+ 2 =‘2’ ... 从这些关系中，我们很容易看出在余数上加上‘0’就可以产生对应字符的代码。接着就打印出余数。下一步再取商的值，4267/10等于426。然后用这个值重复上述步骤。 这种处理方法存在的唯一问题是它产生的数字次序正好相反，它们是逆向打印的。所以在我们的程序中使用递归来修正这个问题。 我们这个程序中的函数是递归性质的,因为它包含了一个对自身的调用。乍一看，函数似乎永远不会终止。当函数调用时，它将调用自身，第2次调用还将调用自身，以此类推，似乎永远调用下去。这也是我们在刚接触递归时最想不明白的事情。但是，事实上并不会出现这种情况。 这个程序的递归实现了某种类型的螺旋状while循环。while循环在循环体每次执行时必须取得某种进展，逐步迫近循环终止条件。递归函数也是如此，它在每次递归调用后必须越来越接近某种限制条件。当递归函数符合这个限制条件时，它便不在调用自身。 在程序中，递归函数的限制条件就是变量quotient为零。在每次递归调用之前，我们都把quotient除以10，所以每递归调用一次，它的值就越来越接近零。当它最终变成零时，递归便告终止。 /*接受一个整型值（无符号0，把它转换为字符并打印它，前导零被删除*/[转]递归算法详解
必修三数学算法案例获奖说课导学案
《ACM算法与程序设计》期末问题集
递归算法详解
相关主题
文本预览