5. 2018/10/16计算机算法设计与分析5递归的概念简单地说，递归就是用自己来定义自己。
一般地说，一个递归过程P可以表示为基语句S(不含P)和P自身的组合β：
P β(S, P)
这样的表示包含了过程不终止的可能，因此递归算法应更准确地表述为P if B then Q else β(S, P)
其中Q也不包含P，B为递归终止条件。
13. 整数划分问题正整数n的划分数p(n)=q(n,n)。 int q(int n, int m) { if ((n < 1) || (m < 1)) return 0; if((n == 1) || (m == 1)) return 1; if(n < m) return q (n, n); if(n == m) return (q (n, m - 1) + 1); return (q (n, m-1)+ q( (n- m), m)); }
14. 2018/10/16计算机算法设计与分析14Hanoi塔问题例1：Hanoi塔问题：有A、B、C三根柱子。A上有n个圆盘，自下而上由大到小地叠在一起。ABC现要将A上的全部圆盘移到B上，并要求：(1)每次只能移动一个圆盘；(2)任何时刻都不允许将较大的圆盘压在较小的圆盘上；(3)圆盘只能在A、B、C三个柱子间移动。Hanoi塔的解可以很自然地看成这样一个过程：
(1)先将A上面n–1个盘借助 B移至C。 (2)再将A上剩下的1个盘移至B。 (3)最后将C上的n–1个盘借助A移至B。 于是可得到如下的程序：
void Hanoi(int n, int Fr, int To, int As)
{
if (n > 0) {
Hanoi(n–1, A, C, B);
Move(A, B);
Hanoi(n–1, C, B, A)}
}
41. 2018/10/16计算机算法设计与分析41二分搜索有序表的递归式算法int recursive_binary_search ( int a[] , int left , int right , int T ) { int k , mid; if ( left > right ) k = -1 ; //*数组中不存在T，返回-1
else
{mid = ( left + right ) / 2 ;//*取中点下标
if ( a[mid] == T ) k = mid ;
else if (a[mid] < T ) k = recursive_binary_search ( a , mid+1 , right , T ) ; else k = recursive_binary_search ( a , left , mid-1 ,T ) ; } return ( k ) ;//*返回T在数组a中位置的下标值 }
42. 2018/10/16计算机算法设计与分析42二分搜索有序表的非递归式算法int binary_search ( int a[] , int n , int T ) { int left , right , mid , k ; left = 0 ; right = n - 1 ; k = -1 ; while ( left <= right && k == -1 ) { mid = ( left + right ) / 2; if ( a[mid] == T ) k = mid ; else
if ( a[mid] > T ) right = mid-1; else left = mid+1 ; } return ( k ) ; }
43. 2018/10/16计算机算法设计与分析43二分搜索有序表的算法分析[n][n/2][n/2][n/4][n/4][n/4][n/4][1][1][1][1]log n + 1二分搜索的每次循环查找区间减半，查找区间构成一棵二叉树，最坏的情况是一直走到二叉树的叶子。因此算法的复杂度为 log n + 1。
44. 2018/10/16计算机算法设计与分析44二分搜索有序表的算法分析我们也可以根据递归算法列出如下的递归方程：W(n) =W( n/2) + 1 n > 1 1 n = 1由前面所学的求解递归方程的一般结论有：时间复杂度为O(log n)。
68. 2018/10/16计算机算法设计与分析68下面是划分的过程： void qkpass(int a[], int low, int high, int *T); /*在a[low..high]中找基准位置，使得基准前面的元素均小于等于基准值， 基准后面的元素均大于等于基准值，基准所在的位置由*T返回。*/
{ int temp;
temp=a[low]; /*以第一个元素为基准值，并把这个位置腾出来*/
while (low < high )
{ while (low < high && a[high]≥temp) high=high-1;
a[low]=a[high]; /* 找到一个比基准小的元素并把它放到空当*/
/*现在的空当在[high]处，如果不存在这样的元素，low=high*/
while (low < high && a[low]≤temp) low=low+1;
a[high]=a[low]; /*找到一个比基准大的元素并把它放到空当*/
/*现在的空当重新回到[low]处，如果不存在这样的元素，low=high*/ }
a[low]=temp;
*T=low; /*记录下基准的位置*/ }
75. 2018/10/16计算机算法设计与分析75循环赛日程表算法void arrange(int tab[n][n], int StartRow, int n) { if (n==2) { //将数组tab中指定大小(=1)的左上角复制到右下角 copy(tab, StartRow, 1, StartRow+1, 1); //将数组tab中指定大小的左下角复制到右上角 copy(tab,StartRow+1, 1, StartRow, 1); } else { n=n/2; arrange(tab, StartRow,n); //排列左上角 copy(tab,StartRow, n, StartRow+n, n); //把左上角复制到右下角 arrange(tab, StartRow+n,n); //排列左下角 copy(tab,StartRow+n , n, StartRow, n); //把左下角复制到右上角 } }
76. 2018/10/16计算机算法设计与分析76循环赛日程表算法其中的 copy()函数如下：
Void copy(int tab[n][n], int StartRow, int n , int DestRow, int DestCol) //StartRow是要复制的起始行,n表示要复制的行数，DestRow和DestCol是复制到的位置 {int i，r，j，c；
for(i=StartRow, r=DestRow; i
77. 2018/10/16计算机算法设计与分析77循环赛日程表算法 主函数调用如下：
void main() { int k, tab[n][n]; for(k=0;k
