Question

急!求Java试题答案（在下图中的九个点上，空出中间的点..）

谁做过这道题，请做过的高手给迅速解决下。本人高分悬赏。图我发不上来。抱歉。

在下图中的九个点上，空出中间的点，其余的点上任意填入数字1至8；1的位置保持不动，然后移动其余的数字，使1到8顺时针从小到大排列。移动的规则是：只能将数字沿线移向空白的点。请将制作好的源文件保存为“t2.java”。（本题共60分，要求1占20分，要求2占40分）
要求：
（1）分析问题，并描述你的算法设计思想。
（2）编程显示数字移动过程。
http://www.pcsjw.com/InfoView/131687.html
这上面的题和我的一样。看那个图。谢谢了。我实在是传不上来图片。

Answer 1

public class GuardQueue{
public static void main(String[] args){
SortedCircute sc=new SortedCircute(new int[]{8,5,2,4,7,3,1,6});
int[] result=sc.sort();
for(int i=0;i<result.length;i++){
System.out.print(result[i]);
}
System.out.println();
}
}
class SortedCircute{
private Element head;
private int count;
public SortedCircute(int[] values){
count=values.length;
Element previous,next=null;
head=previous=new Element(values[0]);
for(int i=1;i<count;i++){
next=new Element(values[i]);
previous.next=next;
next.previous=previous;
previous=next;
}
next.next=head;
head.previous=next;
Element e=head;
}
public int[] sort(){
int maxSteps=count*(count+1)/2,index=0;
int[] steps=new int[maxSteps];
Element start=head;
while(start.value!=1){
start=start.next;
}
Element center=new Element(0),temp;
for(int i=1;i<count;i++){
if(start.next.value!=i+1){
for(temp=start.next.next;temp.value!=i+1;temp=temp.next);
center.previous=temp;
start.next.previous=center;
temp=center;
do{
temp.value=temp.previous.value;
steps[index++]=temp.value;
temp=temp.previous;
}while(temp!=center);
start.next.previous=start;
}
start=start.next;
}
int[] result=new int[index];
System.arraycopy(steps,0,result,0,index);
return result;
}
public String toString(){
String result=String.valueOf(head.value);
Element e=head.next;
for(int i=1;i<count;i++){
result+="-"+String.valueOf(e.value);
}
return result;
}
class Element{
Element next,previous;
int value;
public Element(int value){
this.value=value;
}
}
}
方法：首先找到1的位置；假定在A处。
如果1的下一个（B）是2，就找3；否则，
从1的下一个开始，往下找到2，假定位置在C上。
C的2到空位，C的前一个到C，......，B到B的下一个，最后，2到B，2排好。以些类推再排3，4......
关键问题在于，从1往下依次找2，3......移动时，却是反向。于是将每个数字存储于双向循环链表的结点中。正向查找，反向移动。
此算法构造个对象并调用sort方法就能得到步骤。构造时，按外圈次序给出一个乱序整型数组即可。下面的程序你可以当个小游戏，试验解出的结果正确与否。
import javax.swing.*;
import java.awt.event.*;
import java.awt.*;
import java.util.Arrays;
import java.awt.event.WindowEvent;
public class GuardQueueGame2 extends JFrame{
private Insets insFrame;
private JButton btnStart;
Board pnlBoard;
int[] position;
int unused;
public GuardQueueGame2(){
super("巡逻兵游戏");
setResizable(false);
getContentPane().setBackground(new Color(0x0000C000));
setLayout(new BoxLayout(getContentPane(),BoxLayout.X_AXIS));
add(Box.createHorizontalStrut(20));
Box boxContent=Box.createVerticalBox();
add(boxContent);
boxContent.add(Box.createVerticalStrut(20));
pnlBoard=new Board();
pnlBoard.setBackground(new Color(0x00000800));
pnlBoard.setBorder(new javax.swing.border.BevelBorder(javax.swing.border.BevelBorder.LOWERED));
boxContent.add(pnlBoard);
boxContent.add(Box.createVerticalStrut(20));
btnStart=new JButton("开始");
btnStart.setAlignmentX(Component.CENTER_ALIGNMENT);
boxContent.add(btnStart);
boxContent.add(Box.createVerticalStrut(20));
add(boxContent);
add(Box.createHorizontalStrut(20));
btnStart.addActionListener(new ActionListener(){
public void actionPerformed(ActionEvent e){
pnlBoard.restart();
}
});
setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
setVisible(true);
insFrame=this.getInsets();
setSize(insFrame.left+insFrame.right+400,insFrame.top+insFrame.bottom+460);
}
public static void main(String[] args){
new GuardQueueGame2();
}
}
class Board extends JPanel implements ComponentListener,MouseListener,MouseMotionListener{
private int X0,Y0,gridWidth,gridHeight,r1,r2,fontSize,vacant,active,xOffset,yOffset;
private int[] position,vacantSiblings;
private Point[] displayPoint;
public Board(){
position=new int[8];
displayPoint=new Point[8];
addComponentListener(this);
addMouseListener(this);
addMouseMotionListener(this);
vacant=4;
vacantSiblings=getSiblings(vacant);
active=-1;
for(int i=0;i<8;i++){
position[i]=i+i/4;
displayPoint[i]=getPosition(position[i]);
}
}
public void paintComponent(Graphics g){
Dimension size=getSize();
g.setColor(new Color(0x00008000));
g.fillRect(0,0,size.width,size.height);
g.setColor(Color.white);
g.drawLine(X0,Y0,X0+gridWidth*2-1,Y0);
g.drawLine(X0+gridWidth*2-1,Y0,X0+gridWidth*2-1,Y0+gridHeight*2-1);
g.drawLine(X0+gridWidth*2-1,Y0+gridHeight*2-1,X0,Y0+gridHeight*2-1);
g.drawLine(X0,Y0+gridHeight*2-1,X0,Y0);
g.drawLine(X0,Y0,X0+gridWidth*2-1,Y0+gridHeight*2-1);
g.drawLine(X0+gridWidth-1,Y0,X0+gridWidth-1,Y0+gridHeight*2-1);
g.drawLine(X0+gridWidth*2-1,Y0,X0,Y0+gridHeight*2-1);
g.drawLine(X0+gridWidth*2-1,Y0+gridHeight-1,X0,Y0+gridHeight-1);
int x,y;
g.setFont(new Font("黑体",Font.BOLD,fontSize));
FontMetrics metrics=g.getFontMetrics();
xOffset=metrics.charWidth('9')/2;
yOffset=metrics.getHeight()/2;
for(int i=0;i<8;i++){
x=displayPoint[i].x;
y=displayPoint[i].y;
g.setColor(active==i?Color.pink:Color.red);
g.fillOval(x-r1,y-r1,r1*2,r1*2);
g.setColor(active==i?Color.yellow:Color.white);
g.fillOval(x-r2,y-r2,r2*2,r2*2);
g.setColor(active==i?Color.pink:Color.red);
g.drawString(String.valueOf(i+1),x-xOffset,y+yOffset-3);
}
}
public void restart(){
int index,temp;
for(int i=0;i<8;i++){
position[i]=i+i/4;
}
for(int i=0;i<8;i++){
index=(int)(Math.floor(Math.random()*8));
temp=position[i];
position[i]=position[index];
position[index]=temp;
}
vacant=4;
vacantSiblings=getSiblings(vacant);
for(int i=0;i<8;i++){
displayPoint[i]=getPosition(position[i]);
}
repaint();
}
private Point getPosition(int i){
return new Point(X0+(i%3)*gridWidth,Y0+(i/3)*gridHeight);
}
public void componentHidden(ComponentEvent e){}
public void componentMoved(ComponentEvent e){}
public void componentResized(ComponentEvent e){
X0=getWidth()/15;
Y0=getHeight()/15;
gridWidth=getWidth()/2-X0;
gridHeight=getHeight()/2-Y0;
r1=Math.min(gridWidth,gridHeight)/8;
r2=r1*7/10;
fontSize=r1;
for(int i=0;i<8;i++){
displayPoint[i]=getPosition(position[i]);
}
repaint();
}
public void componentShown(ComponentEvent e){}
public void mouseEntered(MouseEvent e){}
public void mouseExited(MouseEvent e){}
public void mousePressed(MouseEvent e){}
public void mouseReleased(MouseEvent e){
int d=getBelongDigit(e.getX(),e.getY());
if(d>=0){
boolean canClick=false;
if(Arrays.binarySearch(vacantSiblings,d)>=0){
Point vacantPoint=getPosition(vacant);
double distance,xStep,yStep;
distance=displayPoint[d].distance(vacantPoint);
xStep=(vacantPoint.x-displayPoint[d].x)/distance;
yStep=(vacantPoint.y-displayPoint[d].y)/distance;
Point p=new Point(displayPoint[d]);
Graphics g=getGraphics();
for(int i=1;displayPoint[d].distance(vacantPoint)>=0.5;i++){
displayPoint[d].x=(int)(Math.round(xStep*i+p.x));
displayPoint[d].y=(int)(Math.round(yStep*i+p.y));
if(i%10==0){
update(g);
}
}
repaint();
active=-1;
int temp=vacant;
vacant=position[d];
position[d]=temp;
vacantSiblings=getSiblings(vacant);
setCursor(Cursor.getDefaultCursor());
}
}
}
public void mouseClicked(MouseEvent e){}
public void mouseMoved(MouseEvent e){
active=getBelongDigit(e.getX(),e.getY());
if(active>=0&&Arrays.binarySearch(vacantSiblings,active)>=0){
setCursor(new Cursor(Cursor.HAND_CURSOR));
}
else{
setCursor(Cursor.getDefaultCursor());
active=-1;
}
repaint();
}
public void mouseDragged(MouseEvent e){}
private int getBelongDigit(int x,int y){
int i,xLen=0,yLen=0;
for(i=7;i>=0;i--){
xLen=x-displayPoint[i].x;
yLen=y-displayPoint[i].y;
if(xLen*xLen+yLen*yLen<=r1*r1){
break;
}
}
return i;
}
private int[] getSiblings(int p){
int[] digits=new int[8];
int index=0;
boolean isSibling;
for(int i=0;i<8;i++){
switch(position[i]){
case 0:isSibling=p==1||p==3||p==4;break;
case 1:isSibling=p==0||p==2||p==4;break;
case 2:isSibling=p==1||p==4||p==5;break;
case 3:isSibling=p==0||p==4||p==6;break;
case 4:isSibling=p==0||p==1||p==2||p==3||p==5||p==6||p==7||p==8;break;
case 5:isSibling=p==2||p==4||p==8;break;
case 6:isSibling=p==3||p==4||p==7;break;
case 7:isSibling=p==4||p==6||p==8;break;
case 8:isSibling=p==4||p==5||p==7;break;
default:throw new IllegalArgumentException(String.valueOf(position[i]));
}
if(isSibling){
digits[index++]=i;
}
}
int[] result=new int[index];
System.arraycopy(digits,0,result,0,index);
return result;
}
}

