《算法分析与设计》作业（一）本课程作业由两部分组成。

第一部分为“客观题部分”，由15个选择题组成，每题1分，共15分。

第二部分为“主观题部分”，由简答题和论述题组成，共15分。

作业总分30分，将作为平时成绩记入课程总成绩。

客观题部分：一、选择题（每题1分，共15题）1、递归算法：（C ）A、直接调用自身B、间接调用自身C、直接或间接调用自身D、不调用自身2、分治法的基本思想是将一个规模为n的问题分解为k个规模较小的字问题，这些子问题：（D ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同3、备忘录方法的递归方式是：（C ）A、自顶向下B、自底向上C、和动态规划算法相同D、非递归的4、回溯法的求解目标是找出解空间中满足约束条件的：（A ）A、所有解B、一些解C、极大解D、极小解5、贪心算法和动态规划算法共有特点是：（ A ）A、最优子结构B、重叠子问题C、贪心选择D、形函数6、哈夫曼编码是：（B）A、定长编码B、变长编码C、随机编码D、定长或变长编码7、多机调度的贪心策略是：（A）A、最长处理时间作业优先B、最短处理时间作业优先C、随机调度D、最优调度8、程序可以不满足如下性质：（D ）A、零个或多个外部输入B、至少一个输出C、指令的确定性D、指令的有限性9、用分治法设计出的程序一般是：（A ）A、递归算法B、动态规划算法C、贪心算法D、回溯法10、采用动态规划算法分解得到的子问题：（ C ）A、相互独立B、与原问题相同C、相互依赖D、相互独立且与原问题相同11、回溯法搜索解空间的方法是：（A ）A、深度优先B、广度优先C、最小耗费优先D、随机搜索12、拉斯维加斯算法的一个显著特征是它所做的随机选性决策有可能导致算法：（ C ）A、所需时间变化B、一定找到解C、找不到所需的解D、性能变差13、贪心算法能得到：（C ）A、全局最优解B、0-1背包问题的解C、背包问题的解D、无解14、能求解单源最短路径问题的算法是：（A ）A、分支限界法B、动态规划C、线形规划D、蒙特卡罗算法15、快速排序算法和线性时间选择算法的随机化版本是：（ A ）A、舍伍德算法B、蒙特卡罗算法C、拉斯维加斯算法D、数值随机化算法主观题部分：二、写出下列程序的答案（每题2.5分，共2题）1、请写出批处理作业调度的回溯算法。

#include<iostream>#include<algorithm>using namespace std;class Flowing{friend int Flow(int ** ,int ,int []);private://int Bound(int i);void Backtrack(int t);int **M;//int *x;//当前解int *bestx;//int *f2;//int f1;//int f;//int bestf;//int n;//};void Flowing::Backtrack(int i){if(i>n){for(int j=1;j<=n;j++)bestx[j]=x[j];bestf=f;}elsefor(int j=i;j<=n;j++){f1+=M[x[j]][1];f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];f+=f2[i];if(f<bestf){swap(x[i],x[j]);Backtrack(i+1);swap(x[i],x[j]);}f1-=M[x[j]][1];f-=f2[i];}}int Flow(int ** M,int n,int bestx[]){int ub=INT_MAX;Flowing X;X.x=new int[n+1];X.f2=new int[n+1];X.M=M;X.n=n;X.bestx=bestx;X.bestf=ub;X.f1=0;X.f=0;for(int i=0;i<=n;i++)X.f2[i]=0,X.x[i]=i;X.Backtrack(1);delete[] X.x;delete[] X.f2;return X.bestf;}void main(){int **M;int n;int *bestx;cout<<"请输入作业数:";cin>>n;M=new int *[n+1];cout<<"请输入各作业处理时间:"<<endl;for(int i=1;i<=n;i++)M[i]=new int[2];for(int k=1;k<=n;k++)for(int j=1;j<3;j++)cin>>M[k][j];bestx=new int[n+1];for(i=1;i<=n;i++)bestx[i]=0;cout<<"最优完成时间:"<<Flow(M,n,bestx)<<endl;cout<<"最优方案:";for(i=1;i<=n;i++)cout<<"作业"<<bestx[i]<<" ";cout<<endl;}2、函数渐进阶对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或f(n)= ))((n g Ω或f(n)=))((n g θ，并简述理由。

