27 55 50 65 38 49 13 13 图3.1 （b） 65 50 27 38 55 49 图3.1（c） 图3.1快速排序一次划分
在主函数里调用Quicksort，如图3.2主函数流程图
开始 个整数 输入N 调用QuickSort 输出数据 结束 图3.2 快速排序主流程图
5
3.代码实现
#include
void Swap(int &x,int &y) //交换x,y { }
int Partition(int a[],int p,int r)
//Partition 以确定一个基准元素a[q]对子数组a[p:r]进行划分 {
int temp=x; x=y; y=temp;
int i=p,j=r+1; int x=a[p];
//将
while(1) { }
while(a[++i]
Swap(a[i],a[j]); //交换a[i],a[j]
a[p]=a[j];a[j]=x; return j; //返回划分点 }
void QuickSort(int a[],int p,int r) //利用递归进行快速排序 {
if(p int q=Partition(a,p,r); //Partition返回划分点j，此处使q=j 6 } } QuickSort(a,p,q-1); QuickSort(a,q+1,r); int main() { } 3.2 棋盘覆盖问题 1.问题描述 在一个2×2个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为个特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有 k k int a[N],i,j; int len; printf(\请输入%d个整数:\\n\\n\\t\for(i=0;i scanf(\ QuickSort(a,0,N-1); //对数据进行快排 printf(\排序后的数据是:\\n\\n\\t\for(j=0;j printf(\ //顺序输出数据 printf(\return 0; 4k种情形。因而对任何k≥0，有4k种不同的特殊棋盘。用L型骨牌覆盖一个给定的 特殊棋盘上除特殊方格外的所有方格，且任何2个L型骨牌不得重叠覆盖。 用分治策略，设计棋盘覆盖问题的一个简捷的算法。 输入棋盘的规模k（k<5），棋盘为2×2，给出特殊方格的坐标(x，y)。输出棋盘并显示出各L型骨牌，将计算结果用数字表示，特殊方格用数字0显示。 2.解题思路 下面讨论棋盘覆盖问题中数据结构的设计。 7 k k （1）棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中，size=2。为了在递归处理的过程中使用同一个棋盘，将数组board设为全局变量； （2）子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上角的下标tr、tc和棋盘大小s表示； （3）特殊方格：用board[dr][dc]表示特殊方格，dr和dc是该特殊方格在二维数组board中的下标; （4） L型骨牌：一个2×2的棋盘中有一个特殊方格，所以，用到L型骨牌的个数为(4-1)/3，将所有L型骨牌从1开始连续编号，用一个全局变量t表示。 图3.3 棋盘覆盖问题中的数据结构 k k k k tc tdc dr siz 主函数流程图如图3.4所示。 图3.4 棋盘覆盖主流程图 8 开始 输入棋盘规模K 输入特殊方格坐标x,y 调用ChessBoard子函数输出棋盘数字 结束 3.代码实现 #include int tile=1; //记录骨牌的型号 int board[32][32]={0}; //存储棋盘被覆盖的情况 void ChessBoard(int tr,int tc,int dr,int dc,int size) { //tr和tc是棋盘左上角的下标,dr和dc是特殊方格的下标,size是棋盘的大小 int t=0; int s; if (size==1)return; t=tile++; s=size/2; //划分棋盘 //覆盖左上角棋盘 if (dr board[tr+s-1][tc+s-1]=t; ChessBoard(tr,tc,tr+s-1,tc+s-1,s); ChessBoard(tr,tc,dr,dc,s); else } //覆盖右上角棋盘 if (dr board[tr+s-1][tc+s]=t; ChessBoard(tr,tc+s,tr+s-1,tc+s,s); ChessBoard(tr,tc+s,dr,dc,s); else } //覆盖左下角棋盘 if (dr>=tr+s&&dc ChessBoard(tr+s,tc,dr,dc,s); else 9
分治法开放性实验报告-正文
