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

循环赛程表#defineMAXN64#defineMAX32inta[MAX][MAX];voidCopy(inttox,inttoy,intfromx,intfromy,intn){for(inti=0;i<n;i++)for(intj=0;j<n;j++)a[tox+i][toy+j]=a[fromx+i][fromy+j];}voidTable(intk,inta[][MAX]){inti,n=1<<k;intr;for(i=0;i<n;i++)a[0][i]=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}voidOut(inta[][MAX],intn){for(inti=0;i<n;i++){for(intj=0;j<n;j++)printf("%3d",a[i][j]);printf("\n");}printf("\n");getch();}voidmain(){inti;for(i=0;i<5;i++){intlen=1<<i;Table(i,a);Out(a,len);}}归并排序voidmerge(intdata[],intp,intq,intr){intn1=q-p+1;intn2=r-q;intL[n1],R[n2];for(inti=0,k=p;i<n1;i++,k++)L[i]=data[k];for(inti=0,k=q+1;i<n2;i++,k++)R[i]=data[k];for(intk=p,i=0,j=0;i<n1&&j<n2;k++){if(L[i]>R[j]){data[k]=L[i];i++;}else{data[k]=R[j];j++;}}if(i<n1){for(j=i;j<n1;j++,k++)data[k]=L[j];}if(j<n2){for(i=j;i<n2;i++,k++)data[k]=R[i];}}voidmerge_sort(intdata[],intp,intr){if(p<r){intq=(p+r)/2;merge_sort(data,p,q);merge_sort(data,q+1,r);merge(data,p,q,r);}}快速排序intpartition(intnumber[],intleft,intright){ints=number[right];inti=left-1;for(intj=left;j<right;j++)if(number[j]<=s){i++;SWAP(number[i],number[j]);}SWAP(number[i+1],number[right]);returni+1;}voidquicksort(intnumber[],intleft,intright){intq;if(left<right){q=partition(number,left,right);quicksort(number,left,q-1);quicksort(number,q+1,right);}}二分搜索（非递归）publicstaticintbinarySearch(int[]a,intx,intn){ //在a[0]<=a[1]<=...<=a[n-1]中搜索x//找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;while(left<=right){intmid=(left+right)/2;//mid=low+((high-low)/2);if(x==a[mid])returnmid;if(x>a[mid])left=mid+1;elseright=mid-1;}return-1;//未找到x}二分递归publicstaticintbinarySearch(inta[],intx,intleft,intright){ //找到x时返回其在数组中的位置，否则返回-1if(left>right)return-1;//未找到xelse {intmid=(left+right)/2; if(x==a[mid])returnmid; if(x>a[mid])returnbinarySearch(a,x,mid+1,right); elsereturnbinarySearch(a,x,left,mid);}}大数乘法intqiuweishu(longz){ intt=0;while(z>0){z=z/10;t++;}returnt;}main(){longx,y,a,b,c,d;doublez;printf("Pleaseinputthetwonumberxandy:\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("theresultis%ld:",z);}棋盘覆盖#defineBOARD_SIZE4intboard[BOARD_SIZE][BOARD_SIZE];//c1,r1:棋盘左上角的行号和列号c2,r2:特殊方格的行号和列号voidchessboard(intr1,intc1,intr2,intc2,intsize)//size=2^k{ if(1==size)return;inthalf_size;staticintdomino_num=1;intd=domino_num++;half_size=size/2;if(r2<r1+half_size&&c2<c1+half_size)//特殊方格在左上角子棋盘{chessboard(r1,c1,r2,c2,half_size);}else//不在此棋盘，将此棋盘右下角设为相应的骨牌号{board[r1+half_size-1][c1+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//不在此棋盘，将此棋盘左下角设为相应的骨牌号{ board[r1+half_size-1][c1+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//不在此棋盘，将此棋盘右上角设为相应的骨牌号{board[r1+half_size][c1+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//不在此棋盘，将此棋盘左上角设为相应的骨牌号{board[r1+half_size][c1+half_size]=d;chessboard(r1+half_size,c1+half_size,r1+half_size,