第一篇：算法和算法描述教案
一、教学内容：算法和算法的描述（选修1算法与程序设计 广东教育出版社）
二、教学课时：1课时
三、教学地点：计算机室2
四、教学目标：
1、知识目标
（1）明白算法的概念，理解算法的特征。（2）掌握算法描述的三种方法，能看懂流程图。（3）了解算法的意义，找出三种算法描述的优缺点。
2、技能目标
（1）知道在什么场合应该用什么算法描述。
（2）能对算法和算法的描述正确定位，能用算法解决实际问题，为学习后面的程序设计打下基础。
3、情感目标
（1）能把现实社会中的问题用算法描述出来，培养学生们的合作精神和想象能力，以提高学生们的信息素养。
五、教学方法：任务驱动法
六、教学重点：
算法的概念、描述算法的三种方法。
七、教学难点：
用流程图描述算法。
八、教学过程
1.激发兴趣、创设情景
这节课内容主要是一些概念和理论，而算法的概念和理论都太抽象，讲起来非常的枯燥乏味，那么就要把这些抽象的东西变得通俗易懂，使学生能轻松而又愉快的接受并理解。
举出一个例子如炒土豆丝如何做？引导学生们一步步说出步骤，最后教师总结：算法就是解决问题的方法和步骤。在以后的编程中也要记住了，有些步骤是可以颠倒的，不影响程序的结果；但是有些一但颠倒了那最终的结果也就全变了。
2.讲.解
激发学生的兴趣后对算法、算法的特征（确定性、有穷性）进行讲解，注意运用生活中的实例，以便让学生们理解。
讲述算法的三种描述方法：自然语言、流程图、伪代码。学生们比较熟悉的是自然语言，陌生难理解的是流程图和伪代码。
先带学生们了解自然语言，然后讲伪代码，讲完伪代码后，引导学生们如何把这些程序用流程图表示出来。流程图的基本图形及其功能
给出一个程序，让学生们先读这个程序，再用流程图表示这个程序如：
Private Sub Command1_Click()a = InputBox(“输入数字”)If a Mod 2 = 0 Then Print a & “是偶数” Else Print a & “是奇数” End If End Sub 学生们自学后，由教师引导发现这是一个判断奇偶数的程序，找一个学生展示他的流程图，然后大家共同检查这个流程图是否正确。
九、课堂作业 再给学生们一个程序，让学生们读并且在word中画出流程图，然后教到主机上。
十、课后反思：
在本节课中进行任务驱动式教学，充分发挥学生的主观能动性。同时这节课内容多，而且难以理解，练习生活中的实例，既可以激发学生们的兴趣，又有助于知识的迁移和内化。
第二篇：算法、流程图教案
算法、流程图
教学目标：
①了解算法的含义、算法的思想．
②理解程序框图的三种基本逻辑结构：顺序、选择、循环．
③理解几种基本算法语句—输入语句、输出语句、赋值语句、条件语句、循环语句的含义.考情分析：
①高考对本章的考查主要以填空题的形式出现，单独命题以考查考生对流程图的识别能力为主，对算法语言的阅读理解能力次之。
② 算法可结合在任何试题中进行隐性考查，因为算法思想在其他数学知识中的渗透是课标的基本要求，常见的与其他知识的结合有分段函数，方程，不等式，数列，统计等知识综合，以算法为载体，以算法的语言呈出，实质考查其他知识。
1.(必修3P11练习2改编)下面的流程图表示了一个____________________的算法．
2.(必修3P34复习7改编)图中的伪代码运行后输出的结果为________．
3.为了在运行如下所示的伪代码后输出的y值为16，应输入的整数x＝________.S←0Read xIf x<0 Thena←x2 y←x＋1For I From 1 To 9 Step 2Else(第3题图)
S←S＋a×I
(第4题图)2 y←x－2 a←a×－1End IfEnd ForPrint yPrint S4.(必修3P24习题7改编)阅读伪代码，若使这个算法执行的结果是－1＋3－5＋7－9的计算结果，则a的初始值x是________．
1.算法： 2.流程图：
流程图是由一些图框和流程线组成的，其中图框表示各种操作的类型，图框中的文字和符号表示操作的内容，流程线表示操作的先后次序．
3.构成流程图的图形符号及其作用 起止框用““” ” 输入、输出框用“
” 处理框用“
” 判断框用4.基本的算法结构（顺序结构、选择结构、循环结构）5.伪代码
赋值语句：
用符号“x←y”表示 输入语句：“Read a，b” 输出语句：“Print x” 条件语句： If A Then
B Else
C End If 其中A表示判断的条件，B表示满足条件时执行的操作内容，C表示不满足条件时执行的操作内容，End If表示条件语句结束．
循环语句：“For”语句和“While”语句．“For”语句的一般形式为For I From “初值” To “终值” Step “步长” „ End For.例1 写出下列用伪代码描述的算法执行后的结果． 下列用条件语句描述的算法： Read x If x≤10 Then
p←0.35x Else
p←3.5＋0.7(x－10)End If Print p 若输入x＝18，则p＝________.例2 如图，如果执行下面流程图，那么输出的S等于________．
反馈练习
1.(2011·福建文)下列用伪代码描述的算法执行后的结果是________． Read a，ba＝1If a>b Thenb＝2 m←aa＝a＋b
Else
m←bPrint aEndEnd If
Print m2.(2011·江苏)根据如图所示的伪代码，当输入a，b分别为2,3时，最后输出的m的值为________.3.(2011·天津文)阅读左下边的程序框图，运行相应的程序，若输入x的值为－4，则输出y的值为________．
4.(2011·湖南文)若执行如下图所示的框图，输入x1＝1，x2 ＝ 2, x3 ＝ 4, x4 ＝ 8，则输出的数等于________.
第三篇：算法案例教案
课题：§1．3算法案例
第1课时 辗转相除法与更相减损术、秦九韶算法
一、教学目标：
根据课标要求：在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力。制定以下三维目标：
1、知识与技能
理解算法案例的算法步骤和程序框图.2、过程与方法：
引导学生得出自己设计的算法程序.3、情感态度与价值观：
体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.二、重点与难点：
重点：引导学生得出自己设计的算法步骤、程序框图和算法程序.解决策略：通过分析解决具体问题的算法步骤来引导学生写出算法，根据算法画出程序框图，再根据框图用规范的语言写出程序。
难点：体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力.解决策略：让学生能严谨地按照自己是程序框图写出程序。
三、学法与教学用具：
1、学法：直观感知、操作确认。
2、教学用具：多媒体。
四、教学过程
（一）引入课题
大家喜欢打乒乓球吧，由于东、西方文化及身体条件的不同，西方人喜欢横握拍打球，东方人喜欢直握拍打球，对于同一个问题，东、西方人处理问题方式是有所不同的.在小学，我们学过求两个正整数的最大公约数的方法：先用两个数公有的质因数连续去除，一直除到所得的商是互质数为止，然后把所有的除数连乘起来.当两个数公有的质因数较大
时（如与6 105），使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.（二）研探新知
（1）怎样用短除法求最大公约数？
（2）怎样用穷举法（也叫枚举法）求最大公约数？（3）怎样用辗转相除法求最大公约数？（4）怎样用更相减损术求最大公约数？ 讨论结果：（1）短除法
求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.（2）穷举法（也叫枚举法）
穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.（3）辗转相除法
辗转相除法求两个数的最大公约数，其算法步骤可以描述如下： 第一步，给定两个正整数m，n.第二步，求余数r：计算m除以n，将所得余数存放到变量r中.第三步，更新被除数和余数：m=n，n=r.第四步，判断余数r是否为0.若余数为0，则输出结果；否则转向第二步继续循环执行.如此循环，直到得到结果为止.这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法.（4）更相减损术
我国早期也有解决求最大公约数问题的算法，就是更相减损术.《九章算术》是中国古代的数学专著，其中的“更相减损术”也可以用来求两个数的最大公约数，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也.以等数约之.”翻译为现代语言如下：
第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.（三）范例分析
例1 用辗转相除法求8 251与6 105的最大公约数,写出算法分析，画出程序框图，写出算法程序.解：用两数中较大的数除以较小的数，求得商和余数：8 251=6 105×1+2 146.由此可得，6 105与2 146的公约数也是8 251与6 105的公约数，反过来，8 251与6 105的公约数也是6 105与2 146的公约数，所以它们的最大公约数相等.对6 105与2 146重复上述步骤：6 105=2 146×2+1 813.同理，2 146与1 813的最大公约数也是6 105与2 146的最大公约数.继续重复上述步骤： 2 146=1 813×1+333，1 813=333×5+148，333=148×2+37，148=37×4.最后的除数37是148和37的最大公约数，也就是8 251与6 105的最大公约数.这就是辗转相除法.由除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步之后完成，从而总可以用辗转相除法求出两个正整数的最大公约数.算法分析：从上面的例子可以看出，辗转相除法中包含重复操作的步骤，因此可以用循环结构来构造算法.算法步骤如下：
第一步，给定两个正整数m，n.第二步，计算m除以n所得的余数为r.第三步，m=n，n=r.第四步，若r=0，则m，n的最大公约数等于m；否则，返回第二步.程序框图如右图： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m
END 例2 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，如下图所示.98-63=35 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公约数等于7.前面我们学习了辗转相除法与更相减损术，现在我们来学习一种新的算法：秦九韶算法.（1）怎样求多项式f(x)=x+x+x+x+x+1当x=5时的值呢？
一个自然的做法就是把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算.另一种做法是先计算x的值，然后依次计算x·x，（x·x）·x，（（x·x）·x）·x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果.（2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约1202~1261）在他的著作《数书九章》中提出了下面的算法：
把一个n次多项式f(x)=anx+an-1x+„+a1x+a0改写成如下形式： f(x)=anx+an-1x+„+a1x+a0 =（anx+an-1x+„+a1）x+ a0 =（（anx+an-1x+„+a2）x+a1)x+a0 =„
=（„（（anx+an-1）x+an-2）x+„+a1）x+a0.求多项式的值时，首先计算最内层括号内一次多项式的值，即v1=anx+an-1，然后由内向外逐层计算一次多项式的值，即 v2=v1x+an-2，n-2n-3n-1n-2nn-1n
n-1
222
5432
v3=v2x+an-3，„
vn=vn-1x+a0，这样，求n次多项式f（x）的值就转化为求n个一次多项式的值.上述方法称为秦九韶算法.直到今天，这种算法仍是多项式求值比较先进的算法.（3）计算机的一个很重要的特点就是运算速度快，但即便如此，算法好坏的一个重要标志仍然是运算的次数.如果一个算法从理论上需要超出计算机允许范围内的运算次数，那么这样的算法就只能是一个理论的算法.例3 已知一个5次多项式为f（x）=5x+2x+3.5x-2.6x+1.7x-0.8，用秦九韶算法求这个多项式当x=5时的值.解：根据秦九韶算法，把多项式改写成如下形式： f(x)=（(((5x+2)x+3.5)x-2.6)x+1.7)x-0.8，按照从内到外的顺序，依次计算一次多项式当x=5时的值： v0=5； v1=5×5+2=27;v2=27×5+3.5=138.5;v3=138.5×5-2.6=689.9;v4=689.9×5+1.7=3 451.2;v5=3 415.2×5-0.8=17 255.2;所以，当x=5时，多项式的值等于17 255.2.算法分析：观察上述秦九韶算法中的n个一次式，可见vk的计算要用到vk-1的值，若令v0=an，我们可以得到下面的公式：
32v0an, vvxa(k1,2,,n).k1nkk这是一个在秦九韶算法中反复执行的步骤，因此可用循环结构来实现.算法步骤如下：
第一步，输入多项式次数n、最高次的系数an和x的值.第二步，将v的值初始化为an，将i的值初始化为n-1.第三步，输入i次项的系数ai.第四步，v=vx+ai,i=i-1.第五步，判断i是否大于或等于0.若是，则返回第三步；
否则，输出多项式的值v.程序框图如右图： 程序：
INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE i＞=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END
（四）随堂练习P45 练习1、2
（五）归纳总结
（1）用辗转相除法求最大公约数.（2）用更相减损术求最大公约数.（3）.秦九韶算法的方法和步骤.以及计算机程序框图.（六）作业布置
1、P48习题1.3 A组1、2
2、完成课后巩固作业
（八）五、教学反思：
_________________________________________________________ ___________________________________________________________________________________________________________________________________________________________________________
_________________________________________________________
1.3 算法案例 第2课时 进位制
一、教学目标：
根据课标要求：掌握不同进制之间的相互转化，会用程序描述不同进制之间的转化，体会数学的转化思想，制定以下三维目标：
1、知识与技能
学生理解各种进位制与十进制之间转换的规律，会利用十进制与各种进制之间的联系进行各种进位制之间的转换。
2、过程与方法
学生经历得出各种进位制与十进制之间转换的规律的过程，进一步掌握进位制之间转换的方法。
3、情感、态度与价值观
学生通过合作完成任务后，领悟十进制，二进制的特点，了解计算机的电路与二进制的联系，进一步认识到计算机与数学的联系，培养他们的合作精神和严谨的态度。
二、教学重点、难点
重点：各进位制之间的转换。
解决策略：让学生弄懂各进位制的特点和联系，再搭配习题讲解。难点：“除k取余法”的理解。
解决策略：先给出具体的例子讲解，再延伸到一般的情况。
三、学法与教学用具
1、学法：讲授法、归纳法、讨论法。
2、教学用具：多媒体，投影仪
四、教学过程
（一）引入课题
在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一
年十二个月、一小时六十分的历法.今天我们来学习一下进位制.（二）研探新知
进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；满六十进一，就是六十进制等等.也就是说：“满几进一”就是几进制，几进制的基数（都是大于1的整数）就是几.在日常生活中，我们最熟悉、最常用的是十进制，据说这与古人曾以手指计数有关，爱好天文学的古人也曾经采用七进制、十二进制、六十进制，至今我们仍然使用一周七天、一年十二个月、一小时六十分的历法.十进制使用0 ~9十个数字.计数时，几个数字排成一行，从右起，第一位是个位，个位上的数字是几，就表示几个一；第二位是十位，十位上的数字是几，就表示几个十；接着依次是百位、千位、万位„„
例如：十进制数3 721中的3表示3个千，7表示7个百，2表示2个十，1表示1个一.于是，我们得到下面的式子： 3 721=3×10+7×10+2×10+1×10.与十进制类似，其他的进位制也可以按照位置原则计数.由于每一种进位制的基数不同，所用的数字个数也不同.如二进制用0和1两个数字，七进制用0~6七个数字.一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式 anan-1„a1a0（k）（0＜an＜k，0≤an-1，„，a1，a0＜k).其他进位制的数也可以表示成不同位上数字与基数的幂的乘积之和的形式，如 110 011（2）=1×2+1×2+0×2+0×2+1×2+1×2，7 342（8）=7×8+3×8+4×8+2×8.非十进制数转换为十进制数比较简单，只要计算下面的式子值即可： anan-1„a1a0(k)=an×k+an-1×k+„+a1×k+a0.第一步：从左到右依次取出k进制数anan-1„a1a0(k)各位上的数字，乘以相应的k的幂，k的幂从n开始取值，每次递减1，递减到0，即an×k,an-1×k,„,a1×k,a0×k； 第二步：把所得到的乘积加起来，所得的结果就是相应的十进制数.关于进位制的转换，教科书上以十进制和二进制之间的转换为例讲解，并推广到十进制和
n
n-
10nn-1321
0
543210321
0
其他进制之间的转换.这样做的原因是，计算机是以二进制的形式进行存储和计算数据的，而一般我们传输给计算机的数据是十进制数据，因此计算机必须先将十进制数转换为二进制数，再处理，显然运算后首次得到的结果为二进制数，同时计算机又把运算结果由二进制数转换成十进制数输出.1°十进制数转换成非十进制数
把十进制数转换为二进制数，教科书上提供了“除2取余法”，我们可以类比得到十进制数转换成k进制数的算法“除k取余法”.2°非十进制之间的转换
一个自然的想法是利用十进制作为桥梁.教科书上提供了一个二进制数据与16进制数据之间的互化的方法，也就是先由二进制数转化为十进制数，再由十进制数转化成为16进制数.（三）范例分析
例1 把二进制数110 011(2)化为十进制数.解：110 011(2)=1×2+1×2+0×2+0×2+1×2+1×2=1×32+1×16+1×2+1=51.点评：先把二进制数写成不同位上数字与2的幂的乘积之和的形式，再按照十进制的运算规则计算出结果.例2设计一个算法，把k进制数a（共有n位）化为十进制数b.算法分析：从例1的计算过程可以看出，计算k进制数a的右数第i位数字ai与k的乘积ai·k，再将其累加，这是一个重复操作的步骤.所以，可以用循环结构来构造算法.算法步骤如下： 第一步，输入a，k和n的值.第二步，将b的值初始化为0，i的值初始化为1.第三步，b=b+ai·k，i=i+1.第四步，判断i＞n是否成立.若是，则执行第五步；否则，返回第三步.第五步，输出b的值.程序框图如右图：
i-1i-1
i-154
0
程序：
INPUT “a,k，n=”；a，k，n b=0 i=1 t=a MOD 10 DO b=b+t*k^（i-1）a=a10 t=a MOD 10 i=i+1 LOOP UNTIL i＞n PRINT b END 例3 把89化为二进制数.解：根据二进制数“满二进一”的原则，可以用2连续去除89或所得商，然后取余数.具体计算方法如下：
因为89=2×44+1，44=2×22+0，22=2×11+0，11=2×5+1，5=2×2+1，2=2×1+0，1=2×0+1，所以
89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1 =2×（2×（2×（2×（2+1）+1）+0）+0）+1 =„=1×2+0×2+1×2+1×2+0×2+0×2+1×2 =1 011 001(2).这种算法叫做除2取余法，还可以用右边的除法算式表示：
把上式中各步所得的余数从下到上排列，得到89=1 011 001(2).上述方法也可以推广为把十进制数化为k进制数的算法，称为除k取余法.6543
02
例4 设计一个程序，实现“除k取余法”.算法分析：从例2的计算过程可以看出如下的规律：
若十制数a除以k所得商是q0，余数是r0，即a=k·q0+r0，则r0是a的k进制数的右数第1位数.若q0除以k所得的商是q1，余数是r1，即q0=k·q1+r1，则r1是a的k进制数的左数第2位数.„„
若qn-1除以k所得的商是0，余数是rn，即qn-1=rn，则rn是a的k进制数的左数第1位数.这样，我们可以得到算法步骤如下：
第一步，给定十进制正整数a和转化后的数的基数k.第二步，求出a除以k所得的商q，余数r.第三步，把得到的余数依次从右到左排列.第四步，若q≠0，则a=q，返回第二步；否则，输出全部余数r排列得到的k进制数.程序框图如右图： 程序：
INPUT “a，k=”；a，k b=0 i=0 DO q=ak r=a MOD k b=b+r*10^i i=i+1 a=q LOOP UNTIL q=0 PRINT b END
（四）随堂练习
1、将十进制数34转化为二进制数． 解：
即34(10)=100 010(2)
2、把1 234(5)分别转化为十进制数和八进制数． 解：1 234(5)=1×5+2×5+3×5+4＝194． 则1 234(5)=302(8)
所以，1 234(5)=194＝302(8)
点评：本题主要考查进位制以及不同进位制数的互化．五进制数直接利用公式就可以转化为十进制数；五进制数和八进制数之间需要借助于十进制数来转化．
32（五）归纳总结
（1）理解算法与进位制的关系.（2）熟练掌握各种进位制之间转化.（六）作业布置
1、习题1.3A组3、4.2、完成课后巩固作业
（九）五、教学反思：
_________________________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________
第四篇：算法总结
算法分析与设计总结报告
71110415 钱玉明
在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。
下面我将谈谈我对这门课程的心得与体会。
一、数学是算法的基础
经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。
①主定理
本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。
②随机算法中的许多定理的运用
在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。
这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。
二、算法的核心是思想
我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。
①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。
动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。
贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。
周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。
回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。
分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。
②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。
这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。
三、算法与应用紧密相关
我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。
这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。
四、对计算模型和NP问题的理解
由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。
首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。
NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。
最后谈谈对这门课程的建议
①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。
②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。
③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。
第五篇：算法复习材料
1.假票统计
问题描述：
由于你们团队在国际大学生诗歌大赛上取得的巨大成就，你们学校决定为你们召开一次庆功鸡尾酒会，到来的人数大大超出了预期。然而庆功会的主管却抱怨发现了有人使用假票，实际的门票是从1到N(N <= 10000)，主管怀疑有人采用复印、打印等手段伪造了门票。他把所有收上来的门票拿给你，要求你编写程序，统计所有门票中存在假票的门票数。输入：
输入文件中包含多组测试数据，每组测试数据占两行。第1行包括两个整数N和M，分别表示门票的初始总张数和参加晚会的总人数(1 <= N <= 10000,1 <= M <= 20000)。第2行为M个整数Ti，表示收到的M张门票的号码(1 <= Ti <= N)。输入文件最后一行为0 0，表示输入结束。输出：
对每组输入测试数据，输出一个整数，占一行，表示收上来的门票中共有多少张票被伪造过。输入样例： 5 5 3 3 1 2 4 6 10 6 1 3 6 6 4 2 3 1 2 0 0 输出样例： 1 4
参考代码：
//计算有几个号码被复制过 #include
2.看和说
问题描述：
看和说的顺序定义如下：任何一个字符串都是以数字开头，每个随后的元素都是被前一个元素重新定义。例如，字符串“122344111”可以被描述为“1个1，两个2，1个3，2个4和3个1”。因此，122344111以序列的形式表示出来就是1122132431。同理，101就表示1111111111。输入：
输入包括测试数据的组数，然后依次为相应的测试数据，每个数据占一行，不会超过1000位。输出： 对于每个测试数据，输出对应的字符串。
输入样例： 3 122344111 1111111111 12345 输出样例： 1122132431 101 1112131415 参考代码：
#include
num=1;
gets(s);
len=strlen(s);
for(i=0;i { if(s[i]!=s[i+1]) { printf(“%d%c”,num,s[i]); num=1; } else num++; } printf(“n”);} return 0;} 3．二进制转化为十六进制 问题描述： 输入一个2进制的数，要求输出该2进制数的16进制表示。在16进制的表示中，A-F表示10-15 输入： 第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000。输出： n行，每行输出对应一个输入。输入样例： 100000 111 输出样例： 7 参考代码1： #include inti,n,dec,len; char bin[10001]; scanf(“%d”,&n); while(n--) { scanf(“%s”,bin); len=strlen(bin);//求二进制数的长度 dec=4-len%4; if(len%4)//处理头几位，后移dec位，使得变成4的整数倍，前面补0 { for(i=len;i>=0;i--) bin[i+dec]=bin[i]; for(i=0;i bin[i]='0'; len+=dec; } for(i=0;i printf(“%X”,(bin[i+3]-'0')+(bin[i+2]-'0')*2+(bin[i+1]-'0')*4+(bin[i]-'0')*8); printf(“n”); } return 0;} //参考代码2： #include int main(){ int i, j, t, tp, p;charstr[maxn], str_rev[maxn];char res[maxn/4], tmp[6], tmp_rev[6];while(scanf(“%d”, &t)!=EOF){ while(t--){ p = 0;scanf(“%s”, &str);intlen = strlen(str);for(i = lenii;strncpy(tmp, str_rev + i, k);for(j = kj-1] = tmp[j];sscanf(tmp_rev, “%d”, &tp);//printf(“k = %d tp = %d tmp = %s tmp_rev = %sn”, k, tp, tmp, tmp_rev);switch(tp){ case 0: res[p++] = '0';break;case 1: res[p++] = '1';break;case 10: res[p++] = '2';break;case 11: res[p++] = '3';break;case 100: res[p++] = '4';break;case 101: res[p++] = '5';break;case 110: res[p++] = '6';break;case 111: res[p++] = '7';break;case 1000: res[p++] = '8';break;case 1001: res[p++] = '9';break;case 1010: res[p++] = 'A';break;case 1011: res[p++] = 'B';break;case 1100: res[p++] = 'C';break;case 1101: res[p++] = 'D';break;case 1110: res[p++] = 'E';break;case 1111: res[p++] = 'F';break;default: break;} i += 4; } for(i = p-1;i >= 0;i--)printf(“%c”, res[i]);printf(“n”);} } return 0;}
点击咨询 