第1章 基础算法思想

零基础学算法第1章：基础算法思想课程安排•编程的灵魂：数据结构+算法•算法的作用•递推算法•枚举(穷举)算法•递归算法•分治算法•贪婪算法•试探算法•模拟算法•算法的评价1.1编程的灵魂：数据结构+算法•由上面的公式可以看出，程序设计中数据结构和算法是最重要的，是编程的灵魂。•数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。往往是在发展一种算法的时候，构建了适合于这种算法的数据结构。一种数据结构如果脱离了算法，也就没有存在的价值了。程序=数据结构+算法+程序设计语言1.2算法的作用•1.2.1算法的作用解决任何一个实际问题，都不可避免地涉及到算法的问题，例如本章开头提到的存钱问题，再如节假日公司值班人员的排班等，都需要通过一定的算法，得到一个最优（或较优）的方案。•1.2.2实例：看商品猜价格首先出示一件价格在999元以内的商品，参与者要猜出这件商品的价格。在猜价格的过程中，主持人会根据参与者给出的价格，相应地给出“高了”或“低了”的提示。1.3递推算法递推算法使用“步步为营”的方法，不断利用已有的信息推导出新的东西。–顺推法：是指从已知条件出发，逐步推算出要解决问题的方法。例如：斐波拉契数列就可以通过顺推法不断递推算出新的数据。–逆推法：是从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。1.3.1算法思路1.3.2顺推实例1.3递推算法1.3.3逆推实例•若在第48月小龙大学毕业时连本带息要取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枚举(穷举)算法枚举法的本质就是从所有候选答案中去搜索正确的解，使用该算法需要满足两个条件：（1）可预先确定候选答案的数量；（2）候选答案的范围在求解之前必须有一个确定的集合。1.4.1算法思路算法描述题×算_____________题题题题题题12345×1_____________5555551.4枚举(穷举)算法1.4.2实例：填数游戏555555=由于算术表达式的特殊性，在编程求解这个算式时，需要注意以下几点：–当填入除号时，要求右侧的数不能为0。–乘除的运算级别比加减高。555555=*/-+1.4枚举(穷举)算法1.4.3实例：填运算符1.5递归算法递归算法，就是一种直接或者间接地调用自身的算法。递归算法的具体实现过程一般通过函数或子过程来完成，在函数或子过程的内部，编写代码直接或者间接地调用自己，即可完成递归操作。1.5.1算法思路fact(5)=5*fact(4)fact(4)=4*fact(3)fact(3)=3*fact(2)fact(2)=2*fact(1)fact(1)=1fact(2)=2*1fact(3)=3*2*1fact(4)=4*3*2*1fact(5)=5*4*3*2*1返回返回返回返回第2次调用第3次调用第4次调用第5次调用第6次调用fact(6)=6*fact(5)fact(6)=6*5*4*3*2*1第1次调用返回1.5.2求阶乘1.5递归算法6!=6*5*4*3*2*112160301573102222222……余1……余0……余0……余1……余1……余1……余11.5.3实例：数制转换1.5递归算法(121)10=(1111001)21.6分治算法•1.6.1算法思路使用分治法设计程序时，一般可按以下步骤进行：（1）分解：将要求解的问题划分成若干规模较小的同类问题；（2）求解：当子问题划分得足够小时，用较简单的方法解决；（3）合并：按求解问题的要求，将子问题的解逐层合并，即可构成最终的解。•1.6.2实例：乒乓球比赛赛程安排1.7贪婪算法•1.7.1算法思路贪婪算法基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到算法中的某一步不能再继续前进时，就停止算法，给出近似解。由贪婪算法的特点和思路可看出，该算法存在以下问题：–不能保证最后的解是最优的；–不能用来求最大或最小解问题；–只能求满足某些约束条件的可行解的范围。•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算法思路为了求得问题的解，先选择某一种可能情况进行试探，在试探过程中，一旦发现原来的选择的假设情况是错误的，就退回一步重新选择，继续向前试探，如此反复进行，直至得到解或证明无解。•1.8.2实例：生成彩票号码组合假设有一种彩票，每注由7个1~29的数字组成，且这7个数字不能相同，编写程序生成所有的号码组合。1.9模拟算法•1.9.1算法思路在程序设计语言中，可使用随机函数来模拟自然界中发生的不可预测情况。C语言中使用srand()和rand()函数可生成随机数。•1.9.2实例：猜数游戏使用模拟法编写一个猜数游戏，由计算机随机生成一个1~100之内的整数，然后由用户来猜这个数，根据用户猜测的次数分别给出不同的提示文字。•1.9.3实例：模拟掷骰子游戏由用户输入骰子数量和参赛人数，然后由计算机随机生成每一粒骰子的数量，再累加起来就得到每一个选手的总点数。1.10算法的评价•1.10.1算法评价原则–正确性。–高效性。–空间性。–可读性。•1.10.2算法的效率通常认为，通过统计算法中基本操作重复执行的次数就可近似地得到算法的执行效率，用O(n)表示，称为时间复杂度。性格决定命运,专注成就人生