算法2010-2011考题-答案.doc

Learn General Secretary on "two to learn a" strengthening "four Consciousnesses" important speech caused a strong reaction in the country. 　　Time, watching "red treasure", the origin of building the party back to power, how to strengthen services for the masses, improve party cohesion, fighting to become the grass-roots party members and masses hot topic. Grass-roots party organizations "two" is to strengthen the service of party members and cadres, the pioneer spirit. Distribution of grass-roots party organizations in all walks of people, clothing, shelter, which belongs to the nerve endings of the party organization and comments reputation has a direct perception of the masses. 　　Strengthen the party ahead of the "pedal" spirit; strengthen the party members and cadres "success does not have to be me" and "the first to bear hardships, the last to" service spirit to set the party's positive image among the people is important. Grass-roots party organizations "two" is to cleanse all people not happy not to see "stereotypes", establish the honest faithful, diligent faith for the people. No need to avoid mentioning that, some members of our party can not stand the "money," corrosion of temptation, thin, Xu Zhou, such abuse and corrupt bribery, malfeasance borers, and rats. Two, is to clean up, thin, Xu, Zhou's solution to restore the party's fresh and natural, solid and honest work style. 　　Cleansing "take, eat, card," undesirable and behaviour, "cross, hard and cold, push" attitude. Grass-roots party organizations "two" is to strengthen the sense of ordinary party members, participating in consciousness, unity consciousness. For reasons known, members of grass-roots party branches less mobile, less resources, and the construction of party organizations have some lag. Two studies, is to focus on the grass-roots party branches "loose, soft, loose" problem, advance the party members and cadres, "a gang working", "Hong Kong report." 　　Strong cleanup actions, style and rambling, presumptuous "unqualified" party members, pays special attention to party members and cadres "joining party of thought" problem. "Party building" is obtained in the long-term development of our party's historical experience accumulated. Two is our party under the new historical conditions, strengthen the party's construction of a new "rectification movement." Grass-roots party organizations should always catch the hard work, results-oriented. Two educational outcomes are long-term oriented and become an important impetus for the work. "Two" should have three kinds of consciousness "two" study and education, basic learning lies in the doing. Only the Constitution address the series of party rules, and do solid work, be qualified party members had a solid ideological basis. Only the "learning" and "do" real unity, to form a "learn-learn-do-do" the virtuous cycle, and ultimately achieve the fundamental objective of education. This requires that the Organization
1、使用分治法写一个算法完成一个无序的整数数组的归并排序，并分析算法的时间复杂度。要求：算法的函数表示是MergeSort（1，n）算法对于A[1:n]进行排序，A是一个全局数组，含有n个元素。算法的实现可利用Merge（low,mid,high）计数，其功能是将全程数组A[low:high]进行合并排序，函数调用前，A[low,high]由两部分已经排序的子数组构成：A[low:mid]和A[low+1:high]，函数的任务是将这两部分子数组合并成一个整体排好序的数组，再存于数组A[low:high]。（实现时，可认为Merge是已知的，不需要编写）（20分）
解：
（1）递归实现的归并排序：
1. //2d7-1 递归实现二路归并排序  
2. #include "stdafx.h"  
3. #include <iostream>       
4. using namespace std;   
5.   
6. int a[] = {10,5,9,4,3,7,8};  
7. int b[7];  
8.   
9. template <class Type>  
10. void Merge(Type c[],Type d[],int l,int m,int r);  
11.   
12. template <class Type>  
13. void MergeSort(Type a[],int left,int right);  
14.   
15. int main()  
16. {  
17.     for(int i=0; i<7; i++)  
18.     {  
19.         cout<<a[i]<<" ";  
20.     }  
21.     cout<<endl;  
22.     MergeSort(a,0,6);  
23.     for(int i=0; i<7; i++)  
24.     {  
25.         cout<<a[i]<<" ";  
26.     }  
27.     cout<<endl;  
28. }  
29.   
30. template <class Type>  
31. void Merge(Type c[],Type d[],int l,int m,int r)  
32. {  
33.     int i = l,j = m + 1,k = l;  
34.     while((i<=m)&&(j<=r))  
35.     {  
36.         if(c[i]<=c[j])  
37.         {  
38.             d[k++] = c[i++];  
39.         }  
40.         else  
41.         {  
42.             d[k++] = c[j++];  
43.         }  
44.     }  
45.   
46.     if(i>m)  
47.     {  
48.         for(int q=j; q<=r; q++)  
49.         {  
50.             d[k++] = c[q];  
51.         }     
52.     }  
53.     else  
54.     {  
55.         for(int q=i; q<=m; q++)  
56.         {  
57.             d[k++] = c[q];  
58.         }  
59.     }  
60. }  
61.   
62. template <class Type>  
63. void MergeSort(Type a[],int left,int right)  
64. {  
65.     if(left<right)  
66.     {  
67.         int i = (left + right)/2;  
68.         MergeSort(a,left,i);  
69.         MergeSort(a,i+1,right);  
70.         Merge(a,b,left,i,right);//合并到数组b  
71.   
72.         //复制回数组a  
73.         for(int g=left; g<=right; g++)  
74.         {  
75.             a[g] = b[g];  
76.         }  
77.     }  
78. }  
（2）非递归实现的归并排序：
1. //2d7-1 自然二路归并排序  
2. #include "stdafx.h"  
3. #include <iostream>       
4. using namespace std;   
5.   
6. int a[] = {10,5,9,4,3,7,8};  
7. int b[7];  
8.   
9. template <class Type>  
10. void Merge(Type c[],Type d[],int l,int m,int r);  
11.   
12. template <class Type>  
13. void MergePass(Type x[],Type y[],int s,int n);  
14.   
15. template <class Type>  
16. void MergeSort(Type a[],int n);  
17.   
18. int main()  
19. {  
20.     for(int i=0; i<7; i++)  
21.     {  
22.         cout<<a[i]<<" ";  
23.     }  
24.     cout<<endl;  
25.     MergeSort(a,7);  
26.     for(int i=0; i<7; i++)  
27.     {  
28.         cout<<a[i]<<" ";  
29.     }  
30.     cout<<endl;  
31. }  
32.   
33. template <class Type>  
34. void Merge(Type c[],Type d[],int l,int m,int r)  
35. {  
36.     int i = l,j = m + 1,k = l;  
37.     while((i<=m)&&(j<=r))  
38.     {  
39.         if(c[i]<=c[j])  
40.         {  
41.             d[k++] = c[i++];  
42.         }  
43.         else  
44.         {  
45.             d[k++] = c[j++];  
46.         }  
47.     }  
48.   
49.     if(i>m)  
50.     {  
51.         for(int q=j; q<=r; q++)  
52.         {  
53.             d[k++] = c[q];  
54.         }     
55.     }  
56.     else  
57.     {  
58.         for(int q=i; q<=m; q++)  
59.         {  
60.             d[k++] = c[q];  
61.         }  
62.     }  
63. }  
64.   
65. template <class Type>  
66. //合并大小为s的相邻子数组  
67. void MergePass(Type x[],Type y[],int s,int n)  
68. {  
69.     int i = 0;  
70.     while(i<=n-2*s)  
71.     {  
72.         //合并大小为s的相邻两段子数组  
73.         Merge(x,y,i,i+s-1,i+2*s-1);  
74.         i = i + 2*s;  
75.     }  
76.     //剩下的元素个数少于2s  
77.     if(i+s<n)  
78.     {  
79.         Merge(x,y,i,i+s-1,n-1);  
80.     }  
81.     else  
82.     {  
83.         for(int j=i; j<=n-1; j++)  
84.         {  
85.             y[j]=x[j];  
86.         }  
87.     }  
88. }  
89.   
90. template <class Type>  
91. void MergeSort(Type a[],int n)  
92. {  
93.     Type *b = new Type[n];  
94.     int s = 1;  
95.     while(s<n)  
96.     {  
97.         MergePass(a,b,s,n);//合并到数组b  
98.         s += s;  
99.         MergePass(b,a,s,n);//合并到数组a  
100.         s += s;  
101.     }  
102. }  