Answer 2

不给图我怕理解上会出问题，不轻易下手

Answer 3

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class t2 {
public static void main(String args[]) {
// 第一步：定义Internet数组i的长度为9，并把1-8随机赋值给i[0]-i[7]
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
Random r = new Random();
Integer i[] = new Integer[9];
for (int j = 0; j < 8; j++) {
int m = r.nextInt(list.size());
i[j] = list.get(m);
list.remove(m);
}
// 第二步：给数组排序。思想：我们可以用一个数组i（当然也可以用map，list，而且要比数组简单）
// 模拟题目要实现的功能。从图中可以看出每个数组元素除了能直接赋值给i[8](也就是图中的中间那个点)之外就只能和
// 它相邻的2个数交换位置。所以我们先把i[0]放入i[8]中，再找到1所在的位子，利用循环把它放入i[0],再把i[8]的值赋给
// 刚才存放1的那个位置.如此循环下去就能得到想要的结果，代码如下：
for (int m = 0; m < 8; m++) {
int n = m + 1;
for (int j = 0; j < i.length - 1; j++) {
if (i[j] == n) {
int l = j - m;
i[8] = i[m];
for (int x = 0; x < l; x++) {
int t = i[j - x - 1];
i[j - x - 1] = i[j - x];
i[j - x] = t;
}
}
}
}
for (int m : i) {
System.out.println(m);// 输出经过排序后的数组
}
}
}