计算机常用算法_g

本文收了计算中常用又经典的算法,有背包问题,动态规划,最短路程等经典算法

计算机常用算法简介

龚雄兴 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分

计算机常用算法简介

本文来源：https://www.bwwdw.com/article/pan1.html