mataqipanqiujiewenti1.java

算法分析实验 java实现： 有： 公约数 合并算法 字符排序 快速排序 马踏棋盘问题 马踏棋盘问题（文本做法） 折半查找 最大子段和

import java.applet.Applet;
import java.awt.Graphics;
import java.awt.Color;
import javax.swing.JOptionPane;
import java.awt.Font;


//提供二元型数值
class Pair
{
 private int x;
 private int y;
// Pair()
// {
// }
 Pair(int a,int b)
 {
  x=a;
  y=b;
 }
 public int getX()
 {
  return x;
 }
 public int getY()
 {
  return y;
 }
}

//提供巡游结果
class GetKnightCruise
{
 //存储8*8棋盘上各位置为第几步
 private static int[][] arr=new int[8][8];
 //用来存储骑士可以到达的8个位置的偏移量
 private static Pair[] index=new Pair[8];
 //设置index的初始值
 
 int a,b;
 private static void setIndex()
 {
  index[0]=new Pair(-2,1);
  index[1]=new Pair(-1,2);
  index[2]=new Pair(1,2);
  index[3]=new Pair(2,1);
  index[4]=new Pair(2,-1);
  index[5]=new Pair(1,-2);
  index[6]=new Pair(-1,-2);
  index[7]=new Pair(-2,-1);
 }
 //设置棋盘位置的处始值
 private static void setArr()
 {
 
  for (int i=0;i<8;i++)
  {
   for (int j=0;j<8;j++)
   {
    arr[i][j]=0;
   }
  }
 
 }
 //计算位置（i,j）的出口数
 private static int getExitNum(int i,int j)
 {
  int num=0;
  for(int t=0;t<8;t++)
  {
   if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
   {
    num++;
   }
  }
  return num;
 }
 //选择下一个所走的位置，beginIndex的作用是定位选择优先权的起始位置
 private static Pair getNextPositioin(int i,int j,int beginIndex)
 {
  int[] temp=new int[8];
  int min=8;
  for(int t=0;t<8;t++)
  {
   if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
   {
    temp[t]=getExitNum(i+index[t].getX(),j+index[t].getY());
    if(temp[t]!=0&&temp[t]<min)
    {
     min=temp[t];
    }
   }
  }
  for(int t=0;t<8;t++)
  {
   int h=(t+beginIndex)%8;
   if(temp[h]==min)
   {
    return new Pair(i+index[h].getX(),j+index[h].getY());
   }
  }
  return new Pair(-1,-1);
 }
 //寻找下一个唯一的出口（主要给最后一步使用，因为getNextPositioin已经不适合了）
 private static Pair getNextPositioinOfTheLastStep(int i,int j)
 {
  for(int t=0;t<8;t++)
  {
   if(i+index[t].getX()>=0&&i+index[t].getX()<=7&&j+index[t].getY()>=0&&j+index[t].getY()<=7&&arr[i+index[t].getX()][j+index[t].getY()]==0)
   {
    return new Pair(i+index[t].getX(),j+index[t].getY());
   }
  }
  return new Pair(-1,-1);
  
 }
 //从（i,j）开始骑士巡游
 static int[][] getKnightCruise(int i,int j)
 { 
  Pair tt;
  setArr();
  setIndex();
  for(int q=0;q<8;q++)
  {
   int ii=i,jj=j;
   int p=0;
   for(p=1;p<=64;p++)
   {
    arr[ii][jj]=p;
    if(p==63)
    {
     tt=getNextPositioinOfTheLastStep(ii,jj);
     ii=tt.getX();
     jj=tt.getY();
     continue;
    }
    tt=getNextPositioin(ii,jj,p);
    ii=tt.getX();
    jj=tt.getY();
    if(ii==-1||jj==-1)
    {
     break;
    }
   }
   if(p==65)
   {
 // return; 
    return arr;
   }
  }
    return arr;
 }
 //得到巡游数组
 public static int[][] getResult()
 {
 // int i=0,j=0;
  int i=1,j=1;
  getKnightCruise(i,j);
  return arr;
 }
}


public class mataqipanqiujiewenti1 extends Applet
{
 String xString=JOptionPane.showInputDialog(null,"输入起点坐标X:","X:",JOptionPane.QUESTION_MESSAGE); 
 int b=Integer.parseInt(xString);	
 String yString=JOptionPane.showInputDialog(null,"输入起点坐标Y:","Y:",JOptionPane.QUESTION_MESSAGE);
 int a=Integer.parseInt(yString); 	 
 public void paint(Graphics g)
 {
  setBackground(Color.gray);
  for(int i=1;i<=8;i++)
  {
   for(int j=1;j<=8;j++)
   {
    if((((i%2)==1)&&((j%2)==0))||(((i%2)==0)&&((j%2)==1)))
    {
     g.setColor(Color.black);
     g.fillRect(i*60+180,j*60,60,60);
    }
    else
    {
     g.setColor(Color.white);
     g.fillRect(i*60+180,j*60,60,60);
    }
   }
  }
  Font num1=new Font("宋体",Font.BOLD,30);
  g.setFont(num1);
  g.setColor(Color.green);
  g.drawString("马踏棋盘：",400,40);
  Font num2=new Font("宋体",Font.BOLD,15);
  g.setFont(num2);
  g.setColor(Color.black);
  g.drawString("****-*-*******",750,520);
  g.drawString("***",750,500);
  
  g.setColor(Color.gray);
  for(int i=0;i<8;i++)
  {
   for(int j=0;j<8;j++)
   {
    g.fillOval(250+i*60,70+j*60,35,35);
   }
  }
  g.setColor(Color.black);
  int[][] board=new int[8][8];
  board=GetKnightCruise.getKnightCruise(a,b);
  Font num=new Font("宋体",Font.BOLD,15);
  g.setFont(num);
  for(int i=0;i<8;i++)
  {
   for(int j=0;j<8;j++)
   {
    g.drawString(board[i][j]+"",258+i*60,90+j*60);
   }
  }
        return;
 }
}