趣味智能模擬程序設(shè)計實(shí)例*

馬　旭　王大勇

(遼寧大學(xué)計算中心　沈陽　110036)

?

趣味智能模擬程序設(shè)計實(shí)例*

馬旭王大勇

(遼寧大學(xué)計算中心沈陽110036)

摘要計算機(jī)軟件模塊化、組件化,越來越多的計算機(jī)用戶不再注重傳統(tǒng)編程。列舉騎士游歷問題、九宮八數(shù)問題,韓信分油問題三個應(yīng)用深度搜索編程的趣味智能模擬程序,并給出九宮八數(shù)問題的完整C語言程序,對這一類程序概述講解,希望能激發(fā)更多學(xué)生的編程興趣。

關(guān)鍵詞騎士游歷問題; 九宮八數(shù)問題; 韓信分油問題; 深度搜索; 智能模擬

Class NumberTP311.11

1引言

今天,計算機(jī)的應(yīng)用已在網(wǎng)絡(luò)、媒體等方方面面廣泛普及,計算機(jī)軟件模塊化、組件化也已逐漸形成,越來越多的計算機(jī)應(yīng)用基本上已不再需要編寫大量代碼(程序),只需要下載或調(diào)用相應(yīng)軟件模塊或組件即可完成,傳統(tǒng)的程序設(shè)計思想及方法已不再被廣大計算機(jī)用戶重視了。

本文列舉一些智能模擬的趣味程序深度搜索類程序,并給出其九宮八數(shù)問題的傳統(tǒng)C語言程序及概述說明,希望能通過這些趣味程序激發(fā)更多學(xué)生的編程興趣。

2三個智能模擬程序

2.1九宮八數(shù)問題(九宮格)

在一個3*3的九宮格中,隨機(jī)擺放1～8這8個數(shù),如圖1(a)所示,每次只能將與空格相鄰的一個數(shù)字移動到空格中。現(xiàn)在要求將該九宮格調(diào)整為任一指定樣式,如圖1(b)所示,試編程實(shí)現(xiàn)這一問題的求解。

圖1　給定原始矩陣及目標(biāo)矩陣

2.2騎士游歷問題

在8*8格的國際象棋盤上,象棋“馬”能否從某一指定單元格出發(fā),按照其“馬走日”的行走規(guī)則跳遍所有64格,且每個單元格只能跳一次。(或者再進(jìn)一步要求,能否跳回到出發(fā)位子？)編程給出其游歷過程。

2.3韓信分油問題

有10斤裝、7斤裝、3斤裝三個油桶,在10斤裝的大油桶里裝滿油,7斤裝、3斤裝的油桶都是空的,現(xiàn)在要把這10斤油平均分給兩人,每人分5斤。兩人都沒有帶秤,應(yīng)該怎么分？

3九宮八數(shù)問題C程序及圖解答案

3.1編程簡述

九宮八數(shù)問題與上述其他兩個智能模擬問題相似,各種狀態(tài)(結(jié)點(diǎn))可組成一個無向圖結(jié)構(gòu),每個狀態(tài)都可能和任意狀態(tài)相連通,如圖2所示。圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索,本例采用廣度優(yōu)先搜索,遍歷類似于樹的先序遍歷,是樹的先序遍歷的推廣。

圖2　給定原始矩陣及目標(biāo)矩陣

本例move(int a[3][3])函數(shù),以空白點(diǎn)(標(biāo)志為0)的上下左右移動為序,首先備份當(dāng)前狀態(tài)A到X、Y,判斷當(dāng)前狀態(tài)X是否為目標(biāo)狀態(tài),若是則輸出訪問路徑,程序結(jié)束;否則順序判斷其每一相鄰狀態(tài)是否可行,即是否已經(jīng)遍歷過,若可行,則將該狀態(tài)存入訪問路徑矩陣,遞歸調(diào)用訪問該狀態(tài)結(jié)點(diǎn),訪問后需還原(回溯)X狀態(tài)mcopy(x,y),再判斷下一相鄰狀態(tài)。當(dāng)前狀態(tài)X的所有相鄰狀態(tài)結(jié)點(diǎn)都被訪問后,移動次數(shù)減一,同時訪問路徑行計數(shù)也減一,以撤銷訪問路徑矩陣中已存儲的本次訪問,結(jié)束本次調(diào)用。程序中其他輔助函數(shù)已概述說明。

3.2九宮八數(shù)問題C程序及概述說明

#include "stdio.h"

/* 九宮八數(shù)問題 */

/* 定義目標(biāo)矩陣b[3][3],訪問路徑矩陣pass[50][9],

用戶給定的最多移動次數(shù)n,移動次數(shù)計數(shù)變量n。 */

int b[3][3]={1,2,3,4,5,6,7,8,0},

pass[50][9],m,n;

/* 輸出路徑 */

void putpass()

{ int c,k;

for (c=0;c<=n;c++)

{ printf("%3d:",c);

for (k=0;k<9;k++)

printf("%3d",pass[c][k]);

printf(" ");

if (c%10==0)

{ printf("------------- "); getch(); }

}

}

