北京大学屈婉玲算法设计与分析最新课件0r4
第4章贪心法
（Greedy Approach）
4.1 贪心法的设计思想
4.2贪心法的正确性证明
4.3对贪心法得不到最优解情况的处理
4.4贪心法的典型应用
44
4.4.1最优前缀码
4.4.2最小生成树
4.4.3单源最短路径
4.1贪心法的设计思想
活动选择问题={12i i 输入：S {1, 2, … , n }为n 项活动的集合，s i , f i 分别为活动i 的开始和结束时间，活动i 与j 相容?s i ≥f j 或s j ≥f i .求：最大的两两相容的活动集A 实例
i 12345678910s i 1325456882f i
4
5
6
7
9
9
10
11
12
13
策略1：排序使得s 1≤s 2≤…≤s n ，从前向后挑选排序使得从前向后挑选策略2：排序使得f 1－s 1≤f 2－s 2≤…≤f n －s n ，从前向后挑选策略3：排序使得f 1≤f 2≤…≤f n ，从前向后挑选以上策略中的挑选都要注意满足相容性条件
两个反例
=0, f1=20,s2=2, f2=5, s3=8, f3=15 策略1：S={1,2,3}，s
1
=0,f1=8,s2=7,f2=9,s3=8,f3=15 策略2：S={1,2,3}，s
1
23
1
0 2 5 8 10 15 20
2
1
3
0 2 5 8 10 15 20
贪心算法
算法Greedy Select
=12输入：活动集S ，s i ，f i , i =1,2,…,n ，且f 1≤… ≤f n 输出：A ?S ，选中的活动子集1]//1. n ←length [S ] // 活动个数 2. A ←{1}31//已选入的最后一个活动的标号3. j ←1 //已选入的最后个活动的标号 4. for i ←2 to n do 5if 5. if
s i ≥f j //判断相容性6. then A ←A ∪{i }77. j ←i 8. return A
最后完成时间t = max { f k : k ∈A }
算法运行实例
输入：S ={1,2,…,10}i 12345678910s i 1305356882f i
4
5
6
7
8
9
10
11
12
13
解:A = {1, 4, 8}, t =11
时间复杂度排序问题如何该算法对所有的实例都能得到确的解
时间复杂度：排序
+活动选择=O (n log n )+O (n )=O (n log n )问题：如何证明该算法对所有的实例都能得到正确的解？
算法的正确性证明
= 1, i2, …, 定理1算法Select 执行到第k 步, 选择k 项活动i
1
i k, 那么存在最优解A 包含i1=1,i2, … , i k
A1
根据定理：算法至多到第n 步得到最优解
≤… ≤f n
证：S={1,2,…,n}是活动集，且f
1
归纳基础：k=1, 证明存在最优解包含活动1
,截
任取最优解A, A中的活动按截止时间递增排列. 如果A的第一个活动为j，j≠1, 令
A’= (A?{ j })∪{1},
由于f
≤f j, A’也是最优解，且含有1.
1
算法正确性证明（续）
归纳步骤：假设命题对k 为真,证明对k +1 也为真.
算法执行到第k 1k 步, 选择了活动i 1=1, i 2, …, i k , 根据归纳假设存在最优解A 包含i 1= 1, i 2, … , i k , ’={|i }A 中剩下的活动选自集合S { i | i ∈S , s i ≥f k },
且 A = { i 1, i 2, … , i k }∪B
B 是S ’的最优解.（若不然, S ’的最优解为B*, B*的活动比B 多，那么B*∪{1, i 2, … , i k }是S 的最优解，且比A 的活动多,与A 的最优性矛盾.）
根据归纳基础存在中的第个活动根据归纳基础，存在S ’的最优解B’含有S ’中的第一个活动，即i k +1, 且|B ’|=|B |, 于是
})
{'(},,...,{'},...,,{112121++?∪=∪k k k k i B i i i i B i i i 也是原问题的最优解.
贪心算法的特点
设计要素：
(1) 贪心法适用于组合优化问题，该问题满足优化原则.
(2)求解过程是多步判断过程，最终的判断序列对应于问题
的最优解.
()
(3)判断依据某种“短视的”贪心选择性质，性质的好坏决
定了算法的成败.
()贪法须行确性明
(4)贪心法必须进行正确性证明
贪心法的优势：
算法简单，时间和空间复杂性低
算法简单时间和空间复杂性低
4.2贪心法的正确性证明
数学归纳法
1.叙述一个描述算法正确性的命题P(n)，n为算法步数或者
个描算法算法问题规模
2归纳基础(1)
2.归纳基础：P(1) 或P(n 0)为真, n0为某个自然数
3.归纳步骤：P(k) ?P(k+1) 第一数学归纳法
?k(k ) 交换论证 1.分析算法的解的结构特征 分析算法的解的结构特 2.从一个最优解逐步进行结构变换(替换成分、交换次序等) 3证明上述变换最终得到算法的解变换有限步结束变 3.证明上述变换最终得到算法的解、变换有限步结束、变 换保持最优性不降低、 最优装载Loading 问题： g n 个集装箱1,2,…,n 装上轮船，集装箱i 的重量w i , 轮船装载重量限制为C ，无体积限制. 问如何装使得上船的集装n ma 箱最多？不妨设w i ≤c . x i i max 1 ∑=C x w i n i i 1 ≤∑=n i x i ,...,2,11,0==贪心法将集装箱按照从轻到重排序轻者先装贪心法：将集装箱按照从轻到重排序，轻者先装 正确性证明 命题：对装载问题任何规模为n 的输入，算法得到最优解. 对问题规模归纳设集装箱从轻到重记为对问题规模归纳，设集装箱从轻到重记为1, 2, … , n.证：k =1, 只有1个箱子，算法显然正确. 假设对于k 个集装箱的输入，贪心法都可以得到最优解，考虑输入N = {1, 2, … , k +1}, 其中w 1 ≤w 2 ≤… ≤w k+1.k 由归纳假设，对于N’ = {2,3,…,k+1}，C’= C ?w 1, 贪心法得到最优解I ’. 令I = {1}∪I ’，则I (算法解)是关于N 的最优解. 若不然，存在包含1 的关于N 的最优解I *（如果I * 中没有1，用1 替换I * 中的第一个元素得到的解也是最优解），且| I *| > | I |；那么I * ?{1}是N’ 的解且 | I *?{1}| > | I ?{1} | = | I ’| ’与I ’ 的最优性矛盾. 最小延迟调度 问题： 给定客户集合A ，?i ∈A ，t i 为服务时间，d i 为完成时间，t i , d i 为正整数. 一个调度 f : A →N ，(i )为客户i 的开始时间. 求f f 最大延迟达到最小的调度，即求f 使得 }} )({max {min i i A i f d t i f ?+∈) ()(or )()(,,,i f t j f j f t i f j i A j i j i ≤+≤+≠∈? 实例 A={1, 2, 3, 4, 5}, T=<5, 8, 4, 10, 3>, D=<10, 12, 15, 11, 20> (1)=0,f1(2)=5,f1(3)=13,f1(4)=17,f1(5)=27 调度1：f 1 各任务延迟：0, 1, 2, 16, 10; 最大延迟：16 5 13 17 27 30 1 2 3 4 5 (1)0, f2(2)15, f2(3)23,f2(4)5, f2(5)27 (1)=0(2)=15(3)=23(4)=5(5)=27 调度2：f 2 各任务延迟：0, 11, 12, 4, 10; 最大延迟：12 5 15 23 27 30 515232730 1423 1 4 2 3 5 13 贪心策略选择 贪心策略1：按照t i 从小到大安排任务 i 贪心策略2：按照d i ?t i 从小到大安排任务 贪心策略3：按照d i 从小到大安排任务 贪策略按照 i 从小到大安任务策略1 对某些实例得不到最优解. 反例 反例：t 1 =1, d1=100, t2=10, d2=10 策略2对某些实例得不到最优解. 反例：t 1 =1, d1=2, t2=10, d2=10 算法设计 算法Schedule 输入：A, T, D 输入 输出：f 11. 排序A使得d 1≤d2≤…≤d n 2. f(1)←0 3. i←2 3i 3. while i≤n do 4. f(i)←f(i?1)+t i?1 //任务i-1结束时刻是任务i开始时刻41)1 5. i←i+1 设计思想：按完成时间从早到晚安排任务，没有空闲 交换论证：正确性证明 算法的解的性质： (1) (1) 没有空闲时间, 没有逆序. (2) 逆序(i, j): f(i) < f(j) 且d i > d j 引所有没有逆序没有空闲时间的调度具有相同的最引理1所有没有逆序、没有空闲时间的调度具有相同的最大延迟. 证: 设f没有逆序，在f中具有相同完成时间的客户i 1 ,i2, k . k个客户中最大延迟是最后一个客 …,i k 必被连续安排在这个客户中最大延迟是最后个客 户，被延迟的时间是 k ?k d t t j i j +∑ =1 与i 1 ,i2,…,i k 的排列次序无关. 交换论证 证明思想：从一个没有空闲时间的最优解出发，在不 改变最优性的条件下，转变成没有逆序的解. 根据引理1，改变最优性的条件下转变成没有逆序的解 这个解和算法的解具有相同的最大延迟. 证明要点 (1) 相邻逆序的存在性：如果一个最优调度存在逆序，那么 相邻逆序的存在性如果个最优调度存在逆序那么存在i < n 使得(i, i+1) 构成一个逆序. (2) 交换相邻的逆序i 和j ，得到的解的调度仍旧最优. ()每次交换后序数减多()次交换得到(3) 每次交换后逆序数减1，至多经过n n?1)/2 一个没有逆序的最优调度. 交换相邻逆序 (i , j )不影响最优性 (1) 交换i, j 对其他客户的延迟时间没影响(2)j (2) 交换后不增加j 的延迟 (3) i 在f’的延迟delay(f ’,i )小于j 在f 的延迟delay(f ,j ),因此小于f 的最大延迟r f 1(i )=s f 1(j )=s +t i f 1(j )+t j =s+t i +t j j i i d l (f’i d l (f 2(j )=s f 2(i )=s +t j f 2(i )+t i =s +t j +t i j delay(f’,i )=s ＋t j +t i －d i d j < d i ?L 2i 4.3 得不到最优解的处理方法 讨论对于哪些输入贪心法能得到最优解：输入条件 讨论贪心法的解最坏情况下与最优解的误差（见第8章）找零钱问题 设有n 种零钱，重量分别为w 1, w 2, ... , w n , 价值分别为=1,,...,.v 11, v 2, ... , v n . 需要付的总钱数是y .不妨设币值和钱数都为正整数. 问：如何付钱使得所付钱的总重最轻?12令选用第i 种硬币的数目是x i ，i =1,2,…,n n x w n i i i 12N } min{1 ∑∑=n i x y x v i i i i 1,2,...,N,, 1 =∈== 动态规划算法 属于整数规划问题，动态规划算法可以得到最优解设F k (y ) 表示用前k 种零钱，总钱数为y 的最小重量x w x v y F y F } )({min )(+?= ?递推方程 k k k k k v y x k k k 11110111++++? ? ? ??≤≤+++y w y w y F 111)(=?? ??=v 1? ? 华南农业大学期末考试试卷（A卷） 2004学年第二学期(2005.6)考试科目：算法设计与分析考试类型：（开卷）考试时间：120分钟 学号姓名年级专业 一、选择题（30分，每题2分） 1、一个算法应该包含如下几条性质，除了 A 。 （A）二义性（B）有限性（C）正确性（D）可终止性 2、解决一个问题通常有多种方法。若说一个算法“有效”是指 D 。 （A）这个算法能在一定的时间和空间资源限制内将问题解决 （B）这个算法能在人的反应时间内将问题解决 （C）这个算法比其他已知算法都更快地将问题解决 （D）A和C 3、当输入规模为n时，算法增长率最小的是 B 。 （A）5n （B）20log2n（C）2n2（D）3nlog3n 4、渐进算法分析是指 B 。 （A）算法在最佳情况、最差情况和平均情况下的代价 （B）当规模逐步往极限方向增大时，对算法资源开销“增长率”上的简化分析（C）数据结构所占用的空间 （D）在最小输入规模下算法的资源代价 5、当上下限表达式相等时，我们使用下列哪种表示法来描述算法代价？C （A）大O表示法（B）大Ω表示法 （C）Θ表示法（D）小o表示法 6、采用“顺序搜索法”从一个长度为N的随机分布数组中搜寻值为K的元素。以下对顺序搜索法分析正确的是 B 。 （A）最佳情况、最差情况和平均情况下，顺序搜索法的渐进代价都相同 （B）最佳情况的渐进代价要好于最差情况和平均情况的渐进代价 （C）最佳情况和平均情况的渐进代价要好于最差情况的渐进代价 （D）最佳情况的渐进代价要好于平均情况的渐进代价，而平均情况的渐进代价要好于最差情况的渐进代价 7、递归通常用 C 来实现。 （A）有序的线性表（B）队列（C）栈（D）数组 8、分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题，分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。C （A）问题规模相同，问题性质相同 （B）问题规模相同，问题性质不同 （C）问题规模不同，问题性质相同 （D）问题规模不同，问题性质不同 9、在寻找n个元素中第k小元素问题中，如快速排序算法思想，运用分治算法对n 个元素进行划分，如何选择划分基准？下面 D 答案解释最合理。 （A）随机选择一个元素作为划分基准 （B）取子序列的第一个元素作为划分基准 （C）用中位数的中位数方法寻找划分基准 （D）以上皆可行。但不同方法，算法复杂度上界可能不同 10、对于0－1背包问题和背包问题的解法，下面 C 答案解释正确。 （A）0－1背包问题和背包问题都可用贪心算法求解 （B）0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解 （C）0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解 （D）因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解 11、关于回溯搜索法的介绍，下面D是不正确描述。 （A）回溯法有“通用解题法”之称，它可以系统地搜索一个问题的所有解或任意解（B）回溯法是一种既带系统性又带有跳跃性的搜索算法 （C）回溯算法在生成解空间的任一结点时，先判断该结点是否可能包含问题的解，如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向祖先结点回溯 （D）回溯算法需要借助队列这种结构来保存从根结点到当前扩展结点的路径 改：树结构 回溯法，又被称为通用解题法，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在问题的解空间中按深度优先策略，从根结 4.1 已知铜氨络合物各级不稳定常数为 K 不稳1=7.8×10-3 K 不稳2=1.4×10-3 K 不稳3=3.3×10-4 K 不稳4=7.4×10-5 （1）计算各级稳定常数K 1~K 4和各级累积常数β1~β4； （2）若铜氨络合物水溶液中Cu(NH 3)2+4的浓度为Cu(NH 3)2+ 3的10倍，问溶液中[NH 3]是多少？ （3）若铜氨络合物溶液中c (NH 3)=1.0×10-2mol 〃L -1，c (Cu 2+)=1.0×10-4 mol 〃L -1（忽略Cu 2+ ，NH 3的副反应）， 计算Cu 2+ 与各级铜氨络合物的浓度。此时溶液中Cu(Ⅱ)的主要存在型体是什么？ 答案： （1）K 不1 K 不2 K 不3 K 不4 7.8×10-3 1.4×10-3 3.3×10-3 7.4×10-5 14 1 K K = 不 23 1 K K = 不 32 1 K K = 不 41 1K K = 不 1.4×104 3.0×103 7.1×102 1.3×102 11K β= 212K K β= 3213K K K β= 43214K K K K β= 1.4×104 4.2×107 3.0×1010 3.9×1012 （2） ()[]()[] []10NH NH Cu NH Cu 3 4 23 3243==++ K []12 4 3 L mol 10 7.710NH --??==K （3） ()()14123L mol 100.1Cu L mol 100.1NH ----??=??=c c ()() []4 4 333 322 31302][NH ]NH [NH ]NH [1Cu Cu ]Cu [βββ βc x c ++++= ?=+ 12810674424 109.3100.1100.3100.1102.4100.1104.1100.11100.1???+???+???+???+?= -----194 4L mol 104.110 3.7100.1---??=??= ()[]()[]174 4 13 1 23 L mol 109.110 0.110 3.7 NH Cu NH Cu ---+ ??=???=?=βx c ()[]()[]1644 22 32 223L mol 108.5100.1103.7NH Cu NH Cu ---+??=???=?=βx c ()[]()[]1544 33 33 23 3L mol 101.4100.1103.7NH Cu NH Cu ---+??=???=?=βx c ()[]()[]1544 44 34 24 3L mol 103.5100.1103.7NH Cu NH Cu ---+ ??=???=?=βx c 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 课程设计报告 课程设计名称: 算法设计与分析 系 : 三系 学生姓名: 吴阳 班级: 12软件(2)班 学号: 0311232 成绩: 指导教师: 秦川 开课时间: 年一学期 一、问题描述 1．普通背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 能够选择物品i的一部分, 而不一定要全部装入背包, 1≤i≤n。 2．0/1背包问题 给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。选择装入的背包的物品, 使得装入背包中的物品的总价值最大, 在选择物品i装入背包时, 对于每种物品i只有两种选择, 即装入背包或者不装入背包, 不能将物品装入背包多次, 也不能只装入部分的物品i。 3．棋盘覆盖问题 在一个2k x 2k个方格组成的棋盘中恰有一个方格与其它的不同称为特殊方格, 想要求利用四种L型骨牌( 每个骨牌可覆盖三个方格) 不相互重叠覆盖的将除了特殊方格外的其它方格覆盖。 二、问题分析 1．普通背包问题 对于背包问题, 若它的一个最优解包含物品j, 则从该最优解中拿出所含的物品j的那部分重量Ｗ, 剩余的将是n-1个原重物品1, 2, ······, j-1, j+1, ·····, n以及重为Ｗi－Ｗ的物品j 中可装入容量为C－Ｗ的背包且具有最大价值的物品。 2．0/1背包问题 如果当前背包中的物品的总容量是cw, 前面的k-1件物品都已经决定好是否要放入包中, 那么第k件物品是否放入包中取决于不等式 cw + wk <= M (其中, wk为第k件物品的容量, M为背包的容量)( 此即约束条件) 然后我们再寻找限界函数, 这个问题比较麻烦, 我们能够回忆一下背包问题的贪心算法, 即物品按照物品的价值/物品的体积来从大到小排列, 然后最优解为( 1, 1, 1......., 1, t, 0, 0, ......) , 其中0<=t<=1; 因此, 我们在确定第k个物品到底要不要放入的时候(在前k-1个物品已经确定的情况下), 我们能够考虑我们能够达到的最大的价值, 即我们能够经过计算只放入一部分的k物品来计算最大的价值。我们要确保当前选择的路径的最大的价值要大于我们已经选择的路径的价值。这就是该问题的限界条件。经过该条件, 能够减去很多的枝条, 大大节省运行时间。 3．棋盘覆盖问题 每次都对分割后的四个小方块进行判断, 判断特殊方格是否 算法实现题3-7 数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形，如图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。编程任务： 对于给定的由n行数字组成的数字三角形，编程计算从三角形的顶至底的路径经过的数字和的最大值。数据输入： 有文件input.txt提供输入数据。文件的第1行是数字三角形的行数n，1<=n<=100。接下来的n行是数字三角形各行的数字。所有数字在0-99之间。结果输出： 程序运行结束时，将计算结果输出到文件output.txt中。文件第1行中的数是计算出的最大值。 输入文件示例输出文件示 例 input.txt output.txt 5 30 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 源程序： #include "stdio.h" voidmain() { intn,triangle[100][100],i,j;//triangle数组用来存储金字塔数值,n表示行数 FILE *in,*out;//定义in，out两个文件指针变量 in=fopen("input.txt","r"); fscanf(in,"%d",&n);//将行数n读入到变量n中 for(i=0;i HUNAN CITY UNIVERSITY 算法设计与分析课程设计 题目：求最大值与最小值问题 专业： 学号： 姓名： 指导教师： 成绩： 二0年月日 一、问题描述 输入一列整数，求出该列整数中的最大值与最小值。 二、课程设计目的 通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。 三、问题分析 看到这个题目我们最容易想到的算法是直接比较算法：将数组的第 1 个元素分别赋给两个临时变量：fmax:=A[1]; fmin:=A[1]; 然后从数组的第 2 个元素 A[2]开始直到第 n个元素逐个与 fmax 和 fmin 比较，在每次比较中，如果A[i] > fmax，则用 A[i]的值替换 fmax 的值；如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值；否则保持 fmax（fmin）的值不变。这样在程序结束时的fmax、fmin 的值就分别是数组的最大值和最小值。这个算法在最好、最坏情况下，元素的比较次数都是 2(n-1)，而平均比较次数也为 2(n-1)。 如果将上面的比较过程修改为：从数组的第 2 个元素 A[2]开始直到第 n 个元素，每个 A[i]都是首先与 fmax 比较，如果 A[i]>fmax,则用 A[i]的值替换 fmax 的值；否则才将 A[i]与 fmin 比较，如果 A[i] < fmin，则用 A[i]的值替换 fmin 的值。 这样的算法在最好、最坏情况下使用的比较次数分别是 n-1 和 2(n-1),而平均比较次数是 3(n-1)/2,因为在比较过程中，将有一半的几率出现 A[i]>fmax 情况。 压缩软件课程设计书 一、问题描述： 建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 二、算法分析及思路： 对于该问题，我们做如下分析： （1）首先得构造出哈弗曼树，我们用函数HuffmanTree(int w[],int s[],int n)设计；（2）在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen[])设计； （3）实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计； （4）其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen[])设计； （5）在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen[])设计； （6）其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。 三、主要解决的设计问题： 1.写一个对txt文件压缩和解压的程序，使用动态编码。 2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树； 3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。 4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。 四、程序设计的流程图： 3.1 从手册中查出下列各酸的酸度常数p K a ，分别计算它们的K a 及与其相应的共轭碱的K b 值。 34224+43+ 3.2 （1）计算pH=5.0时，H 3PO 4的摩尔分数3210。（2）假定H 3PO 4各种形式总浓度是0.050 mol 〃L -1 ， 问此时H 3PO 4、H 2PO 4-、HPO 42-、PO 43-的浓度各为多少？ 答案：（1）123 112122 a a a 03 2 a a a a a a [H ][H ][H ]K K K x K K K K K K +++ = +++ 10 69.2137.1416.1200.1531.1221.716.2100.31010101010--------?=+++= 3 16 .1200 .15337.1416.1216.1223 16 .1237 .141104.110 10 )994.0(0.1)1010(10102.610 10 ---------?===+= ?==x x x （2）c =0.050mol 〃L -1 1 53431 24 2141241 11034L mol 102.7]PO H [L mol )0497.0(050.0]PO H [L mol 101.3]HPO [L mol 105.1]PO [---- ------??=?=?=?=??=?=??=?=x c x c x c x c 3.3 某溶液中含有HAc 、NaAc 和Na 2C 2O 4，其浓度分别为0.80、0.29和1.0×10-4 mol 〃L -1 。计算此溶液 中C 2O 42-的平衡浓度。 答案：溶液的酸度由HAc-Ac -所决定 ()() 4.76 4.32a HAc 0.80 [H ]10100.29 Ac c K c +---= = ?= 22 a 224 0a 4 4.2951 4.32 4.29 [C O ][H ]1.01010 5.210mol L 1010cK cx K -+------== +??==??+ 写出下列物质水溶液的质子条件： （1）NH 3；（2）NH 4Cl ；（3）Na 2CO 3；（4）KH 2PO 4；（5）NaAc+H 3BO 3。 答案：（1）NH 3 [NH 4+]+[H +]=[OH -] （2）NH 4Cl [H +]=[NH 3]+[OH -] （3）Na 2CO 3 [H +]+[HCO -3]+2[H 2CO 3]=[OH -] 算法设计与分析课程报告 第一章 算法问题求解基础 1、算法的概念：算法是指解决问题的一种方法或过程，是由若干条指令组成的有穷序列。 2、算法的特性 ① 有穷性：一个算法必须保证执行有限步之后结束; ② 确切性：算法的每一步骤必须有确切的定义; ③ 输入： 一个算法有 0 个或多个输入， 法 本身定除了初始条件; ④ 输出： 一个算法有一个或多个输出， 是毫无意义的; ⑤可行性：算法原则上能够精确地运行, 而且人们用笔和纸做有限次运算后即可完成 3、算法与程序的关系： 区别：程序可以不一定满足可终止性。但算法必须在有限时间内结束; 程序可以没有输出 ,而算法则必须有输出; 算法是面向问题求解的过程描述，程序则是算法的实现。 联系：程序是算法用某种程序设计语言的具体实现; 程序可以不满足算法的有限性性质。 4、算法描述方式：自然语言，流程图，伪代码，高级语言。 第二章 算法分析基础 1、算法复杂性分析： 算法复杂性的高低体现运行该算法所需计算机资源（时间，空间）的多少。 算法复杂性度量： 期望反映算法本身性能，与环境无关。 理论上不能用算法在机器上真正的运行开销作为标准（硬件性能、代码质量影响） 般是针对问题选择基本运算和基本存储单位，用算法针对基本运算与基本存储单 以刻画运算对象的初始情况， 所谓 0 个输入是指算 以反映对输入数据加工后的结果。 没有输出的算法 位的开销作为标准。算法复杂性C依赖于问题规模N、算法输入I和算法本身A。即C=F（N, I,A）。 第五章分治法 1、递归算法：直接或间接地调用自身的算法。 用函数自身给出定义的函数称为递归函数。 注：边界条件与递归方程是递归函数的二个要素。 实例：①阶乘函数; ② Fibonacci 数列；③ Ackerman 函数; ④排列问题; ⑤整数划分问题; ⑥ Hanoi 塔问题 优缺点：①优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便。 ②缺点：递归算法的运行效率低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 2、分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。（将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解） 分治法所能解决的问题一般具有以下几个特征： ①该问题的规模缩小到一定的程度就可以容易地解决; ②该问题可以分为若干个规模更小的相同问题，即该问题具有最有子结构性质; ③利用该问题分解出的子问题的解可以合并为该问题的解; ④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 第六章贪心法 1、贪心算法的思想： 算法设计与分析课程设计 实验指导书 上海第二工业大学 计算机与信息学院软件工程系 一、运动员比赛日程表 设有n=2k个运动员要进行网球比赛。设计一个满足以下要求的比赛日程表： ●每个选手必须与其它n-1个选手各赛一次 ●每个选手一天只能赛一次 ●循环赛一共进行n-1天 1、运用分治策略，该问题的递归算法描述如下，根据算法编制程序并上机 通过。 输入：运动员人数n（假定n恰好为2的i次方） 输出：比赛日程表A[1..n,1..n] 1. for i←1 to n //设置运动员编号 2. A[i,1]←i 3. end for 4. Calendar(0,n) //位移为0，运动员人数为n。 过程Calendar(v, k) //v表示位移（v=起始行-1），k表示运动员人数。 1. if k=2 then //运动员人数为2个 2. A[v+2,2]←A[v+1,1] //处理右下角 3. A[v+1,2]←A[v+2,1]//处理右上角 4. else 5. Calendar(v,k/2) //假设已制定了v+1至v+k/2运动员循环赛日程表 6. Calendar(v+k/2,k/2) //假设已制定了v+k/2+1至v+k运动员循环赛日程表 7. comment：将2个k/2人组的解，组合成1个k人组的解。 8. for i←1 to k/2 9. for j←1 to k/2 10. A[v+i+k/2,j+k/2]←A[v+i,j] //沿对角线处理右下角 11. end for 12. end for 13. for i←k/2+1 to k 14. for j←1 to k/2 15. A[v+i-k/2,j+k/2]←A[v+i,j] //沿对角线处理右上角 16. end for 17. end for 18. end if 2、编制该问题的非递归算法，上机通过。 将如上文件保存在命名为“学号+姓名+实验一”的文件夹中并上传到指定的服务器。 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 北京大学定量分析化学简明教程习题 第四章 络合滴定法 1．已知铜氨络合物各级不稳定常数为： K 不稳1＝7.8?10-3 K 不稳2＝1.4?10-3 K 不稳3＝3.3?10-4 K 不稳4＝7.4?10-5 (1) 计算各级稳定常数K1－K4和各积累常数β1-β4； (2) 若铜氨络合物水溶液中Cu(NH 3)42+的浓度为Cu(NH 3)32+的10倍，问溶液中[NH 3]是多少？ (3) 若铜氨络合物溶液的C NH3=1.010-2M ，C Cu2+=1.0?10-4M,（忽略Cu 2+，NH 3的副反应）。计算Cu 2+与各级铜氨络合物的浓度。此时溶液中以那种形体为最主要？ 解：(1) 稳定常数 K 1＝45-4 101.4104.711 ??＝＝不稳K K 2=34-3 103.0103.311 ??＝＝不稳K K 3=23-2 107.1101.411 ??＝＝不稳K K 4＝＝＝ 不稳3-1107.811 ?K 1.3?102 各级累积常数 β1＝K 1=1.4?104 β2＝K 1K 2＝1.4?3.0?107＝4.2?107 β3＝K 1K 2K 3＝1.4?3.0?7.1?109=3.0?1010 β4＝K 1K 2K 3K 4=1.4?3.0?7.1?1.3?1011＝3.9?1012 (2) β3=332233]][[])([NH Cu NH Cu ++,β4=432243]][[])([NH Cu NH Cu +- ] )([]][[]][[])([2333 3243224334++++=NH Cu NH Cu NH Cu NH Cu ββ =][1])([])([3233243NH NH Cu NH Cu ? ++ [NH 3]=4 3233243])([])([ββ?++NH Cu NH Cu =10?1210 10 9.3100.3?? =0.077(ml/l) (3) Φ0=4 3433323231][][][][11NH NH NH NH ββββ++++ ＝812610472410 9.3100.3102.4104.111----?+?+?+?+ ＝4 43109.3100.3102.41?+?+? ＝ 4103.71? ＝1.4?10-5 Φ1＝4 343332323131][][][][1][NH NH NH NH NH βββββ++++ ＝ 3104.74102.1 ＝1.910-3 Φ2＝43433323231232] [][][][1][NH NH NH NH NH βββββ++++ ＝43 10 3.7102.4?? ＝0.058 Φ3＝434333232313 33] [][][][1][NH NH NH NH NH βββββ++++ 实验总体要求 为避免重复与抄袭，算法分析与设计的实验只规定算法策略，具体的算法题目由学生依据现实当中的问题自行拟定，选题的难易会影响实验得分。 实验可以分组进行，组内与组间可选不同策略的不同题目（问题）、相同策略里面的不同题目、相同题目的不同解法等，尽量避免重复。完全相同的实验报告得0分，不同的重复率扣不同的分数。分组的意义在于研究与实践不同策略的不同题目的差异、不同策略里不同题目异同、相同题目不解法之间的异同与算法效率等。 所有实验都需要包含八个组成部分： （1）实验题目 要求：一句简要的话概括或抽象出所做的实验内容 （2）个人所承担的工作 要求：独立完成报告所有内容者仅填写独立完成即可，此种情况若发现报告有雷同者得0分。协作完成的，重点写自己完成的部分，其他部分可略写，为了锻炼同学们的设计与分析能力，原则上不允许算法模型、算法描述与分析、算法实现上相同。 （3）选题背景与意义 要求：描述选题的背景、针对该问题求解的算法有多少种，发展历史及研究价值等。 （4）问题描述 要求：可以实际问题的描述，也可以某类问题的抽像描述。如果是某类问题的抽象描述，需要指出它的应用场景。 （5）算法策略选择 要求：简要说出选择该策略的理由 （6）计算模型 要求：最接近程序实现中问题求解的数学模型。指明定义域和值的范围或解空间。可以有数据结构及推导或计算公式。递归模型至少有递推公式、递归的出口。如果有的话，给出必要的证明。 （7）算法描述与分析 要求：以标准的描述方式，如流程图、伪码、语言文字。对算法进行时间和空间复杂度分析。时间复杂度要求有必要的推导步骤。 （8）算法实现 要求：给出编程语言、开发环境。给出可执行的算法代码，提供必要的注释。 （9）调试分析记录 要求：软件开发调试过程中遇到的问题及解决过程；核心算法的运行时间和所需内存空间的 Analysis and Design of Algorithms Analysis and Design of Algorithms Transform Coding Chapter 3: Recursive Algorithm School of Software Engineering ?Yanling Xu Recursive Algorithm Recursive Algorithm Recursion : a procedure or subroutine, whose implementation references itself E l 1R i l ti f ! Example 1: Recursive evaluation of n ! ?n initial condition 0 0)!1(1 !>=?? ?=n n n n recurrence relation C(n)=C(n 1)+1 Times of Basic operation for n ! C()C(n-1)+1 =[C(n-2)+1]+1 = C(n-2)+2=[C(n-3)+1]+2 = C(n-3)+3 Iterative Definition C(n)= n …… =[C(n-n)+1]+n-1 = n 2 n n n ×××××=）－（1...321! Recursive Algorithm Recursive Algorithm Example 4: The Tower of Hanoi Puzzle void hanoi(int n, int a, int b, int c) { if (n > 0) if(0) { hanoi(n-1, a, c, b); move(a,b); (b) hanoi(n-1, c, b, a); } } C(n) ∈Θ (2n) C(n) = 2C(n –1) + 1 =2n-1 for every n > 0 5 《算法设计与分析》教学大纲 一、课程概述 算法设计是计算机科学的一门分支学科，是软件技术的一个重要方向。算法设计既是软件设计的关键，也是培养学生成为未来软件工程师所不可或缺的一门专业知识。 算法设计与分析课程将高级语言程序设计、数据结构和计算方法等内容紧密地结合在一起，全面培养学生分析问题、解决问题的能力。这门学科的重点是在培养和培训学生学会经典算法方面的知识与应用，因此它对学生的专业发展具有极其重要的意义。 算法设计与分析的先修课程是高级语言程序设计、数据结构、高等数据、组合数学。 二、课程目标 1.知道《算法设计与分析》这门学科的性质、地位和独立价值。知道这门学科的研究 范围、分析框架、研究方法、学科进展和未来方向。 2.理解这门学科的主要概念，尤其是算法的时间复杂度和空间复杂度。 3.初步学会运用数学的方法推导和证明算法的时间复杂度和空间复杂度。 4.掌握常用的经典算法，培养学生在软件设计时对算法设计的重视，并能够把所学的 知识应用到具体的软件设计实践中去。 三、课程内容和要求 这门学科的知识与技能要求分为知道、理解、掌握、学会四个层次。这四个层次的一般涵义表述如下： 知道———是指对这门学科和教学现象的认知。 理解———是指对这门学科涉及到的概念、原理、策略与技术的说明和解释，能提示所涉及到的教学现象演变过程的特征、形成原因以及教学要素之间的相互关系。 掌握———是指运用已理解的教学概念和原理说明、解释、类推同类教学事件和现象。 学会———是指能模仿或在教师指导下独立地完成某些教学知识和技能的操作任务，或能识别操作中的一般差错。 教学内容和要求表中的“√”号表示教学知识和技能的教学要求层次。 本标准中打“*”号的内容可作为自学，教师可根据实际情况确定要求或不布置要求。 北京大学定量分析化学简明教程习题- ————————————————————————————————作者：————————————————————————————————日期： 2 北京大学定量分析化学简明教程习题 第四章 络合滴定法 1．已知铜氨络合物各级不稳定常数为： K 不稳1＝7.8?10-3 K 不稳2＝1.4?10-3 K 不稳3＝3.3?10-4 K 不稳4＝7.4?10-5 (1) 计算各级稳定常数K1－K4和各积累常数β1-β4； (2) 若铜氨络合物水溶液中Cu(NH 3)42+的浓度为Cu(NH 3)32+的10倍，问溶液中[NH 3]是多少？ (3) 若铜氨络合物溶液的C NH3=1.010-2M ，C Cu2+=1.0?10-4M,（忽略Cu 2+，NH 3的副反应）。计算Cu 2+与各级铜氨络合物的浓度。此时溶液中以那种形体为最主要？ 解：(1) 稳定常数 K 1＝45-4 101.4104.711 ??＝＝不稳K K 2=34-3 103.0103.311 ??＝＝不稳K K 3=23-2 107.1101.411 ??＝＝不稳K K 4＝＝＝ 不稳3-1107.811 ?K 1.3?102 各级累积常数 β1＝K 1=1.4?104 β2＝K 1K 2＝1.4?3.0?107＝4.2?107 β3＝K 1K 2K 3＝1.4?3.0?7.1?109=3.0?1010 β4＝K 1K 2K 3K 4=1.4?3.0?7.1?1.3?1011＝3.9?1012 (2) β3=332233]][[])([NH Cu NH Cu ++,β4=432243]][[])([NH Cu NH Cu +- ]][[])([3 22++NH Cu NH Cu β 算法设计与分析实验报告 实验名称统计数字问题评分 实验日期年月日指导教师 姓名专业班级学号 一.实验要求 1、掌握算法的计算复杂性概念。 2、掌握算法渐近复杂性的数学表述。 3、掌握用C++语言描述算法的方法。 4．实现具体的编程与上机实验，验证算法的时间复杂性函数。 二.实验内容 统计数字问题 1、问题描述 一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2， (9) 2、编程任务 给定表示书的总页码的10 进制整数n (1≤n≤109) 。编程计算书的全部页码中分别用到多少次数字0，1，2， (9) 三.程序算法 将页码数除以10，得到一个整数商和余数，商就代表页码数减余数外有多少个1—9作为个位数，余数代表有1—余数本身这么多个数作为剩余的个位数，此外，商还代表1—商本身这些数出现了10次，余数还代表剩余的没有计算的商的大小的数的个数。把这些结果统计起来即可。 四.程序代码 #include int zero=1; for(int i=0;i<=l;i++) //去除前缀0 { s[0]-=zero; zero*=10; } } if(n<10) { for(int i=0;i<=n;i++) { s[i]+=1; } return; }//位数为1位时,出现次数加1 //位数大于1时的出现次数 for(int t=1;t<=l;t++)//计算规律f(n)=n*10^(n-1) { m=1;int i; for(i=1;i 第5章 习题答案 5.1 K 3Fe(CN)6在强酸溶液中能定量地氧化I -为I 2，因此可用它为基准物标定Na 2S 2O 3溶液。试计算2 mol ?L -1 HCl 溶液中Fe(CN)63-/Fe(CN)64-电对的条件电位。 [已知3-4- 66(Fe(CN)/Fe(CN))0.36V ?θ=，H 3Fe(CN)6是强酸，H 4Fe(CN)6的 K a3=10-2.2，K a4=10-4.2。计算中忽略离子强度影响。以下计算相同。] 答案： 已知：H 3Fe(CN)6是强酸 H 4Fe(CN)6的K a3=10-2.2，K a4=10-4.2 β1=104.2，β2=10 6.4 4-62 12Fe(CN)(H)1[H ][H ]αββ++=++ 0.74.62.4101041021=?+?+= 3-6Fe(CN)(H)1α= 4-63-6334666463-Fe (CN)(H) 346 664-6Fe(CN)(H)[Fe(CN)] (Fe(CN)/Fe(CN))0.059lg [Fe(CN)] (Fe(CN)) (Fe(CN)/Fe(CN))0.059lg 0.059lg (Fe(CN)) c c ??α?α- θ--- θ--=+=++ 4-63-6Fe(CN)(H) 3-4- 66Fe(CN)(H)7.0(Fe(CN)/Fe(CN))0.059lg 0.360.059lg100.77(V) α??αθθ'=+=+= 5.2 银还原器（金属银浸于1 mol ?L -1 HCl 溶液中）只能还原Fe 3+而不能还原Ti(Ⅳ)，计算此条件下Ag +/Ag 电对的条件电位并加以说明。 答案： +sp +-(Ag /Ag)0.059lg[Ag ] (AgCl) (Ag /Ag)0.059lg [Cl ] K ???θθ+θ=+=+ +sp 9.50(Ag /Ag)0.059lg (AgCl) 0.800.059lg100.24(V)K ??'θθ-=+=+= 算法设计与分析实验报告 教师： 学号： 姓名： 实验一：串匹配问题 实验目的：(1) 深刻理解并掌握蛮力法的设计思想; (2) 提高应用蛮力法设计算法的技能; (3) 理解这样一个观点: 用蛮力法设计的算法, 一般来说, 经过适度的努力后, 都可以对算法的第一个版本进行一定程度的改良, 改进其时间性能。 三、实验要求：( 1) 实现BF 算法; (2 ) 实现BF 算法的改进算法: KMP 算法和BM 算法; (3 ) 对上述 3 个算法进行时间复杂性分析, 并设计实验程序验证 分析结果。 #include "stdio.h" #include "conio.h" #include 2005.6算法设计与分析课程期末试卷
分析化学课后习题答案 北大版(第4章+思考题)
算法设计与分析实验报告贪心算法
算法设计与分析课程设计报告样本
算法设计与分析课后部分习题答案
算法设计与分析课程设计(完整版)
算法设计与分析课程设计报告
分析化学课后习题答案 北大版(第3章)
算法设计与分析课程报告
算法设计与分析课程设计-实验指导书
算法设计与分析实验报告
北京大学定量分析化学简明教程习题-5
算法设计与分析报告 正文
算法设计与分析教学课件3
《算法设计与分析》教学大纲
北京大学定量研究分析化学简明教程习题-
算法设计与分析实验报告 统计数字问题
分析化学课后习题答案北大版思考题
算法设计与分析实验报告
相关文档
- 北京大学电分析课件液液界面电化学及电分析化学简介el
- 北京大学电分析课件电分析化学原理、方法和应用
- 北京大学电分析课件电化学反应动力学共68页
- 北京大学 电分析 课件 电分析化学新技术 elect
- 北京大学电分析课件电分析化学新技术elec6
- 北京大学电分析电分析化学新技术
- 北京大学====现代企业管理全套课件
- 北京大学电分析课件电分析化学原理、方法和应用共54页
- 北京大学 电分析 课件 电分析化学原理、方法和应用 elec1c
- 北京大学电分析课件电分析化学原理、方法和应用el
- 北京大学电分析课件elect4a
- 北京大学电分析课件elect4a
- 北京大学电分析课件液液界面电化学及电分析化学简介
- 北京大学色谱课件1-introduction
- 【北京大学】《分析化学》第三章--电解质溶液--特等奖课件
- 北京大学电分析课件电分析化学原理、方法和应用
- 对流层和平流层的环境意义北京大学《环境科学概论》堂报告PPT课件
- 北京大学电分析课件电分析化学原理、方法和应用elec1c
- 北京大学电分析课件液液界面电化学及电分析化学简介elect7.