馬踏棋盤程序設(shè)計(jì)

1、問(wèn)題描述 設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏棋盤的演示程序。基本要求將馬隨機(jī)放在國(guó)際象棋8*8的棋盤Board88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格只進(jìn)入一次，走遍棋盤全部的64個(gè)方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，3.64一次填入一個(gè)8*8的方陣 輸出之測(cè)試數(shù)據(jù)可自行指定一個(gè)馬的初始位置（i,j）,0<=i,j<=7.。實(shí)現(xiàn)提示一般說(shuō)來(lái)，當(dāng)馬位于位置（i,j）時(shí)，可以走到下列8個(gè)位置之一 （i-2,j+1）,(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1), (i+1,j-2),(i-1,j-2),(i-2,j

2、-1)但是，如果（i，j）靠近棋盤的邊緣，上述有些位置可能超出棋盤范圍，成為不允許的位置。8個(gè)可能位置可以用一維數(shù)組Htry107和HTry20.7來(lái)表示：Htry1 0 1 2 3 4 5 6 7-2 -1 1 2 2 1 -1 -2Htry2 0 1 2 3 4 5 6 712 2 1 -1 -2 -2 -1位于（i,j）的馬可以走到新位置是在棋盤范圍內(nèi)的（i+ Htry1h,j+ Htry2h）,其中h=0,1,.7.一需求分析1輸入的形式和輸入值的范圍； 分開(kāi)輸入馬的初始行坐標(biāo)X和列坐標(biāo)Y，X和Y的范圍都是0,7。2輸出的形式； 一共提供了2種輸出方式：（1）以數(shù)組下標(biāo)形式輸入，代表起

3、始位置，i表示行標(biāo)，j表示列標(biāo)。（2）以棋盤形式輸出，每一格打印馬走的步數(shù)，這種方式比較直觀。3程序所能達(dá)到的功能；讓馬從任一起點(diǎn)出發(fā)都能夠歷遍整個(gè)8×8的棋盤。二概要設(shè)計(jì)1設(shè)定棧的抽象數(shù)據(jù)類型定義：ADT Stack 數(shù)據(jù)對(duì)象：D=ai|aiCharSet,i=1,2.,n 數(shù)據(jù)關(guān)系:R1=<ai-1,ai>|ai-1,aiD,i=2,.,n 基本操作:(這里僅列舉本題中使用的操作) InitStack(&S) 操作結(jié)果:構(gòu)建一個(gè)空棧。 Push(&S,e) 操作結(jié)果:在棧頂插入新的元素。 Pop（&S,&e） 操作結(jié)果：將棧頂元素彈出。

4、SetTop(S,& e) 操作結(jié)果：將e設(shè)為棧頂元素。GetTop(S, &e)操作結(jié)果：將棧頂元素取出。StackEmpty(S) 判斷棧是否為空 ADT Stack 2本程序包含2個(gè)模塊(1).主程序模塊:Void main() 初始化棋盤；while(1) 接受命令；處理命令；執(zhí)行Path(x,y);(2).棧模塊實(shí)現(xiàn)棧抽象數(shù)據(jù)類型3探討每次選擇位置的“最佳策略”思路1）先求出每個(gè)坐標(biāo)點(diǎn)的權(quán)值，即是該坐標(biāo)下一步有幾個(gè)方向可以走2）權(quán)值越小,則被上一點(diǎn)選中的可能性就越大，下一個(gè)方向八個(gè)值的選擇順序保存MAPXYK數(shù)組中，0<=K<=7，例如MAPXY0保存的是

5、下一步優(yōu)先選擇走的方向，MAPXY7就是最后才走的。邊界的點(diǎn)最先走，然后再走中間。4踏遍棋盤偽碼算法：While（）若已經(jīng)走了64步,則 打印輸出結(jié)果； 否則若該點(diǎn)所有方向已走完出棧 若該點(diǎn)所有方向未走完 若該點(diǎn)未走過(guò)且在棋盤內(nèi) 入棧，已走步數(shù)加1否則*下一步方向加1 三詳細(xì)設(shè)計(jì)1棧類型struct SElemType int a; int b; int di;/方向編號(hào) int flag8;/訪問(wèn)過(guò)的方向數(shù);棧的順序存儲(chǔ)表示 typedef struct SqStack SElemType *base; SElemType *top; int stacksize;?；静僮鳎篠tatus I

