算法与数据结构基础

1、湖南工业大学计算机与通信学院湖南工业大学计算机与通信学院湖南工业大学计算机与通信学院湖南工业大学计算机与通信学院1、理解算法的基本概念及特性、理解算法的基本概念及特性2、掌握算法的三大结构并了解其描述方法、掌握算法的三大结构并了解其描述方法 3、结合实例理解算法设计方法：穷举法、回溯法、递归法、结合实例理解算法设计方法：穷举法、回溯法、递归法、分治法、贪心法以及动态规划分治法、贪心法以及动态规划4、认识数据结构研究的三大内容、认识数据结构研究的三大内容5、了解程序设计概念，了解程序设计语言的发展及分类、了解程序设计概念，了解程序设计语言的发展及分类 6.16.1算法的概念算法的概念6.2 6.

2、2 算法策略算法策略v 1974年图灵奖获得者年图灵奖获得者Donald Ervin Knuth: v 计算机科学就是算法的研究计算机科学就是算法的研究v The Art of Computer Programming6.1 6.1 算法的概念算法的概念算法算法（Algorithm）是一组有穷的规则，它们规定了解决某）是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案的准确与完一特定类型问题的一系列运算，是对解题方案的准确与完整的描述。整的描述。算法是一种解决问题的方法，是数学及其应用的重要组成算法是一种解决问题的方法，是数学及其应用的重要组成部分。部分。 6.1.2算

3、法的特性v算法的一般应包含以下特性：算法的一般应包含以下特性：v（1 1）有穷性。）有穷性。v（2 2）确定性。）确定性。v（3 3）可行性。）可行性。v（4 4） 输入。输入。v（5 5） 输出输出。6.1.36.1.3算法与计算机程序算法与计算机程序计算机计算机输入输入输出输出算法算法问题问题算法与计算机之间的关系算法与计算机之间的关系在计算机科学中，在计算机科学中，算法算法要用计算机算法语言要用计算机算法语言描述，描述，算法算法代表用计算机解一类问题的精确、代表用计算机解一类问题的精确、有效的方法。有效的方法。算法算法+数据结构数据结构=计算机程序计算机程序6.1.4算法的控制结构与描述

4、v1 1、算法的控制结构、算法的控制结构算法中各操作之间的执行顺序称之为算法的算法中各操作之间的执行顺序称之为算法的控制结构。控制结构。算法一般都可以用算法一般都可以用顺序结构顺序结构、分支结构分支结构、循循环结构环结构三种基本控制结构组合而成。三种基本控制结构组合而成。（1 1）、自然语言）、自然语言自然语言自然语言是人们日常进行交流的语言，如汉语、英语等是人们日常进行交流的语言，如汉语、英语等优点优点：通俗易懂，即使没有学过算法也能看懂算法执行通俗易懂，即使没有学过算法也能看懂算法执行缺点缺点：不够严谨，容易出现歧义和错误不够严谨，容易出现歧义和错误2、算法的描述、算法的描述v（2 2）、

5、流程图）、流程图 用图直观地描述一个工作过程的具体步骤用图直观地描述一个工作过程的具体步骤 常用来描述算法的图形工具有常用来描述算法的图形工具有：流程图或程序框图、：流程图或程序框图、N-SN-S图和图和PADPAD图。图。 优点优点：直观形象，简洁明了。：直观形象，简洁明了。 缺点缺点：画起来费事，不易修改。：画起来费事，不易修改。常用的流程图符号常用的流程图符号：（3 3）伪代码）伪代码6.1.56.1.5算法的设计要求算法的设计要求 v1 1、正确性。、正确性。 v2 2、可读性。、可读性。 v3 3、高效率与低存储量。、高效率与低存储量。 6.2算法策略v6.2.1 6.2.1 穷举法

6、穷举法v问题问题1 1： 有一把锁和一串钥匙（共有有一把锁和一串钥匙（共有1010把钥匙），怎样把钥匙），怎样找出所有开这把锁的钥匙？找出所有开这把锁的钥匙？穷举法穷举法又称列举法、枚举法，是蛮力策略的具体又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直接地解决问题的方法。其体现，是一种简单而直接地解决问题的方法。其基本思想是逐一列举问题所涉及的所有情形，并基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件检验哪些是问题的解，哪些根据问题提出的条件检验哪些是问题的解，哪些应予排除。应予排除。穷举法穷举法的的特点特点是算法设计比较简单，解的可能为有是算法设计比较简单，解的可能为

