算法5个特征:
1.有穷性:保证执行优先步骤之后结束
2.确切性:每一步骤都有确切的定义
3.输入:每个算法有零个或多个输入
4.输出:每个算法有一个或多个输出
5.可行性:原则上算法能够精确地运行,进行有限次运算后即可完成一种运算
计算机算法可分为两大类:
1.数值运算算法:求解数值
2.非数值运算算法:事务管理领域
算法流程图:1.顺序结构 2.选择结构(也成分支结构) 3.循环结构(当型循环、直到型循环)
算法思想8种:枚举、递推、递归、分治、贪心、试探法、动态迭代、模拟
1.枚举算法
枚举算法思想:将问题的所有可能的答案一一列举,然后根据条件判断此答案是否合适。保留合适的,丢弃不合适的。
解题思路:(1)确定枚举对象、枚举范围和判定条件(2逐一列举可能的解,验证每个解是否是问题的解
枚举算法步骤:(1题解的可能范围,不能遗漏任何一个真正解,也要避免有重复(2判断是否是真正解的方法(3使可能解的范围降至最小,以便提高解决问题的效率
实例一:百钱买百鸡
实例二:填写运算符
2.递推算法思想
(1 顺推法 :从已知条件出发,逐步推算出要解决问题的方法。例如斐波那契数列
(2 逆推法 :从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。
实例一【斐波那契数列】:兔子数列。兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死,一年以后而已繁殖多少对兔子?
实例二【逆推算法】:银行存款。母亲为儿子小sun 4 年的大学生活准备一一笔存款,方式是整存零取,规定小Sun每月月底取下一个月的生活费。现在假设银行的年利息为1.71%,请编写程序,计算母亲最少需要存入多少钱?
3.递归算法思想
递归算法特点:(1 递归过程一般通过函数或子过程来实现 (2 递归算法在函数或子过程的内部,直接或者间接地调用自己的算法 (3 递归算法实际上是把问题转化为规模缩小的同类问题的子问题,然后再递归调用函数或过程来表示问题的解。
注意:(1 递归是在过程或函数中调用自身的过程。(2 在使用递归策略时,必须有一个明确的递归结束条件,这称为递归出口 (3 递归算法通常显得很简洁,但是运行效率较低,所以一般不提倡用递归算法设计程序 (4 在递归调用过程中,系统用栈来存储每一层的返回点和局部量。如果递归次数过多,则容易造成栈溢出,所以一般不提倡用递归算法设计程序
实例一:汉诺塔。寺院里有3根柱子,第一根有64个盘子,从上往下盘子越来越大。方丈要求小和尚A把这64个盘子全部移动到第3根柱子上。在移动的时候,始终只能小盘子压着大盘子,而且每次只能移动一个。[http://demo.sucaihuo.com/2215/]
事例二:阶乘。自然数由1~n的n个数连乘积叫做n的阶乘,记作n!
4.分治算法思想
分治算法解题步骤:(1 分解:将要解决的问题划分成若干个规模较小的同类问题 (2求解:当子问题划分得足够小时,用较简单的方法解决 (3合并:按原问题的要求,将子问题的解逐层合并构成原问题的解
实例一:大数相乘。指计算两个大数的积。假如计算123*456的结果