习题1
1.
图论诞生于七桥问题。出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现
在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，
图 1.7是这条河以及河上的两个岛和七座桥的
草图。请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。 输入：一个起点 输出：相同的点 1， 一次步行
2， 经过七座桥，且每次只经历过一次 3， 回到起点
该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。另一类是只有二个奇点的图形。
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。请用伪代码描述这个版本的欧几里德算法 1.r=m-n
2.循环直到r=0 2.1 m=n 2.2 n=r 2.3 r=m-n 3 输出m
3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C ++描述。
//采用分治法
//对数组先进行快速排序 //在依次比较相邻的差 #include
int partions(int b[],int low,int high) {
图1.7 七桥问题
int prvotkey=b[low];
b[0]=b[low];
while (low { while (low --high; b[low]=b[high]; while (low ++low; b[high]=b[low]; } b[low]=b[0]; return low; } void qsort(int l[],int low,int high) { int prvotloc; if(low { prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴 qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序由 prvotloc+1到 high } } void quicksort(int l[],int n) { qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个 } int main() { int a[11]={0,2,32,43,23,45,36,57,14,27,39}; int value=0;//将最小差的值赋值给value for (int b=1;b<11;b++) cout< cout< quicksort(a,11); for(int i=0;i!=9;++i) { if( (a[i+1]-a[i])<=(a[i+2]-a[i+1]) ) value=a[i+1]-a[i]; else value=a[i+2]-a[i+1]; } cout< return 0; } 4．设数组a[n]中的元素均不相等，设计算法找出a[n]中一个既不是最大也不是最小的元素，并说明最坏情况下的比较次数。要求分别给出伪代码和C++描述。 #include using namespace std; int main() { int a[]={1,2,3,6,4,9,0}; int mid_value=0;//将“既不是最大也不是最小的元素”的值赋值给它 for(int i=0;i!=4;++i) { if(a[i+1]>a[i]&&a[i+1] { mid_value=a[i+1]; cout< break; } else if(a[i+1] { mid_value=a[i+1]; cout< break; } }//for return 0; } 5. 编写程序，求n至少为多大时，n个“1”组成的整数能被2013整除。 #include using namespace std; int main() { double value=0; for(int n=1;n<=10000 ;++n) { value=value*10+1; if(value%2013==0) { cout<<"n至少为:"< break; } }//for return 0; } 6. 计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值 #include using namespace std; int main () { double a,b; double arctan(double x);//声明 a = 16.0*arctan(1/5.0); b = 4.0*arctan(1/239); cout << "PI=" << a-b << endl; return 0； } double arctan(double x) { int i=0; double r=0,e,f,sqr;//定义四个变量初 sqr = x*x; e = x; while (e/i>1e-15)//定义精度范围 { f = e/i;//f是每次r需要叠加的方程 r = (i%4==1)?r+f:r-f; e = e*sqr;//e每次乘于x的平方 i+=2;//i每次加2 }//while return r; } 7. 圣经上说：神6天创造天地万有，第7日安歇。为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。例如，6=1+2+3，因此6是完美数。神6天创造世界，暗示着该创造是完美的。设计算法，判断给定的自然数是否是完美数 #include using namespace std; int main() { int value, k=1; cin>>value; for (int i = 2;i!=value;++i) { while (value % i == 0 ) { k+=i;//k为该自然数所有因子之和 value = value/ i; } }//for if(k==value) cout<<"该自然数是完美数"< else cout<<"该自然数不是完美数"< return 0; } 8.有4个人打算过桥，这个桥每次最多只能有两个人同时通过。他们都在桥的某一端，并且是在晚上，过桥需要一只手电筒，而他们只有一只手电筒。这就意味着两个人过桥后必须有一个人将手电筒带回来。每个人走路的速度是不同的：甲过桥要用1分钟，乙过桥要用2分钟，丙过桥要用5分钟，丁过桥要用10分钟，显然，两个人走路的速度等于其中较慢那个人的速度，问题是他们全部过桥最少要用多长时间？ 由于甲过桥时间最短，那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如： 第一趟：甲，乙过桥且甲回来 第二趟：甲，丙过桥且甲回来 第一趟：甲，丁过桥 一共用时19小时 9．欧几里德游戏：开始的时候，白板上有两个不相等的正整数，两个玩家交替行动，每次行动时，当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差，而且这个数字必须是新的，也就是说，和白板上的任何一个已有的数字都不相同，当一方再也写不出新数字时，他就输了。请问，你是选择先行动还是后行动？为什么？ 设最初两个数较大的为a, 较小的为b，两个数的最大公约数为factor。 则最终能出现的数包括: factor, factor*2, factor*3, ..., factor*(a/factor)=a. 一共a/factor个。 如果a/factor 是奇数，就选择先行动；否则就后行动。 习题4 1.分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O(n)。 O(N)=2*O(N/2)+x O(N)+x=2*O(N/2)+2*x a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知，时间复杂度可达到O(n); 3.分治策略一定导致递归吗？如果是，请解释原因。如果不是，给出一个不包含递归的分治例子，并阐述这种分治和包含递归的分治的主要不同。 不一定导致递归。 如非递归的二叉树中序遍历。 这种分治方法与递归的二叉树中序遍历主要区别是：应用了栈这个数据结构。 4. 对于待排序序列(5, 3, 1, 9)，分别画出归并排序和快速排序的递归运行轨迹。 归并排序： 第一趟：（5,3）（1,9）； 第二趟：（3,5,1,9）； 第三趟：（1,3,5,9）； 快速排序： 第一趟：5（,3,1,9）；//5为哨兵，比较9和5 第二趟：5（1,3, ,9）；//比较1和5，将1挪到相应位置； 第三趟：5（1,3, ,9）;//比较3和5； 第四趟：（1,3,5,9）; 5. 设计分治算法求一个数组中的最大元素，并分析时间性能。 //简单的分治问题 //将数组均衡的分为“前”，“后”两部分 //分别求出这两部分最大值，然后再比较这两个最大值 #include using namespace std; extern const int n=6;//声明 int main() { int a[n]={0,6,1,2,3,5};//初始化 int mid=n/2; int num_max1=0,num_max2=0; for(int i=0;i<=n/2;++i)//前半部分 { if(a[i]>num_max1) num_max1=a[i]; } for(int j=n/2+1;j { if(a[j]>num_max2) num_max2=a[j]; } if(num_max1>=num_max2) cout<<"数组中的最大元素："< else cout<<"数组中的最大元素："< return 0; } 时间复杂度：O（n） 6. 设计分治算法，实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n)，空间复杂性为O(1)。例如，对abcdefgh循环左移3位得到defghabc。 //采用分治法 //将数组分为0-k-1和k-n-1两块 //将这两块分别左移 //然后再合并左移 #include using namespace std; void LeftReverse(char *a, int begin, int end) { for(int i=0;i<(end-begin+1)/2;i++)//交换移动 { int temp=a[begin+i]; a[begin+i]=a[end-i]; a[end-i]=temp; } } void Converse(char *a,int n,int k) { LeftReverse(a, 0, k-1); LeftReverse(a, k, n-1); LeftReverse(a, 0, n-1); for(int i=0;i cout< cout< } int main() { char a[7]={'a','b','c','d','e','f','g'}; Converse(a,7,3); return 0; } 7. 设计递归算法生成n个元素的所有排列对象。 #include using namespace std; int data[100]; //在m个数中输出n个排列数（n<=m） void DPpl(int num,int m,int n,int depth) { if(depth==n) { for(int i=0;i cout< cout< } for(int j=0;j { if((num&(1< { data[depth]=j+1; DPpl(num+(1< } }//for } int main() { DPpl(0,5,1,0); DPpl(0,5,2,0); DPpl(0,5,3,0); DPpl(0,5,4,0); DPpl(0,5,5,0); return 0; } 8. 设计分治算法求解一维空间上n个点的最近对问题。 参见4.4.1最近对问题的算法分析及算法实现 9. 在有序序列(r1, r2, …, r n)中，存在序号i（1≤i≤n），使得r i=i。请设计一个分治算法找到这个元素，要求算法在最坏情况下的时间性能为O(log2n)。 //在有序数组中 //采用二分法查找符合条件的元素 #include using namespace std; void Findnum(int *a,int n) { int low=0; int high=n-1; while(low<=high) { int mid=(low+high)/2; if(a[mid]==mid) { cout<<"这个数是："< break; } else if(a[mid]>mid) high=mid-1; else low=mid+1; } } int main() { int a[7]={1,0,2,5,6,7,9}; Findnum(a,7); return 0; } 时间复杂度为O(log2n)。 10. 在一个序列中出现次数最多的元素称为众数。请设计算法寻找众数并分析算法的时间复杂性。 //先对序列进行快速排序 //再进行一次遍历 //输出众数的重复次数 #include using namespace std; int partions(int b[],int low,int high) { int prvotkey=b[low]; b[0]=b[low]; while (low { while (low --high; b[low]=b[high]; while (low ++low; b[high]=b[low]; } b[low]=b[0]; return low; } void qsort(int l[],int low,int high) { int prvotloc; if(low { prvotloc=partions(l,low,high); //将第一次排序的结果作为枢轴qsort(l,low,prvotloc-1); //递归调用排序由low 到prvotloc-1 qsort(l,prvotloc+1,high); //递归调用排序由prvotloc+1到high } } void quicksort(int l[],int n) { qsort(l,1,n); //第一个作为枢轴，从第一个排到第n个 } int main() { int a[10]={1,2,3,5,3,3,3,2,5,1}; int i=0; int count=0; int max=0;//max表示出现的次数 qsort(a,0,10); while(i<10) { int j; j=i+1; if(a[i]=a[j]&&i<10) { count++; i++; } if(count>max) { max=count; count=0; } }//while cout<<"重复次数："< return 0; } 时间复杂度nlog(n) 11. 设M是一个n×n的整数矩阵，其中每一行（从左到右）和每一列（从上到下）的元素都按升序排列。设计分治算法确定一个给定的整数x是否在M中，并分析算法的时间复杂性。 12. 设S是n（n为偶数）个不等的正整数的集合，要求将集合S划分为子集S1和S2，使得| S1|=| S2|=n/2，且两个子集元素之和的差达到最大。 //先用快速排序进行一趟排序 //如果s1（大的数集）的的个数大于n/2 //将（i<=n/2-low-1）个最小的数排到后面 //如果s1（大的数集）的的个数小于n/2 //将s2（小的数集）n/2-low-1排到前面 //将排好的数组的前n/2个数赋值给s1 //将排好的数组的后n/2个数赋值给s2 #include using namespace std; const int n=8; void partions(int a[],int low,int high) { //进行一趟快排 int prvotkey=a[low]; a[0]=a[low]; while (low { while (low --high; a[low]=a[high]; while (low ++low; a[high]=a[low]; } a[low]=prvotkey; //如果s1（大的数集）的的个数大于n/2 if(low>=n/2) { for(int i=0;i<=n/2-low-1;++i) { for(int j=0;j { if(a[j] { int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } }//for } }//if //如果s1（大的数集）的的个数小于n/2 else for(int i=0;i<=n/2-low-1;++i) { for(int k=n-1;k { if(a[k]>a[k-1]) { int temp1=a[k]; a[k]=a[k-1]; a[k-1]=temp1; } }//for } } int main() { int a[n]={1,3,5,9,6,0,-11,-8}; partions(a,0,n-1); for(int i=0;i { if(i<4) { cout<<"属于子集s1的："< cout< } else { cout<<"属于子集s2的："< cout< } } return 0; } 13. 设a1, a2,…, a n是集合{1, 2, …, n}的一个排列，如果i //用归并进行排序 //当一个子集的一个数大于第二个子集的一个数，为逆序，即a[i]>a[j] //则逆序数为end-j+1; #include using namespace std; int count; void Merge(int a[],int a1[],int begin,int mid,int end)//合并子序列 { int i=begin,j=mid+1,k=end; while(i<=mid&&j<=end) { if(a[i]<=a[j]) a1[k++]=a[i++];//取a[i]和a[j]中较小者放入r1[k] else { a1[k++]=a[j++]; count+=(end-j+1); } } while(i<=mid) a1[k++]=a[i++]; while(j<=end) a1[k++]=a[j++]; } void MergeSort(int a[ ], int begin, int end) { int mid,a1[1000]; if(begin==end) return ; else { mid=(begin+end)/2; MergeSort(a,begin,mid); MergeSort(a,mid+1,end); Merge(a,a1,begin,mid,end); } } int main() { int a[6]={6,5,4,3,2,1}; count=0; MergeSort(a,0,6); cout< return 0; } 14. 循环赛日程安排问题。设有n=2k个选手要进行网球循环赛，要求设计一个满足以下要求的比赛日程表： （1）每个选手必须与其他n-1个选手各赛一次； （2）每个选手一天只能赛一次。 采用分治方法。 将2^k选手分为2^k-1两组，采用递归方法，继续进行分组，直到只剩下2个选手时，然后进行比赛，回溯就可以指定比赛日程表了 15. 格雷码是一个长度为2n的序列，序列中无相同元素，且每个元素都是长度为n的 二进制位串，相邻元素恰好只有1位不同。例如长度为23的格雷码为(000, 001, 011, 010, 110, 111, 101, 100)。设计分治算法对任意的n值构造相应的格雷码。 //构造格雷码 #include using namespace std; int n; char a[100]; void gelei(int k) { if(k==n) { cout< return; } gelei(k+1); a[k]='0'?'1':'0'; //取反 gelei(k+1); } int main() { while(cin>>n && n != 0) { memset(a,'0',sizeof(a)); //初始化，全部置零 a[n] ='\0'; gelei(0); cout< } return 0; } 16. 矩阵乘法。两个n×n的矩阵X和Y的乘积得到另外一个n×n的矩阵Z，且Z ij 满足（1≤i, j≤n），这个公式给出了运行时间为O(n3)的算法。可以用分 治法解决矩阵乘法问题，将矩阵X和Y都划分成四个n/2×n/2的子块，从而X和Y的乘积可以用这些子块进行表达，即 从而得到分治算法：先递归地计算8个规模为n/2的矩阵乘积AE、BG、AF、BH、CE、DG、 CF、DH，然后再花费O(n2)的时间完成加法运算即可。请设计分治算法实现矩阵乘法，并分析时间性能。能否再改进这个分治算法？ 习题5 1.下面这个折半查找算法正确吗？如果正确，请给出算法的正确性证明，如果不正确，请 说明产生错误的原因。 int BinSearch(int r[ ], int n, int k) { int low = 0, high = n - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (k < r[mid]) high = mid; else if (k > r[mid]) low = mid; else return mid; } return 0; } 错误。 正确算法： int BinSearch1(int r[ ], int n, int k) { int low = 0, high = n - 1; int mid; while (low <= high) { mid = (low + high) / 2; if (k < r[mid]) high = mid - 1; else if (k > r[mid]) low = mid + 1; else return mid; } return 0; } 2.请写出折半查找的递归算法，并分析时间性能。 //折半查找的递归实现 #include using namespace std; int digui_search(int a[],int low,int high,int x) { if (low > high) return 0; int mid = (low+high)/2; if (a[mid] == x) return mid; else if (a[mid] < x) digui_search(a,low,mid-1,x); else digui_search(a,mid+1,high,x); } int main() { int a[6]={0,1,2,9,5,3}; int result=digui_search(a,0,5,5); cout< return 0; } 3.修改折半查找算法使之能够进行范围查找。所谓范围查找是要找出在给定值a和b之间 的所有元素（a≤b） 修改第二题算法并实现： //折半查找算法使之能够进行范围查找 #include using namespace std; //折半进行范围查找函数： void digui_search(int min, int max, int a[], int low, int high) { int mid; mid=(low+high)/2; if(a[mid] digui_search(min, max, a, mid, high); else if(a[mid]>max) digui_search(min, max, a, low, mid); else { for(int i=mid; a[i]>=min && i>=low; i--) cout< cout< for(int j=mid+1; a[j]<=max && j<=high; j++) cout< cout< } } void main() { int r[6], min, max; cout<<"请输入数组元素："< for(int i=0; i<6; i++) cin>>r[i]; cout<<"请输入查找范围最小值min和最大值max："<<" "; cin>>min>>max; digui_search(min, max, r, 0, 5); cout< } 4. 求两个正整数m和n的最小公倍数。（提示：m和n的最小公倍数lcm(m, n)与m和n的最大公约数gcd(m, n)之间有如下关系：lcm(m, n)=m×n/gcd(m, n)） //求两个数的最小公倍数 #include using namespace std; int main (void) { int a,b; int i=1; cin>>a>>b; while((i%a!=0)||(i%b!=0)) ++i; cout<<"a,b最小公倍数为："< return 0; } (该算法比较直接，要使其改进，可用欧几里得算法求得两个数的最大公约数，然后套用上面的公式再求最小公倍数) 5. 插入法调整堆。已知（k1, k2, …, k n）是堆，设计算法将（k1, k2, …, k n, k n+1）调整为堆（假设调整为大根堆）。 参照： void SiftHeap(int r[ ], int k, int n) { int i, j, temp; i = k; j = 2 * i + 1; //置i为要筛的结点，j为i的左孩子 while (j < n) //筛选还没有进行到叶子 { if (j < n-1 && r[j] < r[j+1]) j++; //比较i的左右孩子，j为较大者 if (r[i] > r[j]) //根结点已经大于左右孩子中的较大者 break; else { temp = r[i]; r[i] = r[j]; r[j] = temp; //将被筛结点与结点j交换 i = j; j = 2 * i + 1; //被筛结点位于原来结点j的位置 } } } 进行调堆！ 6. 设计算法实现在大根堆中删除一个元素，要求算法的时间复杂性为O(log2n)。 //将要删除的a[k]与最后一个元素a[n-1]交换 //然后进行调堆 void de_SiftHeap(int r[ ], int k, int n) { int i, j, temp,temp1; i = k; j = 2 * i + 1; if(i<0||i>n-1) return error; else if(i==n-1) free(a[i]); else //置i为要筛的结点，j为i的左孩子 while (j < n) //筛选还没有进行到叶子 { temp1=a[i]; //将a[n-1]与a[k]交换； 《计算机算法设计与分析》习题及答案 一．选择题 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 ）。 1. 贪心算法和动态规划算法有什么共同点和区别？它们都有那些优势和劣势？ 共通点：动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解 区别：贪心算法中，作出的每步贪心决策都无法改变，每一步的最优解一定包含上一步的 最优解，而上一部之前的最优解则不作保留。 动态优化算法，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。但它需要计算之前所有情况花费，更加耗费空间。 贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编 码和执行过程中都有一定的速度优势。贪心算法是只是找局部最优解，不一定是全局最优解。 2. 试比较回溯法与分枝限界算法，分别谈谈这两个算法比较适合的问题？ 二者都是在解空间树里搜索问题的可靠解或最优解，但是搜索的方式不同，回溯法采用深 度优先的方式，直到达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的节点，然后，从该节点出发朝新的方向纵深搜索。分枝限界法采用的是宽度优先的方式，它将活节点存放在一个特殊的表中，其策略是，在扩展节点处，首先生成其所有的儿子节点，将那些导致不可行解或导致非最优解的儿子节点舍弃，其余儿子节点加入活节点表中，然后，从活节点中取出一个节点作为当前扩展节点，重复上述节点中扩展过程。可以看出，回溯法一般用于求问题的一个可行解，而分枝限界可以用于求出问题的所有可行解。 3. 何谓最优化原理？采用动态规划算法必须满足的条件是什么？动态规划算法是通过什 么问题的什么特性提高效率的？ 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优子结构性质，子问题重叠性质是计算模型采用动态规划算法求解的两个基本要素。 动态规划算法利用子问题重叠性质，对每一个子问题只计算一次，将其解保存在一个表格中。不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率 4. 什么是多项式时间算法？ 若存在一个常数C，使得对于所有n>=0，都有|f(n)| <= C*|g(n)|，则称函数f(n)是O(g(n))。时间复杂度是O(p(n))的算法称为多项式时间算法，这里p(n)是关于n的多项式。 时间复杂度为O(nlog(n))、O(n^3)的算法都是多项式时间算法，时间复杂度为O(n^log(n))、O(n!)、O(2^n)的算法是指数时间算法。 一个优化问题如果已经找到了多项式时间算法，则称该问题为多项式时间可解问题，并 将这类问题的集合记为P，因此多项式时间可解问题就称为P类问题。。 第3章习题与解答 3－1 在以下两种情况下，画出题3－1图所示电路的图，并说明其节点数和支路数各为多少？KCL、KVL独立方程数各为多少？ （1）每个元件作为一条支路处理； （2）电压源（独立或受控）和电阻的串联组合，电流源和电阻的并联组合作为一条支路处理。 (a) (b) 题3－1图 解：图（a） （1）如图所示：支路数b=11，节点数n=6 b-n+1=6 KCL独立方程数为n-1=5、KVL独立方程数为 （2）如图所示：支路数b=8，节点数n=4 KCL独立方程数为n-1=3、KVL独立方程数为 b-n+1=5 图（b） （1）如图所示：支路数=12，节点数=7 KCL独立方程数为n-1=6、KVL独立方程数为 b-n+1=6 （2）如图所示：支路数=9，节点数=5 KCL独立方程数为n-1=4、KVL独立方程数为 b-n+1=5 3－2 试画出题3－2图所示四点全图的全部树。 ① 题3－2图 解： 3－3 如题3－3图所示的有向图，在以下两种情况下列出独立的KVL方程。 （1）任选一树并确定其基本回路组作为独立回路； （2）选网孔作为独立回路。 ③ 1 8 题3－3图 解：以2、3、5、6支路为树，1、4、7、8支路为连支。这样选网孔正好是基本回路，所以，（1）、（2）两个问题可合并。KVL如下： 2540 u u u +-= 5860 u u u +-= 3760 u u u +-= 1230 u u u ++= 3－4 题3－4图所示电路中，12310,4,R R R ==Ω=Ω458,R R ==Ω62,R =Ω 310,S u V =610,S i A =试列出支路法、支路电流法及支路电压法所需的方程。 i 题3－4图 解：电路的图为 3 设每个回路都为顺时针方向。 列支路法方程如下： 节点① 1260i i i ++= 节点② 2340i i i --= 节点③ 4560i i i -+= 回路1l 2310u u u +-= 回路2l 4530u u u +-= 回路3l 6420u u u +-= 支路特性方程： 111u R i = 算法实现题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 算法设计与分析试卷(A 卷) 一、 选择题 （ 选择1-4个正确的答案, 每题2分，共20分） （1）计算机算法的正确描述是： B 、D A ．一个算法是求特定问题的运算序列。 B ．算法是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型的问题的运算序列。 C ．算法是一个对任一有效输入能够停机的图灵机。 D ．一个算法，它是满足5 个特性的程序，这5个特性是：有限性、确定性、能 行性、有0个或多个输入且有1个或多个输出。 （2）影响程序执行时间的因素有哪些？ C 、D A ．算法设计的策略 B ．问题的规模 C ．编译程序产生的机器代码质量 D ．计算机执行指令的速度 （3）用数量级形式表示的算法执行时间称为算法的 A A ．时间复杂度 B ．空间复杂度 C ．处理器复杂度 D ．通信复杂度 （4）时间复杂性为多项式界的算法有： A ．快速排序算法 B ．n-后问题 C ．计算π值 D ．prim 算法 （5）对于并行算法与串行算法的关系，正确的理解是： A ．高效的串行算法不一定是能导出高效的并行算法 B ．高效的串行算法不一定隐含并行性 C ．串行算法经适当的改造有些可以变化成并行算法 D. 用串行方法设计和实现的并行算法未必有效 （6）衡量近似算法性能的重要标准有： A A ．算法复杂度 B ．问题复杂度 C ．解的最优近似度 D ．算法的策略 （7）分治法的适用条件是，所解决的问题一般具有这些特征： ABCD A ．该问题的规模缩小到一定的程度就可以容易地解决； B ．该问题可以分解为若干个规模较小的相同问题； C ．利用该问题分解出的子问题的解可以合并为该问题的解 D ．该问题所分解出的各个子问题是相互独立的。 （8）具有最优子结构的算法有： A ．概率算法 B ．回溯法 C ．分支限界法 D ．动态规划法 （9）下列哪些问题是典型的NP 完全问题： A ．排序问题 B ．n-后问题 C ．m-着色问题 D ．旅行商问题 （10）适于递归实现的算法有： C A ．并行算法 B ．近似算法 C ．分治法 D ．回溯法 二、算法分析题（每小题5分，共10分） （11）用展开法求解递推关系： （12）分析当输入数据已经有序时快速排序算法的不足，提出算法的改进方案。 ???>+-==1 1)1(211)(n n T n n T 第四章 流体力学基础习题解答 4-1 关于压强的下列说确的是（ ）。 A 、压强是矢量； B 、容器液体作用在容器底部的压力等于流体的重力； C 、静止流体高度差为h 的两点间的压强差为gh P o ρ+； D 、在地球表面一个盛有流体的容器以加速度a 竖直向上运动，则流体深度为h 处的压强为0)(P a g h P ++=ρ。 解：Ｄ 4-2 海水的密度为33m /kg 1003.1?=ρ，海平面以下100m 处的压强为（ ）。 A 、Pa 1011.16?； B 、Pa 1011.15? C 、Pa 1001.16?； D 、Pa 1001.15?。 解：Ａ 4-3 两个半径不同的肥皂泡，用一细导管连通后，肥皂泡将会（ ）。 A 、两个肥皂泡最终一样大； B 、大泡变大，小泡变小 C 、大泡变小，小泡变大； D 、不能判断。 解：Ｂ ４-4 两个完全相同的毛细管，插在两个不同的液体中，两个毛细管（ ）。 A 、两管液体上升高度相同； B 、两管液体上升高度不同； C 、一个上升，一个下降； Ｄ、不能判断。 解：Ｂ 4-5 一半径为r 的毛细管，插入密度为ρ的液体中，设毛细管壁与液体接触角为θ，则液体在毛细管中上升高度为h= ( ) 。（设液体的表面力系数为α） 解:gr h ρθα=cos 2 4-6 如图所示的液面。液面下A 点处压强是（ ） 。设弯曲液面是球面的一部分，液面曲率半径为Ｒ，大气压强是0P ，表面力系数是α。 解:R P P α+ =20 4-7 当接触角2πθ< 时，液体（ ）固体，0=θ时，液体（ ）固体；当2π θ>时，液体（ ）固体，πθ=，液体（ ）固体。 解：润湿，完全润湿，不润湿，完全不润湿。 《算法设计与分析》习题 第一章算法引论 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) { if(n<=2) return 1; else return F(n-1)+ F(n-2); } 上楼梯问题 Int F(int n) { if(n=1) return 1 if(n=2) return 2; else return F(n-1)+ F(n-2); } 整数划分问题 问题描述：将正整数n 表示成一系列正整数之和，n=n1+n1+n3+… 将最大加数不大于m 的划分个数，记作q(n,m)。正整数n 的划分数 p(n)=q(n,n)。 可以建立q(n,m)的如下递归关系： 递归算法： Int q( int n, int m){ if(n<1||m<1) return 0; If((n=1)||(m=1)) return 1; If (n 1、二分搜索算法是利用（ A ）实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是（ A ）。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 4、最长公共子序列算法利用的算法是（ B ）。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 5. 回溯法解TSP问题时的解空间树是（ A ）。 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、实现最长公共子序列利用的算法是（ B ）。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法11．下面不是分支界限法搜索方式的是（ D ）。 A、广度优先 B、最小耗费优先 C、最大效益优先 D、深度优先 12．下列算法中通常以深度优先方式系统搜索问题解的是（ D ）。 A、备忘录法 B、动态规划法 C、贪心法 D、回溯法 13. 一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（ B ）。 A、重叠子问题 B、最优子结构性质 C、贪心选择性质 D、定义最优解14．广度优先是（ A ）的一搜索方式。 A、分支界限法 B、动态规划法 C、贪心法 D、回溯法 15．背包问题的贪心算法所需的计算时间为（ B ）。 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 E说：D应该是第1名。 比赛结束后发现，只有获第1名和第2名的选手猜对了，E不是第2名和第3名，没有出现名次并列的情况。 请编程判断5位选手各是第几名。 输入 无 输出 输出要求：按ABCDE的顺序输出5行，其中第1行是A的名次，第2行是B的名次，第3行是C的名次，第4行是D的名次，第5行是E的名次。 样例输入 样例输出 源代码： #include 填空 1．直接或间接地调用自身的算法称为 递归 。 2．算法的复杂性是 算法效率 的度量，是评价算法优劣的重要依据。 3．以广度优先或以最小耗费方式搜索问题解的算法称为 分支限界法 。 4．回溯法解题的显著特点是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为 o(h(n)) 。 5．人们通常将问题的解决方案分为两大类：一类是可以通过执行若干个步骤就能得出问题 6．算法就是一组有穷的 规则 ，它们规定了解决某一特定类型问题的 一系列运算 。 7．在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是 随机存取机、 随机存取存储程序机 、 图灵机 。 8．快速排序算法的性能取决于 划分的对称性 。 9．计算机的资源最重要的是 内存 和 运算 资源。因而，算法的复杂性有时间 和 空间 之分。 10．贪心算法总是做出在当前看来 最优 的选择。也就是说贪心算法并不从整体最优考虑，它所做出的选择只是在某种意义上的 局部最优解 。 11．许多可以用贪心算法求解的问题一般具有2个重要的性质： 最优子结构的 性质和 贪心选择的 性质。 12．常见的两种分支限界法为 队列式 和 优先队列式 。 13．解决0/1背包问题可以使用动态规划、回溯法和分支限界法，其中需要排序的是 回溯法 ，不需要排序的是 动态规划和分支限界法 。 14．f ( n ) = 6 × 2n + n 2，f(n)的渐进性态f ( n ) = O ( 2^n )。 15．对于含有n 个元素的排列树问题，最好情况下计算时间复杂性为 ，最坏情况下计算时间复杂性为 n! 。 16．在忽略常数因子的情况下，O 、Ω和Θ三个符号中， Θ 提供了算法运行时间的一个上界。 17．回溯法的求解过程，即在问题的解空间树中，按 深度优先 策略从根结点出发搜索解空间树。 18．分支限界法的求解过程，即在问题的解空间树中，按 广度优先 策略从根结点出发搜索解空间树。 19．多项式10()m m A n a n a n a =+ ++的上界为 2^n 。 20．用分支限界法解布线问题时，对空间树搜索结束的标志是 活结点表为空 。 21．使用回溯法进行状态空间树裁剪分支时一般有两个标准：约束条件和目标函数的界，N 皇后问题和0/1背包问题正好是两种不同的类型，其中同时使用约束条件和目标函数的界进 第八章 恒定磁场 8-1 均匀磁场的磁感强度B 垂直于半径为r 的圆面．今以该圆周为边线，作一半球面S ，则通过S 面的磁通量的大小为［ ］。 (A) B r 22π (B) B r 2π (C) 0 (D) 无法确定 分析与解 根据高斯定理，磁感线是闭合曲线，穿过圆平面的磁通量与穿过半球面的磁通量相等。正确答案为（B ）。 8-2 下列说法正确的是[ ]。 (A) 闭合回路上各点磁感强度都为零时，回路内一定没有电流穿过 (B) 闭合回路上各点磁感强度都为零时，回路内穿过电流的代数和必定为零 (C) 磁感强度沿闭合回路的积分为零时，回路上各点的磁感强度必定为零 (D) 磁感强度沿闭合回路的积分不为零时，回路上任意点的磁感强度必定为零 分析与解 由磁场中的安培环路定理，磁感强度沿闭合回路的积分为零时，回路上各点的磁感强度不一定为零；闭合回路上各点磁感强度为零时，穿过回路的电流代数和一定为零。正确答案为（B ）。 8-3 磁场中的安培环路定理∑?=μ=?n L I 1 i i 0d l B 说明稳恒电流的磁场是[ ]。 (A) 无源场 (B) 有旋场 (C) 无旋场 (D) 有源场 分析与解 磁场的高斯定理与安培环路定理是磁场性质的重要表述，在恒定磁场中B 的环流一般不为零，所以磁场是涡旋场；而在恒定磁场中，通过任意闭合曲面的磁通量必为零，所以磁场是无源场；静电场中E 的环流等于零，故静电场为保守场；而静电场中，通过任意闭合面的电通量可以不为零，故静电场为有 习题8-6图 I O R 源场。正确答案为（B ）。 8-4 一半圆形闭合平面线圈，半径为R ，通有电流I ，放在磁感强度为B 的均匀磁场中，磁场方向与线圈平面平行，则线圈所受磁力矩大小为[ ]。 (A) B R I 2π (B) B R I 22 1 π (C) B R I 24 1π (D) 0 分析与解 对一匝通电平面线圈，在磁场中所受的磁力矩可表示为 B e M ?=n IS ，而且对任意形状的平面线圈都是适用的。正确答案为（B ）。 8-5 一长直螺线管是由直径d =0.2mm 的漆包线密绕而成。当它通以I =0.5A 的电流时，其内部的磁感强度B =_____________。(忽略绝缘层厚度，μ0=4π×10-7N/A 2) 分析与解 根据磁场中的安培环路定理可求得长直螺线管内部的磁感强度大小为nI B 0μ=，方向由右螺旋关系确定。正确答安为（T 1014.33-?）。 8-6 如图所示，载流导线在平面内分布，电流为I ，则在圆心O 点处的磁感强度大小为_____________，方向为_____________ 。 分析与解 根据圆形电流和长直电流的磁感强度公式，并作矢量叠加，可得圆心O 点的总的磁感强度。正确答案为（ ?? ? ??π-μ1120R I ，向里）。 8-7 如图所示，平行的无限长直载流导线A 和B ，电流强度均为I ，垂直纸面向外，两根载流导线之间相距为a ，则(1)AB 中点的磁感应强度B P =_____________。 (2)磁感应强度沿图中环路l 的线积分 =??L l B d _____________。 分析与解 根据长直电流的磁感强度公式和电流分布的对称性，P 点的磁感强度是两电流产生的 磁感强 习题8-7图 计算机算法设计与分析习 题及答案 Prepared on 24 November 2020 《计算机算法设计与分析》习题及答案 一．选择题 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、问题分析 2、数学模型建立 3、算法设计与选择 4、算法指标 5、算法分析 6、算法实现 7、程序调试 8、结果整理文档编制 2、算法定义：算法是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程 3、算法的三要素 1、操作 2、控制结构 3、数据结构 算法具有以下5个属性： 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。只有一个入口和一个出口 可行性：一个算法是可行的就是算法描述的操作是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。 输出：一个算法有一个或多个输出，这些输出同输入有着某些特定关系的量。 算法设计的质量指标： 正确性：算法应满足具体问题的需求； 可读性：算法应该好读，以有利于读者对程序的理解； 健壮性：算法应具有容错处理，当输入为非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。 效率与存储量需求：效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般这两者与问题的规模有关。 经常采用的算法主要有迭代法、分而治之法、贪婪法、动态规划法、回溯法、分支限界法 迭代法 基本思想：迭代法也称“辗转法”，是一种不断用变量的旧值递推出新值的解决问题的方法。 解题步骤：1、确定迭代模型。根据问题描述，分析得出前一个（或几个）值与其下一个值的迭代关系数学模型。 2、建立迭代关系式。迭代关系式就是一个直接或间接地不断由旧值递推出新值的表达式，存储新值的变量称为迭代变量 3、对迭代过程进行控制。确定在什么时候结束迭代过程，这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一 《算法设计与分析实用教程》参考解答 1-1 加减得1的数学游戏 西西很喜欢数字游戏，今天他看到两个数，就想能否通过简单的加减，使最终答案等于1。而他又比较厌烦计算，所以他还想知道最少经过多少次才能得到1。 例如，给出16,9：16-9+16-9+16-9-9-9+16-9-9=1，需要做10次加减法计算。 设计算法，输入两个不同的正整数，输出得到1的最少计算次数。（如果无法得到1，则输出-1）。 （1）若输入两个不同的正整数a,b均为偶数，显然不可能得到1。 设x*a与y*b之差为“1”或“-1”,则对于正整数a,b经n=x+y-1次加减可得到1。 为了求n的最小值，令n从1开始递增，x在1——n中取值，y=n+1-x： 检测d=x*a+y*b，若d=1或-1，则n=x+y-1为所求的最少次数。 （2）算法描述 // 两数若干次加减结果为1的数学游戏 #include 第三章习题解答 《化工设备机械基础》习题解答 第三章内压薄壁容器的应力分析 一、名词解释 A组： ⒈薄壁容器：容器的壁厚与其最大截面圆的内径之比小于0.1的容器。 ⒉回转壳体：壳体的中间面是直线或平面曲线绕其同平面内的固定轴线旋转360°而成的壳体。 ⒊经线：若通过回转轴作一纵截面与壳体曲面相交所得的交线。 ⒋薄膜理论：薄膜应力是只有拉压正应力没有弯曲正应力的一种两向应力状态，也称为无力矩理论。 ⒌第一曲率半径：中间面上任一点M处经线的曲率半径。 ⒍小位移假设：壳体受力以后，各点位移都远小于壁厚。 ⒎区域平衡方程式：计算回转壳体在任意纬线上径向应力的公式。 ⒏边缘应力：内压圆筒壁上的弯曲应力及连接边缘区的变形与应力。 ⒐边缘应力的自限性：当边缘处的局部材料发生屈服进入塑性变形阶段时，弹性约束开始缓解，原来不同的薄膜变形便趋于协调，边缘应力就自动限制。 二、判断题（对者画√，错着画╳） A组： 1. 下列直立薄壁容器，受均匀气体内压力作用，哪些能用薄膜理论求解壁内应力？ 哪些不能？ （1）横截面为正六角形的柱壳。（×） （2）横截面为圆的轴对称柱壳。（√） （3）横截面为椭圆的柱壳。（×） （4）横截面为圆的椭球壳。（√） （5）横截面为半圆的柱壳。（×） （6）横截面为圆的锥形壳。（√） 2. 在承受内压的圆筒形容器上开椭圆孔，应使椭圆的长轴与筒体轴线平行。（×） 3. 薄壁回转壳体中任一点，只要该点的两个曲率半径R R2 =，则该点的两向应力 1 σθ σ = m。（√） 4. 因为内压薄壁圆筒的两向应力与壁厚成反比，当材质与介质压力一定时，则壁厚 大的容器，壁内的应力总是小于壁厚小的容器。（×） 5. 按无力矩理论求得的应力称为薄膜应力，薄膜应力是沿壁厚均匀分布的。（√）B组： 1. 卧式圆筒形容器，其内介质压力，只充满液体，因为圆筒内液体静载荷不是沿轴 线对称分布的，所以不能用薄膜理论应力公式求解。（√） 2. 由于圆锥形容器锥顶部分应力最小，所以开空宜在锥顶部分。（√） 3. 凡薄壁壳体，只要其几何形状和所受载荷对称于旋转轴，则壳体上任何一点用薄 膜理论应力公式求解的应力都是真实的。（×） 4. 椭球壳的长，短轴之比a/b越小，其形状越接近球壳，其应力分布也就越趋于均 匀。（√） 5. 因为从受力分析角度来说，半球形封头最好，所以不论在任何情况下，都必须首 先考虑采用半球形封头。（×） 三、指出和计算下列回转壳体上诸点的第一和第二曲率半径 A组： 第一章 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)). 第二章 算法分析题 湖南科技学院二○ 年 学期期末考试 信息与计算科学专业 年级《算法设计与分析》 试题 考试类型：开卷 试卷类型： C 卷 考试时量： 120 分钟 题号 一 二 三 四 五 总分 统分人 得 分 阅卷人 一、填空题（每小题 3 分，共计 30 分） 1. 用 O 、Ω和θ表示函数 f 与 g 之间的关系 ______________________________ 。 f n n lo g n g n log n 1, n 1 2. 算法的时间复杂性为 f (n) n ，则算法的时间复杂性的阶 8 f (3n / 7) n, 2 为__________________________ 。 3. 快速排序算法的性能取决于 ______________________________ 。 4. 算法是 _______________________________________________________ 。 5. 在对问题的解空间树进行搜索的方法中，一个活结点最多有一次机会成为活结点的 是_________________________ 。 6. 在算法的三种情况下的复杂性中， 可操作性最好且最有实际价值的是 _____情况下的时间复杂性。 7. 大Ω符号用来描述增长率的下限，这个下限的阶越 ___________，结果就越有价值。 。 8. ____________________________ 是问题能用动态规划算法求解的前提。 9. 贪心选择性质是指 ________________________________________________________ ____________________________________________________________ 。 大学物理第07章习题分析与解答 r R r R E O r (D) E ∝1/r 2 22 第七章 静电场 7-1 关于电场强度与电势的关系，描述正确的是[ ]。 (A) 电场强度大的地方电势一定高； (B) 沿着电场线的方向电势一定降低； (C) 均匀电场中电势处处相等； (D) 电场强度为零的地方电势也为零。 分析与解 电场强度与电势是描述静电场的两个不同物理量，电场强度为零表示试验电荷在该点受到的电场力为零，电势为零表示将试验电荷从该点移到参考零电势点时，电场力作功为零；电场强度等于负电势梯度；静电场是保守场，电场线的方向就是电势降低的方向。正确答案为（B ）。 7-2 半径为R 的均匀带电球面的静电场中各点的电场强度的大小E 与距球心的距离r 之间的关系曲线为[ ]。 3、下 7-分析与解 根据静电场的高斯定理可以求得均匀带电球面的电场强度分布为 ?????>πε<=R r r Q R r E 2040。正确答案为（B ）。 7-3 下列说法正确的是[ ]。 （A ）带正电的物体电势一定是正的 (B)电场强度为零的地方电势一定为零 （C ）等势面与电场线处处正交 (D)等势面上的电场强度处处相等 分析与解 正电荷在电场中所受的电场力的方向与电场线的切线方向相同，电荷在等势面上移动电荷时，电场力不做功，说明电场力与位移方向垂直。正确答案为（C ）。 7-4 真空中一均匀带电量为Q 的球壳，将试验正电荷q 从球壳外的R 处移至无限远处时,电场力的功为[ ]。 （A ）24R qQ o πε （B ）R Q o πε4 （C ） R q o πε4 （D ）R qQ o πε4 分析与解 静电场力是保守力，电场力做的功等电势能增量的负值，也可以表示成这一过程的电势差与移动电量的乘积，由习题7-2可知电场强度分布，由电势定义式?∞?= R r E d V 可得球壳与无限远处的电势差。正确答案为（D ）。 7-5 关于静电场的高斯定理有下面几种说法，其中正确的是[ ]。 （A ）如果高斯面上电场强度处处为零，则高斯面内必无电荷； （B ）如果高斯面内有净电荷，则穿过高斯面的电场强度通量必不为零； （C ）高斯面上各点的电场强度仅由面内的电荷产生； （D ）如果穿过高斯面的电通量为零，则高斯面上电场强度处处为零《计算机算法设计与分析》习题及答案
中科院陈玉福计算机算法设计与分析期末简答题答案
第3章 习题与解答
算法设计与分析课后部分习题答案
算法设计与分析试卷(2010)
第04章习题分析与解答
算法设计与分析习题
计算机算法设计与分析期末考试复习题
OpenJudge算法设计与分析习题解答
《算法设计与分析》复习题(汇编)
大学物理 第 章习题分析与解答
计算机算法设计与分析习题及答案
算法设计与分析期末试题答案解析
《算法设计与分析实用教程》习题参考解答
第三章习题解答资料
算法设计与分析课后习题
算法设计与分析试卷及答案.doc
大学物理第07章习题分析与解答备课讲稿
相关主题
文本预览