1、 (龟图)Logo语言是年轻的计算机用户所熟悉的种语言,龟图是 这种种语言的一个著名应用。想像一只机器海龟在
Java程序的控制 下在房间内移动。海龟有一支画笔,可以处在两种位置,笔头朝上或 朝下。当画笔朝下时,海龟画出其运动的轨迹;当画笔朝上时,海龟 自由移动,不会写下任何内容。请模拟海龟的操作并创建一个计算机 化的图板。使用一个20*20的数组floor,并将其初始化为0。从一 个包含命令的数组中读取命令, 始终跟踪海龟的当前位置以及画笔的 朝向。假定海龟总是从位置(0,0)开始移动,并且画笔朝上。程序 中必须处理的海龟命令如下: 命令 1 2 3 4 5,10 6 9 含义 画笔朝上 画笔朝下 右转 左转 向前走10步(或不为10的步数) 打印20*20的数组 数据结束(循环结束标志)
假如海龟在图板中心附近的某个位置上,下面的“程序”将在画 笔朝上时画出一个12*12的正方形。 2 5,12 3
5,12
3
5,12
3
5,12
5,12
1
6
9
当海龟在运动的画笔朝下,将数组floor的相应元素置为1。当给出6号命令(打印)时,若某数组元素为1,则显示一个星号,或者显示其它字符;若某数组元素为0,就显示一个空格。编写一个程序,实现龟图功能。编写几个龟图程序,画出有趣的图形,并增加它命令,使龟图语言的功能更强大。
2、(骑士旅行)国际象棋中最有趣的难题之一是骑士旅行问题,最早由数学家欧拉(Euler)提出。这个问题是:骑士这枚棋子在空棋盘上到处移动,能否经过64个方格且在第个方格上只经过一次?我们这里深入讨论一个这个有趣的问题。骑士在棋盘上做L形运动(在一个方向上走过两格然后在垂直的方向上走一格)。因此,从个空棋盘的中间开始,骑士可如图所示完成8种不同的移动(记为0到7)。
a) 在纸上画出一个8*8的棋盘,尝试手工进行骑士的旅行。在要移入的第一方格中放入1,第二个方格中放入2,第三个放入3,依
次类推。在旅行开始前,估计一下能走到多远,记住,一个完整的旅行包含64次移动。最终走了多远?符合以前的估计吗?
b) 现在让我们开发一个程序,使骑士在棋盘上旅行。使用一个8*8二维数组board表示棋盘,每一个方格初始化为0。我们根据水平和垂直方向描述8种可能的移动。例如,图5。20中的位移0包括水平向右移动两格及垂直向上移动一格。位移2包括向左移动一格再向上移动两格。水平向左和垂直向上用负数表示。8种移动可由两个单下标数组horizontal和vertical描述,如下所示:
horizontal[0] = 2
horizontal[1] = 1
horizontal[2] = -1
horizontal[3] = -2
horizontal[4] = -2
horizontal[5] = -1
horizontal[6] = 1
horizontal[7] = 2
vertical[0] = -1
vertical[1] = -2
vertical[2] = -2
vertical[3] = -1
vertical[4] = 1
vertical[5] = 2
vertical[6] = 2
vertical[7] = 1
变量currentRow和currentColumn表示骑士当前位置的行和列。为了进行moveNumber型的移动(其中moveNumber介于0到7之间),程序中应使用语句:
currentRow += vertical[moveNumber];
currentColumn += horizontal[moveNumber];
使一个计数器从1到64变化,记录下骑士所移到的方块的最新数据。试试每种可能的移动,看看骑士是否已经访问过那个方块,并确保骑士尚未走出棋盘。编写一程序,使骑士在棋盘上旅行运行一个该程序,骑士走过了多少步?
骑士的8种移动
c) 在尝试过编写和运行骑士旅行程序之后,读者可能已经获得了一些有价值的想法。我们将使用这些观点来开发一个试探法(或策略),用于移动骑士。试探法并不能保证成功,但一个精细开发的试探法可以大增加成功的概率。读者可能已经注意到,外层的方格比起靠近棋盘中心的方格,在移动方面更麻烦一些事实上,最难到达的方格是四角的方格。凭借直觉,应首先尝试将骑士移到最不容