/* 判斷矩陣a[3][3]是否可行,是否可以作為新路徑。 */

int moveok(int a[][3])

{ int i,j,k,c;

for (c=0;c<=n;c++)

{ for (k=0;k<9;k++)

{ i=k/3;j=k%3;

if (pass[c][k]!=a[i][j]) break;

}

if (k==9) break;

}

if (c>n) /* 可以插入新路徑 */

{ n++;

for (k=0;k<9;k++)

{ i=k/3; j=k%3;

pass[n][k]=a[i][j];

對于24個磁極的發(fā)電電動機(jī)，為滿足繞組完全對稱的條件，可選的支路數(shù)包括1、2、3、4、6、8、12、24，發(fā)電電動機(jī)額定功率為250 MW，額定電壓為15.75 kV，對應(yīng)不同支路數(shù)時的支路電流與槽電流見表1。

}

return 1;

}

else

return 0;

}

/* 判斷矩陣a[3][3]是否為目標(biāo)矩陣b[3][3]。 */

int moveover(int a[][3])

for (i=0;i<3;i++)

for (j=0;j<3;j++)

if (a[i][j]!=b[i][j])

return 0;

return 1;

}

/* 將矩陣s2[3][3]賦值到s1[3][3]。 */

void mcopy(int s1[][3],int s2[][3])

{ int i,j;

for (i=0;i<3;i++)

for (j=0;j<3;j++)

s1[i][j]=s2[i][j];

}

/* 判定空點(diǎn)(0點(diǎn))是否可以左移,若可以,則移動空點(diǎn)。*/

int moveleft(int s[][3],int i,int j)

{ int f,t[3][3];

mcopy(t,s);

t[i][j]=t[i][j-1];

t[i][j-1]=0;

f=moveok(t);

if (f)

mcopy(s,t);

return f;

}

/* 判定空點(diǎn)(0點(diǎn))是否可以上移,若可以,則移動空點(diǎn)。*/

int moveup(int s[][3],int i,int j)

{ int f,t[3][3];

mcopy(t,s);

t[i][j]=t[i-1][j];

t[i-1][j]=0;

f=moveok(t);

if (f)

mcopy(s,t);

return f;

}

/* 判定空點(diǎn)(0點(diǎn))是否可以下移,若可以,則移動空點(diǎn)。*/

int movedown(int s[][3],int i,int j)

{ int f,t[3][3];

mcopy(t,s);

t[i][j]=t[i+1][j];

t[i+1][j]=0;

f=moveok(t);

if (f)

mcopy(s,t);

return f;

}

/* 判定空點(diǎn)(0點(diǎn))是否可以右移,若可以,則移動空點(diǎn)。*/

int moveright(int s[][3],int i,int j)

{ int f,t[3][3];

mcopy(t,s);

t[i][j]=t[i][j+1];

t[i][j+1]=0;

f=moveok(t);

if (f)

mcopy(s,t);

return f;

}

/* 移動空點(diǎn)遞歸調(diào)用函數(shù) */

void move(int a[][3])

