数据结构课程设计报告
目录
1 设计目的与意义 (3)
2 系统描述 (3)
3 运行环境 (3)
4 系统的分析与设计 (3)
4.1 程序结构说明 (3)
4.2 AccessibleSquare算法实现 (4)
4.3 画图类算法实现 (5)
4.4 主调用程序的设计和开发 (7)
5 系统测试 (7)
5.1 游戏初始界面 (8)
5.2 游戏以（1，1）为起点运行界面 (8)
5.3 游戏以（6，3）为起点界面 (9)
5.4 游戏以（6，3）为起点运行界面 (9)
6 总结 (10)
源程序 (10)
1 设计目的与意义
Java课程设计是计算机科学与技术专业学生必做的集中实践性环节之一，是学习完《Java程序设计》课程后进行的一次全面的综合练习。其目的在于通过课程设计，使学生能够得到较系统的技能训练，从而巩固和加深对Java 编程的基础理论知识的理解，培养学生综合运用所学理论解决实际问题的能力，使学生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人才。
2 系统描述
骑士游历问题是一个古老而著名的问题，它最初是由大数学家Euler提出的。问题是这样的：国际象棋中的棋子(叫作骑士)在一个空棋盘内移动，问它能否经过64格中的每一格且只经过一次？(骑士按L行移动,即在某方向前进两格接着在与原方向垂直的方向上前进一格)
该课程设计要求实现骑士游历问题的求解，并能够演示起始位置在棋盘上任何位置的游历问题的实现。程序将采用动态的图形演示，使算法的描述更形象、更生动。本程序采用Applet来编制整个程序，这样既可以加深对算法的实现的了解，也可以进一步熟悉Java图形界面、Applet以及Java语言的命名规范。
骑士游历的课程设计是按照面向对象的思想进行开发，其中主要的类包括AccessibleSquare 类、MyPanel类和KnightsTour类。其中AccessibleSquare 类主要是算法实现，采用启发式算法；KnightsTour类是主类，或者说是控制类，它完成对算法类和图画类的调用；MyPanel类是画图类用来实现图形化显示结果。
3 运行环境
本程序是在windows xp的环境下运行的。
4 系统的分析与设计
4.1 程序结构说明
本程序由三个类组成一个工程文件。其中KnightsTour是主类，或者说是控制类，AccessibleSquare类主要是算法实现，MyPanel实现图形化显示结果。
程序的运行关系如图4-1。
图4-1 程序运行关系图
4.2 AccessibleSquare算法实现
1)AccessibleSquare类主要是算法实现，采用启发式算法。
先把八个可能走的方向用两个数组(horizontal[ ]和vertical[ ])表示，选择走哪个方向就在原坐标上进行相应的加法，表示骑士到了一个新的位置。horizontal[ ]和vertical[ ]表示骑士8个方向走L形状所需的X坐标和Y坐标的变化量：horizontal[] = {2,1,-1,-2,-2,-1,1,2}，vertical [] = {-1,-2,-2,-1,1,2,2,1}。坐标图如下：
图4-2 骑士游历走向坐标图
2)由于程序采用启发式算法，应考察每一方格的可到达性。使用数组
accessibility []表示可达到数,并当骑士游历时，程序动态修正剩余格子的可达到数。accessibility [ arrayPos ] = 0 表明格子已经被占据。
3)使用冒泡法来查询最小数。冒泡排序的基本概念是：依次比较相邻的两个数，
将大数放在前面，小数放在后面。即首先比较第1个和第2个数，将大数放前，小数放后。然后比较第2个数和第3个数，将大数放前，小数放后，如
此继续，直至比较最后两个数，将大数放前，小数放后，此时第一趟结束，在最后的数必是所有数中的最小数。重复以上过程，直至最终完成排序。
//冒泡排序法
private void sortAll (){
for ( int begin = 0 ; begin < countAccessibility - 1 ; begin ++ ){
for ( int i = begin + 1; i < countAccessibility ; i ++ ){
if ( accessibility [ begin ] > accessibility [ i ] ){
swapAll( begin, i ); }//end of if
}// end of inner for
}// end of outer for
}// end of sortAll
//进行移动操作
public void domoving(){
for ( int i = 0 ; i < countAccessibility ; i ++ ){
KnightsTour.access[ xpos [i] ][ ypos[i] ] -- ; }
//直到没有路径了
KnightsTour.access[ ownxpos ][ ownypos ] = 0 ;
}
//交换两个数
private void swapAll ( int i , int j ){
int temp ;
temp = xpos [ i ]; xpos [ i ] = xpos [ j ]; xpos [ j ] = temp;
temp = ypos [ i ]; ypos [ i ] = ypos [ j ]; ypos [ j ] = temp;
temp = accessibility [ i ];
accessibility [ i ] = accessibility [ j ]; accessibility [ j ] = temp;
}
4.3 画图类算法实现
由于目前用户对界面的要求逐步提高，因此，现在的可视化编程已经取代了传统的用户界面的设计方法。而在可视化编程中，人机之间的直接联系主要是通过一些窗口和对话框来实现。JBuilder9也不例外，它也是通过这些窗口和对话框来实现窗体。用户需要的控件则可以直接放置在窗体上，利用这些控件来实现复杂的功能。
用户界面设计器是用户在编写程序过程中最常用到的工具。用户在进行界面设计时，只需单击文件视图标签中的Design页，就会出现该用户界面设计器。用户可以利用JBuilder提供的各种控件来搭建自己的程序界面。而且同时，JBuilder9还为这些界面自动生成了相应的代码，为用户提供了程序的环境。接下来，就要由用户设置属性，来编写一些实现用户特定功能的代码。这在很
大程度上减少了用户界面设计的复杂度，使用户的主要精力投入到如何实现和加强功能上来。
本程序是Applet的图形界面以及如何利用图形用户界面的控件接受用户信息，并用图形或图像显示结果。
1)MyPanel函数实现图形化显示结果，MyPanel类就是画图类。首先用两种不
同颜色的方块(WHITE和BIACK)显示出棋盘，还有其他两种方块(WKNIGHT 和BKNIGHT),这两种方块上都有骑士，但颜色不一样。在骑士游历过程中不断用后来两种有骑士的方块代替前两种方块，其中需要注意的是保持棋盘的颜色一致性。如5-3图所示，将其设置为静态变量，方便使用，防止修改时出错。
图4-3 骑士游历游戏中的棋盘用图
2)显示骑士起始位置，刚走过的步的位置和现在的位置，用边框的不同来加以
区别，采用函数g.setColor(Color.green)(刚走过的步显示为绿色)和
g.setColor(Color.biue)(当步显示为蓝色)实现。这个类的对象在主类
KnightsTour中被实例化。采用public viod paintComponent(Graphics g)函数画出图形。
//MyPanel函数实现图形化显示结果
class MyPanel extends JPanel {
public static final int WHITE = 0 ;//用于显示棋盘
public static final int BLACK = 1 ;
public static final int WKNIGHT = 2 ;//用于显示骑士
public static final int BKNIGHT = 3 ;
private int chessboard[][];
private int xrecord [] ;
private int yrecord [] ;
private int displayCount ;
private int lastxpos ,lastypos ,nextxpos ,nextypos ;
ImageIcon images[] ;
private boolean start ;
public MyPanel() {//MyPanel构造函数
initvariance();
}
public MyPanel( int [] newxrecord ,int [] newyrecord ) {//重载构造函数
initvariance();
initboard( newxrecord , newyrecord );
}
4.4 主调用程序的设计和开发
KnightsTour类是控制类，它完成对算法类和画图类的调用。由于JA VA的GUI编程是事件驱动的，因此在KnightsTour类中，通过监听前面介绍的几个Button的事件相应，完成程序的调用过程。
采用二维数组表示初始位置位于某个位置的可达到数，即以棋盘任意一点为初试位置，骑士游历完整个棋盘的路径数。利用access[][]数组来表示这个二维数组。
Public static int access[][]={
{ 2, 3, 4, 4, 4, 4, 3, 2 }，
{ 3, 4, 6, 6, 6, 6, 4, 3 }，
{ 4, 6, 8, 8, 8, 8, 6, 4 }，
{ 4, 6, 8, 8, 8, 8, 6, 4 }，
{ 4, 6, 8, 8, 8, 8, 6, 4 }，
{ 4, 6, 8, 8, 8, 8, 6, 4 }，
{ 3, 4, 6, 6, 6, 6, 4, 3 }，
{ 2, 3, 4, 4, 4, 4, 3, 2 }}；
本程序中在KnightsTour类中添加了两个按钮，。按钮一：JButton nextMoving = new JButton( "下一步" )；按钮二：JButton nextTour = new JButton( "新起点重新开始" )，用于用户对游戏进行操作，这两个按钮分别有事件响应。
//匿名内部类,定义了actionPerformed函数,调用showNext函数响应Next Moving Button事件
new ActionListener() {
public void actionPerformed ( ActionEvent e ) {
myPanel.showNext() ; }
};
//匿名内部类,定义了actionPerformed函数,调用showNext函数响应Next Moving Button事件
new ActionListener() {
public void actionPerformed ( ActionEvent e ) {
myPanel.showNext() ; }
}
);
5 系统测试
这段时间做骑士游历程序，虽然在编程的过程中遇到了许多的困难，最终通过请教老师，或到图书馆查阅相关书籍或上网查找资料等途径将它们一一解决了。经过不断修改程序终于编译通过可以正常运行，其运行结果如下所示：5.1 游戏初始界面
5.2 游戏以（1，1）为起点运行界面
5.3 游戏以（6，3）为起点界面
5.4 游戏以（6，3）为起点运行界面
6 总结
通过这个星期的课程设计，我也深刻体会到了多问几个为什么的重要性。真正理解了作为一个计算机专业的学生不仅仅要学好计算机理论知识，同时也要有较强的动手能力。
源程序
package cao;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.awt.image.*;
public class KnightsTour extends JApplet {
// 初始位置位于某个位置的可达到数采用二维数组表示
//即以棋盘任意一点为初试位置，骑士游历完整个棋盘的路径数
public static int access[][] = {
{2,3,4,4,4,4,3,2},
{3,4,6,6,6,6,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,6,6,6,6,4,3},
{2,3,4,4,4,4,3,2}};
public static int accessbak[][] = arrayCopy ( access ) ;
int countMoving = -1 ;
int tourXpos [] = new int [ 64 ];//游历中，X，Y都有64个位置
int tourY pos [] = new int [ 64 ];
private int recordXpos [][]; private int recordY pos [][];
private int recordCount = - 1 ;
private int startx ; private int starty ;
private boolean success = false;
MyPanel myPanel ;//声明MyPanel的一个对象
public void tour ( int xpos ,int ypos ){//成员函数
// int x,y;
countMoving ++ ;
//如果64个格子都被走过，则返回
if (countMoving == 63 )
{ tourXpos [ countMoving ] = xpos ;
tourY pos [ countMoving ] = ypos ;
success = true ;
countMoving -- ;
return ;
}
AccessibleSquares nextSquare = new AccessibleSquares( xpos, ypos );
//初试化AccessibleSquares对象，给nextSquare分配内存
while (nextSquare.hasMoreAccessible())
//利用AccessibleSquares()对象调用hasMoreAccessible()成员函数{ // 开始移动
nextSquare.domoving();//调用nextSquare.domoving()函数
//把这一步记录下来
tourXpos [ countMoving ] = xpos ;
tourY pos [ countMoving ] = ypos ;
// 尝试下一步的移动
nextSquare.nextAccessible();
tour ( nextSquare.getXpos() , nextSquare.getY pos() );
//如果64个格子都被走过，则返回
if ( success )
{ countMoving -- ;
return ; }
//如果失败，则从起始位置从新开始
nextSquare.undomoving();
}
countMoving -- ;
}//游历方法结束
//定义棋盘行和列
//先定义一行棋盘
public static int[] arrayCopy ( int array1[] )//定义一个整形数组arrayCopy { int[]array2 = new int [array1.length];
for ( int row = 0 ; row < array1.length ; row ++ )
{ array2 [ row ] = array1 [ row ] ; };
return array2;
}
//复制数组，即定义出棋盘列
public static int[][] arrayCopy ( int array1[][] )
{ int[][] array2 = new int [array1.length][array1[0].length];
for ( int row = 0 ; row < array1.length ; row ++ )
{ for ( int column = 0 ; column < array1[0].length ; column ++ ) { array2 [ row ][ column ] = array1 [ row ][ column ]; };
};
return array2;
}
//棋盘数组函数初始化
public void initialArray ( int chessBoard[][] )
{ for ( int row = 0 ; row < 8 ; row ++ )
{ for ( int column = 0 ; column < 8 ; column ++ )
{ chessBoard [ row ][ column ] = 0 ; };
};
}
public static void main( String args[] ) {
KnightsTour application = new KnightsTour();
application.tour( 0 , 0 );
}
public void init () {
recordCount = -1 ;
recordXpos = new int [ 64 ][ 64 ] ; recordY pos = new int [ 64 ][ 64 ] ;
for (int row = 0 ; row < 8 ;row ++){
for ( int column = 0 ; column < 8 ; column ++ ){
success = false ;
countMoving = -1;
startx = row ; starty = column ;
access = arrayCopy ( accessbak );
tour ( row ,column );
recordCount ++ ;
recordXpos [ recordCount ] = arrayCopy ( tourXpos ) ;
recordY pos [ recordCount ] = arrayCopy ( tourY pos ) ;
}
}
recordCount = 0 ;
myPanel = new MyPanel( recordXpos [ 0 ] ,recordY pos [ 0 ]) ;
JPanel buttonPanel = new JPanel();
JButton nextMoving = new JButton( "下一步" );
JButton nextTour = new JButton( "新起点重新开始" );
buttonPanel.add( nextTour );
buttonPanel.add( nextMoving );
getContentPane().add( buttonPanel, BorderLayout.SOUTH );
getContentPane().add( myPanel );
nextMoving.addActionListener(
//匿名内部类,定义了actionPerformed函数,调用showNext函数响应Next Moving Button事件new ActionListener() {
public void actionPerformed ( ActionEvent e ) {
myPanel.showNext() ; }
}
);//end call to addActionListener
nextTour.addActionListener(
//内部类定义了actionPerformed函数,响应Next Tour Button事件
new ActionListener() {
public void actionPerformed ( ActionEvent e ) {
if ( recordCount < recordXpos.length - 1 ) {
recordCount ++ ;
} else { recordCount = 0 ; }
myPanel.initboard ( recordXpos [ recordCount ] ,
recordY pos [ recordCount ] );
myPanel.repaint();
}
}
);//end call to addActionListener
}
public void paint (Graphics g )
{ super.paint( g ); }
}//end of class KnightsTour
class AccessibleSquares {
//骑士8个方向走L形状所需的X坐标和Y坐标的变化量
private static int horizontal[] = {2,1,-1,-2,-2,-1,1,2};
private static int vertical [] = {-1,-2,-2,-1,1,2,2,1};
private int xpos[] ;//骑士所处X轴的坐标
private int ypos[] ;//骑士所处y轴的坐标
private int accessibility [];//表示可达到数
private int ownxpos ,ownypos ;
private int ownAccessibility ;
private int arrayPos ;
private int countAccessibility;
public AccessibleSquares(int x , int y ){//构造函数
int testXPos; int testYPos;
xpos = new int [ 8 ];//骑士所处X轴的坐标
ypos = new int [ 8 ];
accessibility = new int [ 8 ];
arrayPos = 0 ;
ownxpos = x ; ownypos = y ;
ownAccessibility = KnightsTour.access[ x ][ y ];
for (int i = 0 ; i < horizontal.length ; i++ ){//有八种到达的情况
testXPos = x + horizontal[ i ];//得出X,Y坐标的测试位置
testYPos = y + vertical [ i ];
if ( (testXPos >= 0 ) & ( testXPos < 8 ) &
(testYPos >= 0 ) & ( testYPos < 8 ) ) {//判断测试位置是否在棋盘内
xpos [ arrayPos ] = testXPos ;//由测试位置给出正确X,Y坐标
ypos [ arrayPos ] = testYPos ;
accessibility [ arrayPos ] = KnightsTour.access [testXPos][testYPos];
//利用对应的X,Y坐标得出相应的可到达的路径总数
// accessibility [ arrayPos ] = 0 表明格子已经被占据
if (accessibility [ arrayPos ] > 0 ) arrayPos ++ ;
}//寻找空格子结束
}// 结束for循环,寻找结束
countAccessibility = arrayPos ;//统计可达到数
if (countAccessibility > 0 ) {sortAll();}
arrayPos = -1 ;
}
public boolean hasMoreAccessible(){
// arrayPos + 1 指向下一个可行的
if ( (arrayPos + 1 ) < countAccessibility ){
return true; }
else { return false; }
}// hasMoreAccessible()方法结束
public AccessibleSquares nextAccessible(){
arrayPos ++ ;
return this;
}
public AccessibleSquares accessibleAt( int pos){
if ((pos >= 0) & (pos < countAccessibility ))
arrayPos = pos ;
return this;
}
public int getXpos(){
return xpos[ arrayPos ]; }
public int getY pos(){
return ypos[ arrayPos ]; }
public int getAccessibility(){
return accessibility[ arrayPos ]; }
public int getTotalAccessible(){
return countAccessibility; }
//冒泡排序法.冒泡排序的基本概念是：依次比较相邻的两个数，将大数放在前面，小数放在后面。
private void sortAll (){
for ( int begin = 0 ; begin < countAccessibility - 1 ; begin ++ ){
for ( int i = begin + 1; i < countAccessibility ; i ++ ){
if ( accessibility [ begin ] > accessibility [ i ] ){
swapAll( begin, i ); }//end of if
}// end of inner for
}// end of outer for
}// end of sortAll
//交换两个数
private void swapAll ( int i , int j ){
int temp ;
temp = xpos [ i ]; xpos [ i ] = xpos [ j ]; xpos [ j ] = temp;
temp = ypos [ i ]; ypos [ i ] = ypos [ j ]; ypos [ j ] = temp;
temp = accessibility [ i ];
accessibility [ i ] = accessibility [ j ]; accessibility [ j ] = temp;
}
//进行移动操作
public void domoving(){
for ( int i = 0 ; i < countAccessibility ; i ++ ){
KnightsTour.access[ xpos [i] ][ ypos[i] ] -- ; }
//直到没有路径了
KnightsTour.access[ ownxpos ][ ownypos ] = 0 ;
}
//撤消移动操作
public void undomoving(){
for ( int i = 0 ; i < countAccessibility ; i ++ ){
KnightsTour.access[ xpos [i] ][ ypos[i] ] ++ ; }
KnightsTour.access[ ownxpos ][ ownypos ] = ownAccessibility ;
}
}
//MyPanel函数实现图形化显示结果
class MyPanel extends JPanel {
public static final int WHITE = 0 ;//用于显示棋盘
public static final int BLACK = 1 ;
public static final int WKNIGHT = 2 ;//用于显示骑士
public static final int BKNIGHT = 3 ;
private int chessboard[][];
private int xrecord [] ;
private int yrecord [] ;
private int displayCount ;
private int lastxpos ,lastypos ,nextxpos ,nextypos ;
ImageIcon images[] ;
private boolean start ;
public MyPanel() {//MyPanel构造函数
initvariance();
}
public MyPanel( int [] newxrecord ,int [] newyrecord ) {//重载构造函数initvariance();
initboard( newxrecord , newyrecord );
}
public void initvariance () {
chessboard = new int[ 8 ][ 8 ];
xrecord = new int [ 64 ] ; yrecord = new int [ 64 ];
images = new ImageIcon [ 4 ];
images[ 0 ] = new ImageIcon( "white.jpg");
images[ 1 ] = new ImageIcon( "black.jpg");
images[ 2 ] = new ImageIcon( "wknight.jpg");
images[ 3 ] = new ImageIcon( "bknight.jpg");
}
//画棋盘,给棋盘上色
public void initboard ( int [] newxrecord ,int [] newyrecord ){
start = true ;
displayCount = -1 ;
for (int row = 0 ; row < 8 ;row ++){
for ( int column = 0 ; column < 8 ; column ++ ){
//0表示白的，1表示黑的
chessboard [ row ][ column ] = ( row + column ) % 2 ; } }//end of outer for
for ( int row = 0 ; row < newxrecord .length ; row ++ ) {
xrecord [ row ] = newxrecord [ row ] ;
yrecord [ row ] = newyrecord [ row ] ;
}
displayCount = 0 ;
chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
}//end of initboard
public void showNext() {
if ( displayCount < xrecord.length - 1 ){
displayCount ++ ;
chessboard [ xrecord [ displayCount ] ][ yrecord [ displayCount ] ] += 2 ;
repaint();
}
}
public void paintComponent ( Graphics g ) {
//用于显示运行时态的颜色
for (int row = 0 ; row < 8 ;row ++){
for ( int column = 0 ; column < 8 ; column ++ ){
images[ chessboard[ row ][ column ] ].paintIcon( this , g, 40 * row,40 * column );
}//end of inner for
}//end of outer for
if ( displayCount > 0 ){
lastxpos = xrecord [ displayCount - 1];
lastypos = yrecord [ displayCount - 1];
nextxpos = xrecord [ displayCount ];
nextypos = yrecord [ displayCount ];
g.setColor( Color.green);
g.drawRect( 40 * xrecord [ displayCount - 1 ] + 2,
40 * yrecord [ displayCount - 1 ] + 2, 36, 36 );
g.setColor( Color.green);//刚走过的步显示为绿色
g.drawRect( 40 * xrecord [ displayCount ] + 2 ,
40 * yrecord [ displayCount ] + 2, 36, 36 );
g.setColor( Color.blue);//当前步显示为蓝色
g.drawRect( 40 * Math.min( nextxpos, lastxpos ),
40 * Math.min( nextypos, lastypos ),
( Math.abs( nextxpos - lastxpos ) + 1 ) * 40,
( Math.abs( nextypos - lastypos ) + 1 ) * 40 );
}//end of if
g.setColor( Color.red );//起始位置显示为红色
g.drawRect ( 40 * xrecord [ 0 ] + 2,40 * yrecord [ 0 ] + 2, 36, 36 ) ;
}// end of the method paintComponent}
【题3】骑士游历问题 设有一个n*m 的棋盘(2≤n ≤50，2≤m ≤50)，如下图。在棋盘上任一点有一个中国象棋马， 马走的规则为： 1.马走日字 2.马只能向右走。即下图所示： 当n ，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)： 输入： n ，m ，x1，y1，x2，y2(分别表示n ，m ，起点坐标，终点坐标) 输出： 路径数目(若不存在从起点到终点的路径，输出0) 分析：使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较短的时间内出解。因为题目并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。 从(x 1，y 1)出发，按照由左而右的顺序定义阶段的方向。位于（x ，y ）左方且可达（x ，y ）的跳马位置集合都是（x ，y ）的子问题，起点至（x ，y ）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。 如此一来，状态转移关系便凸显出来。设状态转移方程map ，其中map[i ，j]为起点（x1，y1）至（i ， j ）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map 数组的元素类型为extended 。初始时，除map[x1，y1]=1外其余为０。显然 }),(],[],[{],[),),(在界内的坐标集 可达（y x y x map j i map y x map y x j i ∑∈+=。 我们采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目map[x2，y2]： 阶段j ：中国象棋马当前的列位置(y 1≤j ≤y2)； 状态i ：中国象棋马在j 列的行位置（1≤i ≤n ）；
骑士游历问题 设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如下图。在棋盘上任一点有一个中国象棋马， 马走的规则为： 1.马走日字 2.马只能向右走。 即下图所示： 当n，m 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(n=10，m=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如下图)： 输入： n，m，x1，y1，x2，y2(分别表示为：n，m，起点坐标，终点坐标) 输出： 路径数目(若不存在从起点到终点的路径，输出0) 分析： 使用回溯法是可以计算路径数目，但问题是搜索效率太低，根本不可能在较
短的时间内出解。因为题目并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。 从(x 1，y 1)出发，按照由左而右的顺序定义阶段的方向。位于（x ，y ）左方且可达（x ，y ）的跳马位置集合都是（x ，y ）的子问题，起点至（x ，y ）的路径数实际上等于起点至这些位置集的路径数之和（如下图）。 如此一来，状态转移关系便凸显出来。设状态转移方程map ，其中map[i ，j]为起点（x1，y1）至（i ，j ）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map 数组的元素类型为extended 。初始时，除map[x1，y1]=1外其余为０。 显然 }),(],[],[{],[),),(在界内的坐标集可达（y x y x map j i map y x map y x j i ∑∈+= 。 采用动态程序设计的方法计算起点（x1，y1）至终点（x2，y2）的路径数目map[x2，y2]： 阶段j ：中国象棋马当前的列位置(y 1≤j ≤y2)； 状态i ：中国象棋马在j 列的行位置（1≤i ≤n ）； 决策k ：中国象棋马在（i ，j ）的起跳方向(1≤k ≤4)； 计算过程如下： fillchar(map ，sizeof(map)，0)； map[x1，y1] ←1； {从（x1，y1）出发} for j ←y1 to y2 do {递推中国象棋马的列位置} for i ←1 to n do {递推中国象棋马在j 列的行位置}
【题5】骑士游历问题（1） 设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如图10.2.1。在棋盘上任一点有一个中国象棋马， 图10.2.1 马走的规则为： 1.马走日字 2.马只能向右走。即如图10.2.2所示： 图10.2.2 问题：当N，M 输入之后，找出一条从左下角到右上角的路径。例如：输入N=4，M=4。对应的路径如图10.2.3所示： 图10.2.3 输出：路径的格式：(1，1)->(2，3)->(4，4) 若不存在路径，则输出"no" 题解 1.计算跳马方向 按题意，中国象棋马共有四个跳动方向 图10.2.4 我们通过子程序move（x，y，x1，y1，i）计算中国象棋马从（x，y）出发，沿i方向跳至（x1，y1）的过程 procedure move(x，y：byte；var x1，y1：byte；i：integer)； begin case i of ｛根据方向计算跳后位置｝ 1：begin x1←x-2；y1←y+1；end； 2：begin x1←x-1；y1←y+2；end； 3：begin x1←x+1；y1←y+2；end； 4：begin x1←x+2；y1←y+1；end； end；{case} end；{move} 2.从起始点出发，沿方向序列输出路径 设
var path：array[1..1000] of integer；{path[i]—第i步的方向。初始时path 清零} 由(1，1)至（n，m）的路径长度为k。我们通过调用print(k)过程输出该条路径。 procedure print(k：integer)； var x，y，x0，y0：byte； i：integer； begin x←1； y←1；｛从（１，１）出发｝ write(’(’，x，’，’，y，’)’)； for i←1 to k do ｛顺序输出长度为k的跳动路线｝ begin move(x，y，x0，y0，path[i])；｛第i步由（x,y）跳至（x0,y0）｝ write(’=>(’，x0，’，’，y0，’)’)； x←x0； y←y0； {从（x0,y0）继续往下跳} end；{for} writeln end；{print} 3.回溯搜索 状态：起跳位置（x，y）和步数k，即准备从（x，y）出发跳第k步； 目标：（x，y）为目的地（n，m）。若满足条件，则输出长度为k-1的路径并成功退出； 搜索范围：四个跳动方向，即1≤i≤4。中国象棋马沿i方向跳至（x1，y1）； 约束条件：（x1，y1）在界内。若满足条件，则记下第k步的方向i，并从（x1，y1）出发递归第k+1步； procedure search(k：integer；x，y：byte)； var i：integer； x1，y1：byte； begin if (x=n) and (y=m) {若（x，y）为目的地，则输出长度为k-1的路径并成功退出} then begin print(k-1)； halt； end； for i←1 to 4 do {搜索4个方向} begin move(x，y，x1，y1，i)； { 中国象棋马从（x，y）出发，沿i方向跳至（x1，y1）} if (x1 in [1..n]) and (y1 in [y+1..m]){若（x1，y1）在右方界内，则记下第k步的方向i，并从（x1，y1）出发递归第k+1步} then begin path[k]←i； search(k+1，x1，y1)；end；{then} end{for} end；{ search } 显然，递归调用search（1，1，1）后可得出由（1，1）至（n，m）的一条路径。
需要记忆的算法： -1 pascal 运算优先级 1not 2and * / div mod 3or xor + - 4 in = > < >= <= 0. 文件的输入和输出： begin assign(input,'p1.in'); reset(input); assign(output,'p1.out'); rewrite(output); for i:=1 to 20 do readln(a[i]); sum:=0; for i:=1 to 20 do sum:=sum+a[i]; writeln(sum); close(input); close(output); end. 1. 素数的判断： function ok(x:longint):boolean;
var i:longint; begin for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit(false); exit(true); end; 2.选择排序 For i:=1 to n-1 do For j:=i+1 to n do If a[j]>a[i] then begin t:=a[j];a[j]:=a[i];a[i]:=t;end; 3.二进制枚举法: Fillchar(b,sizeof(b),0); while b[0]=0 do begin j:=m; \\第m位为最低位。 while b[j]=1 do dec(j); \\从最低位开始找非1 的位子； b[j]:=1; \\该位置1； for i:=j+1 to m do b[i]:=0; \\把刚才经过的1全部置0； {已经产生一种2进制数} ｛处理……｝ End;
NOIP复赛谈 复赛的命题 1．遵循大纲：考察常用的数据结构和基本算法； 2．考察能力：包括阅读理解能力、构建数学模型的能力、程序编码与调试能力、程序的时空性能分析和测试数据的生成能力、各种知识的综合应用能力等； 3．有区分度：一般4题，复赛题目的特点是：1-2题算法和数据结构比较明显、或者和数学关系比较大的题目，得率比较高；1题好上手，但程序量要大一点或数据规 模大的题目，考虑全面、得满分也不容易；还有1题一般是搜索、或者算法不明显、或者用到复杂高深一点的数据结构的题目，难度较大。但顺序不一定！！！ 如何备战复赛 1.做做以往历年的竞赛题和网上的模拟题，熟悉比赛的题型和要求，找出自己的不 足，加强训练； 2.增强自己编写代码和调试的熟练程度，提高做题的时间和节奏感； 3.熟练掌握文件的输入/输出操作，熟悉新大纲中对复赛的要求； 4.提高自己设计测试数据的能力； 5.提高自己做题的正确率（分数/时间）； 6.算法方面：递推、递归、动态规划、贪心、搜索（初中到回溯就差不多了）基本 上是必考！！！对一些经典问题和算法，一定要熟练的不能再熟练； 7.数据结构方面：字符串经常考，树（尤其二叉树）、图的基本算法（最短路径、最 小生成树等）； 复赛注意事项 1.认真审题，尤其要注意问题的规模（数据范围），从某种意义上说，问题规模也 暗示了你可能的算法。数据小，也许是搜索派上用场的时候；数据大了，可能 只能考虑动态规划、数学方法等高算法了。 2.正确的估计题目的难度和自己的水平。拿到试题后先从总体上分析一下题目， 做到心中有数！注意：题目的难易对所有人是公平的，只要最大限度地发挥自 己的水平，不要有包袱，考出自己的最佳成绩。 3.正确地选择题目去做（最擅长、最简单的先完成），合理地安排时间和解题顺序。 4.复赛中：一定提高正确率！！！解题速度是其次。 5.复赛考查的算法并不困难，选手在实现上的问题往往要多一些。建议大家： 1）充分利用草稿纸，不要对自己的“心算能力”太自信！编程熟练的同学喜欢“一气呵成”，拿到题目就开始编码。这样不好，做信息学竞赛题的思维过程是丰 富而曲折多变的，考虑问题必须全面，仅凭一时的“感觉”来编程往往是漏洞
例1、骑士游历：（noip1997tg） 设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,马走的规则为：1.马走日字 2.马只能向右走，即如下图所示： 任务1：当N,M 输入之后,找出一条从左下角到右上角的路径。 例如：输入N=4,M=4 输出：路径的格式：(1,1)->(2,3)->(4,4)；若不存在路径,则输出"no" 任务2：当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。 例如：(N=10,M=10),(1,5)(起点),(3,5)(终点) 输出：2(即由(1,5)到(3,5)共有2条路径) 输入格式：n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标) 输出格式：路径数目(若不存在从起点到终点的路径,输出0) 算法分析：为了研究的方便，我们先将棋盘的横坐标规定为i，纵坐标规定为j，对于一个n×m的棋盘，i的值从1到n，j的值从1到m。棋盘上的任意点都可以用坐标(i,j)表示。对于马的移动方法，我们用K来表示四种移动方向(1,2,3,4)；而每种移动方法用偏移值来表示，并将这些偏移值分别保存在数组dx和dy中，如下表 根据马走的规则，马可以由（i-dx[k],j-dy[k]）走到(i,j)。只要马能从（1，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。我们以（n,m）为起点向左递推，当递推到（i-dx[k],j-dy[k]）的位置是（1，1）时，就找到了一条从（1，1）到（n,m）的路径。 我们用一个二维数组a表示棋盘，对于任务一，使用倒推法，从终点(n,m)往左递推，设初始值a[n,m]为（-1，-1），如果从(i,j)一步能走到(n,m)，就将(n,m)存放在a[i,j]中。如下表，a[3,2]和a[2,3]的值是（4，4），表示从这两个点都可以到达坐标（4,4）。从（1,1）可到达（2，3）、（3，2）两个点，所以a[1,1]存放两个点中的任意一个即可。递推结束以后，如果a[1,1] 任务一的源程序： const dx：array[1..4]of integer=(2,2,1,1); dy：array[1..4]of integer=(1,-1,2,-2); type map=record x,y：integer; end;
华东交通大学理工学院课程设计报告书 所属课程名称数据结构 题目骑士游历 分院电信分院 专业班级电子商务2班 学号 学生姓名 指导教师吴军良 2012 年6月15 日
目录 目录 (2) 第1章课程设计内容及要求 (3) 1.1课程设计的内容 (3) 1.2课程设计要求 (3) 第2章程序设方法与分析 (4) 2.1程序设计方法 (4) 2.2程序详细分析 (4) 2.21创建棋盘 (4) 2.22分析骑士行走方法的实现 (4) 2.3程序实现结构图 (6) 第3章源程序代码 (7) 第4章程序的测试与运行 (10) 4.1编译程序 (10) 4.2链接结果如图 (12) 4.3运行程序结果 (13) 第5章课程设计心得 (17) 第6章参考文献（资料） (18)
第1章课程设计内容及要求 1.1课程设计的内容 在WINDOWS XP系统中，运行Visual C++ 6.0，在Visual C++ 6.0环境下，根据所学教材C语言版数据结构知识，运用C语言编写一个可以实现骑士游历的游戏程序。 1.2课程设计要求 （1）运行环境要求： window xp 系统 Visual C++ 6.0环境 （2）骑士游历棋盘要求： 设计一个8行*8列共64格的棋盘。 （3）棋子走法要求： 放一个“马”，按“马走日字”的规则，马要走到棋盘上每一个格子，且每个格子只走一次。 （4）课程设计目的要求： 骑士游历问题是一个古老而著名的问题，它最初是由大数学家Euler 提出的。我们通过在window xp系统中，Visual C++ 6.0环境下，根据数据结构所学知识运用C语言编写一个8行*8列64格，满足“马走日字”的规则的骑士游历游戏来巩固数据结构知识，对理论知识加以实践，加深对知识的理解与运用。
第二章 递推练习 2014-2-23 例1:已知费波那契数列的前几个数分别为0,1,1,2,3,5,8,13,……,编程求此数列的前n 项。 样例输入:30 样例输出:514229 例2:用迭代法求y= 的值。X 由键盘输入。利用下列迭代公式计算yn=2/3*yn-1+x/(3*yn-1*yn-1)，初始值y0=x ，误差要求在10-4 练习1：楼梯问题 问题描述：设有一个共有n 级的楼梯，某人每步可走1级，也可走2级，用递推公式给出某人从底层开始走完全部楼梯的走法。例如：当n=3时，共有3种走法，即1+1+1 1+2 2+1. 输入数据：n 为6 输出数据：13 [练2] 小猴子第一天摘下若干桃子,当即吃掉一半,又多吃一个.第二天早上又将剩下的桃子吃一半,又多吃一个.以后每天早上吃前一天剩下的一半另一个.到第10天早上猴子想再吃时发现,只剩下一个桃子了.问第一天猴子共摘多少个桃子？ 例3：问题描述:火车从始发站（称为第一站）开出，在始发站上车的人数为a ，然后到达第二站，在第2站有人上车、下车，但上、下车的人数相等，因此在第2站开出时（即到达第3站之前）车上的人数保持为a 人。从第3站起（包括第3站）上、下车的人数有一定的规律:上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（n-1站），都满足此规律。现给出的条件是:共有n 个车站，始发站上车的人数为a ，最后一站下车的人数是m （全部下车）。试问在第2站上车的人数？从x 站开出时车上的人数是多少？ 输入:a,n,m,x 输出:x 站开出时车上的人数，如果无法求解则输出‘noanswer’ 输入：5 7 32 4 输出：3 13 练习3、栈（noip2003pj ）题目大意：求n 个数通过栈后的排列总数。（1≤n ≤18） 如输入 3 输出 5 练习4、过河卒棋盘上A 点有一个过河卒，需要走到目标B 点。卒行走的规则：可以向下、或者向右。同时在棋盘上的任一点有一个对方的马（如下图中的C 点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点（如下图中的C 点和P1，P2，……，P8）。卒不能通过对方马的控制点。棋盘用坐标表示，A 点(0,0)、B 点(n, m) (n,m 为不超过20的整数),同样马的位置坐标是需要给出的，C ≠A 且C ≠B 。现在从键盘输入n ，m ，要你计算出卒从A 点能够到达B 点的路径的条数。 输入：6 6 3 2 输出：17 扩展1、贮油点：一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。显然卡车装一次油是过不了沙漠的。因此司机必须设法在沿途建立若干个贮油点，使卡车能3x
程序设计艺术与方法 实验一STL 的熟悉与使用 1．实验目的（1）掌握C++中STL 的容器类的使用。（2）掌握C++中STL 的算法类的使用。 2．试验设备硬件环境：PC 计算机软件环境：操作系统：Windows 2000 / Windows XP / Linux 语言环境：Dev cpp / gnu c++ 3．试验内容(1) 练习vector 和list 的使用。定义一个空的vector，元素类型为int，生成10 个随机数插入到vector 中，用迭代器遍历vector 并输出其中的元素值。在vector 头部插入一个随机数，用迭代器遍历vector 并输出其中的元素值。用泛型算法find 查找某个随机数，如果找到便输出，否则将此数插入vector 尾部。用泛型算法sort 将vector 排序，用迭代器遍历vector 并输出其中的元素值。删除vector 尾部的元素，用迭代器遍历vector 并输出其中的元素值。将vector 清空。定义一个list，并重复上述实验，并注意观察结果。(2) 练习泛型算法的使用。 - 149 定义一个vector，元素类型为int，插入10 个随机数，使用sort 按升序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用find 查找元素。用min 和max 找出容器中的小元素个大元素，并输出。 源代码： #include 动态规划部分常见题目 作者: 发表于2011-06-10 14:20:49【大中小】浏览:230次评论:0条 求两个字符串的最长公共子序列 0-1背包问题 骑士游历 设有一个n*m的棋盘(2<=n<=50,2<=m<=50),在棋盘上任一点有一个中国象棋马,马走的规则为:1.马走日字 2.马只能向右走. 任务1:当N,M 输入之后,找出一条从左下角到右上角的路径. 例如:输入 N=4,M=4 输出:路径的格式:(1,1)->(2,3)->(4,4) 若不存在路径,则输出"no" 任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目. 例如:(N=10,M=10),(1,5)(起点),(3,5)(终点) 输出:2(即由(1,5)到(3,5)共有2条路径) 输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标) 输出格式:路径数目(若不存在从起点到终点的路径,输出0) 数字三角形 （图３.１－１）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路 径，使该路径所经过的数字的总和最大。 ●每一步可沿左斜线向下或右斜线向下走； ●1＜三角形行数≤100； ●三角形中的数字为整数0，1，…99； 输入数据： 由INPUT.TXT文件中首先读到的是三角形的行数。 在例子中INPUT.TXT表示如下： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 输出数据： 把最大总和（整数）写入OUTPUT.TXT文件。上例为： 30 ７ ３８ ８１０ ２７４４ ４５２６５ （图３.１－１） 添加号 有一个由数字1，2，... ，9组成的数字串（长度不超过200），问如何将M(M<=20)个加号("+")插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。 注意： 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。 M保证小于数字串的长度。 例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。 图1 骑士单次L 形路线的方向示意图 Fig.1Sketch map of knight single L-shaped route directions 收稿日期：2011-03-17 稿件编号：201103098 作者简介：惠燕（1979—），女，陕西咸阳人，硕士，讲师。研究方向：计算机网络管理和计算机软件理论。 骑士游历问题算法的研究 惠燕，潘煜 （西安工业大学计算机学院，陕西西安710032） 摘要：骑士游历问题是一个经典的数学问题。其思想在电路图的设计及图像加密等方面都有帮助，如果能将骑士游历问题算法通过计算机语言程序化将对其在其他领域中的应用有极大帮助。通过研究骑士游历的规则对问题进行数学模型抽象，通过研究骑士游历的方向与可到达情况，将骑士的空间移动抽象成数学表达式，进而映射到程序中所需对应的数据结构形式，最后通过利用JAVA 语言得以实现骑士游历问题中骑士游历过程的动态图形演示。关键词：骑士；游历；欧拉；方向中图分类号：TP311.1 文献标识码：A 文章编号：1674－6236（2011）11-0112-03 Research on knight travel problem algorithm HUI Yan ，PAN Yu （College of Computer ，Xi ’an Technological University ，Xi ’an 710032，China ） Abstract ：Knight travel problem is a classical mathematical problem.Its thought contributes to the circuit diagram design and image encryption.If it can be programmed which will have great help in other application fields ，it made mathematical model abstraction through the study on the rules of knight travel problems ，researched on the direction and the reached conditions of knight travel ，knight ’s moving was abstracted into mathematical expressions ，then mapped to the corresponding data structures required in the program ，and at last ，using JAVA language realized knight travelled graphic demonstration of dynamic processes. Key words ：knight ；travel ；Euler ；direction 骑士游历问题是一个古老而著名的问题，问题的描述是：在8×8格的国际象棋棋盘上，象棋马能否从某个格子出发按照“马跳日”的规则跳遍所有64个格子最后再回到出发的那个格子?国际象棋中的马，英语为knight ，恰好又意指中世纪西方世界的“骑士”，因此，这个问题又被称为“骑士游历”问题。该问题即可以理解为国际象棋中的棋子在一个空棋盘内移动，问它能否经过六十四格并且只经过一次？骑士按“L ”形路线移动，即在某方向前进两格，接着在与原方向垂直的方向上前进一格。 1骑士游历问题模型的数学抽象 骑士游历问题最初是由大数学家欧拉（Euler ）在1759年 开始研究的。定义1：给定无孤立结点图G ，若存在一条路，经过图中每边一次且仅一次，该路称为欧拉路；若存在一条回路，经过图中每边一次且仅一次，该回路称为欧拉回路[1]。 骑士游历问题因为它的典行性和可研究性，引来了国内外很多数学爱好者和程序设计者的注意。自从数学家提出这个问题以来，有很多人开始潜心研究。根据问题的描述可知求解骑士游历问题的每一步就是马在棋盘上走的每一步变化，而具体解决问题的关键在于骑士可走的8个方向以及可走的方向上相应的数据变化的确定[2-3]。 1.1方向的研究1.1.1 方向的分类 骑士游历的规则确定了骑士游历的方向。在国际象棋的 棋盘里总共有8×8个格子，若使棋子“骑士”从任何一个格子开始，按照L 形路线（在某方向前进两格，接着在与原方向垂直的方向上前进一格）移动方法，游历每一个格子，并且每个格子只允许被到达一次，则每次骑士可走的有8个方向的选择。图1是骑士将某一位置作为起始位置，继续按照在某方向前进2格，接着在与原方向垂直的方向前进1格的方式即所谓L 形路线可走的8个方向的示意图。 电子设计工程 Electronic Design Engineering 第19卷Vol.19第11期No.112011年6月Jun.2011 －112－ 《Java基础》实验题和课程设计补充题 《Java基础》课程实验题 专业：计算机科学与技术、软件工程、网络工程（2013级起） 教材：《Java程序设计实用教程（第4版）》 第6章图形用户界面 实验目的、要求和题意详见教材实验6。选题分配如下。 6-1 裁判评分。 6-2 算术表达式计算。 6-3 计算器。 6-4 货币转换，使用表格组件显示汇率表。 6-5 复数表达式计算。 6-6 整数多种进制转换。 6-7 十进制整数的算术运算及二进制显示。 6-8 整数位运算及二进制显示。 6-9 制作日期组件和月历组件，日期运算。见实验6-38和6-39。 6-10 显示字符串中每个字符的Unicode值。 6-11 例6.4 Person对象信息管理增加功能，见思考题 6-3。 6-12 Friends对象信息管理，图形用户界面类似例6.4，Friends类声明见教材实验3。 6-13 Student对象信息管理，见思考题6-3⑤。 6-14 例6.4 Person对象信息管理增加功能，见思考题 6-3，使用表格。 6-15 Friends对象信息管理，题同6-12，使用表格。 6-16 Student对象信息管理，见思考题6-3⑤，使用表格。 6-17 例6.5 文本编辑器增加功能，见思考题6-4。 6-18 例6.6 银行贷款计算增加功能，见思考题6-5，并提供等额本息还款法等多种还款方式计算银行贷款每月还本付息金额。 6-19 缴税计算。 6-20 课程成绩多级统计。 6-21 幻方阵的图形用户界面，幻方阵题见教材第44页例2.6。 6-22 杨辉三角的图形用户界面，杨辉三角题见教材第50页例2.8。 6-23 下标和相等方阵的图形用户界面，题意详见教材实验2。 6-24 约瑟夫环的图形用户界面，题意详见教材实验2。 6-25 哥德巴赫猜想的图形用户界面，题意详见教材实验2。 6-26 Smith数的图形用户界面，题意详见教材实验2。 6-27 亲密数对的图形用户界面，题意详见教材实验2。 6-28 求n个数的最大公约数和最小公倍数，图形用户界面，题意详见教材实验2。 6-29 识别字符串中包含的所有标识符，图形用户界面，题意详见教材实验2。 6-30 绘制平面图形并计算周长和面积。 6-31 等腰三角形、正五边形与五角星等图形设计，指定图形大小、位置和颜色，最小化后恢复全部图形。 6-32 星形线图形设计，指定图形大小、位置和颜色。 6-33 心形线图形设计，指定图形大小、位置和颜色。 6-34 阿基米德螺线图形设计，指定图形大小、位置和颜色。 NOI’95 “同创杯”全国青少年信息学（计算机）奥林匹克竞赛 分区联赛复赛试题（高中组） （上机编程，完成时间：210分钟） <1>编码问题： 设有一个数组A:ARRAY[0..N-1] OF INTEGER； 数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。 例如：N=6时，有：A=（4，3，0，5，1，2） 此时，数组A的编码定义如下： A[0]的编码为0； A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）∴上面数组A的编码为：B=（0，0，0，3，1，2） 程序要求解决以下问题： ①给出数组A后，求出其编码。 ②给出数组A的编码后，求出A中的原数据。 <2>灯的排列问题： 设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……N k（k表示不同颜色灯的个数）。 放灯时要遵守下列规则： ①同一种颜色的灯不能分开； ②不同颜色的灯之间至少要有一个空位置。 例如：N=8（格子数） R=2（红灯数） B=3（蓝灯数） 放置的方法有： R-B顺序 B-R顺序 放置的总数为12种。 数据输入的方式为： N P1（颜色，为一个字母）N1（灯的数量） P2 N2 …… Q（结束标记，Q本身不是灯的颜色） 程序要求：求出一种顺序的排列方案及排列总数。 <3> 设有一个四层的积木块，1～4层积木块的数量依次为：5，6，7，8 如下图所示放置： 其中，给出第三层与第四层所标示的数字，并已知第三层的数据是由第四层的数据计算出来的。 计算的方法是：第三层的某个数据A是由第四层相邻的两个数据B，C经过某种计算后产生的： 计算所用到的计算符为：+，-，?，且无优先级之分（自左向右计算），运算符最多为2个。 如：3+4?5=35 5?4+3=23 可以看出，上图中的第三层的数据是由第四层的数据用以下计算公式计算出来的： A=B?C+B 也就是：8=2?3+2，15=3?4+3，……14=2?6+2 程序要求： 给出第四层与第三层的数据后，将第一、二层的每块积木标上相应的数据，并输出整个完整的积木图及计算公式。 ①输入数据不存在出错的情况，同时也不会超过整数的范围。 课程实验报告汇总 ————————————————————————————————作者：————————————————————————————————日期: ? 实验一 SＴL的熟悉与使用 实验名称实验一STL的熟悉与使用 姓名汪子成系院专业信息工程系班级 计算机15－1 班 学号20152１６7５８ 实验日期指导教师徐本柱成绩 一、实验目的和要求 1．掌握C++中ＳＴL的容器类的使用; 2.掌握C++中ＳTL的算法类的使用. 二、实验预习内容 1．预习ICPC讲义，大致了解STL的相关内容。 2.了解STL中一些类vｅctor ｌist类的使用方法 3.了解泛型算法的使用 三、实验项目摘要 (1) 练习vecｔor 和ｌist 的使用。定义一个空的veｃtor，元素类型为int,生成10个随机数插入到 veｃtor中,用迭代器遍历vector并输出其中的元素值。在vecｔoｒ头部插入一个随机数，用迭代器遍历veｃtor并输出其中的元素值。用泛型算法fiｎd 查找某个随机数,如果找到便输出,否则将此数插入veｃｔor 尾部。用泛型算法sort 将vectoｒ排序，用迭代器遍历ｖeｃtor 并输出其中的元素值。删除ｖectoｒ尾部的元素,用迭代器遍历vectoｒ并输出其中的元素值。将ve ｃtor清空。定义一个ｌｉst,并重复上述实验,并注意观察结果。 (2)练习泛型算法的使用。定义一个vector，元素类型为int,插入1０个随机数，使用ｓoｒt按升 序排序，输出每个元素的值，再按降叙排序，输出每个元素的值。练习用finｄ查找元素。用min和ｍaｘ找出容器中的最小元素和最大元素,并输出。 【题7】骑士游历问题（2） 设有一个n*m的棋盘(2≤n≤50，2≤m≤50)，如图１１.2.1。在棋盘上任一点有一个中国象棋马， 图１１.2.1 马走的规则为： 1.马走日字 2.马只能向右走。即图１１.2.2所示： 图１１.2.2 当N，M 给出之后，同时给出马起始的位置和终点的位置，试找出从起点到终点的所有路径的数目。例如：(N=10，M=10)，(1，5)(起点)，(3，5)(终点)。应输出2(即由(1，5)到(3，5)共有2条路径，如图１１.2.3)： 图１１.2.3 输入： n，m，x1，y1，x2，y2(分别表示n，m，起点坐标，终点坐标) 输出： 路径数目(若不存在从起点到终点的路径，输出0) 题解 由【例题10.2.1】骑士游历问题（1）看出，使用回溯法同样可以计算路径数目。只要将起点（1，1）和终点（n，m）调整为（x1，y1）、（x2，y2），并在回溯程序(search(k，x，y))中，将马跳到目的地时由退出程序（halt）改为回溯（exit）即可。但问题是搜索效率太低，根本不可能在较短的时间内出解。本题与【例题10.2.1】骑士游历问题（1）不同，并不要求每一条路径的具体走法。在这种情况下，是否非得通过枚举所有路径方案后才能得出路径数目，有没有一条简便和快效的“捷径”呢。 从(x1，y1)出发，按照由左而右的顺序定义阶段的方向。位于（x，y）左方且可达（x，y）的跳马位置集合都是（x，y）的子问题，起点至（x，y）的路径数实际上等于起点至这些位置集的路径数之和（图11.2.4）。 图11.2.4 如此一来，状态转移关系便凸显出来。设状态转移方程map，其中map[i，j]为起点（x1，y1）至（i，j）的路径数目。由于棋盘规模的上限为50*50，可能导致路径数目大得惊人，因此不妨设map数组的元素类型为extended。初始时，除map[x1，y1]=1外其余为０。显然 第10章课程设计 10.4 课程设计选题 课程设计的目的、要求和选题详见教材10.4节，及课程设计任务书。 10.4.1 线性表 1. 多项式的表示和运算 题意详见教材2.4节。 （1）使用排序单链表存储多项式 10-1 ?一元多项式相加，PolySinglyList 数据结构课程设计报告 目录 1 设计目的与意义 (3) 2 系统描述 (3) 3 运行环境 (3) 4 系统的分析与设计 (3) 4.1 程序结构说明 (3) 4.2 AccessibleSquare算法实现 (4) 4.3 画图类算法实现 (5) 4.4 主调用程序的设计和开发 (7) 5 系统测试 (7) 5.1 游戏初始界面 (8) 5.2 游戏以（1，1）为起点运行界面 (8) 5.3 游戏以（6，3）为起点界面 (9) 5.4 游戏以（6，3）为起点运行界面 (9) 6 总结 (10) 源程序 (10) 1 设计目的与意义 Java课程设计是计算机科学与技术专业学生必做的集中实践性环节之一，是学习完《Java程序设计》课程后进行的一次全面的综合练习。其目的在于通过课程设计，使学生能够得到较系统的技能训练，从而巩固和加深对Java 编程的基础理论知识的理解，培养学生综合运用所学理论解决实际问题的能力，使学生成为具有扎实的计算机理论基础和较强的独立动手能力的复合型、应用型人才。 2 系统描述 骑士游历问题是一个古老而著名的问题，它最初是由大数学家Euler提出的。问题是这样的：国际象棋中的棋子(叫作骑士)在一个空棋盘内移动，问它能否经过64格中的每一格且只经过一次？(骑士按L行移动,即在某方向前进两格接着在与原方向垂直的方向上前进一格) 该课程设计要求实现骑士游历问题的求解，并能够演示起始位置在棋盘上任何位置的游历问题的实现。程序将采用动态的图形演示，使算法的描述更形象、更生动。本程序采用Applet来编制整个程序，这样既可以加深对算法的实现的了解，也可以进一步熟悉Java图形界面、Applet以及Java语言的命名规范。 骑士游历的课程设计是按照面向对象的思想进行开发，其中主要的类包括AccessibleSquare 类、MyPanel类和KnightsTour类。其中AccessibleSquare 类主要是算法实现，采用启发式算法；KnightsTour类是主类，或者说是控制类，它完成对算法类和图画类的调用；MyPanel类是画图类用来实现图形化显示结果。 3 运行环境 本程序是在windows xp的环境下运行的。 4 系统的分析与设计 4.1 程序结构说明 本程序由三个类组成一个工程文件。其中KnightsTour是主类，或者说是控制类，AccessibleSquare类主要是算法实现，MyPanel实现图形化显示结果。 程序的运行关系如图4-1。 存档资料成绩： 华东交通大学理工学院 课程设计报告书 所属课程名称数据结构 题目骑士游历 分院 专业班级 学号 学生姓名黄锦辉 指导教师 2012 年6月15 日 目录 第1章课程设计内容及要求 (1) 第2章功能的说明与实现 (2) 2.1 程序功能模块 (2) 2.2 程序功能模块图 (2) 第3章程序功能的具体实现 (3) 3.1 主函数main()的执行流程 (3) 3.2 系统测试与调试 (3) 第4章源代码 (6) 第5章课程设计心得 (9) 第6章参考文献 (10) 第1 章课程设计内容及要求 运行程序设置一个8行8列的棋盘，在国际象棋的原则下，任意的输入一个存在的点，这个被视为骑士（马）的初始位置，让马通过这个点走完棋盘上的每一个点，并且不重复。在对已经走过的路线里，采用标志矩阵进行记录。标志矩阵的引入利用了数据的线性存储。这个称为骑士游历算法。 本课程设计所采用的计算机语言是C语言，所使用的软件是使用比较普遍的Microsoft Visual C++ 软件。 第2章 功能的说明与实现 2.1 程序功能模块 总共分为三个模块，分别是创建棋盘模块，位置设置模块和显示结果模块 1.创建棋盘模块：此时我们使用矩阵设计一个模拟的棋盘。其关键代码如下： int f[11][11] ; /*定义一个矩阵来模拟棋盘*/ int adjm[121][121]; /*于上述棋盘，标志矩阵*/ void creatadjm(void) /*创建标志矩阵函数声明*/ void mark(int,int,int,int); /*将标志矩阵相应位置置1*/ void travel(int,int); /*巡游函数声明*/ int n,m; /*定义矩阵大小及标志矩阵的大小*/ 2.位置设置模块：输入任意一个在8行8列棋盘中的一个点，其格式表示为：m n （m 表示行，n 表示列）。 3.显示结果模块：将起始位置设定好了，将在这个模拟棋盘中用数字显示马走过的每一步。 2.2 程序功能模块图 总共有三个模块，如下图所示： 图2.2—1 骑士游历 创建棋盘 显示结果 位置设置 创建矩阵 进行游历 显示结果动态规划部分常见题目
骑士游历问题算法的研究
《Java基础》实验题和课程设计补充题
历届noip提高组复赛试题
课程实验报告汇总
【题07】骑士游历问题(2)
《数据结构(Java版)(第4版)》课程设计题
(完整word版)骑士游历java课程设计
骑士游历、骑士巡游(C语言)课程设计[1]
相关主题
文本预览