实验报告
课程算法设计与分析实验实验名称贪心算法设计与应用第 1 页一、实验目的
理解贪心算法的基本原理，掌握贪心算法设计的基本方法及其应用；
二、实验内容
(一)Huffman编码和译码问题：
1．问题描述
给定n个字符在文件中的出现频率，利用Huffman树进行Huffman编码和译码。设计一个程序实现：
1.输入含n(n<=10)个字符的字符集S以及S中各个字符在文件中的出现频
率，建立相应的Huffman树，求出S中各个字符的Huffman编码。
2.输入一个由S中的字符组成的序列L，求L的Huffman 编码。
3. 输入一个二进制位串B，对B进行Huffman译码，输出对应的字符序列；
若不能译码，则输出无解信息。
提示：对应10 个字符的Huffman树的节点个数<211。
2．测试数据
Input
n=5
字符集合S={a, b, c, d, e},
对应的频率分别为
a: 20
b: 7
c: 10
d: 4
e: 18
字符序列L=ebcca
二进制位串B=01100111010010
Output
S中各个字符的Huffman编码：（设Huffman树中左孩子的权<=右孩子的权）a: 11
b: 010
c: 00
d: 011
e: 10
L的Huffman 编码：10010000011
B对应的字符序列： dcaeeb
若输入的B=01111101001，则无解
(二) 加油问题（Problem Set 1702）：
1.问题描述
一个旅行家想驾驶汽车从城市A到城市B（设出发时油箱是空的）。给定两个
城市之间的距离dis、汽车油箱的容量c、每升汽油能行驶的距离d、沿途油站数n、油站i离出发点的距离d[i]以及该站每升汽油的价格p[i],i=1,2,…,n。设d[1]=0 2.具体要求 Input 输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含4个正整数，依次为A和B两个城市之间的距离d1、汽车油箱的容量c（以升为单位）、每升汽油 能行驶的距离d2、沿途油站数n (1<=n<=200)；第二行含n个实数d 1, d 2 ,…, d n ，表示各油站离出发点的距离（d 1 =0）；第三行含n个实数p 1 , p 2 ,…, p n ， 表示各油站每升汽油的价格。同一行的数之间用一个空格隔开。 Output 对于每个测试例输出一行，含一个实数，表示从城市Ａ到城市Ｂ所要花费的最少油费（输出的结果精确到小数点后一位）。若问题无解，则输出“No Solution”。 3.测试数据 2 1500 50 10 4 0 300.0 800.0 1200.0 4.0 5.0 4.0 4.5 1000 40 10 3 0 500.0 750.0 4.5 5.0 4.2 Sample Output 640.0 No Solution 4．设计与实现的提示 （1）注意考虑无解的情况 （2）对终点站可进行特殊处理 5.扩展内容 (1) 演示时建议采用可视化界面 (2) The Express Mail(Problem Set 1755) (三) 黑白点的匹配（Problem Set 1714）：（选作题） 4.问题描述 设平面上分布着n个白点和n个黑点，每个点用一对坐标（x, y）表示。一个黑点b=（xb,yb）支配一个白点w=(xw, yw)当且仅当xb>=xw和yb>=yw。 若黑点b支配白点w，则黑点b和白点w可匹配（可形成一个匹配对）。在一 个黑点最多只能与一个白点匹配，一个白点最多只能与一个黑点匹配的前提下，求n个白点和n个黑点的最大匹配对数。 5.具体要求 输入的第一行是一个正整数k，表示测试例个数。接下来几行是k个测试例的数据，每个测试例的数据由三行组成，其中第一行含1个正整数n(n<16)； 第二行含2n个实数xb 1, yb 1 ,xb 2 , yb 2 ,…, xb n , yb n ， (xb i , yb i )，i=1, 2, …, n表示n个黑点的坐标；第三行含2n个实数xw 1, yw 1 ,xw 2 , yw 2 ,…, xw n , yw n ， (xw i , yw i )，i=1, 2, …, n表示n个白点的坐标。同一行的实数之间用一个 空格隔开。 Output 对于每个测试例输出一行，含一个整数，表示n个白点和n个黑点的最大匹配对数。 6.测试数据 输入： 1 3 5.0 3.0 5.0 -1.0 4.0 4.0 2.0 3.5 2.0 2.0 -2.0 -2.0 输出： 3 7.扩展内容 (1) 建议采用可视化界面 三、实验环境 硬件：Windows XP计算机、鼠标、键盘、显示器 开发环境：Microsoft Visual C++ 6.0 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，发生的现象和中间结果） ①、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验五.(1).cpp”,再点击确定. ②、编写程序如下： #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 100 struct HafNode { char ch; int weight; int parent,lchild,rchild; }*HaffmanTree; struct Coding { char bit[MAX]; char ch; int weight; }*HaffmanCode; /*------------------------//构造哈弗曼树-----------------------------*/ void Haffman(int n)//构造哈弗曼树 { int i,j,x1,x2,s1,s2; for(i=n+1;i<=2*n-1;i++) { s1=s2=10000; x1=x2=0; for(j=1;j<=i-1;j++) { if(HaffmanTree[j].parent==0&&HaffmanTree[j].weight s2=s1; x2=x1; s1=HaffmanTree[j].weight; x1=j; } else if(HaffmanTree[j].parent==0&&HaffmanTree[j].weight s2=HaffmanTree[j].weight; x2=j; } } HaffmanTree[x1].parent=i; HaffmanTree[x2].parent=i; HaffmanTree[i].weight=s1+s2; HaffmanTree[i].lchild=x1; HaffmanTree[i].rchild=x2; } } /*---------------------------//构造哈弗曼编码------------------------*/ void Haffman_Code(int n) { int start,c,f,i,j,k; char *cd; cd=(char *)malloc(n*sizeof(char)); HaffmanCode=(struct Coding *)malloc((n+1)*sizeof(struct Coding)); cd[n-1]='\0'; for(i=1;i<=n;++i) { start=n-1; for(c=i,f=HaffmanTree[i].parent;f!=0;c=f,f=HaffmanTree[f].parent) if(HaffmanTree[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; for(j=start,k=0;j { HaffmanCode[i].bit[k]=cd[j]; k++; } HaffmanCode[i].ch=HaffmanTree[i].ch; HaffmanCode[i].weight=HaffmanTree[i].weight; } free(cd); } int CreatHuffman() { int i,n,m; printf("请输入字符集大小n:\n"); scanf("%d",&n); m=2*n-1; HaffmanTree=(struct HafNode *)malloc(sizeof(struct HafNode)*(m+1)); for(i=1;i<=n;i++) { printf("请输入第%d个字符和权值: ",i); scanf("%s%d",&HaffmanTree[i].ch,&HaffmanTree[i].weight); HaffmanTree[i].parent=0; HaffmanTree[i].lchild=0; HaffmanTree[i].rchild=0; } for(i=n+1;i<=m;i++) { HaffmanTree[i].ch ='#'; HaffmanTree[i].lchild=0; HaffmanTree[i].parent=0; HaffmanTree[i].rchild=0; HaffmanTree[i].weight=0; } Haffman(n); Haffman_Code(n); return n; } /*-----------------------输出每个字符的哈弗曼编码------------------------------*/ void output(int n) { printf("\n\n"); int i; for(i=1;i<=n;i++) { printf("%c的哈弗曼编码是：%s\n",HaffmanCode[i].ch,HaffmanCode[i].bit); } } /*------------------------------对字符进行编码---------------------------*/ void Char_Change(int m)//对字符进行编码 { int n,i,j; char string[50],*p; printf("请输入字符串："); scanf("%s",string); n=strlen(string);//n为输入的字符串的长度 printf("字符串的编码为: "); for(i=1,p=string;i<=n;i++,p++) { for(j=1;j<=m;j++) { if(HaffmanCode[j].ch==*p)//输入的字符串逐个与哈弗曼树的字符比对 printf("%s",HaffmanCode[j].bit); } } printf("\n"); } /*---------------------------对输入的编码进行译码---------------------*/ int Code_Change(int n) { int i,t; char code[1000]; printf("请输入编码： "); scanf("%s",code); printf("编码的字符串为： "); for(i=0;code[i]!='\0';) { t=2*n-1; while(code[i]!='\0') { if(code[i]-'0'==1) { if(HaffmanTree[t].rchild!=0) { t=HaffmanTree[t].rchild; } else { printf("No solution!\n"); return 0; } } else { if(HaffmanTree[t].lchild!=0) { t=HaffmanTree[t].lchild; } else { printf("No solution!\n"); return 0; } } if(HaffmanTree[t].lchild==0&&HaffmanTree[t].rchild==0) { printf("%c",HaffmanTree[t].ch); i++; if(code[i]=='\0') return 0; else break; } i++; } } } /*-----------------------主函数-----------------------------*/ void main() { int n; printf("---------------开始程序------------------\n\n"); n=CreatHuffman(); output(n);//输出每个字符的编码 printf("--------------对字符进行编码--------------\n\n"); Char_Change(n);//执行编码操作 printf("--------------对编码进行译码--------------\n\n"); Code_Change(n);//执行译码操作 printf("\n"); } ③、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验五.(2).cpp”,再点击确定. ④、编写程序如下： #include #define MAX 20 /*----------------------*/ void look(float dis[],float pir[],int n,int d2,int oil)//dis[i]表示第i个站点离起点的距离，pir[i]表示每升油的价格 {//n表示站点个数，d2表示每升油可走的距离，oil表示邮箱容量int i,j,k; float pirce=0.0,c1=0,x,c2; for(j=0;j<=n;j++) { for(i=j+1;i<=n;i++) { if(pir[i] { k=i; c2=(dis[k]-dis[j])/d2;//从开始站到符合条件站点所需要的油量 if(c2>=oil) { x=oil-c1;//加满油 } else { x=c2-c1;//需要的油量减去剩余的油量 if(x<0)//若剩余的油量够走到符合条件的站点，则不需要再加油 { x=0; } } pirce=pirce+pir[j]*x; break; } } c1=c1+x-((dis[j+1]-dis[j])/d2);//剩余油量 } printf("%.1f",pirce); } /*----------------------*/ void main() { int k,i,j,n[MAX],c[MAX],d1[MAX],d2[MAX],length[MAX],flag[MAX]; float A[MAX][MAX],B[MAX][MAX]; printf("输入测试例个数: \n"); scanf("%d",&k); for(i=0;i { printf("输入第%d个数据：\n",i+1); flag[i]=0; scanf("%d %d %d %d",&d1[i],&c[i],&d2[i],&n[i]); length[i]=c[i]*d2[i]; for(j=0;j { scanf("%f",&A[i][j]); } A[i][n[i]]=d1[i]*1.0; for(j=0;j { scanf("%f",&B[i][j]); } B[i][n[i]]=0.0; printf("\n"); for(j=n[i];j>0;j--) { if(A[i][j]-A[i][j-1]>length[i]) { flag[i]=1; } } if(flag[i]==1) { printf("第%d次结果： ",i+1); printf("NO solution!\n"); } else { printf("第%d次结果： ",i+1); printf("最少油费： "); look(A[i],B[i],n[i],d2[i],c[i]); } printf("\n"); printf("\n"); } } ⑤、点击开始菜单中的程序-Microsoft Visual C++ 6.0 点击菜单栏中的文件—新建—文件—C++ Source File ，在文件名(N)中写入“实验五.(3)黑白点问题.cpp”,再点击确定. ⑥、编写程序如下： #include #define INT_MAX 1000000 struct point { float x; float y; int tag; }w[10],b[10]; void bubble_sort(point w[], int n) { int j, k, h; point t; for (h=n-1; h>0; h=k) /*循环到没有比较范围*/ { for (j=0, k=0; j { if (w[j].x> w[j+1].x) /*大的放在后面，小的放到前面*/ { t = w[j]; w[j] = w[j+1]; w[j+1]= t; /*完成交换*/ k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了 的。*/ } } } } int match(point w[],point b[],int n) { int i,j,minflag,minp,count; count=0; float miny; for(i=n-1;i>=0;i--)//关于w[pw].x从大到小做{ minflag=0;//标记初始化 minp=0;//最接近点的下标初始化 miny=INT_MAX;//初始化y的无穷大 for(j=n-1;j>=0;j--) { if(b[j].tag) continue; if(b[j].x continue; if(b[j].y>=w[i].y) { minflag=1; if(miny>b[j].y) { miny=b[j].y; minp=j; } } } if(minflag) { count++; b[minp].tag=1; } } return count; } void main() { int k,n,i,count; printf("输入测试数据个数\n"); scanf("%d",&k); while(k>0) { printf("输入点的个数\n"); scanf("%d",&n); printf("输入黑点的坐标\n"); for(i=0;i { scanf("%f %f",&b[i].x,&b[i].y); } printf("输入白点的坐标\n"); for(i=0;i {scanf("%f %f",&w[i].x,&w[i].y); } for(i=0;i { w[i].tag=b[i].tag=0; } bubble_sort(w,n);//对白点的x值从小到大排序 count=match(w,b,n); printf("count=%d\n",count); k--; } } 五、实验结果 实验五.(1).cpp 按照实验要求输入测试例，得到的实验结果是： 实验五.(2).cpp 按照实验要求输入测试例，得到的实验结果是： 实验五.(3).cpp 按照实验要求输入测试例，得到的实验结果是： 六、总结 1.主要要注意实验中的细节 2.在写算法的时候要注意时间复杂性。 3.在做哈弗曼树实验时，即在创建树时，要注意结点的设置，还有在编码的时候要注意左右孩子的权值问题。 4.做加油问题时，要注意贪心算法的思想，即在每一要找出当前最佳，另外还要注意，在每一站，剩余油量和所需油量的计算。 算法设计与分析实验报告 贪心算法 班级：2013156 学号：201315614 姓名：张春阳哈夫曼编码 代码 #include printf("\n"); for(i=0;i 《计算机算法设计与分析》习题及答案 一．选择题 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4. 回溯法解旅行售货员问题时的解空间树是（ A ）。 A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树 5．下列算法中通常以自底向上的方式求解最优解的是（B ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 6、衡量一个算法好坏的标准是（ C ）。 A 运行速度快 B 占用空间少 C 时间复杂度低 D 代码短 7、以下不可以使用分治法求解的是（ D ）。 A 棋盘覆盖问题 B 选择问题 C 归并排序 D 0/1背包问题 8. 实现循环赛日程表利用的算法是（A ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 9．下面不是分支界限法搜索方式的是（D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 10．下列算法中通常以深度优先方式系统搜索问题解的是（D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 11.备忘录方法是那种算法的变形。（ B ） A、分治法 B、动态规划法 C、贪心法 D、回溯法 12．哈夫曼编码的贪心算法所需的计算时间为（B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 13．分支限界法解最大团问题时，活结点表的组织形式是（B ）。 A、最小堆 B、最大堆 C、栈 D、数组 14．最长公共子序列算法利用的算法是（B）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．实现棋盘覆盖算法利用的算法是（A ）。 A、分治法 B、动态规划法 C、贪心法 D、回溯法 16.下面是贪心算法的基本要素的是（C ）。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、定义最优解 17.回溯法的效率不依赖于下列哪些因素（ D ） A.满足显约束的值的个数 B. 计算约束函数的时间 C.计算限界函数的时间 D. 确定解空间的时间 18.下面哪种函数是回溯法中为避免无效搜索采取的策略（B ） A．递归函数 B.剪枝函数 C。随机数函数 D.搜索函数 19. （D）是贪心算法与动态规划算法的共同点。 A、重叠子问题 B、构造最优解 C、贪心选择性质 D、最优子结构性质 20. 矩阵连乘问题的算法可由（ B ）设计实现。 A、分支界限算法 B、动态规划算法 C、贪心算法 D、回溯算法 21. 分支限界法解旅行售货员问题时，活结点表的组织形式是（ A ）。 贪心算法经典例题 发布日期：2009-1-8 浏览次数：1180 本资料需要注册并登录后才能下载！ ·用户名密码验证码找回密码·您还未注册？请注册 您的账户余额为元，余额已不足，请充值。 您的账户余额为元。此购买将从您的账户中扣除费用0.0元。 内容介绍>> 贪心算法经典例题 在求最优解问题的过程中，依据某种贪心标准，从问题的初始状态出发，直接去求每一步的最优解，通过若干次的贪心选择，最终得出整个问题的最优解，这种求解方法就是贪心算法。 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④ 6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] a.in： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 算法实现题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 贪心算法的应用 课程名称：算法设计与分析 院系：计算机科学与信息工程学院 学生姓名：**** 学号：********** 专业班级：********************************** 指导教师：****** 201312-27 贪心算法的应用 摘要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法背包问题最优化 目录 第1章绪论 (3) 1.1 贪心算法的背景知识 (3) 1.2 贪心算法的前景意义 (3) 第2章贪心算法的理论知识 (4) 2.1 问题的模式 (4) 2.2 贪心算法的一般性描述 (4) 第3章背包问题 (5) 3.1 问题描述 (5) 3.2 问题分析 (5) 3.3算法设计 (5) 3.4 测试结果与分析 (10) 第4章结论 (12) 参考文献 (13) 附件 (13) 1.引言： 贪心法是一种改进了的分级处理方法。用贪心法设计算法的特点是一步一步地进行，每一步上都要保证能获得局部最优解。每一步只考虑一个数据，它的选取满足局部优化条件。若下一个数据与部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加为止。这种能够得到某种度量意义下的最优解的分级处理方法称为贪心法。 贪心算法总是做出在当前看来是最优的选择，也就是说贪心算法并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该题运用贪心算法可以得到最优解或较优解。 2.贪心算法的基本思想及存在问题 贪心法的基本思想： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 3.活动安排问题： 3.1 贪心算法解决活动安排问题 学校举办活动的安排问题是用贪心算法有效求解的一个很好例子。活动安排问题要求安排一系列争用某一公共资源的活动。用贪心算法可使尽可能多的活动能兼容的使用公共资源。设有n个活动的集合｛0，1，2，…，n-1｝，其中每个活动都要求使用同一资源，如会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间starti和一个结束时间endi，且starti 精品文档习题胡明-版)-王红梅-算法设计与分析(第2答案 1 习题）—1783Leonhard Euler，17071.图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（提 出并解决了该问题。七桥问题是这样描述的：北区一个人是否能在一次步行中穿越哥尼斯堡（现东区在叫加里宁格勒，在波罗的海南岸）城中全部岛区的七座桥后回到起点，且每座桥只经过一次，南区是这条河以及河上的两个岛和七座桥的图1.7 1.7 七桥问题图草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。 七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点一次步行1，经过七座桥，且每次只经历过一次2，回到起点3，该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。）用的不是除法而是减最初的欧几里德算法2．在欧几里德提出的欧几里德算法中（即法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n r=0 循环直到2.m=n 2.1 n=r 2.2 r=m-n 2.3 m 输出3 ．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代3++描述。C码和 采用分治法// //对数组先进行快速排序在依次比较相邻的差//精品文档． 精品文档 #include 贪心算法详解 贪心算法思想： 顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。 贪心算法的基本要素： 1.贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。 2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的 最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 贪心算法的基本思路： 从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到算法中的某一步不能再继续前进时，算法停止。 该算法存在问题： 1. 不能保证求得的最后解是最佳的； 2. 不能用来求最大或最小解问题； 3. 只能求满足某些约束条件的可行解的范围。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解； 用背包问题来介绍贪心算法： 背包问题：有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要 求尽可能让装入背包中的物品总价值最大，但不能超过总容量。 贪心方法：总是对当前的问题作最好的选择，也就是局部寻优。最后得到整体最优。 应用：1：该问题可以通过“局部寻优”逐步过渡到“整体最优”。贪心选择性质与“动态规划”的主要差别。 2：最优子结构性质：某个问题的整体最优解包含了“子”问题的最优解。 代码如下： #include for(i=1;i<=n;i++) goods[i].X=0; cu=M; //背包剩余容量 for(i=1;i 贪心算法与动态规划的比较 【摘要】介绍了计算机算法设计的两种常用算法思想：贪心算法与动态规划算法。通过介绍两种算法思想的基本原理，比较两种算法的联系和区别。通过背包问题对比了两种算法的使用特点和使用范围。 【关键字】动态规划；贪心算法；背包问题 1、引言 为了满足人们对大数据量信息处理的渴望，为解决各种实际问题，计算机算法学得到了飞速的发展，线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中，产生了解决各种现实问题的有效算法。虽然设计一个好的求解算法更像是一门艺术而不像是技术，但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法，你可以使用这些方法来设计算法，并观察这些算法是如何工作的。一般情况下，为了获得较好的性能，必须对算法进行细致的调整。但是在某些情况下，算法经过调整之后性能仍无法达到要求，这时就必须寻求另外的方法来求解该问题。本文针对部分背包问题和0/ 1 背包问题进行分析，介绍贪心算法和动态规划算法的区别。 2、背包问题的提出 给定n种物品( 每种物品仅有一件) 和一个背包。物品i的重量是w i，其价值为p i，背包的容量为M。问应如何选择物品装入背包，使得装入背包中的物品的总价值最大,每件物品i的装入情况为x i，得到的效益是p i*x i。 ⑴部分背包问题。在选择物品时，可以将物品分割为部分装入背包，即0≤x i≤1 ( 贪心算法)。 ⑵0/ 1背包问题。和部分背包问题相似，但是在选择物品装入时要么不装，要么全装入，即x i = 1或0。( 动态规划算法) 。 3、贪心算法 3.1 贪心算法的基本要素 能够使用贪心算法的许多例子都是最优化问题，每个最优化问题都包含一组限制条件和一个优化函数，符合限制条件的问题求解方案称为可行解；使优化函数取得最佳值的可行解称为最优解。此类所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到(这是贪心算法与动态规划的主要区别) 。 3.2贪心策略的定义 贪心策略是指从问题的初始状态出发，通过若干次的贪心选择而得出最优值( 或较优解) 的一种解题方法。贪心策略总是做出在当前看来是最优的选择，也就是说贪心策略并不是从整体上加以考虑，它所做出的选择只是在某种意义上的局部最优解，而许多问题自身的特性决定了该问题运用贪心策略可以得到最优解或较优解。(注：贪心算法不是对所有问题都能 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:_________,________,________,__________,__________。 2.算法的复杂性有_____________和___________之分，衡量一个算法 好坏的标准是______________________。 3.某一问题可用动态规划算法求解的显著特征是 ____________________________________。 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y的一个最长公共子序列_____________________________。 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含___________。 6.动态规划算法的基本思想是将待求解问题分解成若干____________，先求解___________，然后从这些____________的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为_____________。 8.0-1背包问题的回溯算法所需的计算时间为_____________,用动态规划算法所需的计算时间为____________。 9.动态规划算法的两个基本要素是___________和___________。 10.二分搜索算法是利用_______________实现的算法。 二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 2.流水作业调度问题的johnson算法的思想。 基于贪心算法与最小路径的基因组组装优化问题 摘要 随着人类基因组计划的实施和飞速发展，基因组测序拼接作为生物信息学的核有着极其重要的应用价值。新的测序技术大量涌现，产生的reads 长度更短，数量更多，覆盖率更大，能直接读取的碱基对序列长度远小于基因组长度。本文通过如何在保证组装序列的连续性、完整性和准确性的同时设计耗时短、内存小的组装算法，建立数学模型来解决基因组组装问题。 针对问题一，首先，利用相应的软件对原基因组G 进行切割，利用全基因鸟枪法测序对切割后的短基因进行测序，得到较小的基因组j i G ,通过对比多条任意切割后相似的基因组j i G 从而找出个别碱基对存在的识别错误。而对于基因组中存在的重复片段可以通过两个read 之间的DNA 片段的长度满足一定的分布规律即pared end read 来解决。 接下来对比任意两个11 1m n read 和3 2 2 m n read 是否相等，通过MATLAB 软件建立n m 阶的关联矩阵，最后利用图论中的最短路径方法使更多的基因组能拼接在一起，尽可能使拼接出来的基因组在原基因组的覆盖率达到最大。 针对问题二，先把附件给出的数据提取出来导入MATLAB 中，再结合问题一给出的模型对基因组进行重组，从而得到新的基因。 最后，基于对基因组组装的研究，为使重组基因能更接近原基因序列，对问题一提出模型进行合理性的评价。 关键词：基因组组装 全基因鸟枪法测序 贪心算法 最短路径 一、问题的重述 1.1问题背景 快速和准确地获取生物体的遗传信息对于生命科学研究具有重要的意义。对每个生物体来说，基因组包含了整个生物体的遗传信息，这些信息通常由组成基因组的DNA或RNA分子中碱基对的排列顺序所决定。获得目标生物基因组的序列信息，进而比较全面地揭示基因组的复杂性和多样性，成为生命科学领域的重要研究内容。 1.2问题提出 确定基因组碱基对序列的过程称为测序（sequencing）。测序技术始于20世纪70年代，伴随着人类基因组计划的实施而突飞猛进。从第一代到现在普遍应用的第二代，以及近年来正在兴起的第三代，测序技术正向着高通量、低成本的方向发展。尽管如此，目前能直接读取的碱基对序列长度远小于基因组序列长度，因此需要利用一定的方法将测序得到的短片段序列组装成更长的序列。通常的做法是，将基因组复制若干份，无规律地分断成短片段后进行测序，然后寻找测得的不同短片段序列之间的重合部分，并利用这些信息进行组装。例如，若有两个短片段序列分别为 ATACCTT GCTAGCGT GCTAGCGT AGGTCTGA 则有可能基因组序列中包含有ATACCTT GCTAGCGT AGGTCTGA这一段。当然，由于技术的限制和实际情况的复杂性，最终组装得到的序列与真实基因组序列之间仍可能存在差异，甚至只能得到若干条无法进一步连接起来的序列。对组装效果的评价主要依据组装序列的连续性、完整性和准确性。连续性要求组装得到的（多条）序列长度尽可能长；完整性要求组装序列的总长度占基因组序列长度的比例尽可能大；准确性要求组装序列与真实序列尽可能符合。 利用现有的测序技术，可按一定的测序策略获得长度约为50–100个碱基对的序列，称为读长（reads）。基因组复制份数约为50–100。基因组组装软件可根据得到的所有读长组装成基因组，这些软件的核心是某个组装算法。常用的组装算法主要基于OLC（Overlap/Layout/Consensus）方法、贪婪图方法、de Bruijn 图方法等。一个好的算法应具备组装效果好、时间短、内存小等特点。新一代测序技术在高通量、低成本的同时也带来了错误率略有增加、读长较短等缺点，现有算法的性能还有较大的改善空间。 具体解决问题如下： 问题一：试建立数学模型，设计算法并编制程序，将读长序列组装成基因组。你的算法和程序应能较好地解决测序中可能出现的个别碱基对识别错误、基因组中存在重复片段等复杂情况。 问题二：现有一个全长约为120,000个碱基对的细菌人工染色体（BAC），采用Hiseq2000测序仪进行测序，测序策略以及数据格式的简要说明见附录一和附录二，测得的读长数据见附录三，测序深度（sequencing depth）约为70×，即基因组每个位置平均被测到约70次。试利用你的算法和程序进行组装，并使之具有良好的组装效果。 @ 实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； 】 （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 { w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 ~ #include <> #include <> #include <> typedef struct { unsigned int weight; arent==0) { @ min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { ! if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; ∑=j i k k a for(i=1; i<=n; i++) { ~ if((*ht)[i].parent==0 && i!=(*s1)) { min=i; break; } } for(i=1; i<=n; i++) { % if((*ht)[i].parent==0 && i!=(*s1)) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s2=min; } - eight=w[i]; (*ht)[i].LChild=0; (*ht)[i].parent=0; (*ht)[i].RChild=0; } for(i=n+1; i<=m; i++) eight=0; (*ht)[i].LChild=0; \ (*ht)[i].parent=0; (*ht)[i].RChild=0; } printf("\n哈夫曼树为: \n"); for(i=n+1; i<=m; i++) arent=i; (*ht)[s2].parent=i; 。 (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; printf("%d (%d, %d)\n",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight); } printf("\n"); } 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型：C 卷 考试时量：120 分钟 1. 用O 、Ω和θ表示函数f 与g 之间的关系______________________________。 ()()log log f n n n g n n == 2. 算法的时间复杂性为1, 1()8(3/7), 2 n f n f n n n =?=? +≥?，则算法的时间复杂性的阶 为__________________________。 3. 快速排序算法的性能取决于______________________________。 4. 算法是_______________________________________________________。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的是_________________________。 6. 在算法的三种情况下的复杂性中，可操作性最好且最有实际价值的是_____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越___________，结果就越有价值。。 8. ____________________________是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指________________________________________________________ ____________________________________________________________。 题 号 一 二 三 四 五 总分 统分人 得 分 阅卷人 从贪心算法的定义可以看出，贪心法并不是从整体上考虑问题，它所做出的选择只是在某种意义上的局部最优解，而由问题自身的特性决定了该题运用贪心算法可以得到最优解。 我们看看下面的例子 例1 均分纸牌（NOIP2002tg） [问题描述] 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为： ①9 ②8 ③17 ④6 移动3次可达到目的： 从③取 4 张牌放到④（9 8 13 10） -> 从③取 3 张牌放到②（9 11 10 10）-> 从②取 1 张牌放到①（10 10 10 10）。 [输入]：键盘输入文件名。 文件格式：N（N 堆纸牌，1 <= N <= 100） A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000） [输出]：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。 [输入输出样例] ： 4 9 8 17 6 屏慕显示：3 算法分析：设a[i]为第i堆纸牌的张数（0<=i<=n），v为均分后每堆纸牌的张数，s为最小移到次数。 我们用贪心法，按照从左到右的顺序移动纸牌。如第i堆(0 摘要：作业和测试的自动组卷是在线形成性考核系统的核心内容。本文在深入研究贪心算法的基础上，提出了基于贪心算法的自动组卷算法，分析了题库和作业库的约束条件，实现了快速高效的组卷过程。最后给出具体实例加以论证。该算法已经成功应用于实际的在线形成性考核系统中。 关键词：贪心算法；在线形成性考核；约束条件；组卷 一、引言目前，常用的自动组卷算法有随机选取算法、回溯试探算法、蛮力法和遗传算法等，这些算法对在线考试系统确实具有一定的应用价值，但这些方法生成的作业卷和测试卷在试卷的科学性和合理性上考虑较少。在综合研究以上各种算法的优缺点后，保证达到较好时间效率和空间效率的基础上，采用贪心算法为核心和随机选取算法为辅助的组卷算法，应用于在线形成性考核系统在线作业和在线测试中，能够达到较好的组卷效果，并且达到教学辅助效果。决定组卷效率和作业卷质量的主要因素有两个：一是题库和作业库的结构；二是组卷算法的设计。二、贪心算法简介贪心算法建议通过一系列步骤来构造问题的解，每一步对目前构造的部分解做一个扩展，直到获得问题的完整解为止。在每一步中，它要求“贪婪”地选择最佳操作，并希望通过一系列局部的最优选择，能够产生一个全局的最优解。贪心算法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪心算法的基本要素。一是贪心选择性质。所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。二是最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。在题库组卷问题中，其最优子结构性质表现为：若a是对于e的题库组卷问题包含试题1的一个最优解，则相容作业卷集合a′= a-{1}是对于e′= {i∈e：si≥f1}的题库组卷问题的一个最优解。三、基于贪心算法的在线形成性考核系统组卷算法1、在线形成性考核系统结构在线形成性考核是指对学生学习过程的测评，是对学生课程学习的阶段性考核，是加强教学过程管理、检验学习效果的重要措施。在该系统中，管理员模块主要负责数据导入导出和系统维护，按照学生的课程注册信息绑定学生的班级、课程、辅导教师及恢复误删除成绩；教师模块完成课程形成性考核方案设计，作业题设计，查询考核内容，作业管理，作业批阅，查询批阅结果，删除已批阅但学生要求重做的作业成绩，学生信息管理，查询作业完成情况，到课率录入；学生模块主要功能是查看形考方案、主持教师、辅导教师、导学教师，在线作业，在线测试，作业成绩及反馈查询。在线形成性考核系统结构如图1所示。图1 在线形成性考核系统结构2、题库设计首先需要确定的是试题组织的方式。为了保证达标原则、全面性原则和主要性原则，最好将试题库与具体的知识内容进行关联，也即以课程知识点为核心组织试题库。然后就要考虑试题本身固有的特性参数，主要有题型、试题内容、答案、难度系数等。难度系数是试题难易程度的指标，也是试卷生成中的一个重要参数，它可以由教师录入试题时给定，并且在同一门课程中要坚持相同的标准，并且难度标准初始设定时要充分考虑到所要测试学生的程度范围。难度系数一般用等级来表示, 在五级难度系数中, 一级难度为最低, 五级难度为最高。题型分为客观题和主观题。客观题分单项选择题、多项选择选、判断题和填空题，主观题分计算题、简答题和论述题。3、作业库设计组卷方式可以按需求由主持老师进行客观题和主观题自由组卷。客观题在学生完成并提交成功后，系统自动阅卷并给出成绩。主观题在学生完成并提交后，由辅导老师阅 数据结构课程设计 设计说明书 题目 TSP问题贪心算法 起止日期：2014年11月10 日至2014 年11月17日 计算机科学与工程学院 2014年11月9日 课程设计任务书 一、设计目的 熟悉各种数据结构和运算，会使用数据结构的基本操作解决一些实际问题。二、设计要求 在本课程设计过程中要求学生： （1）重视课程设计环节，用严谨、科学和踏实的工作态度对待课程设计的每一项任务； （2）按照课程设计的题目要求，独立地完成各项任务，严禁抄袭；凡发现抄袭，抄袭者与被抄袭者皆以零分计入本课程设计成绩。凡发现实验报告或源程序雷同，涉及的全部人员皆以零分计入本课程设计成绩。 （3）学生在接受设计任务后，根据要求认真完成。 （4）认真编写课程设计报告。 三、设计内容 TSP问题（贪心法求解） 1) 问题描述 所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 2) 基本要求 (1) 上网查找TSP问题的应用实例； (2) 分析求TSP问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3) 设计思想 对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n大到一定程度后是不可解的。 4）设计思想 对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n 大到一定程度后是不可解的。 本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。 为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下： 1. 任意选择某个顶点v作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点； 2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j； 2.2 访问顶点j； 3. 从最后一个访问的顶点直接回到出发点v； 四、参考文献 1. 王红梅，数据结构，清华大学出版社； 2. 王红梅，数据结构学习辅导与实验指导，清华大学出版社； 3. 王晓东，计算机算法设计与分析，电子工业出版社。 第一章作业 1.证明下列Ο、Ω和Θ的性质 1）f=Ο(g)当且仅当g=Ω(f) 证明：充分性。若f=Ο(g)，则必然存在常数c1>0和n0，使得?n≥n0，有f≤c1*g(n)。由于c1≠0，故g(n) ≥ 1/ c1 *f(n)，故g=Ω(f)。 必要性。同理，若g=Ω(f)，则必然存在c2>0和n0，使得?n≥n0，有g(n) ≥ c2 *f(n).由于c2≠0，故f(n) ≤ 1/ c2*f(n)，故f=Ο(g)。 2）若f=Θ(g)则g=Θ(f) 证明：若f=Θ(g)，则必然存在常数c1>0，c2>0和n0，使得?n≥n0，有c1*g(n) ≤f(n) ≤ c2*g(n)。由于c1≠0，c2≠0，f(n) ≥c1*g(n)可得g(n) ≤ 1/c1*f(n)，同时，f(n) ≤c2*g(n)，有g(n) ≥ 1/c2*f(n)，即1/c2*f(n) ≤g(n) ≤ 1/c1*f(n)，故g=Θ(f)。 3）Ο(f+g)= Ο(max(f,g))，对于Ω和Θ同样成立。 证明：设F(n)= Ο(f+g)，则存在c1>0，和n1，使得?n≥n1，有 F(n) ≤ c1 (f(n)+g(n)) = c1 f(n) + c1g(n) ≤ c1*max{f,g}+ c1*max{f,g} =2 c1*max{f,g} 所以，F(n)=Ο(max(f,g))，即Ο(f+g)= Ο(max(f,g)) 对于Ω和Θ同理证明可以成立。 4）log(n!)= Θ(nlogn) 证明： ?由于log(n!)=∑=n i i 1 log ≤∑=n i n 1 log =nlogn ，所以可得log(n!)= Ο(nlogn)。 ?由于对所有的偶数n 有， log(n!)= ∑=n i i 1 log ≥∑=n n i i 2 /log ≥∑=n n i n 2 /2/log ≥(n/2)log(n/2)=(nlogn)/2-n/2。 当n ≥4，(nlogn)/2-n/2≥(nlogn)/4，故可得?n ≥4，log(n!) ≥(nlogn)/4，即log(n!)= Ω(nlogn)。 综合以上两点可得log(n!)= Θ(nlogn) 2. 设计一个算法，求给定n 个元素的第二大元素，并给出算法在最坏情况下使用的比较次数。（复杂度至多为2n-3） 算法： V oid findsecond(ElemType A[]) { for (i=2; i<=n;i++) if (A[1]算法设计与分析实验报告贪心算法
《计算机算法设计与分析》习题及答案
贪心算法经典例题
算法设计与分析课后部分习题答案
【精选】贪心算法的应用
贪心算法解决活动安排问题报告
算法设计与分析第2版 王红梅 胡明 习题答案
贪心算法详解分析
背包问题的贪心算法
贪心算法与动态规划的比较
算法设计与分析考试题及答案
基于贪心算法与最短路径的基因组组装最优拼接问题---1411
实验三.哈夫曼编码的贪心算法设计
算法设计与分析试卷及答案
贪心算法的应用
基于贪心算法的在线形成性考核系统组卷研究
数据结构课设_TSP贪心算法
算法设计与分析习题解答
相关主题
文本预览