五种基本算法设计递归实现.docVIP

1. 二分有哪些信誉好的足球投注网站的递归和非递归实现算法； import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; //用BufferedReader进行输出 public class Test3_1 { public static void main(String[] args) { int list[]=new int[(int)(Math.random()*5)+5];//定义一个随机出现的数组 for (int i = 0; i list.length; i++) { list[i]=(int)(Math.random()*100)+1;//赋值 } Arrays.sort(list);//按照升序对所有元素进行排序 System.out.println(您待查找的数列为：); for (int i = 0; i list.length; i++) { System.out.print(list[i]+ );//输出已经排好的数组 } System.out.println(); BufferedReader buf=new BufferedReader(new InputStreamReader(System.in));//控制器输入 System.out.println(请输入您要查找的数字：); try { int x=Integer.parseInt(buf.readLine()); //int result=binarySearch(list, x); int result=diGuiBinarySearch(list, x, 0, list.length-1); int result1=result+1; if(result==-1) System.out.println(您要查找的数字不存在！); else System.out.println(您查找的数字在数组的下标为:+result); System.out.println(您查找的数字在数组的第:+result1+个); } catch (Exception e) { System.out.println(您输入的数字有误，请重新输入！); } } public static int binarySearch(int list[],int x) //非递归实现！大一学年中已经学过具体算法，二分查找 { int left=0; int right=list.length-1; int mind; while(left=right) { mind=(left+right)/2; if(x==list[mind]) return mind; else if(xlist[mind]) left=left+1; else right=right-1; } return -1; } public static int diGuiBinarySearch(int list[],int x,int l,int r) //递归实现！1，r分别为数组中的首尾元素 { if(lr) return -1;//返回错误 int m=(l+r)/2;//取中和x比较 if(x==list[m]) return m; else if(xlist[m])//以下为递归中元素的查找操作 return diGuiBinarySearch(list, x, l+1, r); else return diGuiBinarySearch(list, x, l, r-1); } } 2.棋盘覆盖的递归实现算法； import java.util.Scanner; //用Scanner输出流进行控制 输出 public class Test3_2 { private int qipan[][]; //用来表示棋盘 private int qipanSize; //表示棋盘的大小为2的多少次方 private int dr,dc; //棋盘中特殊方格的位置（行号、列号） private int tile;//骨牌标号 public Test3_2(){ qipan=new int[1][1]; dr=0;dc=0;qipanSize=0; }