7、有限种，一一列举问题所涉及的所有情形。限种，一一列举问题所涉及的所有情形。例如：例如：在在QQQQ上，上，OicqPassOverOicqPassOver这个工具穷举用户的口这个工具穷举用户的口令，它根据机器性能最高可以每秒测试令，它根据机器性能最高可以每秒测试2000020000个口个口令，如果口令简单，一分钟内，密码就会遭到破译令，如果口令简单，一分钟内，密码就会遭到破译。 穷举法运用于一些经典问题穷举法运用于一些经典问题1 1、百钱百鸡问题、百钱百鸡问题中国古代算书张丘建的中国古代算书张丘建的算经算经中有一道著名的百鸡问题：公中有一道著名的百鸡问题：公鸡每只值鸡每只值5 5 文钱，母鸡每

8、只值文钱，母鸡每只值3 3 文钱，而文钱，而3 3 只小鸡值只小鸡值1 1 文钱。现在文钱。现在用用100 100 文钱买文钱买100 100 只鸡，问：这只鸡，问：这100 100 只鸡中，公鸡、母鸡和小鸡各只鸡中，公鸡、母鸡和小鸡各有多少只？有多少只？这个问题流传很广，解法很多，但从现代数学观点来看，实际这个问题流传很广，解法很多，但从现代数学观点来看，实际上是一个求不定方程整数解的问题。解法如下：设公鸡、母鸡、小上是一个求不定方程整数解的问题。解法如下：设公鸡、母鸡、小鸡分别为鸡分别为x x、y y、z z 只，由题意得：只，由题意得：用穷举法求解，对每组求得满足等式方程组的值，从而找到

9、百用穷举法求解，对每组求得满足等式方程组的值，从而找到百钱百鸡的解。钱百鸡的解。031003331201100335100 mod,/zzyxzyxzyxv 用用穷举穷举算法解决问题，通常可以从两个方面进行分析：算法解决问题，通常可以从两个方面进行分析：1 1、问题所涉及的情况：问题所涉及的情况有哪些，情况的、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不可以确定。把它描述出来。种数可不可以确定。把它描述出来。2 2、答案需要满足的条件：分析出来的这些情况，需要满足、答案需要满足的条件：分析出来的这些情况，需要满足什么条件，才成为问题的答案，把这些条件描述出来。什么条件，才成为问题的

10、答案，把这些条件描述出来。v 由于由于穷举法穷举法穷举的数据量过大，效率较低，对于小规模的问穷举的数据量过大，效率较低，对于小规模的问题还是适用的，但是问题规模一旦扩大，穷举法就没有什么题还是适用的，但是问题规模一旦扩大，穷举法就没有什么可取性了。一般巧妙和高效算法很少来自穷举法。可取性了。一般巧妙和高效算法很少来自穷举法。6.2.2 6.2.2 回溯法回溯法迷宫游戏迷宫游戏回溯算法回溯算法也叫试探法，是一种选优搜索法，按选也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退步时，发现原

11、先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为为回溯法，而满足回溯条件的某个状态的点称为“回溯点回溯点”。回溯法回溯法的指导思想：走不通，就掉头的指导思想：走不通，就掉头回溯法回溯法在搜索过程中通过对约束条件的判定，排在搜索过程中通过对约束条件的判定，排除错误答案，提高了搜索效率。除错误答案，提高了搜索效率。网络爬虫网络爬虫v 网络爬虫网络爬虫是一个功能强大的自动提取是一个功能强大的自动提取网页的程序，它为搜索引擎从万维网网页的程序，它为搜索引擎从万维网下载网页，是搜索引擎的重要组成部

