分治算法经典问题算法：循环赛程表,归并排序,快速排序,二分搜索,二分递归,大数乘法,棋盘覆盖.doc

《分治算法经典问题算法：循环赛程表,归并排序,快速排序,二分搜索,二分递归,大数乘法,棋盘覆盖.doc》由会员分享，可在线阅读，更多相关《分治算法经典问题算法：循环赛程表,归并排序,快速排序,二分搜索,二分递归,大数乘法,棋盘覆盖.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、循环赛程表#define MAXN 64#define MAX 32 int aMAXMAX; void Copy(int tox, int toy, int fromx, int fromy, int n) for (int i=0; in; i+) for (int j=0; jn; j+) atox + itoy + j = afromx + ifromy + j; void Table(int k, int aMAX) int i, n = 1 k; int r; for (i=0; in; i+) a0i = i + 1; for (r=1; rn; r=1) for (i=0; i

2、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; in; i+) for (int j=0; jn; j+) printf(%3d, aij); printf(n); printf(n);getch(); void main() int i; for (i=0; i5; i+) int len = 1 i; Table(i, a); Out(a, len); 归并排序void merge(int data, int p, int

3、 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 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

4、= 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(nu

5、mberj = 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

6、, int n)/ 在 a0 = a1 = . = an-1 中搜索 x/ 找到x时返回其在数组中的位置，否那么返回-1int left = 0; int right = n - 1;while (left 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 (leftright) return -1; / 未找到xelse int mid

7、 = (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(z0) 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,

8、&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);

9、*/ 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 /

10、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 = c1 + half_size) /特殊方格在右上角子棋盘 chessboard(r1, c1 +

11、 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 = r1 + half_size & c2 = c1 + half_size) /特殊方格在左上角子棋盘 chessboard(r1 + half_size, c1 + half

12、_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);