下载文档原格式
《算法分析与设计》期末试题及参考答案一、简要回答下列问题：1.算法重要特性是什么？2.算法分析的目的是什么？3.算法的时间复杂性与问题的什么因素相关？4.算法的渐进时间复杂性的含义？5.最坏情况下的时间复杂性和平均时间复杂性有什么不同？6.简述二分检索（折半查找）算法的基本过程。
7.背包问题的目标函数和贪心算法最优化量度相同吗？8.采用回溯法求解的问题，其解如何表示？有什么规定？9.回溯法的搜索特点是什么？10.n皇后问题回溯算法的判别函数place的基本流程是什么？11.为什么用分治法设计的算法一般有递归调用？12.为什么要分析最坏情况下的算法时间复杂性？13.简述渐进时间复杂性上界的定义。
14.二分检索算法最多的比较次数？15.快速排序算法最坏情况下需要多少次比较运算？16.贪心算法的基本思想？17.回溯法的解（x1,x2,……x n）的隐约束一般指什么？18.阐述归并排序的分治思路。
19.快速排序的基本思想是什么。
20.什么是直接递归和间接递归？消除递归一般要用到什么数据结构？21.什么是哈密顿环问题？22.用回溯法求解哈密顿环，如何定义判定函数？23.请写出prim算法的基本思想。
二、复杂性分析1、MERGESORT(low，high)if low<high；then mid←(low，high)/2；MERGESORT(low，mid)；MERGESORT(mid+1，high)；MERGE(low，mid，high)；endifend MERGESORT2、procedure S1(P，W，M，X，n)i←1; a←0while i≤ n doif W(i)>M then return endifa←a+ii←i+1 ;repeatend3.procedure PARTITION(m,p)Integer m,p,i;global A(m:p-1)v←A(m);i←mlooploop i←i+1 until A(i) ≥v repeatloop p←p-1 until A(p) ≤v repeatif i<pthen call INTERCHANGE(A(i),A(p))else exitendifrepeatA(m) ←A(p);A(p) ←vEnd PARTITION4.procedure F1(n)if n<2 then return(1)else return(F2(2,n,1,1))endifend F1procedure F2(i,n,x,y)if i≤nthen call F2(i+1,n,y,x+y)endifreturn(y)end F25.procedure MAX(A,n,j)xmax←A(1);j←1for i←2 to n doif A(i)>xmax then xmax←A(i); j←i;endif repeatend MAX6.procedure BINSRCH(A,n,x,j)integer low,high,mid,j,n;low←1;high←nwhile low≤high domid←|_(low+high)/2_|case:x<A(mid):high←mid-1:x>A(mid):low←mid+1:else:j ←mid; returnendcase repeat j ←0 end BINSRCH三、算法理解1、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。
算法设计与分析基础习题1.15..证明等式gcd(m,n)=gcd(n,m mod n)对每一对正整数m,n都成立.Hint:根据除法的定义不难证明:●如果d整除u和v, 那么d一定能整除u±v;●如果d整除u,那么d也能够整除u的任何整数倍ku.对于任意一对正整数m,n,若d能整除m和n,那么d一定能整除n和r=m mod n=m-qn；显然，若d能整除n和r，也一定能整除m=r+qn和n。
数对(m,n)和(n,r)具有相同的公约数的有限非空集，其中也包括了最大公约数。
故gcd(m,n)=gcd(n,r)6.对于第一个数小于第二个数的一对数字,欧几里得算法将会如何处理?该算法在处理这种输入的过程中,上述情况最多会发生几次?Hint:对于任何形如0<=m<n的一对数字,Euclid算法在第一次叠代时交换m和n, 即gcd(m,n)=gcd(n,m)并且这种交换处理只发生一次.7.a.对于所有1≤m,n≤10的输入, Euclid算法最少要做几次除法?(1次)b. 对于所有1≤m,n≤10的输入, Euclid算法最多要做几次除法?(5次)gcd(5,8)习题1.21.(农夫过河)P—农夫W—狼G—山羊C—白菜2.(过桥问题)1,2,5,10---分别代表4个人, f—手电筒4. 对于任意实系数a,b,c, 某个算法能求方程ax^2+bx+c=0的实根,写出上述算法的伪代码(可以假设sqrt(x)是求平方根的函数)算法Quadratic(a,b,c)//求方程ax^2+bx+c=0的实根的算法//输入:实系数a,b,c//输出:实根或者无解信息If a≠0D←b*b-4*a*cIf D>0temp←2*ax1←(-b+sqrt(D))/tempx2←(-b-sqrt(D))/tempreturn x1,x2else if D=0 return –b/(2*a)else return “no real roots”else //a=0if b≠0 return –c/belse //a=b=0if c=0 return “no real numbers”else return “no real roots”5.描述将十进制整数表达为二进制整数的标准算法a.用文字描述b.用伪代码描述解答：a.将十进制整数转换为二进制整数的算法输入：一个正整数n输出：正整数n相应的二进制数第一步：用n除以2，余数赋给Ki(i=0,1,2...)，商赋给n第二步：如果n=0，则到第三步，否则重复第一步第三步：将Ki按照i从高到低的顺序输出b.伪代码算法DectoBin(n)//将十进制整数n转换为二进制整数的算法//输入：正整数n//输出：该正整数相应的二进制数，该数存放于数组Bin[1...n]中i=1while n!=0 do {Bin[i]=n%2;n=(int)n/2;i++;}while i!=0 do{print Bin[i];i--;}9.考虑下面这个算法,它求的是数组中大小相差最小的两个元素的差.(算法略) 对这个算法做尽可能多的改进.算法MinDistance(A[0..n-1])//输入:数组A[0..n-1]//输出:the smallest distance d between two of its elements习题1.31.考虑这样一个排序算法,该算法对于待排序的数组中的每一个元素,计算比它小的元素个数,然后利用这个信息,将各个元素放到有序数组的相应位置上去.a.应用该算法对列表‖60,35,81,98,14,47‖排序b.该算法稳定吗?c.该算法在位吗?解:a. 该算法对列表‖60,35,81,98,14,47‖排序的过程如下所示:b.该算法不稳定.比如对列表‖2,2*‖排序c.该算法不在位.额外空间for S and Count[] 4.(古老的七桥问题)习题1.41.请分别描述一下应该如何实现下列对数组的操作,使得操作时间不依赖数组的长度. a.删除数组的第i 个元素(1<=i<=n)b.删除有序数组的第i 个元素(依然有序) hints:a. Replace the i th element with the last element and decrease the array size of 1b. Replace the ith element with a special symbol that cannot be a value of the array ’s element(e.g., 0 for an array of positive numbers ) to mark the i th position is empty. (―lazy deletion ‖)第2章 习题2.17.对下列断言进行证明:(如果是错误的,请举例) a. 如果t(n )∈O(g(n),则g(n)∈Ω(t(n)) b.α>0时,Θ(αg(n))= Θ(g(n)) 解:a. 这个断言是正确的。
算法设计与分析期末试卷A卷A卷一、选择题1.二分搜索算法是利用（A）实现的算法。
A、分治策略2.回溯法解旅行售货员问题时的解空间树是（A）。
A、子集树3.下列算法中通常以自底向上的方式求解最优解的是（B）。
B、动态规划法4．下面不是分支界限法搜索方式的是（D）。
D、深度优先5．采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为(。
B。
)。
B、O（nlogn）6．分支限界法解最大团问题时，活结点表的组织形式是（B）。
B、最大堆7、下面问题（B）不能使用贪心法解决。
B N皇后问题8.下列算法中不能解决0/1背包问题的是（A）A贪心法9.背包问题的贪心算法所需的计算时间为（B）A、O （nlogn）B、O（nlogn）10.背包问题的贪心算法所需的计算时间为（B）。
B、O（nlogn）二、填空题1.算法的复杂性有时间复杂性和空间复杂性之分。
2.算法是由若干条指令组成的有穷序列，且要满足输入、输出、确定性和有穷性四条性质。
其中算法的“确定性”指的是组成算法的每条指令是清晰的，无歧义的。
3.解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中不需要排序的是回溯法，需要排序的是动态规划和分支限界法。
4.动态规划算法的两个基本要素是最优子结构性质和重叠子问题性质。
5.回溯法是一种既带有深度优先搜索又带有回溯的搜索算法；分支限界法是一种既带有广度优先搜索又带有回溯的搜索算法。
6.用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
在任何时刻，算法只保存从根结点到当前扩展结点的路径。
如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。
7.用回溯法解图的m着色问题时，使用下面的函数OK检查当前扩展结点的每一个儿子所相应的颜色的可用性，则需耗时O(n)。
Bool Color::OK(int k)for(int j=1;j<=n;j++)if((a[k][j] == 1) && (x[j] == x[k])) {return false;return true;8.用回溯法解布线问题时，求最优解的主要程序段如下。
如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n))如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O的定义，存在正常数C1，C2和自然数N1,N2，使得对所有的n>= N1，f （n）<=C1s(n)；对所有的n>= N2,g(n) <=C2r(n)所以 f（n）+ g(n) <= C1s(n)+ C2r(n)，f（n）*g(n)<= C1C2s(n)r(n)；令 C3=max（C1,C2），C4=C1*C2；则：f（n）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))f（n）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))试说明为什么“在现代计算机上运行指数（如2n）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即零次多项式)来限界，而一个时间为Ο(n2)的算法则由一个二次多项式来限界。
当数据集的规模（即n的取值）很大时，要在现代计算机上运行具有比O（nlog2 n）复杂度还高的算法是很困难的，尤其是指数时间算法，它只有在在n值取得非常小的时候才实用。
例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n^2和nlogn.则N=1024，分别需要1048576和10240次运算。
N=2048：分别需要4194304和22528次运算。
由此，在n加倍的情况下，一个O（n^2)的算法计算时间增长4倍，而一个O（nlogn）算法则只用两倍多一点的时间。
所以数量级的大小对算法的有效性有决定性的影响。
尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n足够大时，n每增加1，1000倍的提速即可瞬间化为乌有。
算法设计与分析复习题目及答案.docx一。
选择题1、二分搜索算法是利用（A）实现的算法。
A、分治策略B、动态规划法C、贪心法D、回溯法2、下列不是动态规划算法基本步骤的是（B）。
A、找出最优解的性质B、构造最优解C、算出最优解D、定义最优解3、最大效益优先是（A）的一搜索方式。
A、分支界限法B、动态规划法C、贪心法D、回溯法4、在下列算法中有时找不到问题解的是（B）。
A、蒙特卡罗算法B、拉斯维加斯算法C、舍伍德算法D、数值概率算法5. 回溯法解旅行售货员问题时的解空间树是（B）。
A、子集树B、排列树C、深度优先生成树D、广度优先生成树6．下列算法常以自底向上的方式求解最优解的是（B）。
A、备忘录法B、动态规划法C、贪心法D、回溯法7、衡量一个算法好坏的标准是（ C ）。
A 运行速度快B 占用空间少C 时间复杂度低D 代码短8、以下不可以使用分治法求解的是（ D ）。
A 棋盘覆盖问题B 选择问题C 归并排序D 0/1 背包问题9. 实现循环赛日程表利用的算法是（A）。
A、分治策略B、动态规划法C、贪心法D、回溯法10、下列随机算法中运行时有时候成功有时候失败的是（ C ）A 数值概率算法B 舍伍德算法C 拉斯维加斯算法D 蒙特卡罗算法11．下面不是分支界限法搜索方式的是（DA、广度优先B、最小耗费优先C、最大效益优先12．下列算法常以深度优先方式系统搜索问题解的是（A、备忘录法B、动态规划法C、贪心法13.备忘录方法是那种算法的变形。
（ B ）A、分治法B、动态规划法C、贪心法14．哈弗曼编码的贪心算法所需的计算时间为（BnB、 O（nlogn ）n ）A、O（ n2 ）C、O（215．分支限界法解最大团问题时，活结点表的组织形式是（A、最小堆B、最大堆C、栈组）。
D、深度优先D）。
D、回溯法D、回溯法）。
D、 O（ n）B）。
D 、数16．最长公共子序列算法利用的算法是（B）。
A、分支界限法B、动态规划法C、贪心法D、回溯法17．实现棋盘覆盖算法利用的算法是（A）。
北京工业大学2014 ——2015 学年第二学期算法设计与分析期末考试模拟试卷 A卷考试说明：承诺：本人已学习了《北京工业大学考场规则》和《北京工业大学学生违纪处分条例》，承诺在考试过程中自觉遵守有关规定，服从监考教师管理，诚信考试，做到不违纪、不作弊、不替考。
若有违反，愿接受相应的处分。
承诺人：学号：班号：。
注：本试卷共三大题，共 6 页，满分100分，考试时答案请写在试卷空白处。
一、算法时间复杂性问题（共30分）Part 1. The Time Complexity Of the Algorithm Test1、试证明下面的定理：[12分](1) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)+g(n)=O(s(n)+r(n))(2) 如果f(n)=O(s(n))并且g(n)=O(r(n))，则f(n)*g(n)=O(s(n)*r(n)) 1. Prove the following Theorem [12 marks](1) if f(n)=O(s(n)) and g(n)=O(r(n)), to prove f(n)+g(n)=O(s(n)+r(n))(2) if f(n)=O(s(n)) and g(n)=O(r(n))，to prove f(n)*g(n)=O(s(n)*r(n))2、已知有如下的断言：f(n)=O(s(n))并且g(n)=O(r(n))蕴含f(n)-g(n)=O(s(n)-r(n)) 请你举出一个反例。
[8分]2. Known as the following assertionIf f(n)=O(s(n)) and g(n)=O(r(n))，then f(n)-g(n)=O(s(n)-r(n)) 。
Please cite a counter-example [8 marks]3、假设某算法在输入规模为n时的计算时间为：T（n）=3*2n，在A型计算机上实现并完成该算法的时间为t秒，现有更先进的B型计算机，其运算速度为A 型计算机的256倍。
《算法设计与分析》期末必考复习及答案题整理1、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。
递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择，3、 Prim算法：设G=(V,E)是连通带权图，V={1,2,…,n}。
构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件i?S，j?V-S，且c[j]最小的边，将顶点j添加到S 中。
这个过程一直进行到S=V时为止。
4、什么是剪枝函数：回溯法搜索解空间树时，通常采用两种策略避免无效搜索，提高回溯法的搜索效率。
其一是用约束函数在扩展结点处剪去不满足约束的子树；其二是用限界函数剪去得不到最优解的子树。
这两类函数统称为剪枝函数。
6、分支限界法的基本思想：(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。
(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。
5、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。
6、最优子结构性质：该问题的最优解包含着其子问题的最优解。
7、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。
这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。
算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。
如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
新祥旭高硕网站：
/ 一：填空题
1.数据模型的三要素
2.数据库系统与数据库管理系统的区别
3.码键的两个条件()和() ，R(A,B,C,D)A →B,C →D,CB →A,B →C,所有的键是()
4.选择对应于 SQL 的什么语句
5.R(A,B,C)键码为 AC 或 AB ，该关系最高达()范式，为什么()
6.三级体系结构引出的两层数据独立性是什么()
7.R(U)分解为 R1(U1),R2(U2)，无损连接的条件是
二.大题
1.设计数据库存储每个人的父母和孩子。
给出 ER 模型和数据模型查询王立的父母，用关系代数和 SQL 语句分别给出能否查询祖父母信息。
2.R(A,B,C,D,E,F) F={A →B,AC →D,BE →F,EF →C}，分解成 3NF ，使保持依赖。
3.大学学习数据库有否上机课程，是干什么的，用的哪个 DBMS ，它提供哪些基本工具， 使用是否方便。
你是否使用过编程语言连接数据库，如何连接的。
一、算法时间复杂性问题1. 试证明下面的定理：(1)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)+g(n)=O(s(n)+r(n));(2)如果f(n)=O(s(n))并且g(n)=O(r(n)),则f(n)*g(n)=O(s(n)*r(n))根据符号O 的定义，存在正常数C 1，C 2和自然数N 1,N 2，使得对所有的n>= N 1，f （n ）<=C 1s(n)；对所有的n>= N 2,g(n) <=C 2r(n)所以 f （n ）+ g(n) <= C 1s(n)+ C 2r(n)，f （n ）*g(n)<= C 1C 2s(n)r(n)；令 C3=max （C1,C2），C4=C1*C2；则：f （n ）+ g(n) <= C3[s(n)+ r(n)]=O(s(n)+ r(n))（n ）*g(n) <= C4*s(n)*r(n)=O(s(n)* r(n))2. 假设某算法在输入规模为n 时的计算时间为：T （n ）=3*2n ，在A 型计算机上实现并完成该算法的时间为t 秒，现有更先进的B 型计算机，其运算速度为A 型计算机的64倍。
试求出若在先进的B 型机上运行同一算法在则T 秒内能求解输入规模为多大的问题？某台t 秒内完成的基本运算的次数=3*2^n 新机器t 秒内完成的基本运算的次数=64*3*2^n=2^6*3*2^n=3*2^(n+6)设N 为B 型机上t 秒钟能求解的问题的规模所以T=T(N)=3*2^N=3*2^(n+6) 则：N=n+63. 试说明为什么“在现代计算机上运行指数（如2n ）时间算法是不可能的，要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法计算复杂度的数量级，而不是提高计算机的速度”。
一个计算时间为Ο(1)的算法，它的基本运算执行的次数是固定的，因此，总的时间由一个常数(即，零次多项式)来限界，而一个时间为Ο(n 2)的算法则由一个二次多项式来限界。
以下六种计算时间的多项式时间算法是最为常见的，其关系为指数时间算法一般有Ο(2n )、Ο(n!)和Ο(n n )等。
其关系为：其中，最常见的是时间为Ο(2n )的算法。
当n 取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊因为根本就找不到一个这样的m ，使得2n 囿界于n^m 。
换言之，对于任意的m ≥0，总可以找到n 0，当n ≥n 0时，有2n ＞n m 。
因此，只要有人能将现有指数时间算法中的任何一个算法简化为多项式时间算法，那就取得了一个伟大的成就。
Ο(log 2n)、Ο(n)和Ο(nlog 2n)比另外三种时间函数的增长率慢得多。
～ 由这些结果可看出，当数据集的规模(即n 的取值)很大时，要在现代计算机上运行具有比Ο(nlog 2n)复杂度还高的算法往往是很困难的。
尤其是指数时间算法，它只有在n 值取得非常小时才实用。
尽管通过提高计算机的速度比之前快1000倍，甚至10000倍，但当指数规模的n 足够大时，n 每增加1，1000倍的提速即可瞬间化为乌有，所以要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度的数量级，而不是提高计算机的速度。
二、简答1.对计算复杂性的研究能够使人们弄清所求解问题的固有难度，并得出评价某类算法优劣的准则，用以指导设计出更高效的算法。
试用简短的语言说明“建立一个问题复杂性的下界要比确定它的上界困难得多！”其复杂性上界是已知求解该问题的最快算法的费用，而复杂性下界只能通过理论证明来建立。
寻求某个问题的计算复杂性上界，只要研究一个算法的复杂性即可。
但是要寻求同一问题的计算复杂性下界，则必须考察所有的解决该问题的算法，证明一个问题的复杂性下界就需要证明不存在任何复杂性低于下界的算法。
显然，建立下界要比确定上界困难得多。
2.满足何种性质的问题被称为NP 完全问题？请简述研究NP 完全问题的意义；（1）NP 即是多项式复杂程度的非确定性问题。
而如果任何一个NP 问题都能通过一个多项式时间算法转换为某个NP 问题，那么这个NP 问题就称为NP 完全问题。
如果一个NP 完全问题能在多项式时间内得到解决，那么NP 中的每一个问题都可以在多项式时间内解决。
（2）NP 完全是指这样一类NP 问题,所有的NP 问题都可以用多项式时间划归到他们中的一个.所以显然NP 完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP －完全问题也可以在多项式时间内求解。
这样一来,只要我们找到一个NPC 问题的多项式解,所有的NP 问题都可以多项式时间内划归成这个NPC 问题,再用多项式时间解决,这样NP 就等于P 了.NP 完全性理论的重要性:知道一个问题是NP 完全的就给我们提供了有价值的信息，告诉我们采用什么样的途径可以是最富有成效的。
一定不要去优先寻找有效的、精确的算法。
现在比较适当的途径是集中精力致力于其他较低目标的方法。
例如，你可以寻找解决这个问题的各种特殊情况的有效算法。
寻找在大多数情况下看来能快速运算的算法，虽然不能保证它在任何情况下都能快速地运算。
或者你甚至可以放松问题的某些方面，寻找一个只能给出满足大部分要求的快速算法。
简言之，NP 完全性理论的初步应用是帮助算法设计人员找到最有可能得到有用的算法的努力方向3. “当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质”。
问题的最优子结构性质是该问题可用动态规划算法求解的基本要素，试简要阐述“论证某一问题的最优子结构性质”时的一般方法；矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
这种性质称为最优子结构性质。
在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。
利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
最优子结构是问题能用动态规划算法求解的前提。
Ο(2n )＜Ο(n!)＜Ο(n n ) Ο(1)＜Ο(log 2n)＜Ο(n)＜Ο(nlog 2n)＜Ο(n 2)＜Ο(n n )同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：假设（y1,y2,…,yn ）是0-1背包问题的一个最优解，而（y2,…,yn ）是相应子问题的一个最优解，有2max ni ii v x =∑ 112n i i i w xC w y =≤-∑ {0,1}2x i n ∈≤≤假设（y2,…,yn ）不是一个最优解，而（z2,…,zn ）是最优解，由此可知，这说明（y1,z1,z2,…,zn ）是问题的整体最优解，与（y1,y2,…,yn ）是最优解矛盾，所以证明了最优子结构性质！三、算法设计与分析问题1. 最大值和最小值问题的最优算法（18）给定n 个实数存放于一维数组A 中，试设计一个算法在最坏情况下用3n/2-2次的比较找出A 中的最大值和最小值（为简化，可假设n 为偶数）。
2. 社会名流问题在 n 个人中，一个被所有人知道但却不知道别人的人，被定义为社会名流。
现在的问题是如果存在，试找出该社会名流。
你可以使用的唯一方式是询问：“对不起，请问你知道那个人吗？”（假定所有回答都正确，甚至这位社会名流也将回答。
）我们的最终目标是将询问的数目最小化。
给定一个n ×n 邻接矩阵，确定是否存在一个i ，其满足在第i 列所有项（除了第ii 项）都为1，并且第i 行所有项（除了第ii 项）都为0。
大致的算法思路：随便取一个非对角线元素比如Array[i][j]，如果Array[i][j]=0成立，则j 不是社会名流，于是删去第j 行和第j 列。
同样，如果Array[i][j]=1成立，则删去第i 行和第i 列；总之，无论对应项取何值，都可以删去一行和一列，因此整个操作只耗费O(n)的时间。
重复此操作直至剩下最后一个元素。
最后，检验该元素是否为社会名流即可。
如果该元素不是，则该群人中不存在社会名流。
3.数列极差问题在黑板上写了N 个正数组成的一个数列，进行如下的操作：每一次任选其中的两个数设为a 和b ，将其擦去，然后在数列中加入一个新的数a*b+1，如此下去直至黑板上只剩下一个数为止。
在所有按这种操作方式最后得到的数中，最大的数记为Max ，最小的数记为Min ，则该数列的极差定义为M=Max-Min 。
贪心算法最重要的两个性质是：贪心选择性质和最优子结构性质。
贪心选择性质是所求问题的整体最优解可以通过一系列局部最优的选择，也就是贪心选择来达到。
而最优子结构性质是指一个问题的最优解包含其子问题的最优解。
问题的关键就是MAX MIN 值的求解问题，所以首先看下怎么样来求MAX MIN 值。
设有三个数x y z,且x<y<z ，按问题描述来做的话，结果有下面三种情况：num1=（x*y+1）*z+1=xyz+z+1 , num2=(x*z+1)*y+1=xyz+y+1，num3=(y*z+1)*x+1=xyz+x+1。
很容易看出num1>num2>num3。
所以我们可以得出结论：优先选择数列中最小的2个数进行（a*b+1）运算得到的值大，优先选择数列中最大的2个数进行（a*b+1）运算得到的值小。
我们可以把整体的MAX ，MIN 值通过一系列局部求MAX,MIN 值来求我们想要的结果。
我们再看下用贪心策略求解的合理性：假设经（N －3）次运算后得到3个数：x y max （max>x>y ），其中max 是（N －2）个数经（N －3）次运算后所得的最大值，此时最大值m ＝（x*y ＋1）×max ＋1。
若经（N －2）次变换后所得的3个数为：x y z （z>x>y ）且z 不为（N －2）次变换后的最大值，即z ＜max 则所求得的最大值为： m ’＝（x*y+1）*z+1， 此时m －m ’＝（1+x*y ）（max －z ）＞0 所以此时不为最优解。
所以若使第k （1≤k ≤N －1）次变换后所得值最大，必使（k －1）次变换后所得值最大（符合贪心策略的最优子结构性质），在进行第k次变换时，只需取在进行（k－1）次变换后所得数列中的两最小数x，y进行运算，再把结果插入到数列即可。
所以综上所述：该算法可以简单的描述为：MAX：不断地取当前黑板上的两个最小的数进行运算并且放回，会使最后的结果最大。
MIN：不断地取当前黑板上的两个最大的数进行运算并且放回，会使最后的结果最小。
