算法学习与应用从入门到精通

时间:2022-11-21 00:37:37

 

算法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的结果