F0=0， Fl=1， Fn=Fn-1+Fn-2, n=2,3... 请就此斐波那契数列，回答下列问题。
(1) 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?, Fl, F0精确计算多少次? (2) 如果用大O表示法，试给出递归计算Fn时递归函数的时间复杂度录多少? 【解答】
（1）由斐波那契数列的定义可得： 1. Fn=Fn-1+Fn-2 =2Fn-2+Fn-3 =3Fn-3+2Fn-4 =5Fn-4+3Fn-5 ?? =pF1+qF0
设Fm的执行次数为Bm(m=0、1、2、?、n-1)，由以上等式可知，Fn-1被执行一次，即Bn-1=1；Fn-2被执行两次，即Bn-2=2；直至F1被执行p次、F0被执行q次，即B1=p，B0=q。Bm的执行次数为前两等式第一因式系数之和，即Bm=Bm-1+Bm-2，再有Bn-1=1和Bn-2=2，这也是一个斐波那契数列。可以解得：
（2）时间复杂度为O(n)
六、程序填空题（或算法阅读题） 1．void DD ( ) {
ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9);
for ( int i=0; i<10; i++) cout< 调用该算法后，输出结果为： 【解答】1 2 3 4 5 6 7 8 9 10 七、算法设计题 1. 已知输入x，y，z三个不相等的整数，设计一个“高效”算法，使得这三个数按从小到大输出。“高效”的含义是用最少的元素比较次数、元素移动次数和输出次数。 【解答】 void Best() {//按序输出三个整数的优化算法 int a,b,c,t; scanf(“%d%d%d”,&a,&b,&c); if(a>b) 11 {t=a; a=b; b=t:} //a和b已正序 if(b>c) {t=c; c=b; //c已到位 if(a>t) {b=a; a=t;} //a和b已正序 else b=t; } printf(“%d,%d,%d\\n”,a,b,c); //最佳2次比较，无移动；最差3次比较，7个赋值 } 2. 在数组A[n]中查找值为k的元素，若找到则输出其位置i(1≤i≤n)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。 【题目分析】从后向前查找，若找到与k值相同的元素则返回其位置，否则返回0。 【解答】 int Search(ElemType A[n+1], ElemType k) {i=n; while(i>=1)&&(A[i]!=k)) i--; if(i>=1) return i; else return 0; } 当查找不成功时，总的比较次数为n+1次，所以最坏情况下时间复杂度为O(n)。 在学过第 9 章 “查找”后，可优化以上算法:设“监视哨”。算法如下： int Search(ElemType A[n+1], ElemType k) {i=n; A[0]=k; while(A[i]!=k) i--; return i; } 研究表明，当n>=1000时，算法效率提高50%。 12
