算法设计与分析复习题
1、一个算法应有哪些主要特征？
有限性、确定性、输入、输出、可行性
2、分治法（Divide and Conquer）与动态规划（Dynamic Programming）有什么不同？ 分治法是将一个问题划分成一系列独立的子问题，分别处理后将结果组合以得到原问题的答案。动态规划同样将一个问题划分成一系列子问题进行处理，但当子问题不是互相独立而是互有联系时，动态规划不会重复计算子问题间联系的问题，是更高效的解决办法。
3、试举例说明贪心算法对有的问题是有效的，而对一些问题是无效的。 贪心算法的思想是通过选择局部最优以求得最优解，但某些最优解问题无法由局部最优推出，如0-1 knapsack problem（背包问题，一个能装20斤的背包装入一定商品，要求价值最高） 4、编写一个递归算法求解Hanoi 塔问题。 #include
printf(\}
void hanoi(int n,char x,char y,char z) { if(n==1) move(x,z); else { } } int main()
hanoi(n-1,x,z,y); move(x,z); hanoi(n-1,y,x,z);
{ int n;
printf(\ scanf(\ hanoi(n,'A','B','C'); return 0; }
5、求解方程f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1。 X^2=X+1 解得
X1=(1+√5)/2,，X2=(1-√5)/2。 则F(n)=C1*X1^n + C2*X2^n。 ∵F⑴=F⑵=1。 ∴C1*X1 + C2*X2。 C1*X1^2 + C2*X2^2。 解得C1=√5/5，C2=-√5/5。
∴F(n)=（√5/5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}（√5表示根号5）。 6、求解方程T(n)=2T(n/2)+1，T(1)=1，设n=2k。 T(n)=2n-1;(不确定)
7、求解方程T(n)=aT(n/b)+n，T(1)=1，设n=2k。
8、编写一个Quick Sorting 算法，并分析时间复杂性。 #include
#define M 100000 using namespace std;
int partition(double a[],int p,int r); void quicksort(double a[],int p,int r); int main()
{
double a[M]; srand(time(0)); printf(\ for (int i=0;i quicksort(a,0,M-1); if(i==0) printf(\else printf(\} a[i]=rand()-5000; a[i]+=rand()/10000.0; if(i==0) printf(\else printf(\ cout< return 0; } void quicksort(double a[],int p,int r) { int q; if(p int partition(double a[],int p,int r) { double x=a[r]; int i=p-1; for (int j=p;j<=r-1;j++) { } double temp=a[i+1]; //将作为基准的最后一个数交换到合适位置 a[i+1]=a[r]; a[r]=temp; double temp=a[i]; //将比最后一个数大的数交换到后面去 a[i]=a[j]; a[j]=temp; } if (a[j]<=x) {i++; { } q=partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); return i+1; } 最坏时间复杂度为O(n^2)（每次选中的中间元素为序列的最小或最大元T(n)=T(n-1)+T(0)+O(n)） 最好时间复杂度为O(nlogn)（每次选中的中间元素为序列的正中元素T(n)<=2T(n/2)+O(n)） 平均时间复杂度为O(nlogn)（不会分析??） 9、利用Quick Sorting的原理，编写一个查找第k小元素的算法。 double quicksortk(double a[],int p,int r,int k) { int q; q=partition(a,p,r); if((q+1)==k) { } else if ((q+1)>k) return quicksortk(a,p,q-1,k); else return quicksortk(a,q+1,r,k); } 10、 编写一个Heap Sorting算法，并分析时间复杂性。 int heapsize=0; int alength=M-1; cout<<\return a[q];