10计本算法实验棋盘覆盖问题
更新时间:2023-03-20 07:50:01 阅读量: 实用文档 文档下载
- 钢管计重算法推荐度:
- 相关推荐
实验报告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。(粗心)
三.其实老师讲的非递归算法可以不用给我们代码,让我们自己去想,更有助于我们思维能力的提高,就只要在上课的时候把算法讲清楚就好了。这样子更能检查同学们对上课的内容的理解程度;不然就算同学们有去做,也是老师做的。(个人感觉)
正在阅读:
10计本算法实验棋盘覆盖问题03-20
公共政策分析简答题03-09
新视野2 读写教程答案(2)05-03
树木大苗培育要领10-11
33225-00_现代市场营销调查与预测_赵轶_模拟试题06-21
月收入2000元的理财规划07-19
八年级语文记叙文阅读的基本思路与答题方法人教实验版知识精讲03-29
我的心“打一字”02-08
超星尔雅幸福心理学答案201712-08
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 棋盘
- 算法
- 覆盖
- 实验
- 问题
- 北师大版2019-2020年五年级下学期语文开学考试B卷B卷
- 高一历史必修一复习提纲(1
- 【结局】刘谦魔术揭秘大汇总
- 摄影测量学考试重点
- 《全国医疗服务价格项目规范》(2010版)
- 有机产品认证加工业调查表
- 北京地铁运营管理模式交流
- 国家电网1000kV特高压交流输变电工程张力架线施工方案
- 公众演说技巧(演说准备)上
- 2808-甘肃省平凉市2010年第六次全国人口普查主要数据公报
- 城市综合体招商策划前期定位
- 吊耳局部有限元建模技术分析
- 高校教师绩效考核:教师教学工作评价的问题与改进建议——基于样本高校的实证分析
- 事业单位会计分录业务处理汇总
- 2011年7月国资委中央直属大型国有企业名单
- 睿高猎头服务流程
- 中石油_司库进行时
- 语文二年级下册期中阅读练习
- 实验四 触发器及其应用
- 基于GIS和VB_net的牧草种质资源数据库的研究与开发