(1) f(n)=logn 2; g(n)=logn+5;f(n)与g(n)同阶，f(n)=))((n g θ(2) f(n)=logn 2; g(n)=n ;当n>=8时，f(n)<=g(n)，故f(n)=O(g(n))分析：此类题目不易直接看出阶的高低，可用几个数字代入观察结果。

如依次用n=1,21, 22, 23, 26, 28, 210(3) f(n)=n; g(n)=log 2n;f(n)= ))((n g Ω(4) f(n)=nlogn+n; g(n)=logn;f(n)= ))((n g Ω(5) f(n)=10; g(n)=log10;f(n)=))((n g θ(6) f(n)= log 2n; g(n)=logn;f(n)= ))((n g Ω(7) f(n)=2n ; g(n)=100n 2;f(n)= ))((n g Ω(8) f(n) =2n ; g(n)=3n ;f(n)=O(g(n))三、写出下列题目的程序（每题5分，共2题）1、请写出背包问题的贪心算法。

procedure GREEDY-KNAPSACK(P，W，M，X，n)X←0 //将解向量初始化为零//cu←M //cu是背包剩余容量//for i←1 to n doif W(i) ≤cu then exit endifX(i) ← 1 ；cu←cu-W(i) ；repeat ；if i≤n then X(i) ←cu/ W(i) ；endifend GREEDY-KNAPSACK2、字符串比较问题问题描述：对于长度相同的2个字符串A和B，其距离定义为相应位置字符距离之和。

2个非空格字符的距离是它们的ASCII码之差的绝对值。

空格与空格的距离为0，空格与其它字符的距离为一定值k。

在一般情况下，字符串A和B的长度不一定相同。

字符串A的扩展是在A中插入若干空格字符所产生的字符串。

在字符串A和B的所有长度相同的扩展中，有一对距离最小的扩展，该距离称为字符串A和B的扩展距离。

对于给定的字符串A和B，试设计一个算法，计算其扩展距离。

编程任务：对于给定的字符串A和B，编程计算其扩展距离。

数据输入：由文件input.txt给出输入数据。

第1行是字符串A，第2行是字符串B，第3行是空格与其它字符的距离定值k。

结果输出：将计算出的字符串A和B的扩展距离输出到文件output.txt。

输入文件示例输出文件示例input.txt output.txtcmc 10snmn2解答：设字符串A和B的字串A[1...i]和B[1...j]的扩展距离是val(i, j)；依题意，字符串A和B有三种可能的情况：1）A串最后一个字符是空格，B串最后一个字符是字母，则val(i, j) = val(i-1, j) + k；2）A串最后一个字符时字母，B串最后一个字符时空格，则val(i, j) = val(i, j-1) + k；3）A串和B串最后一个字符均是字母，则val(i, j) = val(i-1, j-1) + dist(ai , bi)；由上可知，val(i, j)具有最优子结构性质，且满足如下递推式：val(i, j) = min{ val(i-1, j) + k，val(i, j) + k，val(i-1, j-1) + dist(ai , bi) }（使用动态规划算法，自底向上的计算各个子问题并利用每次计算的结果，避免重复运算，从而降低算法复杂度。

）从动态规划递归式可知，算法的时间复杂度为O（mn），m和n分别是字符串A和B的长度。

代码如下：#include <iostream>#include <cmath>#define MAX 100000 //标识最大的可能整数int val[300][300];std::string stra; //字符串Astd::string strb; //字符串Bint k; //定值k//返回字符a与b的ASCII码的差的绝对值int dist(char a, char b){return abs(a-b);}int comp(){int len1, len2;int tmp;val[0][0] = 0;len1 = stra.length();len2 = strb.length();for(int i=0; i<=len1; i++) //字符串A和B的有效下标是º1~len,下标0表示空字符串{ //i或j是0表示A或B串为空串for(int j=0; j<=len2; j++){if(i+j)//i和j至少一个大于0{val[i][j] = MAX;tmp = val[i-1][j] + k;if(i && (tmp<val[i][j]))//i大于0val[i][j] = tmp;tmp = val[i][j-1]+k;if(j && (tmp<val[i][j]))//j大于0val[i][j] = tmp;tmp = val[i-1][j-1] + dist(stra[i], strb[j]);if((i*j) && (tmp<val[i][j])) //i和j至少有一个不为0val[i][j] = tmp;}}}return val[len1][len2];}int main(){std::cin>>stra>>strb>>k;stra = " " + stra; //此处在字符串开头添加一个空格，是为了使字符串strastrb = " " + strb; //的控制台输入的有效字符下标从1到stra.length()std::cout<<comp()<<std::endl;system("pause");return 0;}售后组投身消毒售后无畏，西装革履精心准备。