6、nitStack(SqStack *S) /* 構(gòu)造一個(gè)空棧S */ (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存儲(chǔ)分配失敗 */ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; Status StackEmpty(SqStack S) /* 若棧S為空棧，則返回TRUE，否則返回FALSE */ if(S.top=S.base) return TRUE; els

7、e return FALSE; Status GetTop(SqStack S,SElemType *e) /* 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR/ if(S.top>S.base) *e=*(S.top-1); return OK; else return ERROR; Status SetTop(SqStack S,SElemType *e) if(S.top>S.base) *(S.top-1)=*e; return OK; else return ERROR; Status Push(SqStack *S,SElemType e) /* 插入

8、元素e為新的棧頂元素 */ if(*S).top-(*S).base>=(*S).stacksize) /* 棧滿，追加存儲(chǔ)空間 */ (*S).base=(SElemType*)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /* 存儲(chǔ)分配失敗 */ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; Sta

9、tus Pop(SqStack *S,SElemType *e) /* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; 2求最佳策略算法 求各點(diǎn)權(quán)值:可走的方向數(shù)越少,則被上一點(diǎn)選中的可能性越大int num(int x1,int y1) int count1=0; for(int j=0;j<8;j+) int x2=x1+Htry1j; int y2=y1+Htry2j; if(Pass(x2,y2) count1+; retu

10、rn count1;主要程序：#include <stdio.h>#include<malloc.h>#include<string.h>#define STACK_INIT_SIZE 10#define STACKINCREMENT 2int board88=0; /棋盤初始化int Htry18=-2,-1,1,2,2,1,-1,-2;int Htry28=1,2,2,1,-1,-2,-2,-1;struct SElemType int a; int b; int di; int flag8;typedef struct SqStack SElemTyp

11、e *base; SElemType *top; int stacksize;void InitStack(SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(0); S.top=S.base; S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.base=S.top) return 1;else return 0;void Push(SqStack &S,SElemType

12、&e) if(S.top-S.base>=S.stacksize) S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(0); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e;int Pop(SqStack &S,SElemType &e) if(S.top=S.base) return 0; e=*-S.top; return 1;i

13、nt Pass(int i,int j) if(i>=0&&i<=7&&j>=0&&j<=7&&boardij=0) return 1; else return 0;/判斷該方向是否能夠通過(guò)int num(int x1,int y1) int count1=0; for(int j=0;j<8;j+) int x2=x1+Htry1j; int y2=y1+Htry2j; if(Pass(x2,y2) count1+; return count1;SElemType NextPos(SElemType

14、 e) int x1,y1; int i,j; int x=e.a; int y=e.b; int p=0; int di_num=0; int di_min=8; for(i=0;i<8;i+) if(e.flagi!=0) continue;/判斷該方向是否走過(guò) x1=x+Htry1i; y1=y+Htry2i; if(Pass(x1,y1) di_num=num(x1,y1); if(di_num<di_min) /判斷該方向是否有最少的可通過(guò)方向 e.a=x1; e.b=y1; di_min=di_num; p=i; e.flagp=1; return e;int sear

15、ch(int x,int y,SqStack &S) SElemType e,curpos; int count=0; memset(curpos.flag,0,sizeof(curpos.flag);/將結(jié)構(gòu)體中的flag賦0 curpos.a=x; curpos.b=y; while(count<64) x=curpos.a; y=curpos.b; if(Pass(x,y)若找到下一個(gè)點(diǎn)，則將該點(diǎn)壓入棧中 count+; /printf("count=%d n", count); boardxy=count; e.di=0; e=curpos; Push

16、(S,e); curpos=NextPos(e); memset(curpos.flag,0,sizeof(curpos.flag); else if(!StackEmpty(S) Pop(S,e); else return 0; count-; while(e.di=7&&!StackEmpty(S)若8個(gè)方向都不能通過(guò)，則從棧中彈出上一個(gè)點(diǎn) boarde.ae.b=0; Pop(S,e); count-; if(e.di<7)若該點(diǎn)的還有方向沒(méi)有訪問(wèn)過(guò)，則換下一個(gè)方向 e.di+; Push(S,e); count+; curpos=NextPos(e); memset(curpos.flag,0,sizeof(curpos.flag); return 1;void display()/將馬的軌跡輸出 int i,j; for(i=0;i<8;i+) for(j=0;j<8;j+) printf("%2d ",boardij); printf("n"); int main()/主函數(shù) int x,y; SqStack S; InitStack(S); printf("輸入馬的初始位置：n"); scanf("%d%d",&