{ int i,j,p,pf,f1=0;

int x[3][3],y[3][3];

/* 備份a矩陣到x,y矩陣 */

mcopy(x,a);

mcopy(y,a);

/* 確定空點(diǎn)坐標(biāo) */

for(i=0;i<3;i++)

{ for (j=0;j<3;j++)

if (x[i][j]==0) {f1=1;break;}

if(f1) break;

}

/* 判斷移動矩陣x是否為目標(biāo)矩陣,若為目標(biāo)矩陣則輸出路徑,程序結(jié)束。*/

if (moveover(x))

{ putpass(); exit(0); }

if (moveok(x)==0 && n

{ /* 分別判斷x矩陣中空點(diǎn)是否可以向某一方向移動,若可以,則遞歸調(diào)用本函數(shù),

若不可以,需還原x矩陣,再向其他方向移動。*/

if (i!=0 && moveup(x,i,j))

{ move(x); mcopy(x,y);}

if (i!=2 && movedown(x,i,j))

{ move(x); mcopy(x,y);}

if (j!=0 && moveleft(x,i,j))

{ move(x); mcopy(x,y);}

if (j!=2 && moveright(x,i,j))

{ move(x); mcopy(x,y);}

}

n--; /* 移動次數(shù)減一 */

}

/* 主函數(shù)中a[3][3]矩陣為原始矩陣 */

main()

{ int i,j,k;

int a[3][3]={8,7,6,5,4,3,2,1,0};

n=0;

for (k=0;k<9;k++)

{ i=k/3; j=k%3;

pass[0][k]=a[i][j];

}

printf("enter m:");

scanf("%d",&m);

move(a);

getch();

}

3.3圖解答案

圖3　九宮八數(shù)問題的移動步驟

4結(jié)語

騎士游歷問題及韓信分油問題，編程方法與九宮八數(shù)問題相似，這里不再綜述。為了方便理解，以上程序采用了未經(jīng)任何優(yōu)化處理的深度優(yōu)先索搜法編程，實(shí)踐中可以采用各種優(yōu)化策略以優(yōu)化搜索過程。

參 考 文 獻(xiàn)

[1] 王樂芹,李月,徐炳偉.九宮方陣的數(shù)學(xué)解法[J].數(shù)學(xué)學(xué)習(xí)與研究,2015,13:86.

WANG Leqing, LI Yue, XIU Bingwei. Nine rectangle grid’s mathematical solution[J]. Mathematics Learning and Research,2015,13:86.

[2] 秦董洪,陳智勇.算法設(shè)計與分析課程教學(xué)研究[J].計算機(jī)教育,2013,11:98-101.

QIN Donghong, CHEN Zhiyong. Teaching research on algorithm design and analysis[J]. Computer Education,2013,11:98-101.

[3] 惠燕,潘煜.騎士游歷問題算法的研究[J].電子設(shè)計工程,2011,19(11):112-114.

HUI Yan, PAN Yu. Research on knight travel problem algorithm[J]. Electronic Design Engineering,2011,19(11):112-114.

[4] 葛文庚,藺莉.程序設(shè)計基礎(chǔ)課程教學(xué)模式研究與設(shè)計[J].電子設(shè)計工程,2012,20(4):44-46.

GE Wengeng, LIN Li. Research and design of the program design foundation course teaching[J]. Electronic Design Engineering,2012,20(4):44-46.

[5] 朱龍梅.淺論人工智能啟發(fā)式搜索策略的研究[J].電子設(shè)計工程,2013,21(16):61-64.

ZHU Longmei. Strategy research on artificial intelligence heuristic search[J]. Electronic Design Engineering,2013,21(16):61-64.

[6] 蔡志榮,宣華俊,應(yīng)吉平.基于趣味案例法程序設(shè)計教學(xué)的探討與實(shí)踐[J].信息與電腦(理論版),2010,5:220.

CAI Zhirong, XUAN Huajun, YING Jiping. Discussion and practice of programming design teaching based on the case of interest[J]. China Computer & Communication,2010,5:220.

[7] 石竑松,秦志光.對數(shù)空間可構(gòu)造的無向圖遍歷序列[J].計算機(jī)工程與應(yīng)用,2010,46(8):11-15.

SHI Hongsong, QIN Zhiguang. Log-space constructible traversal sequences for undirected graphs[J]. Computer Engineering and Applications,2010,46(8):11-15.

[8] 何苑,郝夢巖.搜索引擎優(yōu)化策略研究[J].計算機(jī)與數(shù)字工程,2009,37(7):60-63.

HE Yuan, HAO Mengyan. A Survey on the Strategy of Search Engine Optimization[J]. Computer & Digital Engineering,2009,37(7):60-63.

[9] 裴芳敏,億珍珍,趙克.啟發(fā)式搜索在數(shù)學(xué)智能解題系統(tǒng)中的應(yīng)用研究[J].計算機(jī)技術(shù)與發(fā)展,2010,20(7):5-8.

PEI Fangmin, YI Zhenzhen, ZHAO Ke. Application and Research of a Heuristic Search in Intelligent Mathematics Problem Solving System[J]. Computer Technology and Development,2010,20(7):5-8.

[10] 楊慶.提高程序設(shè)計基礎(chǔ)課程的趣味性[J].浙江萬里學(xué)院學(xué)報,2007,20(5):152-154.

YANG Qing. Improving the Interests of Basic Programming Courses[J]. Journal of Zhejiang Wanli University,2007,20(5):152-154.

[11] 徐曉林,陸虹.混合教學(xué)模式在“程序設(shè)計基礎(chǔ)”中的實(shí)踐[J].計算機(jī)教育,2007,10:25-27.

XU Xiaolin, LU Hong. The Exploration and Practice of Blending teaching Model on the Course of Program Design Basis[J]. Computer Education,2007,10:25-27.

Examples for Interesting Programming on Intelligence Simulation

MA XuWANG Dayong

(Computer Center, Liaoning University, Shenyang110036)

AbstractWith the modularity and componentization of computer software, more and more computer users are no longer pay attention to traditional programming. Knight travelling, Eight-number and nine-rectangle-grid, and HanXin allocates oil, the intelligence simulation programs of the three interesting deep-searching programs are listed, a complete C language program about Eight-number and nine-rectangle-grid problem is given, this type is explaned briefly, it hopes to inspire more students interested in programming.

Key Wordsknight travelling, eight-number and nine-rectangle-grid, HanXin allocates oil, deep-searching, intelligence simulation

* 收稿日期:2015年11月12日,修回日期:2015年12月12日

作者簡介:馬旭,男,碩士,高級實(shí)驗(yàn)師,研究方向:程序設(shè)計教學(xué),圖像處理。

中圖分類號TP311.11

DOI:10.3969/j.issn.1672-9722.2016.05.045