程序设计基础12_2_动态规划(2015春)

3级 28 20 7 2 8 3 f(i, j) —— 从第 i 堆到第 j 堆的代价和。 g(i, j) —— 从第 i 堆到第 j 堆的重量和。 f(1, 3) = 20 + 28 = 48 1级 13 序号 1 = f(1, 2) + g(1, 3)
2级
n=4时：有3大类归并法。前1堆后3堆、前2堆后2堆、前3堆后1堆。
因3堆有2种归并法，所以一共5小类归并法。前1堆第1种情况：
4级 3级 2级 1级 13 序号 1
44 31 15 7
2
f(1, 4) = 15 + 31 + 44 = 90 = f(2, 4) + g(1, 4) w不变 = f(2, 3) + g(2, 4) + g(1, 4)
若f(2,4)越小，则f(1,4)就越小。 8
3
16
4
n=4 时：前1堆的第2种情况。
4级 44 31 24 7 2 8 3 f(1, 4) = 24 + 31 + 44 = 99 = f(2, 4) + g(1, 4) w不变 = f(3, 4) + g(2, 4) + g(1, 4) 若f(2,4)越小，则f(1,4)就越小。 16 4 f(1, 4) = 20 + 24 + 44 = 88
的一种通用方法，对最优化问题提出最优性原则，从而创建最优化问题
的一种新算法设计技术——动态规划，它是一种重要的应用数学工具。 至少在计算机科学圈子里，人们不仅用它解决特定类型的最优化问题， 而最终把它作为一种通用的算法设计技术，即包括某些非最优化问题。 多阶段决策过程最优化： 现实世界里有许多问题属于这种情况：它有很多解，应用要求最优解。 穷举法通过找出全部解，再从中选出最优解。这种方法对于那些计算

计算机算法设计五⼤常⽤算法的分析及实例摘要算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。

也就是说，能够对⼀定规范的输⼊，在有限时间内获得所要求的输出。

如果⼀个算法有缺陷，或不适合于某个问题，执⾏这个算法将不会解决这个问题。

不同的算法可能⽤不同的时间、空间或效率来完成同样的任务。

其中最常见的五中基本算法是递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法。

本⽂通过这种算法的分析以及实例的讲解，让读者对算法有更深刻的认识，同时对这五种算法有更清楚认识关键词：算法，递归与分治法、动态规划、贪⼼算法、回溯法、分⽀限界法AbstractAlgorithm is the description to the problem solving scheme ,a set of clear instructions to solve the problem and represents the describe the strategy to solve the problem using the method of system mechanism . That is to say, given some confirm import，the Algorithm will find result In a limited time。

If an algorithm is defective or is not suitable for a certain job, it is invalid to execute it. Different algorithms have different need of time or space, and it's efficiency are different.There are most common algorithms: the recursive and divide and conquer、dynamic programming method、greedy algorithm、backtracking、branch and bound method.According to analyze the five algorithms and explain examples, make readers know more about algorithm , and understand the five algorithms more deeply.Keywords: Algorithm, the recursive and divide and conquer, dynamic programming method, greedy algorithm、backtracking, branch and bound method⽬录1. 前⾔ (4)1.1 论⽂背景 (4)2. 算法详解 (5)2.1 算法与程序 (5)2.2 表达算法的抽象机制 (5)2.3 算法复杂性分析 (5)3．五中常⽤算法的详解及实例 (6)3.1 递归与分治策略 (6)3.1.1 递归与分治策略基本思想 (6)3.1.2 实例——棋盘覆盖 (7)3.2 动态规划 (8)3.2.1 动态规划基本思想 (8)3.2.2 动态规划算法的基本步骤 (9)3.2.3 实例——矩阵连乘 (9)3.3 贪⼼算法 (11)3.3.1 贪⼼算法基本思想 (11)3.3.2 贪⼼算法和动态规划的区别 (12)3.3.3 ⽤贪⼼算法解背包问题的基本步骤： (12)3.4 回溯发 (13)3.4.1 回溯法基本思想 (13)3.3.2 回溯发解题基本步骤 (13)3.3.3 实例——0-1背包问题 (14)3.5 分⽀限界法 (15)3.5.1 分⽀限界法思想 (15)3.5.2 实例——装载问题 (16)总结 (18)参考⽂献 (18)1. 前⾔1.1 论⽂背景算法（Algorithm）是指解题⽅案的准确⽽完整的描述，是⼀系列解决问题的清晰指令，算法代表着⽤系统的⽅法描述解决问题的策略机制。

