如何呈现递归算法的思想及举例说明
高密市康成中学陈飞鹏 2009年7月22日23:09
浏览：239 专家浏览：0 | 评论：7 专家评论：0
孟凡桥于09-7-23 21:49推荐总结了递归算法的特点、定义等，例子列举的简洁，适当，值得学习。
一、递归算法的定义
递归算法是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，
它往往使算法的描述简洁而且易于理解。
二、递归算法的特点
递归过程一般通过函数或子过程来实现。
递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
三、递归算法解决问题的特点：
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递增归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，
所以一般不提倡用递归算法设计程序。
递归算法所体现的“重复”一般有三个要求：
一是每次调用在规模上都有所缩小(通常是减半)；
二是相邻两次重复之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
三是在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达
到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束
四、下面我们用c语言举俩个例子来对递归算法进行一下演绎：
1、有一个农场在第一年的时候买了一头刚出生牛，这头牛在第四年的时候就能生一头小牛，以后每年这头牛就会生一头小牛。
这些小牛成长到第四牛又会生小牛，以后每年同样会生一头牛，假设牛不死，如此反复。请问50年后，这个农场会有多少头牛？
首先定义最终终止条件f(4)=1;
然后定义递归公式中f(n)=f(n-1)+f(n-3)。
#include
int fn(int a);
void main()
{
int i;
i = fn(20);
printf("%d\n",i);
}
int fn(int a)
{
if (a<4 && a>0)
{
return 1;
}
else if(a>=4)
{
a = fn(a-1) + fn(a-3);
return a;
}
}
2、有个莲花池里起初有一只莲花，每过一天莲花的数量就会翻一倍。假设莲花永远不凋谢，30天的时候莲花池全部长满了莲花，
请问第23天的莲花占莲花池的几分之几？
首先定义最终终止条件f(1)=1;
然后定义递归公式中f(n)=f(n-1)*2。
#include
int fn(int a);
void main()
{
int a;
int b;
double c;
a = fn(30);
b = fn(23);
c = (double)b/a;
printf("%.20lf\n",c);
}
int fn(int a)
{
if(a == 1)
{
return 1;
}
else
{
a = fn(a-1)*2;
return a;
}
}
数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放
该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 一、教学目标 1、知识与技能 (1)．认识递归现象。 (2)．使用递归算法解决问题往往能使算法的描述乘法而易于表达 (3)．理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4)．认识递归算法往往不是高效的算法。 (5)．了解递归现象的规律。 (6)．能够设计递归程序解决适用于递归解决的问题。 (7)．能够根据算法写出递归程序。 (8)．了解生活中的递归现象，领悟递归现象的既有重复，又有变化的 特点，并 且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 （1）了解递归现象和递归算法的特点。 （2）能够根据问题设计出恰当的递归程序。 2、教学难点 (1)递归过程思路的建立。 (2)判断问题是否适于递归解法。 (3)正确写出递归程序。 三、教学环境 1、教材处理 教材选自《广东省普通高中信息技术选修一：算法与程序设计》第四章第五节，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2)和练习(3)这两道题目的形式相差很远，但方法和答案却都是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 教学方法采用讲解、探究、任务驱动和学生自主学习相结合 2、预备知识 学生已掌握了用计算机解决问题的过程，掌握了程序设计基础，掌握了解析法、穷举法、查找法、排序法设计程序的技巧。 3、硬件要求 建议本节课在多媒体电脑教室中完成，最好有广播教学系统或投影仪，为拓展学习，学生机应允许上互联网。 4、所需软件 学生机要安装VB6.0或以上版本。 5、所需课时 2课时（90分钟） 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 利用递归思想解决计数问题 福建省永定第一中学 简绍煌 我们常会遇到一些看似排列组合应用题的计数问题，但其复杂的情形有时令人无从下手，若是利用递归思想建立递归方程加以求解，则往往能够迎刃而解． 【例1】有一楼梯共10级，如果规定每步只能跨上一级或二级，要上10级，共有多少种走法？ 解 设上n 级楼梯共有n a 种走法，当1n =时，11a =；当2n =时，22a =． 当有(2)n n >级楼梯时，其走法分两类． 第一类：走完前面1n -级楼梯有1n a -种走法，走第n 级只有1种走法； 第二类：走完前面2n -级楼梯有2n a -种走法，走第1n -级与第n 级楼梯时一步走，也是1种走法． 由分类计数原理，知n 级楼梯的走法为21(2)n n n a a a n N n --=+∈>且，． 由此可以算出1089a =． 点评 其通项公式可用换元法转化为一阶线性递归数列求解． 令11n n n c a x a +=-，使数列{}n c 是以2x 为公比的等比数列(12x x 、待定)． 即211211()n n n n a x a x a x a +++-=-，∴212112()n n n a x x a x x a ++=+-．对照已给递归式， 有12121 1x x x x +==-，，即12x x 、是方程210x x --=的两个根． 从而121211112222x x x x += === ∴211111(222n n n n a a a a +++-=-) ① 或211111(222n n n n a a a +++-=-) ② 由式①得1 1131(222n n n a a -++-=； 由式②得1 1131(222 n n n a a -++--=． 消去 1n a +，得11n n n a --? =?? ． 【例2】将数字123n ，，，，填入标号为123n ，，，，的n 个方格内，每格一个数字，则 标号与所填数字均不同的填法共有多少种？ 解 设这n 个自然数的错排数为n a ． 当1n =时，10a =；当2n =时，21a =． 当3n ≥时，n 个自然数的错排数可以分两类情况计算． 第一类：自然数(11)k k n ≤≤-与n 互换，这时错排数为2n a -； 第二类：自然数n 在第k 位上，但自然数不在第n 位上．这时就把第n 位看做第k 位，相当于将n 以外的1n -个自然数进行错排，错排数为1n a -． 所以，自然数n 在第k 位上的错排数共有21n n a a --+种，由于k 可以是121n - ，，，共 1n -种可能，故n 个自然数的错排数为21(1)()(3)n n n a n a a n --=-+≥．① 由①式得，112[(1)]n n n n a a a n a ----=---，∴112 (1)[]!!!! n n n n a na a n a n n n n -----=--， 递归算法与递归程序 岳西中学：崔世义一、教学目标 1知识与技能 (1) ?认识递归现象。 (2) ?使用递归算法解决冋题往往能使算法的描述乘法而易于表达 (3) ?理解递归三要素：每次递归调用都要缩小规模；前次递归调用为后次作准备：递归调用必须有条件进行。 (4) ?认识递归算法往往不是咼效的算法。 (5) ? 了解递归现象的规律。 (6) ?能够设计递归程序解决适用于递归解决的问题。 (7) ?能够根据算法写出递归程序。 (8) ? 了解生活中的递归现象，领悟递归现象的既有重复，又有变化的特点，并且从中学习解决问题的一种方法。 2、方法与过程 本节让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习(2) 和练习(3)这两道题目的形式相差很远，但方法和答案却是完全相同的练习，体会其中的奥妙，加深对递归算法的了解。最后用子过程解决汉诺塔的经典问题。 3、情感态度和价值观 结合高中生想象具有较强的随意性、更富于现实性的身心发展特点，综合反映出递归算法的特点，以及递归算法解答某些实践问题通常得很简洁，从而激发学生对程序设计的追求和向往。 二、重点难点 1、教学重点 (1) 了解递归现象和递归算法的特点。 (2) 能够根据问题设计出恰当的递归程序。 2、教学难点 (1) 递归过程思路的建立。 (2) 判断冋题是否适于递归解法。 (3) 正确写出递归程序。 三、教学环境 1、教材处理 教材选自《浙江省普通高中信息技术选修：算法与程序设计》第五章，原教材的编排是以本节以斐波那契的兔子问题引人，导出递归算法，从而自 定义了一个以递归方式解决的函数过程。然后利用子过程解决汉诺塔的经典问题。 教材经处理后，让同学们玩汉诺塔的游戏，导入递归问题，从用普通程序解决斐波那契的兔子问题入手，引导学生用自定义了一个以递归方式解决的函数过程解决问题，同时让同学们做三个递归练习，巩固提高。然后让学生做练习⑵ 和练习 算法分析与设计习题集整理 第一章算法引论 一、填空题： 1、算法运行所需要的计算机资源的量，称为算法复杂性，主要包括时间复杂度和空间复杂度。 2、多项式10()m m A n a n a n a =+++L 的上界为O(n m )。 3、算法的基本特征：输入、输出、确定性、有限性 、可行性 。 4、如何从两个方面评价一个算法的优劣：时间复杂度、空间复杂度。 5、计算下面算法的时间复杂度记为： O(n 3) 。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) {c[i][j]=0; for(k=1;k<=n;k++) c[i][j]= c[i][j]+a[i][k]*b[k][j]; } 6、描述算法常用的方法：自然语言、伪代码、程序设计语言、流程图、盒图、PAD 图。 7、算法设计的基本要求：正确性 和 可读性。 8、计算下面算法的时间复杂度记为： O(n 2) 。 for （i ＝1；i 中学思想政治课教学方法论 长期以来，思想政治课是中学思想理论教育的主渠道和主要阵地，是每个学生的必修课程；思想政治课教学为培养德、智、体、美等全面发展的社会主义事业的建设者和接班人发挥着至关重要的作用，并取得了有目共睹的成就。然而，在新的时期，国际、国内形势发生了急遽而深刻的变化，这使得中学生思想政治教育既面临有利条件，同时也面临着严峻挑战。面对新形势、新情况，中学生思想政治教育工作还存在着不少的薄弱环节，比如：认识不够全面，学校不够重视，教师难教，学生难学，教育与实践脱节等。因此，加强和改进中学生思想政治教育成为一项极为紧迫的重要任务，此文将着重探讨中学思想政治课教学方法的改进。 一、思想政治课教学方法改革的必要性 中学生思想政治课教学方法改革的迫切在于新时期发展的必然要求、思想政治教育本身发展的内在要求以及改变思想政治教育现状的迫切要求。我们知道，新世纪是知识经济的时代，知识经济对创新的强调必然要求对教育进行改革。思想政治教育在培养学生创新素质方面理应做出应有贡献，因而必须不断改进思想政治课教学方法以应对不断变化的时代发展。 调查发现中学政治课教学存在着两大“差距”，也就是教学效果与教学目标、学生所希望的政治课模式与教师设计的政治课模式在内容和形式上都存在不同程度的差距。实际上，这两大差距也反映着当前中学思想政治教学中所存在的难以令人满意 的现状与亟需解决的问题。具体而言，学校思想政治教育在以下几方面依然有待改善。 第一，在教学方式上，偏重于灌输式教学方式。在传统的思想政治课教学课堂上，教师所采用的一般是灌输式教法，在理论上更多的是采用空洞的说教。在教学过程中，主要以教师讲授知识、讲解概念为主，以教师的“讲”、学生的“听”代替教师和学生的双向互动；而课堂上所灌输的内容与学生的生理、心理特点以及社会现实严重脱节，加上学生个体理解能力所限，这必然导致教师照本宣科、学生死记硬背却完全背离培养“健全的人”这样的理念的教学效果。 第二，在师生关系上，学生作为教学主体的地位遭受忽视。单一的教学方法、僵化的教学模式的推行必然牺牲学生在教学活动中的教学主体地位，学生的自主性、创造性也就被压抑甚至丧失了。以往的思想政治课教学中，学生仅仅被视为被动接受知识的“容器”，完成认知性任务作为课堂教学的唯一目的，知识的占有与否往往成为衡量教学效果的唯一指标。学生在课堂上用心配合教师完成教案的讲解即可，教师是“主角”，学生是“观众”、“听众”，它使课堂教学变得机械沉闷、公式化，缺乏生气与乐趣，使教学本身成为导致学生厌学、教师厌教的因素。这种把人当作“客体”、把人视为一种资源进行培养的教学与“以人为本”的教学理念相违背，是与教学发展的趋势不相符的。 第三，在学习方式上，不仅不能理解、掌握知识，甚至在思维训练方面也存在很大缺陷。由于长期受传统的、单一的教学方式的影响，学生在学习过程中缺乏主动性和创新性，而更不用说 分治算法 一、分治算法 分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。 分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它分解成几个子问题，找到求出这几个子问题的解法后，再找到合适的方法，把它们组合成求整个问题的解法。如果这些子问题还较大，难以解决，可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。这就是分治策略的基本思想。下面通过实例加以说明。 【例1】[找出伪币] 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。 另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。 递归算法向非递归算法转换 递归算法实际上是一种分而治之的方法，它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如hanio塔问题)，递归算法是一种自然且合乎逻辑的解决问题的方式，但是递归算法的执行效率通常比较差。因此，在求解某些问题时，常采用递归算法来分析问题，用非递归算法来求解问题；另外，有些程序设计语言不支持递归，这就需要把递归算法转换为非递归算法。 将递归算法转换为非递归算法有两种方法，一种是直接求值，不需要回溯；另一种是不能直接求值，需要回溯。前者使用一些变量保存中间结果，称为直接转换法；后者使用栈保存中间结果，称为间接转换法，下面分别讨论这两种方法。 1. 直接转换法 直接转换法通常用来消除尾递归和单向递归，将递归结构用循环结构来替代。 尾递归是指在递归算法中，递归调用语句只有一个，而且是处在算法的最后。例如求阶乘的递归算法： long fact(int n) { if (n==0) return 1; else return n*fact(n-1); } 当递归调用返回时，是返回到上一层递归调用的下一条语句，而这个返回位置正好是算法的结束处，所以，不必利用栈来保存返回信息。对于尾递归形式的递归算法，可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法： long fact(int n) { int s=0; for (int i=1; i<=n;i++) s=s*i; //用s保存中间结果 return s; } 单向递归是指递归算法中虽然有多处递归调用语句，但各递归调用语句的参数之间没有关系，并且这些递归调用语句都处在递归算法的最后。显然，尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下： int f(int n) { n = 3 Backtrack(1) t=1 for i = 1 to 3 i=1 Swap(x[1], x[1]) t=1时，x[1]取了x[1]=1 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=2 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> t = 4 > 3 输出(1,2,3) swap(x[3],x[3]) swap(x[2],x[2]) i=3 swap(x[2],x[3]) x[2]=3, x[3]=2 t=2时，x[2]取了3 Backtrack(3) -------> t=3 for i = 3 to 3 swap(x[3],x[3]) t=2时，x[3]取了x[3]=2 Backtrack(4) ---> t = 4 > 3 输出(1,3,2) swap(x[3],x[3]) swap(x[2],x[3]) x[2]=2, x[3]=3 Swap(x[1], x[1]) i=2 Swap(x[1], x[2]) x[1]=2, x[2]=1 t=1时，x[1]取了2 Backtrack(2) -----> t = 2 for i = 2 to 3 i=2 swap(x[2], x[2]) t=2时，x[2]取了x[2]=1 Backtrack(3) -----> t=3 for i = 3 to 3 swap(x[3],x[3]) t=3时，x[3]取了x[3]=3 Backtrack(4) ---> 网络教育课程考试复习题及参考答案算法分析与设计一、名词解释：1.算法 2.程序 3.递归函数 4.子问题的重叠性质 5.队列式分支限界法 6.多机调度问题7.最小生成树二、简答题： 1.备忘录方法和动态规划算法相 比有何异同？简述之。 2.简述回溯法解题的主要步骤。 3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用，将递归算法转化为非递归算法的方法。 6.简要分析分支限界法与回溯法的异同。7.简述算法复杂性的概念，算法复杂性度量主要指哪两个方面？8.贪心算法求解的问题主要具有哪些性质？简述之。9.分治法的基本思想是什么？合并排序的基本思想是什么？请分别简述之。10.简述分析贪心算法与动态规划 算法的异同。三、算法编写及算法应用分析题： 1.已知有3个物品： (w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10),背包的容积M=20，根据0-1背包动态规划的递推式求出最优解。 2.按要求完成以下关于排序和查找的问题。①对数组A={15，29，135，18，32，1，27，25，5}，用快速排序方法将其排成递减序。②请描述递减数组进行二分搜索的基本思想，并给出非递归算法。③给出上述算法的递归算法。④使用上述算法对①所得到的结果搜索如下元素，并给出搜索过程：18，31，135。已知，=1，2，3，4，5，6，=5，=10，=3，=12，=5，=50，=6，kijr*r1234567ii1求矩阵链积A×A×A×A×A×A的最佳求积顺序（要求给出计算步骤）。1234564.根据分枝限界算法基本过程,求解0-1背包问题。已知n=3,M=20，(w1,w2,w3)=(12,10,6),(p1,p2,p3)=(15,13,10)。 5.试用贪心算法求解汽车加油问题：已知一辆汽车加满油后可行驶n公里，而旅途中有若干个加油站。试设计一个有效算法，指出应在哪些加油站停靠加油，使加油次数最少，请写出该算法。6.试用动态规划算法实现下列问题：设A和B是两个字符串。我们要用最少的字符操作，将字符串A转换为字符串B，这里所说的字符操作包括：①删除一个字符。②插入一个字符。③将一个字符改为另一个字符。请写出该算法。7.对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。be2g212ad323182cf2h 8.试写出用分治法对数组A[n]实现快速排序的算法。9.有n个活动争用一个活动室。已知活动i占用的时间区域为[s，f ]，活动i,j相容的条件是：sj≥f ii，问题的解表示为(x| x =1，2…，n,)，x表示顺序为i的活动编号活动，求一个相容的活动子集，iiii且安排的活动数目最多。xxx10.设、、是一个三角形的三条边，而且x+x+x=14。请问有多少种不同的三角形？给出解答过程。12312311. 《中学思想政治课教学法》教学大纲 课程名称: 中学思想政治课教学法 学分: 2分 总学时: 30课时 适用专业 :思想政治教育 教材名称：《思想品德与思想政治课教学论》 出版社：高等教育出版社 一、本课程的性质和任务 本课程为师范类思想政治教育专业必修课程。本课程的任务是通过本课程的学习帮助学生运用马克思主义的立场、观点和方法。依据党的教育方针，在理论与实践的结合上了解新时期中学思想政治课以下简称“思想政治课”的性质、地位和任务，了解当今中学生的思想心理特点，掌握思想政治课教学的内容、过程、原则和方法，巩固专业思想，认清思想政治课教师在培养合格的社会主义建设者和接班人方面的地位和作用，为做一名优秀的思想政治课教师作准备。 二、本课程的教学内容和基本要求 第一章中学政治课的历史沿革 [3学时] 教学目的和要求： 通过教学，使学生明确中学思想政治课程设置的理论基础，了解该课程的发展历程，掌握中学政治课程发展的规律与启示。 教学内容： 第一节中学政治课程设置的理论基础 一、哲学基础 二、心理学基础 三、社会学基础 第二节中学政治课的发展历程 一、革命战争时期的中学政治课程 二、新中国成立以后中学政治课程 第三节中学政治课发展的规律与启示 一、坚持以马克思主义指导 二、坚持党的教育方针 三、适应社会发展需求 四、尊重学生身心发展的实际 五、处理好坚持和发展的关系 第二章思想品德与思想政治课的性质和任务 [3学时] 教学目的和要求： 通过教学，使学生明确中学思想政治课的性质、地位和任务，正确认识思想政治课在中学思想政治教育工作中的重要作用，纠正对中学思想政治课地位和作用的错误认识。 教学内容： 第一节课程的性质 一、认清思想品德与思想政治课程性质的必要性 二、思想品德与思想政治课程性质的历史考察 三、思想品德与思想政治课程性质的当代阐释 第二节课程的任务 一、思想品德与思想政治课程目标的含义及其作用 二、思想品德与思想政治课程任务的历史考察 三、思想品德与思想政治课程任务的当代阐释 《算法设计与分析》习题 第一章算法引论 1、算法的定义 答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。 通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征 答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种 答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面 答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义 答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次， 语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点 答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略 答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法： 递归法：汉诺塔问题兔子序列（上楼梯问题） 整数划分问题 蛮力法：百鸡百钱问题 倒推法：穿越沙漠问题 答：算法如下： （1） 递归法 汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci 数列 ） 递归实现： Int F(int n) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 数据结构习题 一、填空题 1、算法应具有的五个特性，分别为输入，输出，， 及。 2、对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。 3、设有一个顺序栈S，元素s l，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，s l，则顺序栈至少应能存放个元素。 4、串的两种最基本的存储方式是、。 5、具有10个顶点的有向图，边的总数最多为。 6、INDEX（‘DATASTRUCTURE’，‘STR’）=___ _____。（INDEX为子串定位） 7、一棵有n个结点的满二叉树有个度为1的结点、有 个分支（非终端）结点和个叶子。 8、堆排序的算法时间复杂度为。在数据表有序时，快速排序算法的时间复杂度是。 9、数据结构是研讨数据的____________和____________，以及它们之间的相互关系，并对与这种结构定义相应的______________。 10、数据结构中评价算法的两个重要指标是：和 。 11、栈中存取数据的原则，队列中存取数据的原则。 12、链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的。 13、如果一个函数，则称这个函数是一个递归函数。 14、具有10个顶点的无向图，边的总数最多为。 15、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次，当使用监视哨时，若查找失败，则比较关键字的次数为__ __。 16、已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。 17、下列程序段的时间复杂度为________________。 product = 1; for (i = n;i>0; i--) for (j = i+1; j 初中政治课常用教学方法有哪些 一建构特色教学方法体系的必要性思想政治课教学方法必须满足下列要求： 一、逻辑认知与直觉感悟相结合 把握世界的基本方式有两种,第一是科学的方式,第二种是审美的方式,由此获得两种知识,第一种是事实性知识,思想性知识,科学性知识,第二种是评价性知识.价值性知识,规范性知识。 二、接受式学习与研究性学习相结合 第一类知识具有客观性,它应当主要以接受式方式学习获得,但这种方式有有致命的弱点,缺少直接经验的过程,缺少知识发展的历史叙述,忽视具体知识结论的相对性和条件性,这样的知识缺乏活力,不利于学生创新能力的培养。 三、书本学习与社会学习相结合.社会学习的主要方式有调查研究,体察民情,观察模仿,实践反思.二思想政治课各类方法的功能和适用条件。 1、组织进行认识与实践活动的明理导行方法 第一、直接传递信息和视觉感知信息的方法,即直观演示法.包括现场实物直观演示,形象性直观教具演示,象征性直观教具演示三种方法。 第二、口头传递信息和听觉感知信息的方法,即口述法.包括讲述法,讲解法,讲读法,讲演法,谈话法,讨论法。 讲述法主要用于叙述事件经过,描述人物和课堂举例。讲解法主要用于概念原理的教学讲读法主要用于关键性结论性内容教学。 讲演法主要用于范围较大深度较大问题的教学,适用于专题讲座或综合复习。 谈话法问答法对话法围绕某一课题,师生之间提问和对话的方法。 讨论法教师引导学生围绕某个问题进行讨论辩论的方法,与谈话法不同之处在于,有同学之间的交流。 第三、通过实践活动来传递和感知信息的方法,即实践活动法，它包括道德践行活动,生活交往活动,角色模拟活动,专题研究活动。 第四、逻辑认知法.包括归纳与演绎,分析与综合,比较,逻辑与历史的统一.所谓逻辑的方法,是撇开发展的曲折过程和偶然因素对事物进行研究的方法,所谓历史的方法,就是从历史的自然过程支研究事物的方法。 逻辑方法使用遵循的顺序运用归纳法帮助学生形成概念和原理运用分析与综合法帮助学生理解概念和原理。 运用比较法帮助学生弄清相近相似及相关概念原理的联系与区别运用论证证明概念原理的科学性,消除学生疑虑。 运用推理使学生概念原理系统化深刻化运用应用加深学生对概念原理的理解,培养实践能力和创新能力。 2、激发和形成学习动力培养学生情感的激情促信的方法（1）激发和形成学习兴趣的方法提高教学内容的使用价值,满足学生需要。 教学内容呈现生动直观,增强其刺激性和吸引力改善师生关系,将学生对教师的积极情感迁移到老师所教内容上去。改善课堂教学结构,增强学生外显活动分量,实现对教学最大参与运用情感的感染功能,加强情感交流,以情激情。运用情感的情景性特征,创设情境,以境激情运用情感的强化和动力功能,帮助学生成功。 （2）激发认知情感,振奋学习精神的方法。 （3）激发学习义务和责任感的方法。 语言的递归性及其根源 钱冠连 （广东外语外贸大学外国语言学及应用语言学研究中心，广州 510420）摘要：（１）递归性不仅是转换生成语法中的一种语法属性，而且它与任意性、线性一样是语言的根本性质之一。（２）作者给出了语言递归性的定义：语言结构层次和言语生成中相同结构成分的重复或相套。（３）作者着重论证了语言递归性，阐述了整个语言结构和言语的生成处于相同结构的重复与层层相套之中，分析了语言整体上的递归性与局部上的非递归性，并指出这二者的必要性：整体上的递归性避免了句式集合的庞大与复杂的危险，使句式有限而简单；局部的非递归性使语言在有限手段之内变得丰富起来。语言递归性的巨大意义甚至是全部意义就在于允许人们用少量的句型生成无限多的句子。（４）语言的递归性的根源在世界（宇宙）的递归结构与语言的递归结构处于全息状态之中。 关键词：递归；语言递归性；全息 On Recursiveness of Language and Its Origin QIAN Guanlian （Center for Linguistics,Guangdong University of Foreign Studies,Guangzhou 510420）Abstract: In Part 1, the author points out that, recursiveness of language should not only be a grammatical attribute restricted to the transformational -generative grammar, but also be an essential property of language on a par with arbitrariness and linear nature of language. In Part 2, the author proposes that recursiveness of language could be defined as the reiteration or the embedded state of the same frames and elements in the structures of language as well as in the process of utterance generation. Part 3 is to give the argumentation on recursiveness of language. The gigantic significance of recursiveness of language lies in that it allows people to generate infinitely many sentences with a small number of sentence patterns. Finally, the author argues that the rootstock of recursiveness of language be that the recursive structure of the cosmos and the recursive structure of language are in a holographic state. Key words: recursion; recursiveness of language; holographics 本文明确地将语言的递归性(recursiveness) ，像语言的任意性与线性一样，作为语言的根本性质之一来对待，然后着重论述，语言递归性的根源来自它的结构与宇宙的结构是全息关系。 １. 理论引入 递归算法的实现 【基本信息】 【课标要求】 （三）算法与问题解决例举 1. 内容标准 递归法与问题解决 （1）了解使用递归法设计算法的基本过程。 （2）能够根据具体问题的要求，使用递归法设计算法、编写递归函数、编写程序、求解问题。 【教材分析】 “算法的程序实现”是《算法与程序设计》选修模块第三单元的内容，本节课是“递归算法的程序实现”，前面学习了用解析法解决问题、穷举法解决问题、在数组中查找数据、对数进行排序以及本节的前一小节知识点“什么是自定义函数”的学习，在学习自定义函数的基础上，学习递归算法的程序实现是自定义函数的具体应用，培养学生“自顶向下”、“逐步求精”的意识起着重要的作用。 『递归算法在算法的学习过程中是一个难点，在PASCAL和C语言等程序语言的学习过程中，往往是将其放在“函数与过程”这一章节中来讲解的。递归算法的实现也是用函数或是过程的自我调用来实现的。从这一点上来讲，作者对教材的分析与把握是准确的，思路是清晰的，目标是明确的。』 【学情分析】 教学对象是高中二年级学生，前面学习了程序设计的各种结构，在学习程序设计各种结构的应用过程中培养了用计算机编程解决现实中问题的能力，特别是在学习循环语句的过程中，应用了大量的“递推”算法。前一节课学习了如何自定义函数，在此基础上学习深入学习和体会自定义函数的应用。以递推算法的逆向思维进行求解问题，在学习过程中体会递归算法的思想过程。多维度的思考问题和解决问题是提高学生的学习兴趣关键。 『递归算法的本质是递推，而递推的实现正是通过循环语句来完成的。作者准确把握了学生前面的学习情况，对递归算法的本质与特征也分析的很透彻，可以说作者对教学任务的分析是很成功的，接来就要看，在成功分析的基础上作者是如何通过设计教学来解决教学难点的了。』 【教学目标】 应用数学学院信息安全专业班学号姓名 实验题目递归与分治法 综合实验评分表 实验报告 一、实验目的与要求 1.掌握递归算法的设计思想 2.掌握分治法设计算法的一般过程 3.理解并掌握算法渐近时间复杂度的分析方法 二、实验内容 1、折半查找的递归算法 （1）源程序代码 #include if(-1 != addr) cout << endl << n << "是上述整数中的第" << addr << "个数" << endl; else cout << endl << n << "不在上述的整数中" << endl << endl; getchar(); return 0; } （2）运行界面 ①查找成功 ②查找失败递归算法与递归程序#
数据结构与算法习题及答案
利用递归思想解决计数问题
《递归算法与递归程序》教学设计
算法分析与设计习题集整理
中学思想政治课教学方法论
递归与分治
递归算法和非递归算法的区别和转换
算法设计与分析排列树递归推算
算法分析与设计复习题及参考答案
《中学思想政治课教学法》教学大纲
算法设计与分析习题
数据结构习题
初中政治课常用教学方法有哪些
语言的递归性及其根源
高中信息技术 算法与程序设计-递归算法的实现教案 教科版
算法设计与分析：递归与分治法-实验报告
相关主题
文本预览