12、下载网页，是搜索引擎的重要组成部分。它可以完全不依赖用户干预实现分。它可以完全不依赖用户干预实现网络上的自动网络上的自动“爬行爬行”和搜索。和搜索。v 网络爬虫网络爬虫是通过网页的链接地址来寻是通过网页的链接地址来寻找网页在抓取网页的时候，找网页在抓取网页的时候，网络爬虫网络爬虫采用了采用了深度优先深度优先策略，策略，深度优先深度优先是指是指网络爬虫网络爬虫会从起始页开始，一个链接会从起始页开始，一个链接一个链接跟踪下去，处理完这条线路一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络爬虫链接。这个方法有个优点是网络爬虫

13、在设计的时候比较容易。这是一种典在设计的时候比较容易。这是一种典型的回溯算法。型的回溯算法。v回溯法回溯法的本质也是一种穷举法，但与穷举法相比，的本质也是一种穷举法，但与穷举法相比，回溯法的回溯法的“聪明聪明”之处在于能适时之处在于能适时“回头回头”，若再，若再往前走不可能得到解，就回溯，退一步另找线路，往前走不可能得到解，就回溯，退一步另找线路，这样可省去大量的无效操作。因此，回溯与穷举相这样可省去大量的无效操作。因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题比，回溯更适宜于量比较大，候选解比较多的问题。6.2.3 递归法v人们都熟悉一个民间故事：从前有一座山，山上人们都熟悉

14、一个民间故事：从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙，事，故事里说，从前有一座山，山上有一座庙，庙里有一个老和尚正在给小和尚讲故事，故事里庙里有一个老和尚正在给小和尚讲故事，故事里说说。 v所谓所谓递归递归就是一个函数或过程可以直接或间接地调就是一个函数或过程可以直接或间接地调用自己。用自己。v递归递归分为分为直接递归直接递归和和间接递归间接递归两种方法。两种方法。v如果一个算法直接调用自己，称为如果一个算法直接调用自己，称为直接递归调用直接递归调用；v如果一个算法如果一个算法A A调用另一

15、个算法调用另一个算法B B，而算法，而算法B B又调用又调用算法算法A A，则此种递归称为，则此种递归称为间接递归调用间接递归调用。德德罗罗斯斯特特效效应应 1 1、n n！问题！问题阶乘可以这样递归地定义成函数：阶乘可以这样递归地定义成函数：这样，所有自然数的阶乘就可以通过上面的两句话表这样，所有自然数的阶乘就可以通过上面的两句话表示了。示了。2 2的阶乘就是的阶乘就是1 12 2；3 3的阶乘就是的阶乘就是2 2的阶乘乘的阶乘乘3 3，即，即1 12 23 3不仅如此，人们还可以知道不仅如此，人们还可以知道0 0的阶乘是多少，的阶乘是多少，1 1的阶乘应该等于的阶乘应该等于0 0的阶乘乘以