2、使用贪心算法解优化问题，关键是选取合适的贪心准则。试说明解装载问题时采用的贪心准则。（最优有装载问题：一批集装箱要装上一艘载重量为c的轮船，其中集装箱i的重量为wi。最优装载问题要求确定在装在体积不受限制的情况下，将尽可能多的集装箱装上轮船。）（10分）
解：
算法分析：采用重量轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体描述如下：

2、贪心选择性质
变换目标后可以证明最优装载问题具有贪心选择性质(归纳法)

3、最优子结构性质
最优装载问题具有最优子结构性质(反证法)
由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法loading的正确性。

算法loading的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为O(nlogn)
3、设使用动态规划算法求解最长公共子序列，写出子序列长度c[i][j]的递归表达式，写出求解序列（A，B，F，G）和序列（D，C，B，F）的最长公共子序列时c[i][j] 的值。（20分）
解：
C[i,j]: 保存Xi与Yj的LCS（最长公共系序列）的长度
递归法递推表达式：

动态规划法递推表达式：

算法：
void LCSLength(int m，int n，char *x，char *y，int**c，int**b)
{
inti，j;
for (i= 1; i<= m; i++) c[i][0] = 0;
for (i= 1; i<= n; i++) c[0][i] = 0;
for (i= 1; i<= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) {
c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) {
c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; }
}
}
构造最长公共子序列
void LCS(inti，intj，char *x，int**b)
{
if (i==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b);
}
4、用回溯法解0-1背包问题，针对实例画出问题的搜索和剪枝过程。（20分）
解：
一个例子（老师PDF）：
n=5，c=10，w={2，2，6，5，4}，v={6，3，5，4，6}
初始时p[6]={(0,0)}，(w5,v5)=(4,6)。因此，q[6]=p[6]Å(w5,v5)={(4,6)}；
p[5]={(0,0),(4,6)}；
q[5]=p[5]Å(w4,v4)={(5,4),(9,10)}。从跳跃点集p[5]与q[5]的并集p[5]Èq[5]={(0,0),(4,6),(5,4),(9,10)}中看到跳跃点(5,4)受控于跳跃点(4,6)。将受控跳跃点(5,4)清除后，得到p[4]={(0,0),(4,6),(9,10)}
q[4]=p[4]Å(6，5)={(6，5)，(10，11)}
p[3]={(0，0)，(4，6)，(9，10)，(10，11)}
q[3]=p[3]Å(2，3)={(2，3)，(6，9)}
p[2]={(0，0)，(2，3)，(4，6)，(6，9)，(9，10)，(10，11)}
q[2]=p[2]Å(2，6)={(2，6)，(4，9)，(6，12)，(8，15)}
p[1]={(0，0)，(2，6)，(4，9)，(6，12)，(8，15)}
p[1]的最后的那个跳跃点(8,15)给出所求的最优值为m(1, c)=15
5、试用优先队列式分支限界算法解旅行商问题，给出针对下图实例的解空间树的扩展过程与队列变化状态。（15分）
解：
一个例题：

