当前位置：文档之家› OpenJudge算法设计与分析习题解答

OpenJudge算法设计与分析习题解答

O p e n J u d g e算法设计与

分析习题解答

Company Document number：WUUT-WUUY-WBBGB-BWYTT-1982GT

1、硬币面值组合

描述

使用1角、2角、5角硬币组成 n 角钱。

设1角、2角、5角的硬币各用了a、b、c个，列出所有可能的a, b, c组合。

输出顺序为：先按c的值从小到大，若c相同则按b的值从小到大。

输入

一个整数n（1 <= n <= 100)，代表需要组成的钱的角数。

输出

输出有若干行，每行的形式为：

i a b c

第1列i代表当前行数（行数从001开始，固定3个字符宽度，宽度不足3的用0填充），后面3列a, b, c分别代表1角、2角、5角硬币的个数（每个数字固定12个字符宽度，宽度不足的在左边填充空格）。

样例输入

样例输出

#include<>

int main(){

int t=1;

int i,j,k;

int n;

scanf("%d",&n);

int A=n,B=n/2,C=n/5;

for(i=0;i<=C;i++){

for(j=0;j<=B;j++){

for(k=0;k<=A;k++){

if(i*5+j*2+k*1==n){

printf("%03d%12d%12d%12d\n",t,k,j,i);

t++;

}

getchar();

return 0;

}

2、比赛排名

描述

5名运动员参加100米赛跑，各自对比赛结果进行了预测：

A说：E是第1名。

B说：我是第2名。

C说：A肯定垫底。

D说：C肯定拿不了第1名。

E说：D应该是第1名。

比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。

请编程判断5位选手各是第几名。

输入

无

输出

输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，

第3行是C的名次，第4行是D的名次，第5行是E的名次。

样例输入

样例输出

源代码：

#include<>

int main()

{

printf("5\n");

printf("2\n");

printf("1\n");

printf("3\n");

printf("4\n");

return 0;

}

3、鸡兔同笼

描述

一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。

输入

一行，一个正整数a (a < 32768)。

输出

一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。

如果没有满足要求的答案，则输出两个0，中间用一个空格分开。

样例输入

样例输出

#include <>

int main()

{

int n;

scanf("%d",&n);

if(n % 4== 0)

printf("%d %d",n/4,n/2);

else if(n % 4!= 0&&n % 2== 0)

printf("%d %d",n/4 +1, n/2);

else

printf("0 0");

return 0;

}

4、谁是你的潜在朋友

描述

“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同

的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。

首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照“臭味相投”的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。

输入

第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)

输出

包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出“BeiJu”（即悲剧，^ ^）

样例输入

样例输出

#include <>

int b[ 222 ];

int a[ 222 ];

int n, m;

int main()

{

scanf("%d%d", &n, &m);

for(int i = 1; i <= n; i++ ){

scanf("%d", &a[ i ]);

b[ a[ i ] ]++;

}

for( int i = 1; i <= n; i++ ){

if( b[ a[ i ] ] == 1 )

printf("BeiJu\n");

else if( b[ a[ i ]] >= 2 )

printf("%d\n", b[ a[ i ]] - 1 );

}

return 0;

}

5、称体重

描述

赵、钱、孙、李四个人中既有大人也有小孩，给他们称体重时发现，他们每个人的体重都不一样，且体重（单位：公斤）恰好是10的整数倍，且他们的体重都不高于50公斤，已知赵、钱两人的

体重之和恰好等于孙、李两人的体重之和；赵、李两人的体重之和大于孙、钱两人的体重之和，并且赵、孙俩人的体重之和还小于钱的体重。请编写一个程序，按照体重从小到大的顺序，打印出四人的姓氏的首字母和体重数。

输入

无

输出

打印出四人的姓氏的首字母（小写）和体重数（每人一行，姓名首字母和体重数之间用空格隔开）。

样例输出

#include<>

int main(){

int a[4],b[4]={1,2,3,4},c[4]={'z','q','s','l'};

int i,j,t;

for(a[0]=1;a[0]<=5;a[0]++){

for(a[1]=1;a[1]<=5;a[1]++){

for(a[2]=1;a[2]<=5;a[2]++){

for(a[3]=1;a[3]<=5;a[3]++){

if((a[1]!=a[0]&&a[2]!=a[1]&&a[2]!=a[0]&&a[3]!=a[2]&&a[3]!=a[1]&&a[3]!=a[0]) &&(a[0]+a[1]==a[2]+a[3])&&(a[0]+a[3]>a[1]+a[2])&&(a[0]+a[2]

for(i=0;i<4;i++){

b[i]=a[i];

}

for(i=0;i<4;i++){

a[i]=b[i];

}

for(i=0;i<4;i++){

for(j=i+1;j<4;j++){

if(b[i]>b[j]){

t=b[i];

b[i]=b[j];

b[j]=t;

}

for(j=0;j<4;j++){

for(i=0;i<4;i++){

if(a[i]==b[j]){

printf("%c %d\n",c[i],b[j]*10);

}

getchar();

return 0;

}

6、比饭量

描述

3个人比饭量，每人说了两句话：

A说：B比我吃的多，C和我吃的一样多

B说：A比我吃的多，A也比C吃的多

C说：我比B吃得多，B比A吃的多。

事实上，饭量和正确断言的个数是反序的关系。请编程按饭量的大小输出3个人的顺序。

输入

无输入

输出

按照饭量大小输出3人顺序，比如：

ABC

样例输入

#include<>

int main(){

int A,B,C;

int a,b,c;

for(A=1;A<=3;A++){

for(B=1;B<=3;B++){

for(C=1;C<=3;C++){

a=((B>A)+(C==A));

b=((A>B)+(A>C));

c=((C>B)+(B>A));

if( ((A>B&&ab))

+ ((A>C&&ac))

+ ((Bc)||(B==C&&b==c)||(B>C&&b

if(a>b&&a>c){

if(b>c) printf("ABC");

else printf("ACB");

}

if(b>a&&b>c){

if(a>c) printf("BAC");

else printf("BCA");

}

if(c>a&&c>b){

if(a>b) printf("CAB");

else printf("CBA");

}

getchar();

return 0;

}

7、求排列的逆序数

描述

在Internet上的搜索引擎经常需要对信息进行比较，比如可以通过某个人对一些事物的排名来估计他（或她）对各种不同信息的兴趣，从而实现个性化的服务。

对于不同的排名结果可以用逆序来评价它们之间的差异。考虑1,2,…,n的排列i1，i2，…，i n，如果其中存在j,k，满足 j < k 且i j> i k，那么就称(i j,i k)是这个排列的一个逆序。

一个排列含有逆序的个数称为这个排列的逆序数。例如排列 263451 含有8个逆序

(2,1),(6,3),(6,4),(6,5),(6,1),(3,1),(4,1),(5,1)，因此该排列的逆序数就是8。显然，由

1,2,…,n 构成的所有n!个排列中，最小的逆序数是0，对应的排列就是1,2,…,n；最大的逆序数是n(n-1)/2，对应的排列就是n,(n-1),…,2,1。逆序数越大的排列与原始排列的差异度就越大。现给定1,2,…,n的一个排列，求它的逆序数。

输入

第一行是一个整数n，表示该排列有n个数（n <= 100000)。

第二行是n个不同的正整数，之间以空格隔开，表示该排列。

输出

输出该排列的逆序数。

样例输入

样例输出

提示

1. 利用二分归并排序算法（分治）；

2. 注意结果可能超过int的范围，需要用long long存储。

#include

using namespace std;

const int MAX_NUM = 100000 + 5;

long long seq[MAX_NUM];

int N;

long long ans;

void reSeq(long long* seq, int lef, int righ) {,&num[i].y);

}

int ans;

sort(num,num+t,cmp);

if(t%2==1)

{

ans=0;

int zong=num[t/2].y;

for(i=0;i

{

ans+=abs(num[i].y-zong);

}

else

{

int zong=num[t/2].y+num[t/2-1].y;

zong/=2;

ans=0;

for(i=0;i

{

ans+=abs(num[i].y-zong);

}

printf("%d\n",ans);

return 0;

}

12、0/1背包问题

描述

给定n种物品和一个背包，物品i(1≤i≤n)的重量是w i，其价值为v i，背包的容量为C，对每种物品只有两种选择：装入背包或者不装入背包。如何选择装入背包的物品，使得装入背包中物品的总价值最大

输入

输入包含一组或多组测试例。每组测试例的第一行是物品的数量n和背包的容量C，之后的n行是每个物品的重量及其价值。

输出

输出第一行是装入背包中物品的总价值，后面n行是各个物品装入背包的情况。

样例输入

样例输出

#include <>

#include

using namespace std;

int dp[110][1010];

int n, c, ans[110];

int w[110], v[110];

void print(){

int i, j, k;

k=c;

for(i=n; i>=1; i--){

if(dp[i][k]!=dp[i-1][k]){

ans[i]=1;

k=k-w[i];

}

else{

}

return;

}

int main(){

int i, j, k;

scanf("%d%d", &n, &c);

for(i=1; i<=n; i++){

scanf("%d%d", &w[i], &v[i]);

}

for(i=1; i<=n; i++){

for(j=1; j<=c; j++){

dp[i][j]=dp[i-1][j];

if(j>=w[i]){

dp[i][j]=max(dp[i-1][j-w[i]]+v[i], dp[i][j]);

}

printf("%d\n", dp[n][c]);

print();

for(i=1; i<=n; i++) {

printf("%d\n", ans[i]);

}

return 0;

}

13、最少硬币问题

描述

设有n种不同面值的硬币，各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。

输入

由文件提供输入数据，文件的第一行中只有1个整数给出n的值，第2行起每行2 个数，分别是T[j]和Coins[j]。最后1行是要找的钱数m。

输出

将计算出的最少硬币数输出到文件中。问题无解时输出-1。

样例输入

样例输出

提示

运用动态规划法进行算法设计并编程实现。源代码：

#include<>

#include

using namespace std;

int w[110], v[110];

int dp[110][20010];

int n, m;

void init(){

for(int i=0; i<110; i++){

for(int j=0; j<20010; j++){

}

int main(){

int i, j, k;

int t, x, cnt=1;

scanf("%d", &n);

for(i=1; i<=n; i++){

scanf("%d%d", &t, &x);

for(j=1; j<=x; j++){

w[cnt]=t;

v[cnt]=1;

cnt++;

}

scanf("%d", &m);

init();

for(i=0; i

.,An}，考察这n个矩阵的连乘积A1A2...An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。

矩阵连乘积的计算次序与其计算量有密切关系。例如，考察计算3个矩阵{A1,A2,A3}连乘积的例子。设这3个矩阵的维数分别为10*100，100*5，和5*50。若按(A1A2)A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50 = 7500。若按A1(A2A3)计算，则总共需要100*5*50+10*100*50 = 75000次数乘。

现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。

输入

输入数据由多组数据组成。每组数据格式如下：

第一行是一个整数n (1≤n≤26)，表示矩阵的个数。

接下来n行，每行有一个大写字母，表示矩阵的名字，后面有两个整数a,b，分别表示该矩阵的行数和列数，其中1

第n+1行是一个矩阵连乘的表达式，由括号与大写字母组成，没有乘号与多余的空格。如果表达式中没有括号则按照从左到右的顺序计算，输入的括号保证能够配对。

输出

对于每组数据，输出仅一行包含一个整数，即将该矩阵连乘方案需要的数乘次数。如果运算过程中出现不满足矩阵乘法法则的情况（即左矩阵列数与右矩阵的行数不同），则输出“error”。

样例输入

样例输出

# include <>

# include

# include <>

# include

using namespace std;

int n, ans;

string exp, str;

int x, y;

struct node{

int x,y;

};

node s[200];

int flage;

stack ope;

stack v;

string change(string t){

int length=();

string des="";

for(int i=0; i

if(isalpha(t[i])){

if(t[i+1]==')'){

des=des+t[i];

}

else{

des=des+t[i]+'*';

}

else if(t[i]=='('){

des=des+t[i];

}

else{

if(t[i+1]==')'){

des=des+t[i];

}

else{

des=des+t[i]+'*';

}

des=des+t[length-1]+'=';

return des;

}

node calc(node a, node b){

if!={

flage=1;

}

node t;

ans=ans+**;

=;=;

return t;

}

char compare(char i, char j){

if(i=='='){

if(j!='='){

return '<';

}

else{

return '=';

}

if(i=='('){

if(j==')'){

return '=';

}

else{

return '<';

}

if(i=='*'){

if(j=='('){

return '<';

}

else{

return '>';

}

int main(){

int i, j, k;

string e;

while(cin>>n){

for(i=1; i<=n; i++){

cin>>str>>x>>y;

s[str[0]].x=x;

s[str[0]].y=y;

算法设计与分析考试题及答案

算法设计与分析考试题及答案 Company number：【WTUT-WT88Y-W8BBGB-BWYTT-19998】

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显着特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X 和Y 的一个最长公共子序列{BABCD}或{CABCD}或{CADCD ｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法背包问题的回溯算法所需的计算时间为o(n*2n ) ,用动态规划算法所需的计算时间为o(min{nc,2n }) 9.动态规划算法的两个基本要素是最优子结构 _和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式； ③最优值的算法描述；④构造最优解； 2. 流水作业调度问题的johnson 算法的思想。 ①令N 1={i|a i =b i }；②将N 1中作业按a i 的非减序排序得到N 1’，将N 2中作业按b i 的非增序排序得到N 2’；③N 1’中作业接N 2’中作业就构成了满足Johnson 法则的最优调度。 3. 若n=4，在机器M1和M2上加工作业i 所需的时间分别为a i 和b i ，且 (a 1,a 2,a 3,a 4)=(4,5,12,10)，(b 1,b 2,b 3,b 4)=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2’={4，2}；最优值为：38 4. 使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。解空间树为：该问题的最优值为：16 最优解为：（1，1，0） 5. 设S=｛X 1，X 2，···，X n ｝是严格递增的有序集，利用二叉树的结点来存储S 中的元素，在表示S 的二叉搜索树中搜索一个元素X ，返回的结果有两种情形，（1）在二叉搜索树的内结点中找到X=X i ，其概率为b i 。（2）在二叉搜索树的叶结点中确定X ∈（X i ，X i+1），其概率为a i 。在表示S 的二叉搜索树T 中，设存储元素X i 的结点深度为C i ；叶结点（X i ，X i+1）的结点深度为d i ，则二叉搜索树T 的平均路长p 为多少假设二叉搜索树T[i][j]=｛X i ，X i+1，···，X j ｝最优值为m[i][j]，W[i][j]= a i-1+b i +···+b j +a j ，则m[i][j](1<=i<=j<=n)递归关系表达式为什么 .二叉树T 的平均路长P=∑=+n i 1 Ci)(1*bi +∑=n j 0 dj *aj

算法设计与分析考试题及答案

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算法的思想。

算法设计与分析实验报告

算法设计与分析课程实验项目目录学生姓名：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。本科实验报告专用纸

课程名称算法设计与分析成绩评定实验项目名称蛮力法指导教师实验项目编号 201 实验项目类型设计实验地点机房学生姓名学号学院信息科学技术学院数学系信息与计算科学专业级实验时间 2012年 3月 1 日～6月30日温度24℃ 1.实验目的和要求：熟悉蛮力法的设计思想。 2.实验原理和主要内容：实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。实验内容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人给出的： S END +MORE MONEY . 这里有两个前提假设：第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。 3.实验结果及分析：（将程序和实验结果粘贴，程序能够注释清楚更好。）本科实验报告专用纸(附页) 该算法程序代码如下：

#include "" #include "" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l

计算机算法设计与分析习题及答案

计算机算法设计与分析习题及答案 Prepared on 24 November 2020

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）是贪心算法与动态规划算法的共同点。

《算法设计与分析》考试题目及答案

《算法分析与设计》期末复习题一、选择题 1.应用Johnson法则的流水作业调度采用的算法是（D） A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上，并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正确的为：（B） " ; | A. void hanoi(int n, int A, int C, int B) 《 { if (n > 0) { hanoi(n-1,A,C, B); move(n,a,b); hanoi(n-1, C, B, A); B. void hanoi(int n, int A, int B, int C) { if (n > 0) { hanoi(n-1, A, C, B); ] move(n,a,b); hanoi(n-1, C, B, A); } C. void hanoi(int n, int C, int B, int A) { if (n > 0) { hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); } }

3. 动态规划算法的基本要素为（C ） A. 最优子结构性质与贪心选择性质 B ．重叠子问题性质与贪心选择性质 C ．最优子结构性质与重叠子问题性质 D. 预排序与递归调用 4. 算法分析中，记号O 表示（B ），记号Ω表示（A ），记号Θ表示（D ）。 … A.渐进下界 B.渐进上界 C.非紧上界 D.紧渐进界 E.非紧下界 5. 以下关于渐进记号的性质是正确的有：（A ） A.f (n)(g(n)),g(n)(h(n))f (n)(h(n))=Θ=Θ?=Θ B. f (n)O(g(n)),g(n)O(h(n))h(n)O(f (n))==?= C. O(f(n))+O(g(n)) = O(min{f(n),g(n)}) D. f (n)O(g(n))g(n)O(f (n))=?= D. void hanoi(int n, int C, int A, int B) { if (n > 0) { | hanoi(n-1, A, C, B); move(n,a,b); hanoi(n-1, C, B, A); }

《计算机算法设计与分析》习题及答案.doc

《计算机算法设计与分析》习题及答案一．选择题 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 ）是贪心算法与动态规划算法的共同点。

算法设计与分析课后习题

第一章 1. 算法分析题算法分析题1－1 求下列函数的渐进表达式 (1). 3n^2 + 10n < 3n^2 + 10n^2 = 13n^2 = O(n^2) (2). n^2 / 10 + 2^n 当n>5是，n^2 < 2 ^n 所以，当n >= 1时，n^2/10 < 2 ^n 故: n^2/10 + 2^n < 2 ^n + 2^n = 2*2^n = O(2^n) (3). 21 + 1/n < 21 + 1 = 22 = O(1) (4). log(n^3)=3log(n)=O(log(n)) (5). 10log(3^n) = (10log3)n = O(n) 算法分析题1-6 (1)因为：f(n)=log(n^2) = 2log(n); g(n) = log(n) + 5 所以：f(n)=Θ(log(n)+5) =Θ(g(n)) (2)因为：log(n) < √n; f(n) = 2log(n); g(n)=√n 所以：f(n) = O(g(n)) (3)因为：log(n) < n; f(n) = n; g(n) = log(n^2) = 2log(n) 所以；f(n) = Ω(g(n)) (4)因为：f(n) = nlogn +n; g(n) = logn 所以：f(n) =Ω(g(n)) (5)因为: f(n) = 10; g(n) = log(10) 所以:f(n) =Θ(g(n)) (6)因为: f(n)=log^2(n); g(n) = log(n) 所以: f(n) ==Ω(g(n)) (7)因为: f(n) = 2^n < 100*2^n; g(n)=100n^2; 2^n > n ^2 所以: f(n) = Ω(g(n)) (8)因为：f(n) = 2^n; g(n) = 3 ^n; 2 ^n < 3 ^n 所以: f(n) = O(g(n)) 习题1－9 证明：如果一个算法在平均情况下的计算时间复杂性为Θ(f(n)),该算法在最坏情况下所需的计算时间为Ω(f(n)). 分析与解答：因此，Tmax(N) = Ω(Tavg(N)) = Ω(Θ(f(n)))=Ω(f(n)). 第二章算法分析题

算法设计与分析习题与实验题(12.18)

《算法设计与分析》习题第一章引论习题1-1 写一个通用方法用于判定给定数组是否已排好序。解答： Algorithm compare(a,n) Begin J=1; While (j=a[j+1]) do j=j+1; If j=n then return true else return false end if End if end 习题1-2 写一个算法交换两个变量的值不使用第三个变量。解答：x=x+y; y=x-y; x=x-y; 习题1-3 已知m,n为自然数，其上限为k（由键盘输入，1<=k<=109）,找出满足条件(n2-mn-m2)2=1 且使n2+m2达到最大的m、n。解答： m:=k; flag:=0; repeat n:=m; repeat l:=n*n-m*n-m*n; if (l*l=1) then flag:=1 else n:=n-1; until (flag=1) or (n=0) if n=0 then m:=m-1 until (flag=1) or (m=0); 第二章基础知识

习题2-1 求下列函数的渐进表达式： 3n 2+10n ; n 2/10+2n ; 21+1/n ; log n 3; 10 log3n 。解答： 3n 2+10n=O （n 2）， n 2/10+2n =O （2n ）， 21+1/n=O （1）， log n 3=O （log n ），10 log3n =O （n ）。习题2-2 说明O (1)和 O (2)的区别。习题2-3 照渐进阶从低到高的顺序排列以下表达式：!n ， 3 /22 ,2,20,3,log ,4n n n n n 。解答：照渐进阶从低到高的顺序为：!n 、 3n 、 2 4n 、2 3n 、20n 、log n 、2 习题2-4 （1）假设某算法在输入规模为n 时的计算时间为n n T 23)(?=。在某台计算机上实现并完成该算法的时间为t 秒。现有另外一台计算机，其运行速度为第一台计算机的64倍，那么在这台新机器上用同一算法在t 秒内能解输入规模为多大的问题？（2）若上述算法的计算时间改进为2)(n n T =，其余条件不变，则在新机器上用 t 秒时间能解输入规模多大的问题？（3）若上述算法的计算时间进一步改进为8)(=n T ,其余条件不变，那么在新机器上用t 秒时间能解输入规模多大的问题？解答：（1）设新机器用同一算法在t 秒内能解输入规模为1n 的问题。因此有 64 /2 3231 n n t ?=?=，解得61+=n n 。（2） n n n n 8641221==>=。（3）由于=)(n T 常数，因此算法可解任意规模的问题。习题2-5 XYZ 公司宣称他们最新研制的微处理器运行速度为其竞争对手ABC 公司同类产品的100倍。对于计算复杂性分别为n ，2n ，3n 和!n 的各算法，若用ABC 公司的计算机能在1小时内能解输入规模为n 的问题，那么用XYZ 公司的计算机在1小时内分别能解输入规模为多大的问题？

《算法设计与分析》实验指导

《算法分析与设计》实验指导.

实验一锦标赛问题 [实验目的] 1.基本掌握分治算法的原理. 2.能用程序设计语言求解锦标赛等问题的算法; [预习要求] 1.认真阅读数据结构教材和算法设计教材,了解分治算法原理; 2.设计用分治算法求解背包问题的数据结构与程序代码. [实验题] 【问题描述】设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其他n-1个选手各赛一次；（2）每个选手一天只能参赛一次；（3）循环赛在n-1天内结束。请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行，第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n，1≤j≤n-1。 [实验提示] 我们可以按分治策略将所有的选手分为两半，则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分，直到只剩下两个选手时，比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。 1 2 3 4 5 6 7 1 （1）（2）（3）图1 2个、4个和8个选手的比赛日程表图1所列出的正方形表（3）是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此，将左上角小块中的所有数字按其相对位置抄到右下角，又将左下角小块中的所有数字按其相对位置抄到右上角，这

样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。 [实验步骤] 1.设计并实现算法并准备测试用例,修改并调试程序,直至正确为止; 2.应用设计的算法和程序求锦标赛问题; 3.去掉测试程序,将你的程序整理成功能模块存盘备用. [实验报告要求] 1.阐述实验目的和实验内容; 2.阐述分治算法原理; 3.提交实验程序的功能模块; 4.记录最终测试数据和测试结果。 [思考与练习] 【金块问题】老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，请用最少的比较次数找出最重和最轻的金块。

算法设计与分析实验(第2、3章)

暨南大学本科实验报告专用纸课程名称算法设计与分析成绩评定实验项目名称分治策略与动态规划指导教师李展实验项目编号01 实验项目类型设计类实验地点南海楼6楼学生姓名陈奕豪学号2012051351 学院信息科学技术学院系计算机系专业软件工程实验时间年月日一、实验目的：本实验涉及用分治策略和动态规划算法来求解优化组合问题。通过上机实验使学员学会程序的录入和调试；通过实验结果的比较，使学员了解两种算法的主要特点。二、实验内容：第二章实验题必做——算法分析题1: 线性时间选择问题 ●问题描述给定线性序集中n个元素和一个整数k, 1≤k≤n, 要求找出这n个元素中第k小的元素 ●主要思路及步骤 1.把a数组中元素分为5个一组,选每组中位数后分别将他们移向数组头,再用同样的方法选取中位数的中位数x,然后按x把a数组分为两个划分,重复上述过程直至划分中元素个数少于75,返回要求值 ●算法描述

Type Select(Type a[], int p, int r, int k) { if (r-p<75) { 用某个简单排序算法对数组a[p:r]排序; return a[p+k-1]; }; for ( int i = 0; i<=(r-p-4)/5; i++ ) 将a[p+5*i]至a[p+5*i+4]的第3小元素与a[p+i]交换位置; //找中位数的中位数，r-p-4即上面所说的n-5 Type x = Select(a, p, p+(r-p-4)/5, (r-p+6)/10); int i=Partition(a,p,r, x), j=i-p+1; if (k<=j) return Select(a,p,i,k); else return Select(a,i+1,r,k-j); } 输入和输出自行设计数组a的元素的值，要求元素个数不少于80个，并实现以下输出：（1）输出数组a中下标范围从p到p+(r-p-4)/5的元素；（2）输出x的值，判断x是否为数组a中下标范围从p到p+(r-p-4)/5的拟中位数；（3）输出数组a中下标范围从p到r的元素，验证其是否为以x为基准元素的划分。源代码：: #include #include #include void S *i,int *j){ int a; a=*i;

《算法设计与分析》实验报告快速排序

《算法分析与设计》实验报告题目：快速排序姓名：于文静班级：计科F1203 学号： 0230 指导教师：靳小波完成时间： 2015-04-06

一、实验题目用递归分治法编写Hoare快速排序算法二、实验目的 1. 理解时间复杂度的概念。 2. 深入地掌握C语言编程。 3. 通过编程直观地理解算法分析的意义三、实验要求请使用递归分治法编写Hoare快速排序算法，算法的输入如下：7.30 7.15 4.27 2.14 6.29 3.99 0.26 9.10 1.89 2.86 0.44 5.52 4.35 4.39 6.70 9.82 3.55 2.38 9.12 3.54 1.30 5.20 6.59 9.08 1.79 3.52 4.06 0.43 5.31 7.19 6.07 7.06 9.92 7.79 3.46 6.16 1.83 2.78 3.20 2.95 9.20 0.22 7.13 8.28 5.58 0.80 2.63 7.44 3.04 8.58 9.61 4.52 2.12 1.73 4.16 3.66 2.36 4.08 9.36 8.03 4.92 4.90 9.59 9.83 7.85 3.99 2.68 2.49 4.69 7.67 7.56 8.85 3.88 7.74 6.27 5.48 7.29 2.81 3.67 2.52 1.95 1.82 4.38 4.42 5.54 4.41 1.94 0.31 8.41 5.69 4.59 四、程序流程图

五、 #include int Partition(double a[],int low,int high){ int i,j; double temp; i=low; j=high; while(i

算法设计与分析+习题参考答案

5..证明等式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

D←b*b-4*a*c If D>0 temp←2*a x1←(-b+sqrt(D))/temp x2←(-b-sqrt(D))/temp return x1,x2 else if D=0 return –b/(2*a) else return “no real roots” else //a=0 if b≠0 return –c/b else //a=b=0 if 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=1 while 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、用计算机求解问题的步骤： 1、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构算法具有以下5个属性：有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。算法设计的质量指标：正确性：算法应满足具体问题的需求；可读性：算法应该好读，以有利于读者对程序的理解；健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法迭代法基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。编写计算斐波那契（Fibonacci）数列的第n项函数fib（n）。写成递归函数有： int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 一个饲养场引进一只刚出生的新品种兔子，这种兔子从出生的下一个月开始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去，问到第12 个月时，该饲养场共有兔子多少只？ Main() {int I,a=1,b=1; Print(a,b); For(i=1;i<=10;i++) { C=a+b; Print(c); A=b; B=c; } } 分而治之法 1、基本思想将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。分治法所能解决的问题一般具有以下几个特征：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

算法设计与分析复习题目及答案复习过程

分治法 1、二分搜索算法是利用（分治策略）实现的算法。 9. 实现循环赛日程表利用的算法是（分治策略） 27、Strassen矩阵乘法是利用（分治策略）实现的算法。 34．实现合并排序利用的算法是（分治策略）。实现大整数的乘法是利用的算法（分治策略）。 17．实现棋盘覆盖算法利用的算法是（分治法）。 29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。不可以使用分治法求解的是（0/1背包问题）。动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。矩阵连乘问题的算法可由（动态规划算法B）设计实现。实现最大子段和利用的算法是（动态规划法）。贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）

分支限界法最大效益优先是（分支界限法）的一搜索方式。分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法). 从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式. （1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。（最优子结构性质）是贪心算法与动态规划算法的共同点。贪心算法与动态规划算法的主要区别是（贪心选择性质）。回溯算法和分支限界法的问题的解空间树不会是( 无序树). 14．哈弗曼编码的贪心算法所需的计算时间为（ B ）。 A、O（n2n） B、O（nlogn） C、O（2n） D、O（n） 21、下面关于NP问题说法正确的是（B ） A NP问题都是不可能解决的问题 B P类问题包含在NP类问题中 C NP完全问题是P类问题的子集 D NP类问题包含在P类问题中 40、背包问题的贪心算法所需的计算时间为（ B ）

算法设计与分析习题

第一章算法引论 1、算法的定义？答：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。通俗讲，算法：就是解决问题的方法或过程。 2、算法的特征？答：1)算法有零个或多个输入；２)算法有一个或多个输出； 3)确定性；４)有穷性 3、算法的描述方法有几种？答：自然语言、图形、伪代码、计算机程序设计语言 4、衡量算法的优劣从哪几个方面？答：(1) 算法实现所耗费的时间（时间复杂度）； (2) 算法实现所所耗费的存储空间（空间复杂度）； (3) 算法应易于理解，易于编码，易于调试等等。 5、时间复杂度、空间复杂度定义？答：指的是算法在运行过程中所需要的资源（时间、空间）多少。 6、时间复杂度计算： {i=1； while（i<=n） i=i*2； } 答：语句①执行次数1次，语句②③执行次数f(n), 2^f(n)<=n,则f(n) <=log2n; 算法执行时间： T(n)= 2log2n +1 时间复杂度：记为O(log2n) ； 7.递归算法的特点？

答：①每个递归函数都必须有非递归定义的初值；否则，递归函数无法计算；（递归终止条件） ②递归中用较小自变量函数值来表达较大自变量函数值；（递归方程式） 8、算法设计中常用的算法设计策略？答：①蛮力法；②倒推法；③循环与递归；④分治法； ⑤动态规划法；⑥贪心法；⑦回溯法；⑧分治限界法 9、设计算法：递归法：汉诺塔问题？兔子序列（上楼梯问题）？整数划分问题？蛮力法：百鸡百钱问题？倒推法：穿越沙漠问题？答：算法如下：（1）递归法汉诺塔问题 void hanoi(int n, int a, int b, int c) {if (n > 0) { hanoi(n-1, a, c, b); move(a,b); hanoi(n-1, c, b, a); } } 兔子序列（fibonaci数列）递归实现： Int F(int n) {

算法设计与分析考试题及答案

一、填空题（20分） 1.一个算法就是一个有穷规则的集合，其中之规则规定了解决某一特殊类型问题的一系列运算，此外，算法还应具有以下五个重要特性:确定性有穷性可行性 0个或多个输入一个或多个输出 2.算法的复杂性有时间复杂性空间复杂性之分，衡量一个算法好坏的标准是时间复杂度高低 3.某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质 4.若序列X={B,C,A,D,B,C,D}，Y={A,C,B,A,B,D,C,D}，请给出序列X和Y的一个最长公共子序列{BABCD}或{CABCD}或{CADCD｝ 5.用回溯法解问题时，应明确定义问题的解空间，问题的解空间至少应包含一个（最优）解 6.动态规划算法的基本思想是将待求解问题分解成若干_子问题，先求解_子问题，然后从这些子问题的解得到原问题的解。 7.以深度优先方式系统搜索问题解的算法称为回溯法 8.0-1背包问题的回溯算法所需的计算时间为o(n*2n) ,用动态规划算法所需的计算时间为o(min{nc,2n}) 9.动态规划算法的两个基本要素是最优子结构_和重叠子问题 10.二分搜索算法是利用动态规划法实现的算法。二、综合题（50分） 1.写出设计动态规划算法的主要步骤。 ①问题具有最优子结构性质；②构造最优值的递归关系表达式；③最优值的算法描述；④构造最优解； 2.流水作业调度问题的johnson算法的思想。 ①令N 1={i|a i =b i }；②将N 1 中作业按a i 的非减序排序得到N 1 ’，将N 2 中作业按b i 的非增序排序得到N 2’；③N 1 ’中作业接N 2 ’中作业就构成了满足Johnson法则的最优调度。 3.若n=4，在机器M1和M2上加工作业i所需的时间分别为a i 和b i ，且(a 1 ,a 2 ,a 3 ,a 4 )=(4,5,12,10)， (b 1,b 2 ,b 3 ,b 4 )=(8,2,15,9)求4个作业的最优调度方案，并计算最优值。步骤为：N1={1，3}，N2={2，4}； N 1’={1，3}， N 2 ’={4，2}；最优值为：38 4.使用回溯法解0/1背包问题：n=3，C=9，V={6,10,3}，W={3,4,4},其解空间有长度为3的0-1向量组成，要求用一棵完全二叉树表示其解空间（从根出发，左1右0），并画出其解空间树，计算其最优值及最优解。解空间为{(0,0,0),(0,1,0),(0,0,1),(1,0,0),(0,1,1),(1,0,1), (1,1,0),(1,1,1)}。解空间树为：该问题的最优值为：16 最优解为：（1，1，0）

相关主题

算法设计与分析上机题

文本预览

相关文档

算法设计与分析考试题目及答案

西安电子科技大学《算法设计与分析》随课上机作业题

算法设计与分析习题与实验题(12.18)

(完整版)算法设计与分析期末试题_考试版

算法设计与分析复习题目及答案.docx

《算法设计与分析》- 课内上机实验题目及其解答

《计算机算法设计与分析》习题及答案.doc

算法设计与分析实验(第2、3章)

最新算法设计与分析实验报告

计算机算法设计与分析习题及答案

算法设计与分析实验报告

算法设计与分析习题与实验题(12.18)

西安电子科技大学《算法设计与分析》随课上机作业题

算法设计与分析+习题参考答案

算法设计与分析考试题及答案

算法设计与分析考试题及答案

《算法设计与分析》考试题目及答案

《算法设计与分析》实验指导

算法设计与分析复习题目及答案复习过程

算法设计与分析习题答案1-6章

最新文档

幼儿园小班科学《小动物过冬》PPT课件教案

2021年春新青岛版(五四制)科学四年级下册 20.《露和霜》教学课件

自然教育课件

小学语文优质课火烧云教材分析及课件

(超详)高中语文知识点归纳汇总

高中语文基础知识点总结(5篇)

高中语文基础知识点总结(最新)

高中语文知识点整理总结

高中语文知识点归纳

高中语文基础知识点总结大全

超详细的高中语文知识点归纳

高考语文知识点总结高中

高中语文知识点总结归纳

高中语文知识点整理总结

高中语文知识点归纳

高中语文知识点归纳(大全)

高中语文知识点总结归纳(汇总8篇)

高中语文基础知识点整理

化工厂应急预案

化工消防应急预案(精选8篇)