分治算法经典问题算法：循环赛程表,归并排序,快速排序,二分搜索,二分递归,大数乘法,棋盘覆盖.doc
循环赛程表#define MAXN 64#define MAX 32 int aMAXMAX; void Copy(int tox, int toy, int fromx, int fromy, int n) for (int i=0; i<n; i+) for (int j=0; j<n; j+) atox + itoy + j = afromx + ifromy + j; void Table(int k, int aMAX) int i, n = 1 << k; int r; for (i=0; i<n; i+) a0i = i + 1; for (r=1; r<n; r<<=1) for (i=0; i<n; i+=2*r) Copy(r, i + r, 0, i, r); Copy(r, i, 0, i + r, r); /ENDFOR void Out(int aMAX, int n) for (int i=0; i<n; i+) for (int j=0; j<n; j+) printf("%3d", aij); printf("n"); printf("n");getch(); void main() int i; for (i=0; i<5; i+) int len = 1 << i; Table(i, a); Out(a, len); 归并排序void merge(int data, int p, int q, int r) int n1 = q - p + 1; int n2 = r - q; int Ln1,Rn2; for(int i = 0, k = p; i < n1; i+, k+) Li = datak; for(int i = 0, k = q + 1; i < n2; i+, k+) Ri = datak; for(int k = p, i = 0, j = 0; i < n1 && j < n2; k+) if(Li > Rj) datak = Li; i+; else datak = Rj; j+; if(i < n1) for(j = i; j < n1; j+, k+) datak = Lj; if(j < n2) for(i = j; i < n2; i+, k+) datak = Ri; void merge_sort(int data, int p, int r) if(p < r) int q = (p + r) / 2; merge_sort(data, p, q); merge_sort(data, q + 1, r); merge(data, p, q, r); 快速排序int partition(int number, int left, int right) int s = numberright; int i = left - 1; for(int j = left; j < right; j+) if(numberj <= s) i+; SWAP(numberi, numberj); SWAP( numberi+1, numberright ); return i+1; void quicksort(int number, int left, int right) int q; if(left < right) q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right); 二分搜索非递归public static int binarySearch(int a, int x, int n)/ 在 a0 <= a1 <= . <= an-1 中搜索 x/ 找到x时返回其在数组中的位置，否那么返回-1int left = 0; int right = n - 1;while (left <= right) int mid = (left + right)/2; / mid = low + (high - low) / 2); if (x = amid) return mid;if (x > amid) left = mid + 1;else right = mid - 1;return -1; / 未找到x二分递归public static int binarySearch(int a, int x, int left ,int right)/ 找到x时返回其在数组中的位置，否那么返回-1if (left>right) return -1; / 未找到xelse int mid = (left + right)/2; if (x = amid) return mid; if (x > amid) return binarySearch(a, x, mid+1,right); else return binarySearch( a,x,left,mid); 大数乘法int qiuweishu(long z) int t=0; while(z>0) z=z/10; t+; return t; main() long x,y,a,b,c,d; double z; printf("Please input the two number x and y:n"); scanf("%,%l",&x,&y); a=x/(long)pow10(qiuweishu(x)/2); b=x%(long)pow10(qiuweishu(x)/2); c=y/(long)pow10(qiuweishu(y)/2); d=y%(long)pow10(qiuweishu(y)/2); z=(double)(a*c*pow10(qiuweishu(x)+(a*d+b*c)*pow10(qiuweishu(x)/2)+b*d); /*z=(a*c*(long)pow10(qiuweishu(x)+(a-b)*(d-c)+a*c+b*d)*(long)pow10(qiuweishu(x)/2)+b*d);*/ printf("the result is %ld:",z); 棋盘覆盖#define BOARD_SIZE 4int boardBOARD_SIZEBOARD_SIZE;/ c1, r1: 棋盘左上角的行号和列号c2, r2: 特殊方格的行号和列号void chessboard(int r1, int c1, int r2, int c2, int size) / size = 2 k if(1 = size) return; int half_size; static int domino_num = 1; int d = domino_num+; half_size = size / 2; if(r2 < r1 + half_size && c2 < c1 + half_size) /特殊方格在左上角子棋盘 chessboard(r1, c1, r2, c2, half_size); else / 不在此棋盘，将此棋盘右下角设为相应的骨牌号 boardr1 + half_size - 1c1 + half_size - 1 = d; chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size); if(r2 < r1 + half_size && c2 >= c1 + half_size) /特殊方格在右上角子棋盘 chessboard(r1, c1 + half_size, r2, c2, half_size); else / 不在此棋盘，将此棋盘左下角设为相应的骨牌号 boardr1 + half_size - 1c1 + half_size = d; chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size); if(r2 >= r1 + half_size && c2 < c1 + half_size) /特殊方格在左下角子棋盘 chessboard(r1 + half_size, c1, r2, c2, half_size); else / 不在此棋盘，将此棋盘右上角设为相应的骨牌号 boardr1 + half_sizec1 + half_size - 1 = d; chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size); if(r2 >= r1 + half_size && c2 >= c1 + half_size) /特殊方格在左上角子棋盘 chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size); else / 不在此棋盘，将此棋盘左上角设为相应的骨牌号 boardr1 + half_sizec1 + half_size = d;chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size); /ENDint main() board22 = 0; chessboard(0, 0, 2, 2, BOARD_SIZE); for(i = 0; i < BOARD_SIZE; i+) for(j = 0; j < BOARD_SIZE; j+)printf("%-4d", boardij); printf("n");
