欢迎来到天天文库
浏览记录
ID:26925785
大小:285.51 KB
页数:20页
时间:2018-11-30
《《基础算法思想》ppt课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、零基础学算法第1章:基础算法思想课程安排编程的灵魂:数据结构+算法算法的作用递推算法枚举(穷举)算法递归算法分治算法贪婪算法试探算法模拟算法算法的评价1.1编程的灵魂:数据结构+算法由上面的公式可以看出,程序设计中数据结构和算法是最重要的,是编程的灵魂。数据结构是算法实现的基础,算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候,构建了适合于这种算法的数据结构。一种数据结构如果脱离了算法,也就没有存在的价值了。1.2算法的作用1.2.1算法的作用解决任何一个实际问题,都不可避免地涉及到算法的问题,例如本章开头提到的存钱问题,再如节假日公司值班人员的排班等,都需要通过
2、一定的算法,得到一个最优(或较优)的方案。1.2.2实例:看商品猜价格首先出示一件价格在999元以内的商品,参与者要猜出这件商品的价格。在猜价格的过程中,主持人会根据参与者给出的价格,相应地给出“高了”或“低了”的提示。1.3递推算法递推算法使用“步步为营”的方法,不断利用已有的信息推导出新的东西。顺推法:是指从已知条件出发,逐步推算出要解决问题的方法。例如:斐波拉契数列就可以通过顺推法不断递推算出新的数据。逆推法:是从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。1.3.1算法思路1.3.2顺推实例1.3递推算法1.3.3逆推实例若在第48月小龙大学毕
3、业时连本带息要取1000元,则要先求出第47个月时银行存款的钱数第47月月末存款=1000/(1+0.0171/12);第46月月末存款=(第47月月末存款+1000)/(1+0.0171/12)依次类推,可以求出第45月、第44月……的月末存款的数值第45月月末存款=(第46月月末存款+1000)/(1+0.0171/12)第44月月末存款=(第45月月末存款+1000)/(1+0.0171/12)…………第2月月末存款=(第3月月末存款+1000)/(1+0.0171/12)第1月月末存款=(第2月月末存款+1000)/(1+0.0171/12)1.3递推算法1.4枚举(穷举
4、)算法枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:(1)可预先确定候选答案的数量;(2)候选答案的范围在求解之前必须有一个确定的集合。1.4.1算法思路1.4枚举(穷举)算法1.4.2实例:填数游戏由于算术表达式的特殊性,在编程求解这个算式时,需要注意以下几点:当填入除号时,要求右侧的数不能为0。乘除的运算级别比加减高。1.4枚举(穷举)算法1.4.3实例:填运算符1.5递归算法递归算法,就是一种直接或者间接地调用自身的算法。递归算法的具体实现过程一般通过函数或子过程来完成,在函数或子过程的内部,编写代码直接或者间接地调用自己,即可完成递归操作。1
5、.5.1算法思路1.5.2求阶乘1.5递归算法6!=6*5*4*3*2*11.5.3实例:数制转换1.5递归算法(121)10=(1111001)21.6分治算法1.6.1算法思路使用分治法设计程序时,一般可按以下步骤进行:(1)分解:将要求解的问题划分成若干规模较小的同类问题;(2)求解:当子问题划分得足够小时,用较简单的方法解决;(3)合并:按求解问题的要求,将子问题的解逐层合并,即可构成最终的解。1.6.2实例:乒乓球比赛赛程安排1.7贪婪算法1.7.1算法思路贪婪算法基本思路:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快地求得更好的解。当达到算法中的某一步不能再
6、继续前进时,就停止算法,给出近似解。由贪婪算法的特点和思路可看出,该算法存在以下问题:不能保证最后的解是最优的;不能用来求最大或最小解问题;只能求满足某些约束条件的可行解的范围。1.7.2实例:换零钱人民币有100、50、10、5、2、1、0.5、0.2、0.1等多种面额(单位为元)。在补零钱时,可有多种方案,例如需补零钱68.90元,至少可有以下方案:1张50、1张10、1张5、3张1、1张0.5、2张0.2;1张50、1张10、1张5、3张1、1张0.5、4张0.1;6张10、1张5、3张1、1张0.5、2张0.2。1.8试探算法1.8.1算法思路为了求得问题的解,先选择某一
7、种可能情况进行试探,在试探过程中,一旦发现原来的选择的假设情况是错误的,就退回一步重新选择,继续向前试探,如此反复进行,直至得到解或证明无解。1.8.2实例:生成彩票号码组合假设有一种彩票,每注由7个1~29的数字组成,且这7个数字不能相同,编写程序生成所有的号码组合。1.9模拟算法1.9.1算法思路在程序设计语言中,可使用随机函数来模拟自然界中发生的不可预测情况。C语言中使用srand()和rand()函数可生成随机数。1.9.2实例:猜数游戏使用模拟法编写一个猜数游戏,由计算
此文档下载收益归作者所有