3
❖ 了解程序 设计 的基本含义 ❖ 了解“算法”的基本特点，学习“算法”的重要 性 ❖ 结构化程序设计
1.了解结构化程序的3种基本结构。 2.掌握如何用一般流程图和N-S流程图表示三种基本结构。
1.1 程序和程序设计
4
知识扩展：C语言概述
❖ C语言出现的历史背景
C语言是国际上广流行的计算机高级语言，又有低级 语言的一些功能。因此既可用它来编写系统软件，也可 以用来编写应用软件。(教材P9-9)
真题举例：
（13）以下叙述中错误的是( B ) (2010.9) A）C程序在运行过程中所有计算都以二进制方式进行 B）C程序在运行过程中所有计算都以十进制方式进行 C）所有C程序都需要编译链接无误后才能运行 D）C程序中整型变量只能存放整数，实型变量只能存放浮点数
1.1 程序和程序设计
1.1.3 C语言运行过程-编译连接过程
MS Office 高级应用
Thank You !
汇报结束
谢谢大家! 请各位批评指正
1.1 程序和程序设计
6
知识扩展：C语言概述
❖ C语言特点
（5）C语言允许直接访问物理地址，能进行位（bit) 操作，能实现汇编语言的大部分功能，可以直接对硬 件进行操作。
（6）C语言生成目标代码质量高，程序执行效率高。
（7）用C语言编写的程序可移植性好（及汇编语言 比）。基本上不做修改就能用于各种型号的计算机和 各种操作系统。
1.1 程序和程序设计
10
1.1.２ 程序设计
考点
❖ 简单的程序设计一般包含以下几个部分：（P2）
(1)确定数据结构
(2)确定算法
(3)编码（编写程序 ）
(4)在计算机上调试程序

程序设计基础
程序设计基础可以理解为计算机编程的基础知识和技能。

它包括了一系列概念、原理、语法和技巧，用于编写计算机程序。

学习程序设计基础通常需要掌握以下内容：
1. 编程语言：选择一门合适的编程语言进行学习，比如C、C++、Python、Java等。

不同的编程语言有不同的特点和用途，初学者可以选择一门容易上手的语言进行学习。

2. 编程概念：了解基本的编程概念，如变量、数据类型、算术运算、逻辑运算、条件
语句、循环语句、函数等。

这些概念是编程的基础，掌握它们可以更好地理解和编写
程序。

3. 数据结构：学习不同的数据结构，如数组、链表、栈、队列、树、图等。

了解数据
结构可以帮助我们更有效地组织和管理数据，提高程序的性能和效率。

4. 算法设计：学习常见的算法设计和分析方法，如递归、分治、动态规划等。

了解算
法可以帮助我们解决实际问题，提供高效的解决方案。

5. 软件工程：学习软件工程的基本原理和方法，如需求分析、设计、编码、测试和维
护等。

了解软件工程可以帮助我们更好地组织和管理程序开发过程，提高程序的质量
和可维护性。

除了上述内容，学习程序设计基础还需要进行实践，通过编写实际的程序来加深理解
和掌握。

可以选择一些简单的编程项目进行练习，逐步提升自己的编程能力。

同时，
阅读相关的编程书籍、在线教程和参与编程社区也是很有帮助的。