10计本算法实验棋盘覆盖问题

实验报告2

课程 数据结构与算法 实验名称 递归与分治策略(二) 第 页 班级 10计本 学号 105032010111 姓名 陈兴灶

实验日期：2012年3月6日 报告退发 (订正 、 重做)

一、实验目的

掌握递归及分治策略的原理和应用。

二、实验环境

1、微型计算机一台

2、WINDOWS操作系统，Java SDK，Eclipse开发环境

三、实验内容

必做题：

1、编程实现二分搜索算法。

2、编程实现棋盘覆盖问题，现有四种类型的骨牌编号分别为1、2、3、4，请用这四种骨牌覆盖特殊棋盘，并输出结果。

3、编程实现合并排序的递归算法。

4、编程实现合并排序的非递归算法。

5、编程实现快速排序。

四、实验步骤和结果

第一题：

import java.util.Arrays;

import java.util.Scanner;

public class BinSearch {

/** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub public static int binsearch(int []a,int start,int stop,int b) { } if(start>stop)return -1; int i=(start+stop)/2; if(a[i]==b)return i; if(a[i]>b)return binsearch(a,start,i-1,b); return binsearch(a,i+1,stop,b);

Scanner sc=new Scanner(System.in); System.out.println("输入数组长度"); int n=sc.nextInt(); int a[]=new int [n]; System.out.println("输入数组元素"); for(int i=0;i<n;i++) a[i]=sc.nextInt(); Arrays.sort(a); System.out.println("排序后的数组为"); for(int i=0;i<a.length;i++) System.out.print(a[i]+" "); System.out.println();

System.out.println("输入要查找的数");

int b=sc.nextInt();

int x=binsearch(a,0,n-1,b);

if(x==-1)

{

System.out.println(b+"不在数组中，请输入另一个数"); b=sc.nextInt();

x=binsearch(a,0,n-1,b);

}

System.out.println(b+"在数组中的第"+(x+1)+"个位置");

}

}

结果：

第二题：棋盘覆盖

import java.util.Scanner;

public class ChessBoard1 {

public static int [][]board;

public static void chessboard(int tr,int tc,int dr,int dc,int size) {

if(size==1)return;

int s=size/2;

if(dr<tr+s&&dc<tc+s)

{

board[tr+s][tc+s-1]=1;

board[tr+s-1][tc+s]=1;

board[tr+s][tc+s]=1;

chessboard(tr,tc,dr,dc,s);

chessboard(tr+s,tc,tr+s,tc+s-1,s);

chessboard(tr,tc+s,tr+s-1,tc+s,s);

chessboard(tr+s,tc+s,tr+s,tc+s,s);

}

if(dr<tr+s&&dc>=tc+s)

{

}

if(dr>=tr+s&&dc<tc+s)

{

} board[tr+s-1][tc+s-1]=3; board[tr+s-1][tc+s]=3; board[tr+s][tc+s]=3; chessboard(tr+s,tc,dr,dc,s); chessboard(tr,tc,tr+s-1,tc+s-1,s); chessboard(tr,tc+s,tr+s-1,tc+s,s); chessboard(tr+s,tc+s,tr+s,tc+s,s); board[tr+s-1][tc+s-1]=2; board[tr+s][tc+s-1]=2; board[tr+s][tc+s]=2; chessboard(tr,tc+s,dr,dc,s); chessboard(tr,tc,tr+s-1,tc+s-1,s); chessboard(tr+s,tc,tr+s,tc+s-1,s); chessboard(tr+s,tc+s,tr+s,tc+s,s);

if(dr>=tr+s&&dc>=tc+s)

{

board[tr+s-1][tc+s-1]=4;

board[tr+s][tc+s-1]=4;

board[tr+s-1][tc+s]=4;

chessboard(tr+s,tc+s,dr,dc,s);

chessboard(tr,tc,tr+s-1,tc+s-1,s);

chessboard(tr+s,tc,tr+s,tc+s-1,s);

chessboard(tr,tc+s,tr+s-1,tc+s,s);

}

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

int n =sc.nextInt();

int a=sc.nextInt();

int b=sc.nextInt();

board=new int[n][n];

chessboard(0,0,a,b,n);

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

if(i==a&&j==b)

{

System.out.print("特殊"+" ");

continue;

}

if(board[i][j]<10)

System.out.print("0"+board[i][j]+" "

else

System.out.print(board[i][j]+" ");

}

System.out.println();

}

} );

}

结果：

第三题：合并排序的递归

import java.util.Scanner;

public class mergeSort {

{

}

public static void merge(int []c,int []d,int l,int m,int r)

{

int i=l;

int j=m+1;

int k=l;

while((i<=m)&&(j<=r)) if(left<right) { } int i=(left+right)/2; mergeSort1(a,left,i); mergeSort1(a,i+1,right); merge(a,b,left,i,right); copy(a,b,left,right); public static int []b; public static void mergeSort1(int []a,int left,int right)

if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++];

if(i>m)

for(int q=j;q<=r;q++)

d[k++]=c[q];

else

for(int q=i;q<=m;q++)

}

public static void copy (int []c,int []b,int left,int right)

{

}

public static void main(String[]args)

{

Scanner sc=new Scanner(System.in); int n=sc.nextInt(); b=new int[n]; int []a; a=new int [n]; for(int i=0;i<n;i++) { } a[i]=sc.nextInt(); for(int i=left;i<=right;i++) { } c[i]=b[i]; d[k++]=c[q];

mergeSort.mergeSort1(a,0,n-1);

for(int j=0;j<=n-1;j++)

System.out.print(a[j]+" ");

}

}

结果

第四题：合并排序的非递归

import java.util.Scanner;

public class MergeFDG {

public static void mergeFDG(int a[]) { } public static void mergePass(int []a,int []b,int s) { int i=0; while(i<=a.length-2*s) { } if(i+s<a.length) merge(a,b,i,i+s-1,a.length-1); for(int j=i;j<a.length;j++) b[j]=a[j]; else merge(a,b,i,i+s-1,i+2*s-1); i=i+2*s; int []b=new int[a.length]; int s=1; while(s<a.length) { } mergePass(a,b,s); s+=s; mergePass(b,a,s); s+=s;

} } public static void merge(int []c,int []d,int l,int m,int r) { int i=l; int j=m+1; int k=l; while((i<=m)&&(j<=r)) if(c[i]<=c[j]) d[k++]=c[i++]; else d[k++]=c[j++]; if(i>m) for(int q=j;q<=r;q++) d[k++]=c[q]; else for(int q=i;q<=m;q++) } /** * @param args */ public static void main(String[] args) { } // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); System.out.println("输入要排序的数组长度"); int n=sc.nextInt(); int []a=new int [n]; System.out.println("输入"+n+"个元素"); for(int j=0;j<n;j++) a[j]=sc.nextInt(); mergeFDG(a); System.out.println("排序后的数组为"); for(int i=0;i<a.length;i++) System.out.print(a[i]+" "); d[k++]=c[q];

结果：

第五题：快速排序

import java.util.Scanner;

public class QuickSort {

public static void quicksort(int p,int r) { } public static int partition(int p,int r) { } int i=p,j=r+1; int x=a[p]; while(true) { } a[p]=a[j]; a[j]=x; return j; while(a[++i]<x&&i<r); while(a[--j]>x); if(i>=j)break; int temp=a[i]; a[i]=a[j]; a[j]=temp; if(p<r) { } int q=partition(p,r); quicksort(p,q-1); quicksort(q+1,r); public static int []a;

} /** * @param args */ public static void main(String[] args) { } // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); System.out.println("输入要排序的数组长度"); int n=sc.nextInt(); a=new int[n]; System.out.println("输入"+n+"个元素"); for(int i=0;i<n;i++) a[i]=sc.nextInt(); quicksort(0,n-1); System.out.println("排序后的数组为"); for(int j=0;j<a.length;j++) System.out.print(a[j]+" ");

结果：

五、实验总结

一．第二题 中，如果把第二个if语句和第三个if语句对调下，结果就是错的。结果会变成这样子

这个问题还没考虑清楚。

二．对着书上的代码，把l当成了一，结果出来的全是0。（粗心）

三．其实老师讲的非递归算法可以不用给我们代码，让我们自己去想，更有助于我们思维能力的提高，就只要在上课的时候把算法讲清楚就好了。这样子更能检查同学们对上课的内容的理解程度；不然就算同学们有去做，也是老师做的。（个人感觉）

本文来源：https://www.bwwdw.com/article/emwj.html