6、设f(x)是[0,2]上的连续函数，且，试利用概率算法计算定积分的近似值（设生成随机数的函数是已知的）。（15）
解：
（1）随机投点法计算定积分：
基本思想是在矩形区域上随机均匀的投点实现。本算法的基本思想是在积分区间上随机均匀的产生点, 即在[a,b]上随机均匀的取点, 求出由这些点产生的函数值的算术平均值, 再乘以区间宽度, 即可解出定积分得近似解。

随机化算法 ：用随机投点法计算定积分：
#include "stdafx.h"  
#include "RandomNumber.h"  
#include <iostream>  
using namespace std;   
double Darts(int n,double a,double b);  
double f(double x);  
int main()  
{  
    int n1 = 100,n2 = 1000,n3 = 1000,n4 = 10000,n5 = ;  
    double a = 2.0,b = 3.0;  
    cout<<"n1="<<n1<<",r1="<<Darts(n1,a,b)<<endl;  
    cout<<"n2="<<n2<<",r2="<<Darts(n2,a,b)<<endl;  
    cout<<"n3="<<n3<<",r3="<<Darts(n3,a,b)<<endl;  
    cout<<"n4="<<n4<<",r4="<<Darts(n4,a,b)<<endl;  
    cout<<"n5="<<n5<<",r5="<<Darts(n5,a,b)<<endl;  
    return 0;  
}   
/* 
 * 基本思想是在矩形区域内随机均匀投点，求出由这些点 
 * 产生的函数值的算术平均值，再乘以区间宽度，即可得 
 * 出定积分的近似解 
 */  
double Darts(int n,double a,double b)  
{  
    static RandomNumber dart;  
    double sum = 0.0;  
    for(int i=0; i<n; i++)  
    {  
        double x = (b-a)*dart.fRandom() + a;//产生[a,b)之间的随机数  
        sum = sum + f(x);  
    }  
    return (b-a)*sum/n;  
} 
double f(double x)  
{  
    return x*x;  
}  
（2）概率法计算定积分：
 设f:[a,b]→[c,d]连续函数(如图2 所示), 则由曲线y=f(x)以及x 轴和直线x=a,x=b 围成的面积由定积分给出。根据几何概型可知。假设向矩形区域随机均匀的投镖n 次, 落入阴影为K次, 又设M为x=a、x=b、y=c、y=d 所围成的矩形面积, s 为定积分面积,则, 所以s= k/n×M。

