计算机常用算法_g
更新时间:2023-08-15 15:54:01 阅读量: 人文社科 文档下载
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
计算机常用算法简介
龚雄兴 2011年4月 年 月
主要内容 算法概述 动态规划 回溯法 分治与递归 贪心算法 分限界法1
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
一、算法概述 1、算法(Algorithm) 、算法 解决问题的方法( 数字世界)。 解决问题的方法(现实世界 数字世界)。 2、程序 、程序(probram) 算法的具体实现(具体的代码序列) 算法的具体实现(具体的代码序列) 3、算法与程序的主要区别 、 算法的主要特征: 算法的主要特征: 1)有输入:有零个或多个数据输入。 )有输入:有零个或多个数据输入。 2)有输出:至少有一个数据输出。 )有输出:至少有一个数据输出。 3)确定性:组成算法的每个操作是无二义的。 )确定性:组成算法的每个操作是无二义的。 4)有限性:每个操作的次数和时间是有限的。 )有限性:每个操作的次数和时间是有限的。 程序可能不满足第4) 程序可能不满足第 )条,如操作系统程序会重复 无限地执行许多用户请求。 地、无限地执行许多用户请求。2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
一、算法概述 4、算法的评价标准 、 1)正确性 ) 2)直观性 可交流性 可交流性) )直观性(可交流性 3)容错性 健壮性 健壮性) )容错性(健壮性 4)分级性 ) 5)高效性 时间 空间 时间,空间 )高效性(时间 空间)* 5、与算法执行时间有关的主要因素 、 1)计算机速度 ) 2)问题的规模 ) 3)数据的原始状态。 )数据的原始状态。 4)算法的结构 )算法的结构*
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
一、算法概述 6、时间复杂性的评价方法 、 1)最少次数-Tmin (n) )最少次数 2)最坏次数 max (n) )最坏次数-T 3)平均次数 avg(n) )平均次数-T 4)渐近阶 )渐近阶-T(n) O(1) /O(n) / O(nlog2n) / O(n2) 7、算法的描述 、 自然语言 高级语言 伪代码 N-S图* 图计算机常用算法简介
S1 S2
e S1 while/for…… S4
S2
2011年8月19日1时13分
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
一、算法概述 7、算法的描述 、 图描述的求一元二次方程的根的算法: 用N-S图描述的求一元二次方程的根的算法 图描述的求一元二次方程的根的算法 取得方程的参数:a,b,c 取得方程的参数 计算判别式:b 计算判别式 2-4ac 判别式=0 判别式 ? 输出两相等 判别式>0 ? 判别式 实根 输出两不等实根 输出两共扼虚根
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
一、算法概述 8、算法实例 、 顺序查找与二分查找 9、几个重要概念 、 1)数组与指针 数组与指针 2)函数与函数接口 函数与函数接口 3)传值与传址 传引用 传值与传址(传引用 传值与传址 传引用) 4)循环与递归 循环与递归
2011年8月19日1时13分
计算机常用
算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 1、递归算法 、 递归算法—直接或间接调用自己的算法。 递归算法 直接或间接调用自己的算法。 直接或间接调用自己的算法 递归算法的特点: 递归算法的特点: 1)子问题结构相似 规模趋小 )子问题结构相似,规模趋小 2)存在递归边界 递归结束条件 递归结束条件) )存在递归边界(递归结束条件 如: 5!=5*4! ! ! 4!=4*3! ! ! 3!=3*2! ! ! 2!=2*1! ! ! int jc (int n) 1!=1*0! ! ! { if (n==0) return 1; 0!=1 ! else return n*jc(n-1);} T(n)=1+T(n-1) =1+1+T(n-2) =……=n+T(0)
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 2、分治法的基本思想 、 分治法的基本思想是将一个规模为n的问题分解为 个规 分治法的基本思想是将一个规模为 的问题分解为k个规 的问题分解为 模较少的子问题, 模较少的子问题,这些子问题相互独立且与原问题结构相 递归地求解这些子问题, 同。递归地求解这些子问题,然后将这些子问题的解合并 得到原问题的解。 得到原问题的解。 int yz (BiNode *T) (n=n1+n2+……+nk){ if (!T) return 0;else return yz(T->lchild) + yz(T->rchild); 3、分治法运用举例 、 1)求二叉树的叶结点数 } )
返回零
空树? 空树 返回左,右子树叶子数之和 返回左 右子树叶子数之和
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 2)已知二叉树 的先序和中序遍历序列分别为串 和r, 已知二叉树T的先序和中序遍历序列分别为串 已知二叉树 的先序和中序遍历序列分别为串l和 , 试构造该二叉树T 试构造该二叉树 某二叉树的先序遍历序列为ABCGIDJEFH,中序遍历 某二叉树的先序遍历序列为 , 序列为DCIBJDAFEH,构造该二叉树 序列为 ,构造该二叉树: ABCGIDJEFH A GCIBJDAFEH BCGIDJ B GCIBJD EFH E FEH
CGI GCI
DJ JD
F F
H H
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 2)已知二叉树 的先序和中序遍历序列分别为串 和r, 已知二叉树T的先序和中序遍历序列分别为串 已知二叉树 的先序和中序遍历序列分别为串l和 , 试构造该二叉树T 试构造该二叉树 (续) 先序遍历: 先序遍历: A B C G I D J E F H 中序遍历: 中序遍历: G C I B J D A F E H
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 2)已知二叉树 的先序和中序遍历序列分别为串 和r, 已知二叉树T的先序和中序遍历序列分别为串 已知二叉树 的先序和中序遍历序列分别为串l和 , 试构造该二叉树T(续 试构造该二叉树 续) 。 事实上:二叉树由树根和两棵子树构成,若分别完成 事实上:二叉树由树根和两棵
子树构成, 根及左、右子树的构造即可完成全部任务(一分三)。 根及左、右子树的构造即可完成全部任务(一分三)。 过程一:构造二叉树的根结点-关键是找到根结点 过程一:构造二叉树的根结点 关键是找到根结点 过程二:构造左子树(与原问题相同且规模更小) 过程二:构造左子树(与原问题相同且规模更小) 过程三:构造右子树(与原问题相同且规模更小) 过程三:构造右子树(与原问题相同且规模更小) 过程四:合并成一棵树(指针修改) 过程四:合并成一棵树(指针修改)
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 2)已知二叉树 的先序和中序遍历序列分别为串 和r, 已知二叉树T的先序和中序遍历序列分别为串 已知二叉树 的先序和中序遍历序列分别为串l和 , 试构造该二叉树T( 试构造该二叉树 (续)。 构造二叉树的N-S图: 构造二叉树的 图 遍历序列为空 建立根结点 构建左子树 构建右子树 左右子树挂于根下 返回根指针
返回空指针
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 3)整数划分问题:将一个正整数 分解成一系列的正整 整数划分问题: 整数划分问题 将一个正整数n分解成一系列的正整 数之和: 数之和: n=n1+n2+……+nk ( n1 n2 …… nk ) 正整数n的一种分解就称为它的一个划分 正整数n的 的一种分解就称为它的一个划分。 正整数 的一种分解就称为它的一个划分。正整数 的 全部不同的划分个数称为n的划分数 记为p(n)。 的划分数, 全部不同的划分个数称为 的划分数,记为 。 例如:正整数6有 例如:正整数 有: p(6)=11。 。 n1 =6:1 : 6=6 n1 =5:1 : =5+1 n1 =4:2 : =4+2 = 4+1+1 n1 =3:3 : =3+3 = 3+2+1 = 3+1+1+1 n1 =2:3 : =2+2+2 = 2+2+1+1 = 2+1+1+1+1 n1 =1:1 : =1+1 +1+1+1+12011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 3)整数划分问题(续) 整数划分问题( 整数划分问题 由于划分方案与被分解数及最大分解数都有关, 由于划分方案与被分解数及最大分解数都有关,故设 q(n,m)是n的最大不超 的分解个数。则分如下几情形: 的最大不超m的分解个数 是 的最大不超 的分解个数。则分如下几情形: 1` 当m>n时,最大分解数最大取n,故有 时 最大分解数最大取 , q(n,m) = q(n,n)。 。 2` 当m=n时,最大分解数有等于和小于n两种情形,有: 时 最大分解数有等于和小于 两种情形, 两种情形 q(n,n) =1+ q(n,n-1)。 。 3` 当n>m>1时,最大分解数有等于和小于m两种情形, 时 最大分解数有等于和小于 两种情形, 两种情形 (等于 的
分解数 小于 的分解数 等于m的分解数 小于m的分解数 有: 等于 的分解数+小于 的分解数) q(n,m) = q(n-m,m)+ q(n,m-1) 。 4` m=1时,仅一种:n=1+1+……+1,即: 时 仅一种: , q(n,1)=1。 。2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 3、分治法运用举例 、 3)整数划分问题(续) 整数划分问题( 整数划分问题 于是我们得到q(n,m)到的递归关系: 到的递归关系: 于是我们得到 到的递归关系 q(n,n) 1+ q(n,n-1) q(n-m,m)+ q(n,m-1) 1 m>n m=n n>m>1 m=1
q(n,m)=
相信大家根据这个递归关系都能给出相应的算法。 相信大家根据这个递归关系都能给出相应的算法。
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
二、分治策略 4、递归算法小结 、 优点:结构清晰,可读性强,它为设计算法、 优点 结构清晰,可读性强,它为设计算法、调试程 结构清晰 序带来很大方便。 序带来很大方便。 缺点:递归算法的运行效率较低, 缺点 递归算法的运行效率较低,无论是耗费的计算 递归算法的运行效率较低 时间还是占用的存储空间都比非递归算法要多。 时间还是占用的存储空间都比非递归算法要多。
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
三、动态规划 1、引例 矩阵连乘问题 、引例--矩阵连乘问题 Cij=ai1*b1j+ai2*b2j+…+ain*bnj
A
B
=n×l
A×B
m×n
m×l
2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
三、动态规划 1、引例 矩阵连乘问题 续) 、引例--矩阵连乘问题 矩阵连乘问题(续 我们知道,矩阵的乘法满足:A*(B*C) =(A*B)*C, 我们知道,矩阵的乘法满足: , 从计算量上考虑,两种方案是否一样呢? 从计算量上考虑,两种方案是否一样呢? 考查实例: 考查实例:A10*100*B100*5*C5*50: 由于矩阵的乘法中相加的次数是固定的, 由于矩阵的乘法中相加的次数是固定的,计算量的差异 主要表现在相乘的次数上: 主要表现在相乘的次数上 A*B: A*B: 10*100*5 10*5) (10*5) (A*B)*C: 10*100*5+10*5*50=7500 : B*C: 100 *5 *50 : (100*50) ) A* ( B*C) : 100 *5 *50 +10*100*50=75000 思考题: 思考题: 1)矩阵的连乘中乘法的计算次数与什么有关? )矩阵的连乘中乘法的计算次数与什么有关? 2)n个矩阵连乘,需要几个参数? ) 个矩阵连乘,需要几个参数? 个矩阵连乘2011年8月19日1时13分
计算机常用算法简介
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
三、动态规划 1、引例 矩阵连乘问题 续 ) 、引例--矩阵连乘问题 矩阵连乘问题(续 以4个矩阵连乘为例,利用分治法的思想,我们有: 个矩阵连乘为例,利用分治法的思想,我们有: 个矩阵连乘为例[1:4] 自顶向下递归, 自顶向下递归,有 许多重复计算 [1:3][4:4]
[1:1][2:4]
[1:2][3:4]
[2:2][3:4] [2:3][4:4] [1
:1][2:2] [3:3][4:4]
[1:1][2:3] [1:2][3:3]
[3:3][4:4]
[2:2][3:3]
[2:2][3:3]计算机常用算法简介
[1:1][2:2]19
2011年8月19日1时13分
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
三、动态规划 1、引例 矩阵连乘问题 续 ) 、引例--矩阵连乘问题 矩阵连乘问题(续 若采用自底向上的方法,有: 若采用自底向上的方法,[1:4] 自底向上计算 没有重复计算
[1:3]
[2:4]
[1:2]
[2:3]
[3:4]
[1:1]
[2:2]
[3:3]计算机常用算法简介
[4:4]20
2011年8月19日1时13分
本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法
三、动态规划 2、动态规划的基本思想 、 动态规划与分治法类似, 动态规划与分治法类似,也是将待求问题分解成若 干个子问题,通过求子问题的解来求出整个问题的解。 干个子问题,通过求子问题的解来求出整个问题的解。与 分治法不同的是,它的子问题往往不是相互独立的。 分治法不同的是,它的子问题往往不是相互独立的。若用 分治法来解,会出现许多的重复计算。 分治法来解,会出现许多的重复计算。动态规划的思想是 按问题规模从小到大逐步求出子问题的解, 按问题规模从小到大逐步求出子问题的解,最后求出整个 问题的解。 问题的解。 3、动态规划算法的基本要素 、 1)最优子结构(小最优 大最优) 大最优) )最优子结构( 2)重叠子问题(有重复子问题) )重叠子问题(有重复子问题)
2011年8月19日1时13分
计算机常用算法简介
正在阅读:
计算机常用算法_g08-15
基于数学形态学的围棋棋群聚类算法08-13
跟师每日一学草药12:鬼针草11-18
银行信贷岗工作总结(多篇)范例08-03
组胚习题09-21
幼儿园小班九月份工作总结08-23
课堂管理艺术试题b(benz)07-18
工业产品设计(Inventor)技能大赛模拟题(咖啡壶)12-06
信号检测论 - 评价法实验报告06-03
- 粮油储藏基础知识
- 论文范文(包括统一封面和内容的格式)
- 经典解题方法
- 综合部后勤办公用品管理办法+领用表
- 学生宿舍突发事件应急预案
- 16秋浙大《生理学及病理生理学》在线作业
- 四分比丘尼戒本(诵戒专用)
- 浙江财经大学高财题库第一章习题
- 九大员岗位职责(项目经理、技术负责人、施工员、安全员、质检员、资料员、材料员、造价员、机管员)
- 旅游财务管理习题(学生版)
- 德阳外国语高二秋期入学考试题
- 投资学 精要版 第九版 第11章 期权市场
- 控制性详细规划城市设计认识
- bl03海运提单3国际贸易答案
- 2010-2011学年湖北省武汉市武珞路中学七年级(上)期中数学试卷
- VB程序填空改错设计题库全
- 教师心理健康案例分析 - 年轻班主任的心理困惑
- 民间借贷司法解释溯及力是否适用?
- 三联书店推荐的100本好书
- 《化工原理》(第三版)复习思考题及解答
- 算法
- 常用
- 计算机