分治算法經(jīng)典問題算法循環(huán)賽程表歸并排序快速排序二分搜索二分遞歸大數(shù)乘法棋盤覆蓋

循環(huán)賽程表#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時(shí)返回其在數(shù)組中的位置，否則返回-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時(shí)返回其在數(shù)組中的位置，否則返回-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);}}大數(shù)乘法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:棋盤左上角的行號(hào)和列號(hào)c2,r2:特殊方格的行號(hào)和列號(hào)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//不在此棋盤，將此棋盤右下角設(shè)為相應(yīng)的骨牌號(hào){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//不在此棋盤，將此棋盤左下角設(shè)為相應(yīng)的骨牌號(hào){ 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//不在此棋盤，將此棋盤右上角設(shè)為相應(yīng)的骨牌號(hào){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//不在此棋盤，將此棋盤左上角設(shè)為相應(yīng)的骨牌號(hào){board[r1+half_size][c1+half_size]=d;chessboard(r1+half_size,c1+half_size,r1+half_size,