具体实现：
1. //随机化算法 用概率法计算定积分  
2. #include "stdafx.h"  
3. #include "RandomNumber.h"  
4. #include <iostream>  
5. using namespace std;  
6.   
7. double Darts(int n,double a,double b,double d);  
8. double f(double x);  
9.   
10. int main()  
11. {  
12.     int n1 = 100,n2 = 1000,n3 = 1000,n4 = 10000,n5 = ;  
13.     double a = 2.0,b = 3.0;  
14.     double d = f(b);  
15.     cout<<"n1="<<n1<<",r1="<<Darts(n1,a,b,d)<<endl;  
16.     cout<<"n2="<<n2<<",r2="<<Darts(n2,a,b,d)<<endl;  
17.     cout<<"n3="<<n3<<",r3="<<Darts(n3,a,b,d)<<endl;  
18.     cout<<"n4="<<n4<<",r4="<<Darts(n4,a,b,d)<<endl;  
19.     cout<<"n5="<<n5<<",r5="<<Darts(n5,a,b,d)<<endl;  
20.     return 0;  
21. }  
22.   
23. /* 
24.  * f 为积分函数, n 为投镖 
25.  * 总数, a,b 为积分区间, c,d 为函 
26.  * 数f 的值域的端点值 
27.  */  
28. double Darts(int n,double a,double b,double d)  
29. {  
30.     static RandomNumber dart;  
31.     int k = 0;  
32.     for(int i=0; i<n; i++)  
33.     {  
34.         double x = (b-a)*dart.fRandom() + a;//产生[a,b)之间的随机数  
35.         double y = d * dart.fRandom();  
36.   
37.         if(y<=f(x))  
38.         {  
39.             k++;  
40.         }  
41.     }  
42.     return d*(b-a)*k/n;  
43. }  
44.   
45. double f(double x)  
46. {  
47.     return x*x;  
48. }  

写作不但能培养学生的观察力、联想力、想象力、思考力和记忆力，它的重要性更表现在于学生对字词句的运用、对思想语言和口头语言的提炼、对现实生活知识经验的总结升华、对情感价值观的宣泄。learning education, need three kinds of consciousness: one is to establish an integrated awareness. "Learning" and "do" what car isTwo-wheel, bird wings, need to go hand in hand, one end can be neglected. Communist theoretician and man. Only by closely combining theory and practice together in order to truly realize their value. "Learning" is the Foundation, the Foundation is not strong, shaking; " "Is the key to net to net thousands of accounts. 　　 "Two" education, "" lay the basis, going to "do" the key grip, so that the "learning" and "doing" back to standard, so that the majority of party members "learn" learning theory of nutrients, in the "doing" practice party's purposes. Second, to establish a sense of depth. "Learning" and "do" not Chu drawn, entirely different, but the organic unity of the whole. "Two" learning education, we need to explore integrating "learning" in "do", exhibit "do" in "Science". To avoid the "learning" into simple room instruction, "do" into a monotone for doing. 　　 Should exploration "learn" in the has "do", "do" in the has "learn" of education and practice of carrier, makes general grass-roots members can in "learn" in the has "do" of achievements sense, in "do" in the has "learn" of get sense, real makes party of theory brain into heart, put for people service concept outside of Yu shaped. Third, to adhere to long-term the awareness. Style construction on the road forever, "two" had to catch the long-term. "Two" study and education, by no means, assault-style wind-sport, but the recurrent education within the party. In recent years, the party's mass line education practice and "three-three" special education in grass-roots borne rich fruits, vast numbers of party members and cadres withstood the baptism of the spirit. "Two" greater need to focus on longer hold long-term, to establish and perfect the effective mechanism of the education, focusing on the creation of long-term education, strive to make the vast number of party members to maintain their vanguard Color, maintain the party's advanced nature and purity. Awareness-raising, antennas and atmosphere – a discussion on how leading cadres of party members "two" current, "two" activity is in full swing up and down the country, party cadres as a "key minority" is both a barometer and impetus. The "two" meaning enough deep, is to determine the party cadres can resolve to study hard first. In the "two" in the process, some cadres of himself, standing long, high awareness, that Constitution Party rules is simple, its not worth bothering some party cadres think speak series has nothing to do with the grass-roots work, water business learning series of speeches seen as window dressing. These "lazy, casual, and decadent" ideas learning lacks motivation, a serious impediment to "two" effect. John Stuart Mill once said, only a basic element of human thought patterns change dramatically, human destiny can make great improvement. The same, only party members and