Java编写分治策略算法
**分治策略运用练习**
一、实验目的
本次实验是针对分治策略运用的算法设计及应用练习，旨在加深学生对该部分知识点的理解，提高学生运用该部分知识解决问题的能力。
二、 实验项目
1．对用户输入的杂乱无序的数字序列按照由小到大的顺序排序。要求分别运用合并排序和快速排序完成该题目要求。
2．棋盘覆盖问题。（要求N可由用户输入）
三、实验过程
（一）题目一：数字排序
-
题目分析
用合并排序和快速排序的方法使得杂乱无序的数字序列按照由小到大的顺序排序。 -
算法构造
在此论证算法设计中的一些必要的设计依据。
（1）在保证元素多于一个的同时，取中点把元素分成两个子序列，然后将它们排好序之后进行合并：
if (left < right)}{
Type* b = new Type[right - left + 1];
int i = (left + right) / 2;
MergeSort(a, left, i);
MergeSort(a, i + 1, right);
Merge(a, b, left, i, right);
Copy(a, b, left, right);}
（2）从第一个数据开始依次与其它的数据比较，比它小的放左边，比它大的放右边，然后在两个子序列中用同样的方法进行数据比较：
while (i != j){
while (a[j] >= t && j > i)
j–;
if (j > i)
a[i++] = a[j];
while (a[i] <= t && j > i)
i++;
if (j > i)
a[j–] = a[i];} -
算法实现
程序源代码（请写入必要的注释）。
（1）合并排序
package com.cn;
import java.util.Arrays;
import java.util.Scanner;
public class OrderMerging {
static int [] num=new int[10];
private static void FenZhi(int[] array,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
FenZhi(array,left,mid,temp);//左边合并排序，使得左边的集合有序排列
FenZhi(array,mid+1,right,temp);//右边合并排序，使得右边的集合有序排列
orderMerging(array,left,mid,right,temp);//将两个有序子数组合并操作
}
}
public static void BuiltArray(int []array){
int []temp = new int[array.length];//在排序前，先建立一个定长的数组，简化实现过程
FenZhi(array,0,array.length-1,temp);
}
private static void orderMerging(int[] array,int left,int mid,int right,int[] temp){
int i = left;//左哨兵
int j = mid+1;//分割之后的右哨兵
int t = 0;//识别数组中位置的哨兵
while (i<=mid && j<=right){
if(array[i]<=array[j]){
temp[t++] = array[i++];
}else {
temp[t++] = array[j++];
}
}
while(i<=mid){//将左边剩余元素放入temp中
temp[t++] = array[i++];
}
while(j<=right){//将右序列剩余元素放入temp中
temp[t++] = array[j++];
}
t = 0;
//将temp中的元素全部合并到原数组中
while(left <= right){
array[left++] = temp[t++];
}
}public static void main(String []args){
System.out.println(“请输入无序的数字串：”);
Scanner scan=new Scanner(System.in);
for(int i=0;i<=9;i++){
num[i]=scan.nextInt();
}
System.out.println(“排序后的数列如下：”);
BuiltArray(num);
System.out.println(Arrays.toString(num));}
}
（2）快速排序
package com.cn;
public class QuickSort {
//arr 需要排序的数组
//low 开始时最左边的索引=0
//high 开始时最右边的索引=arr.length-1
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;//左边哨兵的索引
j=high;//右边哨兵的索引
//temp就是基准位
temp = arr[low];//以最左边为 基准位
while (i<j) {
//先看右边，依次往左递减
//先从右往左找一个小于 基准位的数
//当右边的哨兵位置所在的数>基准位的数 时
//继续从右往左找（同时 j 索引-1）
//找到后会跳出 while循环
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
//步骤和上面类似
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
//z、y 都是临时参数，用于存放 左右哨兵 所在位置的数据
int z = arr[i];
int y = arr[j];
// 左右哨兵 交换数据（互相持有对方的数据）
arr[i] = y;
arr[j] = z;
}
}
//这时 跳出了 “while (i<j) {}” 循环
//说明 i=j 左右在同一位置
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];//或 arr[low] = arr[j];
arr[i] = temp;//或 arr[j] = temp;
//i=j
//这时 左半数组<(i或j所在索引的数)<右半数组
//也就是说(i或j所在索引的数)已经确定排序位置， 所以就不用再排序了，
// 只要用相同的方法 分别处理 左右数组就可以了
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
- 运行结果
合并拍序
快速排序
对 int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};这个无需的数组进行排序
-
经验归纳
主要是理解合并排序和快速排序的算法思想，是对分治思想（分解，求解，合并）的应用。
（二）题目二：棋盘覆盖 -
题目分析
棋盘覆盖问题需要判断特殊方块所在的位置，每次都对分割后的四个小方块进行判断，判断特殊方格是否在里面。如果特殊方块在里面，这直接递归下去求即可，如果不在，这根据分割的四个方块的不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继续递归。 -
算法构造
在此论证算法设计中的一些必要的设计依据。
定义棋盘的大小：size=(int)pow(2.0,(int)n);
判断算法在哪个位置（其中一个）：if (dr < tr + s && dc < tc +s)
{
chessBoard(tr,tc,dr,dc,s);
}
else
{
chess[tr+s-1][tc+s-1] = t;
chessBoard(tr,tc,tr+s-1,tc+s-1,s); -
算法实现
程序源代码（请写入必要的注释）。
package com.cn;
import java.util.Scanner;
public class CheckerBoard {static int Board[][]=new int[50][50];
static int L=1;
public static void checkerBoard(int zsh, int zsl, int dr, int dc, int size){
// zsh:棋盘左上角方格的行号
// zsl:棋盘左上角方格的列号
// dr:标记块的行号
// dc:标记块的列号
if(size==1){ //棋盘方格大小为,说明递归到最里层
return;
}
int t=L++; //每次都加一，为了显示分治的次序
int s=size/2; //将棋盘进行
if(dr<zsh+s && dc<zsl+s){ //划分左上方的棋盘
checkerBoard(zsh, zsl, dr, dc, s);
}
else{ //用L型快覆盖右下角
Board[zsh+s-1][zsl+s-1]=t;
checkerBoard(zsh, zsl, zsh+s-1, zsl+s-1, s);
}
if(dr<zsh+s && dc>=zsl+s){ //划分右下方的棋盘
checkerBoard(zsh, zsl+s, dr, dc, s);
}
else{ //用L型快覆盖右下角
Board[zsh+s-1][zsl+s]=t;
checkerBoard(zsh, zsl+s, zsh+s-1, zsl+s, s);
}
if(dr>=zsh+s && dc<zsl+s){ //划分左下方的棋盘
checkerBoard(zsh+s, zsl, dr, dc, s);
}
else{ //用L型快覆盖右上角
Board[zsh+s][zsl+s-1]=t;
checkerBoard(zsh+s, zsl, zsh+s, zsl+s-1, s);
}
if(dr>=zsh+s && dc>=zsl+s){ //划分右下方的棋盘
checkerBoard(zsh+s, zsl+s, dr, dc, s);
}
else{ //用L型快覆盖左上角
Board[zsh+s][zsl+s]=t;
checkerBoard(zsh+s, zsl+s, zsh+s, zsl+s, s);
}}
public static void main(String[] args) {
int n;
int size;//棋盘大小
System.out.println(“请输入棋盘规格数n(n行n列)”);
Scanner scanner=new Scanner(System.in);
n=scanner.nextInt();
int x,y;
size=(int) Math.pow(2.0,n);
System.out.println(“请输入标记点位于的行号：”);
Scanner scanner1=new Scanner(System.in);
x=scanner1.nextInt()-1;
System.out.println(“输入标记点的列号：”);
Scanner scanner2=new Scanner(System.in);
y=scanner2.nextInt()-1;
checkerBoard(0,0,x,y,size);
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
System.out.println(Board[i][j]+"-");
}
System.out.println();
}
}
}
4. 运行结果
- 经验归纳
主要是分治思想，此问题的关键是要判断出特殊方块所在的位置，然后运用递归把所有情况都考虑一 遍就行了。
五、实验总结
这两个实验都用到了分治思想和递归思想。
第一题合并排序是将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
第二题要分四种情况（特殊方块可能在左上角、右上角、左下角、右下角）讨论。
本文地址：https://blog.csdn.net/qq_45152962/article/details/109645643