16、的阶乘乘以1 1，显然，显然0 0的阶乘必须是的阶乘必须是1 1才才行。行。)0()0()!1(*1!nnnnn)0()0() 1(*1)(nnnfnnf2 2、汉诺塔（、汉诺塔（HanoiHanoi）问题）问题 相传印度有座大寺庙，它曾被认为是宇宙的中心。神庙中放置相传印度有座大寺庙，它曾被认为是宇宙的中心。神庙中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，由上至下了一块上面插有三根长木钉的木板，在其中的一根木钉上，由上至下放了放了6464片直径由小至大的圆环形金属片。古印度教的天神指示他的僧片直径由小至大的圆环形金属片。古印度教的天神指示他的僧侣们将侣们将6464片金属片全部移

17、至另一根木钉上。移动规则只有两个：片金属片全部移至另一根木钉上。移动规则只有两个：（1 1）在每次的移动中，只能移动一片金属片；）在每次的移动中，只能移动一片金属片；（2 2）过程中任意时刻必须保证金属片小的在上，大的在下。）过程中任意时刻必须保证金属片小的在上，大的在下。v使用使用递归递归时必须符合以下三个条件：时必须符合以下三个条件：（1 1）可将一个问题转化为一个新的问题，而新问）可将一个问题转化为一个新的问题，而新问题的解决方法仍与原问题的解法相同，只不过所处题的解决方法仍与原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是有规律的递增理的对象有所不同而已，即它们只是有规律的

18、递增或递减。或递减。 （2 2）可以通过转化过程使问题回到对原问题的求）可以通过转化过程使问题回到对原问题的求解。解。 （3 3）必须要有一个明确的结束递归的条件，否则）必须要有一个明确的结束递归的条件，否则递归会无止境地进行下去。递归会无止境地进行下去。v递归递归对某些问题而言存在重复调用，导致算法效率对某些问题而言存在重复调用，导致算法效率不高。不高。6.2.4 分治法v 分治法分治法的设计思想是将一个难以直接解决的大问题，分割成的设计思想是将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。一些规模较小的相同问题，以便各个击破，分而治之。v 分治法分治法所能

19、解决的问题一般具有以下几个特征：所能解决的问题一般具有以下几个特征：（1 1）该问题的规模缩小到一定的程度就可以容易地解决；）该问题的规模缩小到一定的程度就可以容易地解决；（2 2）该问题可以分解为若干个规模较小的相同问题，即该问题）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。具有最优子结构性质。（3 3）利用该问题分解出的子问题的解可以合并为该问题的解；）利用该问题分解出的子问题的解可以合并为该问题的解；（4 4）该问题所分解出的各个子问题是相互独立的，即子问题之）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。间不包含公共的子问题。 1 1

20、、找出伪币、找出伪币v 一个装有一个装有1 61 6枚硬币的袋子，枚硬币的袋子，1 61 6枚硬币中有一个是伪造枚硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这枚伪造的硬币。务是找出这枚伪造的硬币。v 为了帮助你完成这一任务，将提供一台可用来比较两组为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，比如天平。利用这台仪器，可以知道硬币重量的仪器，比如天平。利用这台仪器，可以知道两组硬币的重量是否相同。两组硬币的重量是否相同。 方法方法1 1v 任意取任意取1 1枚硬币，与其他硬币进行比较，若发现轻者，枚

21、硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币。最多可能有这那枚为伪币。最多可能有1515次比较。次比较。 方法方法2 2v 将硬币分为将硬币分为8 8组，每组组，每组2 2个，每组比较一次，若发现轻的，个，每组比较一次，若发现轻的，则为伪币。最多可能有则为伪币。最多可能有8 8次比较。次比较。 方法方法3 3分析分析v上述三种方法上述三种方法, ,分别需要比较分别需要比较1818次次,8,8次次,4,4次次, ,那么那么形成比较次数差异的根据原因在哪里形成比较次数差异的根据原因在哪里? ?v方法方法1:1:每枚硬币都至少进行了一次比较每枚硬币都至少进行了一次比较, ,而有一枚而有一枚硬币

22、进行了硬币进行了1515次比较次比较v方法方法2:2:每一枚硬币只进行了一次比较每一枚硬币只进行了一次比较v方法方法3:3:将硬币分为两组后一次比较可以将硬币的将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半范围缩小到了原来的一半, ,这样充分地利用了只有这样充分地利用了只有1 1枚伪币的基本性质。枚伪币的基本性质。v根据以上比较，第三种方法就是根据以上比较，第三种方法就是分治法分治法，可以得到，可以得到以下的采用以下的采用分治方法分治方法的结论：的结论：1 1、参与比较的硬币数量越多，使用该方法来实现就越、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大大减少；快，而且

23、投机性大大减少；2 2、解决方法关键在于能将大问题分割成若干小问题；、解决方法关键在于能将大问题分割成若干小问题；3 3、小问题与原有问题是完全类似的。、小问题与原有问题是完全类似的。2 2、二分法、二分法v二分查找二分查找又称为折半查找，是一种可在有序顺序又称为折半查找，是一种可在有序顺序表上实现的效率比较高的查找算法。是一个典型表上实现的效率比较高的查找算法。是一个典型的的分治算法分治算法。n牛顿二分法牛顿二分法n二分法查找二分法查找v 分治法分治法所能解决的问题一般具有以下几个特征：所能解决的问题一般具有以下几个特征：（1 1）该问题的规模缩小到一定的程度就可以容易地解决；）该问题的规模

24、缩小到一定的程度就可以容易地解决；（2 2）该问题可以分解为若干个规模较小的相同问题，即该）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。问题具有最优子结构性质。（3 3）利用该问题分解出的子问题的解可以合并为该问题的）利用该问题分解出的子问题的解可以合并为该问题的解；解；（4 4）该问题所分解出的各个子问题是相互独立的，即子问）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。题之间不包含公共的子问题。思考：求解一元二次方程实根思考：求解一元二次方程实根6.2.5 贪心法v 贪心算法贪心算法（又称贪婪算法）是指，（又称贪婪算法）是指，在对问题求解

25、时，总是做出在当前在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的从整体最优上加以考虑，所做出的仅是在某种意义上的仅是在某种意义上的局部最优解。局部最优解。v 贪心算法贪心算法不是对所有问题都能得到不是对所有问题都能得到整体最优解，但对范围相当广泛的整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者许多问题它能产生整体最优解或者是整体最优解的近似解。是整体最优解的近似解。v 只顾眼前利益，每次都选最好的只顾眼前利益，每次都选最好的1 1、商场找零、商场找零假设只有假设只有3 3种面额的币值，它们的面值分别为种面额

26、的币值，它们的面值分别为2020元、元、1010元、元、5 5元、和元、和1 1元。现要找给某顾客元。现要找给某顾客3737元，这时，售货员元，这时，售货员几乎不假思索地拿出几乎不假思索地拿出1 1个个2020元、元、1 1个个l0l0元、元、1 1个个5 5元和元和2 2个个1 1元元的钱币交给顾客。人们不仅能很快决定要拿哪些钱币，而的钱币交给顾客。人们不仅能很快决定要拿哪些钱币，而且与其它找法相比这时拿出的钱币的个数肯定是最少的且与其它找法相比这时拿出的钱币的个数肯定是最少的。在这里，收货员实际使用了这样的算法：首先选出一个。在这里，收货员实际使用了这样的算法：首先选出一个面值不超过面值不

27、超过3737元的最大面额钱币（元的最大面额钱币（2020元），然后从元），然后从3737元中元中减去减去2020元，剩下元，剩下1717元中再选出一个不超过元中再选出一个不超过1717元的最大面额元的最大面额钱币（钱币（1010元），如此做下去，直到找足元），如此做下去，直到找足3737元。这就是所谓元。这就是所谓的贪心法。的贪心法。2 2、最短距离、最短距离 DijkstraDijkstra算法又称为单源最短算法又称为单源最短路径，所谓单源是在一个有向路径，所谓单源是在一个有向图中，从一个顶点出发，求该图中，从一个顶点出发，求该顶点至所有可到达顶点的最短顶点至所有可到达顶点的最短路径问题。路

28、径问题。 DijstraDijstra算法是运用贪心算法是运用贪心的策略，从源点开始，不断地的策略，从源点开始，不断地通过相联通的点找出到其他点通过相联通的点找出到其他点的最短距离的最短距离基本思想是：基本思想是： 设置一个顶点的集合设置一个顶点的集合s s，并不断地扩充这个集合，一个并不断地扩充这个集合，一个顶点属于集合顶点属于集合s s当且仅当从源点当且仅当从源点到该点的路径已求出。开始时到该点的路径已求出。开始时s s中仅有源点，并且调整非中仅有源点，并且调整非s s中点中点的最短路径长度，找当前最短的最短路径长度，找当前最短路径点，将其加入到集合路径点，将其加入到集合s s，直，直到终

29、点在到终点在s s中。中。v贪心法贪心法主要有以下两个特点：主要有以下两个特点： （1 1）贪心选择性质贪心选择性质：算法中每一步选择都是当前看：算法中每一步选择都是当前看似最佳的选择，这种选择依赖于已做出的选择，似最佳的选择，这种选择依赖于已做出的选择，但不依赖于未作出的选择。但不依赖于未作出的选择。（2 2）最优子结构性质最优子结构性质：算法中每一次都取得了最优：算法中每一次都取得了最优解（即局部最优解），要保证最后的结果最优，解（即局部最优解），要保证最后的结果最优，则必须满足全局最优解包含局部最优解。则必须满足全局最优解包含局部最优解。6.2.6 动态规划动态规划动态规划是运筹学的一个

30、分支，是求解决策过是运筹学的一个分支，是求解决策过程最优化的数学方法。程最优化的数学方法。2020世纪世纪5050年代美国数学家贝尔曼（年代美国数学家贝尔曼（Rechard Rechard BellmanBellman）等人在研究多阶段决策过程的优化问题）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，把多阶段决策过时，提出了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解程转化为一系列单阶段问题逐个求解，创立了解决多阶段过程优化问题的新方法决多阶段过程优化问题的新方法动态规划动态规划。v动态规划动态规划所处理的对象是所处理的对象是多阶段决策问题多阶段决

31、策问题。v多阶段决策问题多阶段决策问题，是指这样的一类特殊的活动过，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。决策序列也称为一个策略。1 1、最短距离、最短距离 DijkstraDijkstra算法又称为单源最短算法又称为单源最短路径，所谓单源是在一个有向路径，所谓单源是在一个有向图中，从一个顶点出发，求该图中，从一个顶点出发，求该顶点至所有可到达顶点的最短顶点至所有可到达顶点的最短路径问题。路径问题。 基本思想是：基本

32、思想是： 设置一个顶点的集合设置一个顶点的集合s s，并不断地扩充这个集合，一个并不断地扩充这个集合，一个顶点属于集合顶点属于集合s s当且仅当从源点当且仅当从源点到该点的路径已求出。开始时到该点的路径已求出。开始时s s中仅有源点，并且调整非中仅有源点，并且调整非s s中点中点的最短路径长度，找当前最短的最短路径长度，找当前最短路径点，将其加入到集合路径点，将其加入到集合s s，直，直到终点在到终点在s s中。中。2 2、背包问题、背包问题背包问题的一个例子：应该选择哪些盒背包问题的一个例子：应该选择哪些盒子，才能使价格尽可能地大，而保持重子，才能使价格尽可能地大，而保持重量小于或等于量小于

33、或等于15 kg？背包问题背包问题(Knapsack problem)可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。背包问题背包问题0-10-1背包问题的描述是：有背包问题的描述是：有N N件物品和一个容量件物品和一个容量为为V V的背包。第的背包。第i i件物品的容量是件物品的容量是cici，价值是，价值是wiwi。求解将哪些物品装入背包可使价值总和。求解将哪些物品装入背包可使价值总和最大。这是最基础的背包问题，特点是：每种最大。这是最基础的背包问题，特点是：每种物品仅有

34、一件，可以选择放或不放。物品仅有一件，可以选择放或不放。用子问题定义状态：即用子问题定义状态：即fivfiv表示前表示前i i件件物品恰放入一个容量为物品恰放入一个容量为v v的背包可以获得的最的背包可以获得的最大价值。则其状态转移方程便是：大价值。则其状态转移方程便是：fiv=maxfi-1v,fi-1v-ci+wi这个方程的含义是这个方程的含义是：“将前将前i i件物品放入容量为件物品放入容量为v v的背包中的背包中”这个子问题，若只考虑第这个子问题，若只考虑第i i件物品的策略（放或不放），那件物品的策略（放或不放），那么就可以转化为一个只牵扯前么就可以转化为一个只牵扯前i-1i-1件物

35、品的问题。件物品的问题。如果不放第如果不放第i i件物品，那么问题就转化为件物品，那么问题就转化为“前前i-1i-1件物品放件物品放入容量为入容量为v v的背包中的背包中”，价值为，价值为fi-1vfi-1v；如果放第；如果放第i i件物品件物品，那么问题就转化为，那么问题就转化为“前前i-1i-1件物品放入剩下的容量为件物品放入剩下的容量为v-civ-ci的背包中的背包中”，此时能获得的最大价值就是，此时能获得的最大价值就是fi-1v-cifi-1v-ci再加再加上通过放入第上通过放入第i i件物品获得的价值件物品获得的价值wiwi。fiv=maxfi-1v,fi-1v-ci+wiv多阶段决

36、策问题的多阶段决策问题的最优化求解目标最优化求解目标是获取导致问是获取导致问题最优值的最优决策序列（最优策略），即得到题最优值的最优决策序列（最优策略），即得到最优解最优解。v动态规划动态规划思想实质是思想实质是分治思想分治思想和和冗余解决冗余解决方法的方法的结合。结合。v动态规划过程是：每次决策依赖于当前状态，又动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，动态规划三要素是的状态中产生出来的，所以，动态规划三要素是阶段、状态、决策。阶段、状态、决策。v动态规划法动态规划法多用来计算最优问

37、题，动态规划法与多用来计算最优问题，动态规划法与分治法的基本思想是一致的，但处理的手法不同分治法的基本思想是一致的，但处理的手法不同。动态规划法在运用时，要先对问题的分治规律。动态规划法在运用时，要先对问题的分治规律进行分析，找出终结子问题，以及子问题向父问进行分析，找出终结子问题，以及子问题向父问题归纳的规则，而算法则直接从终结子问题开始题归纳的规则，而算法则直接从终结子问题开始求解，逐层向上归纳，直到归纳出原问题的解。求解，逐层向上归纳，直到归纳出原问题的解。6.3 数据结构与程序设计语言6.3.1 6.3.1 数据结构概述数据结构概述电话是通讯联络必不可少的工具。如何用计算机来实电话是通

38、讯联络必不可少的工具。如何用计算机来实现自动查询电话号码呢？要求对于给定的任意姓名，如果现自动查询电话号码呢？要求对于给定的任意姓名，如果该人有电话号码，则迅速给出电话号码，否则，给出查找该人有电话号码，则迅速给出电话号码，否则，给出查找不到该人电话号码的信息。不到该人电话号码的信息。为了提高查找效率，就必须了解待处理对象之间的关为了提高查找效率，就必须了解待处理对象之间的关系，以及如何存储和表示这些数据。系，以及如何存储和表示这些数据。 电话号码经过处理，按照拼音排好了顺序，每个电话电话号码经过处理，按照拼音排好了顺序，每个电话号码之间的先后次序就是数据元素之间的关系。号码之间的先后次序就是

39、数据元素之间的关系。数据结构数据结构就是研究这类非数值处理的程序设计问题。就是研究这类非数值处理的程序设计问题。v数据结构数据结构是相互之间存在一种或多种特定关系的是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素之间数据元素的集合。在任何问题中，数据元素之间都不是孤立的，而是存在着一定的关系，这种关都不是孤立的，而是存在着一定的关系，这种关系称为结构系称为结构(Structure)(Structure)。v一般来说包括以下三方面：一般来说包括以下三方面：数据的数据的逻辑结构逻辑结构、数、数据的据的存储结构存储结构和数据的和数据的运算运算。（1 1）数据的逻辑结构）数据的

40、逻辑结构数据的数据的逻辑结构逻辑结构是指数据元素之间的逻辑关系，与数据的在计是指数据元素之间的逻辑关系，与数据的在计算机内部是如何算机内部是如何存储无关存储无关，数据的逻辑结构，数据的逻辑结构独立独立于计算机。于计算机。v 数据结构可分为数据结构可分为线性数据结构线性数据结构和和非线性数据结构非线性数据结构。线性结构的逻辑特征是除第一个结点和最后一个结点外，其他线性结构的逻辑特征是除第一个结点和最后一个结点外，其他所有结点都有且只有一个直接前趋和一个直接后继结点。所有结点都有且只有一个直接前趋和一个直接后继结点。非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接非线性结构的逻辑特征是一个结

41、点可能有多个直接前趋和直接后继。后继。v 为了进一步研究数据的逻辑结构，可以将数据的逻辑结构分为为了进一步研究数据的逻辑结构，可以将数据的逻辑结构分为线性结构和非线性结构两大类。线性结构和非线性结构两大类。v 线性结构包括：线性表、栈和队列等。线性结构包括：线性表、栈和队列等。v 非线性结构包括树和图型结构。非线性结构包括树和图型结构。（2 2）数据的存储结构）数据的存储结构数据必须在计算机内存储，数据的存储结构数据必须在计算机内存储，数据的存储结构( (是研究数据是研究数据元素和数据元素之间的关系如何在计算机中表示，是逻辑数据元素和数据元素之间的关系如何在计算机中表示，是逻辑数据的存储映像，

42、它是的存储映像，它是面向计算机面向计算机的。的。数据在存储器中的存储有四种基本的映像方法：数据在存储器中的存储有四种基本的映像方法： 顺序存储结构。顺序存储结构。 链式存储结构。链式存储结构。 索引存储结构。索引存储结构。 散列存储结构散列存储结构。 （3 3）数据的运算）数据的运算数据的运算是定义在数据逻辑结构上的操作，数据的运算是定义在数据逻辑结构上的操作，也就是删除、检索和排序等与问题相关的处理。也就是删除、检索和排序等与问题相关的处理。数据结构数据结构通常具有下列一些基本操作：通常具有下列一些基本操作：插入：在数据结构的指定位置上添加一个新结点。插入：在数据结构的指定位置上添加一个新结

43、点。删除：删去数据结构中指定位置的结点。删除：删去数据结构中指定位置的结点。更新：修改数据结构中某个结点的值。更新：修改数据结构中某个结点的值。查找：在数据结构中寻找满足指定条件的结点及其位置。查找：在数据结构中寻找满足指定条件的结点及其位置。排序：按照指定的顺序，使结点重新排列排序：按照指定的顺序，使结点重新排列。6.3.2程序设计语言简介1 1、程序设计概念、程序设计概念程序设计程序设计(Programming)(Programming)是给出解决特定问题程序的是给出解决特定问题程序的过程，是软件构造活动中的重要组成部分。过程，是软件构造活动中的重要组成部分。程序设计是指设计、编制、调试程

44、序的方法和过程。程序设计是指设计、编制、调试程序的方法和过程。程序程序= =数据结构数据结构+ +算法算法程序设计规范是进行程序设计的具体规定。程序设计程序设计规范是进行程序设计的具体规定。程序设计要本着要本着“清晰第一，效率第二清晰第一，效率第二”的风格。的风格。 v 按照结构性质，有按照结构性质，有结构化结构化程序设计与程序设计与非结构化非结构化程序设计程序设计v 按照用户的要求，有按照用户的要求，有过程式过程式程序设计与程序设计与非过程式非过程式程序设计程序设计 v 按照程序设计风格，有按照程序设计风格，有逻辑式逻辑式程序设计、程序设计、函数式函数式程序设计程序设计、对象式对象式程序设计

45、。程序设计。 v程序设计过程包括程序设计过程包括分析分析、设计设计、编码编码、测试测试、排排错错等阶段等阶段 2 2、程序设计语言、程序设计语言v程序设计语言程序设计语言，通常简称为编程语言，是一组用，通常简称为编程语言，是一组用来定义计算机程序的来定义计算机程序的语法规则语法规则。 v程序设计语言包含三个方面，即程序设计语言包含三个方面，即语法语法、语义语义和和语语用用 v程序设计语言程序设计按照语言级别可以分为程序设计语言程序设计按照语言级别可以分为低低级语言级语言和和高级语言高级语言。3 3、面向过程和面向对象、面向过程和面向对象4 4、语言处理程序、语言处理程序5 5、程序设计的一般过

46、程、程序设计的一般过程（1 1）确定要解决的问题）确定要解决的问题（2 2）分析问题，建立数学模型）分析问题，建立数学模型（3 3）确定数据结构和算法）确定数据结构和算法（4 4）编写程序）编写程序（5 5）调试程序）调试程序（6 6）整理资料，交付使用）整理资料，交付使用6.3.3结构化程序设计v结构化程序设计，它的基本思想是结构化程序设计，它的基本思想是“自顶向下，自顶向下，逐步求精，模块化，限制使用逐步求精，模块化，限制使用gotogoto语句语句”和和“单单入口单出口入口单出口”的控制结构。的控制结构。v基于这样的思想，提出了三种基本结构，由这三基于这样的思想，提出了三种基本结构，由这三种基本结构组成的程序，就是结构化程序。种基本结构组成的程序，就是结构化程序。v1 1、顺序顺序结构结构v2 2、分支分支结构结构v3 3、循环循环结构（重复结构