五子棋程序設(shè)計(jì)說(shuō)明書及五子連珠問(wèn)題模型研究

中北大學(xué)程序設(shè)計(jì)課程設(shè)計(jì)說(shuō)明書學(xué)生姓名：學(xué)號(hào)：10051041學(xué)院：信息與通信工程學(xué)院專業(yè)：光電信息工程題目：五子棋指導(dǎo)教師：職稱:2012年01月06日(紀(jì)念我已經(jīng)逝去的大學(xué)生活)院：信息與通信工程學(xué)院專業(yè)：光電信息工程學(xué)生姓名：學(xué)號(hào)：10051041課程設(shè)計(jì)題目：五子棋起迄日期：2011年12月24日～2012年1月6日課程設(shè)計(jì)地點(diǎn)：111420指導(dǎo)教師：系主任：下達(dá)任務(wù)書日期:2011年12月25日課程設(shè)計(jì)任務(wù)書1．設(shè)計(jì)目的：1熟悉C語(yǔ)言程序設(shè)計(jì)的原理與方法；2掌握C語(yǔ)言開(kāi)發(fā)環(huán)境下程序的具體設(shè)計(jì)；3掌握利用C語(yǔ)言分析解決具體問(wèn)題。2．設(shè)計(jì)內(nèi)容和要求：設(shè)計(jì)內(nèi)容：用C語(yǔ)言設(shè)計(jì)一個(gè)五子棋游戲程序，允許游戲者自由選擇棋子顏色，實(shí)現(xiàn)人人對(duì)戰(zhàn)和人機(jī)對(duì)戰(zhàn)，利用時(shí)間函數(shù)設(shè)置實(shí)現(xiàn)落子倒計(jì)時(shí)功能程序應(yīng)該具有以下基本功能：1．顯示歡迎界面。2．玩家棋子可選，棋盤范圍足夠。3．落子時(shí)間倒計(jì)時(shí)。設(shè)計(jì)要求：1．不同的功能使用不同的函數(shù)實(shí)現(xiàn)（模塊化），對(duì)每個(gè)函數(shù)的功能和調(diào)用接口要注釋清楚。對(duì)程序其它部分也進(jìn)行必要的注釋。3．對(duì)系統(tǒng)進(jìn)行功能模塊分析、畫出總流程圖和各模塊流程圖。4．用戶界面要求使用方便、簡(jiǎn)潔明了、美觀大方、格式統(tǒng)一。5．所有程序需在Win-Tc或MicrosoftVisualC++6.0環(huán)境調(diào)試通過(guò)。3．設(shè)計(jì)工作任務(wù)及工作量的要求〔包括課程設(shè)計(jì)計(jì)算說(shuō)明書(論文)、圖紙、實(shí)物樣品等〕：課程設(shè)計(jì)說(shuō)明書一份；電子文檔（說(shuō)明書、設(shè)計(jì)程序）一份課程設(shè)計(jì)任務(wù)書4．主要參考文獻(xiàn)：譚浩強(qiáng)《c程序設(shè)計(jì)》北京大學(xué)出版社5．設(shè)計(jì)成果形式及要求：課程說(shuō)明書打印，并裝訂；必要的程序流程圖和程序附錄。6．工作計(jì)劃及進(jìn)度：2011年12月24日～2011年12月26日下達(dá)設(shè)計(jì)任務(wù)書，學(xué)生熟悉設(shè)計(jì)內(nèi)容；2011年12月27日～2011年12月29日查閱參考資料，確定基本設(shè)計(jì)方案；2011年12月29日～2012年01月04日C語(yǔ)言進(jìn)行程序設(shè)計(jì)；2012年01月05日～2012年01月06日完成設(shè)計(jì)報(bào)告；2012年01月06日答辯；系主任審查意見(jiàn)：簽字：年月日目錄1、課程設(shè)計(jì)的背景及意義……………062、設(shè)計(jì)的基本原理………063、設(shè)計(jì)的基本過(guò)程………084、設(shè)計(jì)的結(jié)果……………105、總結(jié)和結(jié)論…………….11設(shè)計(jì)背景及意義我們的五子棋程序是在VisualC++6.0環(huán)境下運(yùn)行的。\o"查看圖片"VisualC++6.0MicrosoftVisualC++（簡(jiǎn)稱VisualC++、MSVC、VC++或VC）微軟公司的C++開(kāi)發(fā)工具，具有集成開(kāi)發(fā)環(huán)境，可提供編輯C語(yǔ)言，C++以及C++/CLI等編程語(yǔ)言。VC++整合了便利的除錯(cuò)工具，特別是整合了微軟視窗程式設(shè)計(jì)（WindowsAPI）、三維動(dòng)畫DirectXAPI，Microsoft.NET框架。目前最新的版本是MicrosoftVisualC++2010。VisualC++6.0集成了MFC6.0，于1998發(fā)行。發(fā)行至今一直被廣泛地用于大大小小的項(xiàng)目開(kāi)發(fā)。五子棋是一種兩人對(duì)弈的純策略型棋類游戲，是起源于中國(guó)古代的傳統(tǒng)黑白棋種之一。我們通過(guò)對(duì)《C語(yǔ)言》以及對(duì)《大學(xué)計(jì)算機(jī)基礎(chǔ)》的初步學(xué)習(xí)后，本學(xué)期末進(jìn)行了課程程序設(shè)計(jì)，設(shè)計(jì)課題為“五子棋”。我們小組由6人組成，通過(guò)分工與合作并在趙老師的耐心指導(dǎo)下共同完成了此程序設(shè)計(jì)。2.設(shè)計(jì)的基本原理2.1問(wèn)題描述連珠(五子棋)是有兩個(gè)人在一盤棋上進(jìn)行對(duì)抗的競(jìng)技運(yùn)動(dòng)。在對(duì)局開(kāi)始時(shí)，先由用戶選擇哪方先開(kāi)局，先開(kāi)局一方將一枚棋子落在一點(diǎn)上，然后由另一方在對(duì)方棋周圍的交叉點(diǎn)上落子，如此輪流落子，直到某一方首先在棋盤的直線、橫線或斜線上形成連續(xù)的五子則該方就算獲勝。此時(shí)，算法結(jié)束。

2.2需求分析（1）輸出棋盤界面（2）要求玩家選擇棋子（3）玩家輪流下棋（4）判斷鍵盤輸入哪個(gè)鍵按規(guī)則執(zhí)行操作（5）判斷誰(shuí)先落棋（6）判斷贏家（7）輸出結(jié)果界面2.3流程圖開(kāi)始玩家選擇棋子玩家移動(dòng)棋子輸出棋盤界面O方先輸入棋子坐標(biāo)刷新棋盤界面轉(zhuǎn)換玩家判斷棋子是否出界判斷是否重子輸出勝利界面刷新棋盤界面結(jié)束判斷是否贏棋NNNYYY開(kāi)始玩家選擇棋子玩家移動(dòng)棋子輸出棋盤界面O方先輸入棋子坐標(biāo)刷新棋盤界面轉(zhuǎn)換玩家判斷棋子是否出界判斷是否重子輸出勝利界面刷新棋盤界面結(jié)束判斷是否贏棋NNNYYY3設(shè)計(jì)的基本過(guò)程charb[40][40];voidshow()//輸出獲勝圖像//{inti=0,j=0;//i為橫坐標(biāo)變量，j為縱坐標(biāo)變量// for(i=0;i<40;i++)//對(duì)圖像數(shù)組賦初值// for(j=0;j<40;j++) {b[i][j]=46;} for(i=0;i<40;i++)//對(duì)圖像數(shù)組特定點(diǎn)賦值// for(j=0;j<40;j++) { if(i>10&&i<16) {if(j>10&&j<16||j>25&&j<31) b[i][j]='O';} else { if(i==21) {if(j>=6&&j<=35) b[i][j]='O';} else { if(i==22) {if(j>=7&&j<=34) b[i][j]='O';} else { if(i==23) {if(j>=8&&j<=33) b[i][j]='O';} else { if(i==24) {if(j>=9&&j<=31) b[i][j]='O';} else { if(i==25) {if(j>=10&&j<=30) b[i][j]='O';} else { if(i==26) {if(j>=12&&j<=28) b[i][j]='O';} else { if(i==27) {if(j>=14&&j<=26) b[i][j]='O';} else { if(i==28) {if(j>=17&&j<=23) b[i][j]='O';} } } } } } } } } } for(i=0;i<40;i++)//輸出圖像數(shù)組// { for(j=0;j<40;j++) printf("%c",b[i][j]); printf("\n"); } }詳細(xì)說(shuō)明：Show函數(shù)的目的是輸出獲勝界面，調(diào)用全局變量b[][]（目的是為圖像分配存儲(chǔ)空間）,i為橫坐標(biāo)變量，j為縱坐標(biāo)變量，接下來(lái)的兩個(gè)for是把b[][]初始化為“.”,再接下來(lái)的雙for是為塑形:限定行間距為10<i<16，再限定列間距為10<j<16或25<j<31，用判斷語(yǔ)句來(lái)塑造圖形“雙眼”；當(dāng)i=21時(shí)，限定6<=j<=25，當(dāng)i=22,23,24,25,26,27時(shí)同理，用判斷語(yǔ)句來(lái)塑造“嘴”，最后用雙for語(yǔ)句來(lái)輸出圖形。4設(shè)計(jì)結(jié)果玩家獲勝顯示界面截圖5總結(jié)與結(jié)論課程設(shè)計(jì)是培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識(shí),發(fā)現(xiàn),提出,分析和解決實(shí)際問(wèn)題,鍛煉實(shí)踐能力的重要環(huán)節(jié),是對(duì)學(xué)生實(shí)際工作能力的具體訓(xùn)練和考察過(guò)程.回顧起此次課程程序設(shè)計(jì)，至今我仍感慨頗多，從選題到定稿，從理論到實(shí)踐，在整整兩星期的日子里，學(xué)到很多很多的的東西，不僅鞏固了以前所學(xué)過(guò)的知識(shí)，而且學(xué)到了很多在書本上所沒(méi)有學(xué)到過(guò)的知識(shí)。通過(guò)這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái)，才能真正提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。在設(shè)計(jì)的過(guò)程中難免會(huì)遇到過(guò)各種各樣的問(wèn)題，同時(shí)在設(shè)計(jì)的過(guò)程中也發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過(guò)的知識(shí)理解得不夠深刻，掌握得不夠牢固，通過(guò)這次課程設(shè)計(jì)之后，把以前所學(xué)過(guò)的知識(shí)重新溫故。

這次課程設(shè)計(jì)順利完成了，在設(shè)計(jì)中遇到了很多編程問(wèn)題，最后在趙宇老師的辛勤指導(dǎo)下，終于游逆而解。同時(shí)，在趙宇老師的身上我學(xué)得到很多實(shí)用的知識(shí)，我表示感謝！同時(shí)，對(duì)給過(guò)我?guī)椭乃型瑢W(xué)和各位指導(dǎo)老師再次表示忠心的感謝！附錄負(fù)責(zé)人設(shè)計(jì)內(nèi)容Viodjudge（）函數(shù)的設(shè)計(jì)及程序的調(diào)試Viodjudge（）函數(shù)的設(shè)計(jì)及程序的調(diào)試Voidmove（）函數(shù)的設(shè)計(jì)及課程設(shè)計(jì)說(shuō)明書的排版制作Intplaying（）函數(shù)的設(shè)計(jì)及程序的調(diào)試Voidshowcheckerboard（）函數(shù)設(shè)計(jì)及相關(guān)操作Voidshow（）函數(shù)的設(shè)計(jì)及程序的調(diào)試程序源代碼：#include<stdio.h>#include<string.h>chara[65][65];charb[40][40];voidshow()//輸出獲勝圖像//{inti=0,j=0;//i為橫坐標(biāo)變量，j為縱坐標(biāo)變量// for(i=0;i<40;i++)//對(duì)圖像數(shù)組賦初值// for(j=0;j<40;j++) {b[i][j]=46;} for(i=0;i<40;i++)//對(duì)圖像數(shù)組特定點(diǎn)賦值// for(j=0;j<40;j++) { if(i>10&&i<16) {if(j>10&&j<16||j>25&&j<31) b[i][j]='O';} else { if(i==21) {if(j>=6&&j<=35) b[i][j]='O';} else { if(i==22) {if(j>=7&&j<=34) b[i][j]='O';} else { if(i==23) {if(j>=8&&j<=33) b[i][j]='O';} else { if(i==24) {if(j>=9&&j<=31) b[i][j]='O';} else { if(i==25) {if(j>=10&&j<=30) b[i][j]='O';} else { if(i==26) {if(j>=12&&j<=28) b[i][j]='O';} else { if(i==27) {if(j>=14&&j<=26) b[i][j]='O';} else { if(i==28) {if(j>=17&&j<=23) b[i][j]='O';} } } } } } } } } } for(i=0;i<40;i++)//輸出圖像數(shù)組// { for(j=0;j<40;j++) printf("%c",b[i][j]); printf("\n"); } }voidmove(int*x,int*y)/*移動(dòng)棋子的方向*///x為上一步棋子橫坐標(biāo)，y為上一步棋子縱坐標(biāo)//{ charb[40];//為記錄棋子將要移動(dòng)的步伐// inti,z,flag=1;//z為某一步的中間變量，flag為標(biāo)志變量// gets(b);//輸入要移動(dòng)的步伐// for(i=0;i<40;i++) { z=b[i];//把b【】的某一步傳遞給z// switch(z)//判斷移動(dòng)棋子方向// { case119:*x=*x-1;break;//w鍵控制棋子上移// case97:*y=*y-1;break;//a鍵控制棋子左移// case115:*x=*x+1;break;//s鍵控制棋子下移// case100:*y=*y+1;break;//d鍵控制棋子右移// case111:flag=0;break;//o鍵確定落子// } if(flag==0)break;//判斷某步是否移動(dòng)完成// }}intplaying()/*開(kāi)始下棋*/{intflag=1,i=0,x=0,y=0,k,l,n=0,m=1;//flag為記錄哪方下棋的標(biāo)志變量，x，y為a[][]的橫縱坐標(biāo)，m，n分別記錄o方，@方的積累步數(shù)// int*p1=&x,*p2=&y; intjudge(intx,inty);//本函數(shù)所用子函數(shù)的聲明// voidmove(int*p1,int*p2); voidshowcheckerboard(intx,inty); printf("O方先輸入首子坐標(biāo)："); scanf("%d%d",&x,&y);//輸入首坐標(biāo)// a[x][y]='O';//首坐標(biāo)的棋盤位置畫棋子// showcheckerboard(m,n);//輸出更新后的棋盤// for(i=0;i<2000;i++)//改變玩家// { if(flag==1) flag=0; else flag=1; for(k=0;k<2000;k++)//玩家落子并判斷下的棋子是否過(guò)界或此處是否有子// { if(flag==1) { printf("O方下棋\n");m++;} else { printf("@方下棋\n");n++;}move(p1,p2); if(x>=1&&x<=64&&y>=1&&y<=64) { if(a[x][y]==46)break; else {if(flag==1)m--;elsen--; printf("此處有子，請(qǐng)繼續(xù)移子"); continue; } } else{if(flag==1)m--;elsen--;printf("此處過(guò)界，請(qǐng)繼續(xù)移子");} } if(flag==1)//在a[][]的特定位置更新字符// a[x][y]='O'; else a[x][y]='@'; showcheckerboard(m,n);//更新棋盤// l=judge(x,y);//記錄誰(shuí)贏變量// if(l==1)returnflag; }}voidshowcheckerboard(intx,inty)/*畫出棋盤*///x,y分別為o方下棋步數(shù)，@方下棋步數(shù)//{ inti,j,w=0;//i,j為橫縱坐標(biāo)變量//printf("================================================================================================================\n");printf("0方累計(jì)下棋步數(shù)：%d@方累計(jì)下棋步數(shù)：%d\n",x,y);printf("================================================================================================================\n"); for(i=0;i<65;i++)//輸出橫縱坐標(biāo)// printf("%2d",i); printf("\n"); for(i=1;i<65;i++) { for(j=0;j<65;j++) { if(j==0) { w+=1; printf("%2d",w); } else { printf("%2c",a[i][j]); } } printf("\n"); } }intjudge(intx,inty)/*判斷各方向五子是否連成一線*///x,y分別為橫縱坐標(biāo)//{ inti,b,c,d,e,z=1;//z為標(biāo)志變量，記錄每個(gè)方向連棋個(gè)數(shù)// for(i=1;i<5;i++)//垂直向下數(shù)// { if(a[x][y+i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak; } for(i=1;i<5;i++)//垂直向上數(shù)// { if(a[x][y-i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak; } e=z;z=1;for(i=1;i<5;i++)//水平向右數(shù)// { if(a[x+i][y]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak; }for(i=1;i<5;i++)//水平向左數(shù)// { if(a[x-i][y]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak;}b=z;z=1;for(i=1;i<5;i++)//向左下方數(shù)// { if(a[x-i][y+i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak;}for(i=1;i<5;i++)//向右上方數(shù)// { if(a[x+i][y-i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak;}c=z;z=1;for(i=1;i<5;i++)//向左上方數(shù)// { if(a[x-i][y-i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak;}for(i=1;i<5;i++)//向右下方數(shù)// { if(a[x+i][y+i]==a[x][y]) { z+=1; if(z==5) {return(1);break;} } elsebreak;}d=z;if(e!=5&&b!=5&&c!=5&&d!=5)//判斷某個(gè)方向五子連棋//{ return(0);}}voidmain(){intx,y,flag,m=0,n=0,p=0;//flag為哪方下棋的判斷變量，m，n為分別記錄雙方的步數(shù)//printf("================================================================================================================\n");printf("w為上移動(dòng)，a為左移動(dòng)，s為下移動(dòng)，d為右移動(dòng),o確定落棋子\n");printf("=================================================================================================================\n");printf("玩家1選擇棋子：選0方輸入1，選@方輸入2\n");scanf("%d",&p);for(x=1;x<65;x++)//棋盤數(shù)組初始化//for(y=1;y<65;y++)a[x][y]=46;showcheckerboard(m,n);//輸出棋盤//flag=playing();//下棋//show();//輸出獲勝圖形//if(flag==1)//判斷哪方獲勝//printf("O方獲勝");elseprintf("@方獲勝");}參賽隊(duì)號(hào)：16018選題題號(hào)：A五子連珠問(wèn)題模型研究摘要本文針對(duì)“五子連珠”問(wèn)題在二維網(wǎng)格和三維網(wǎng)格的最優(yōu)方案進(jìn)行建模與求解。對(duì)于六行七列網(wǎng)格的情況進(jìn)行分析，先考慮一維情況下的模型，并將一維情況下模型的周期性性質(zhì)推廣至二維，據(jù)此建立0-1規(guī)劃模型，進(jìn)行求解得最優(yōu)方案為最少取出8個(gè)棋子。并對(duì)結(jié)果的準(zhǔn)確性進(jìn)行理論證明，對(duì)此給出兩種證明方法。第一中可以通過(guò)軟件求解過(guò)程中的輸出信息來(lái)給與證明，第二種通過(guò)反證法進(jìn)行理論證明。對(duì)上述結(jié)果對(duì)應(yīng)的方案進(jìn)行研究，得到二維網(wǎng)格中最優(yōu)方案的變化存在一定的周期性，據(jù)此周期性建立遞推模型，并得到實(shí)用于一般二維網(wǎng)格中最優(yōu)方案的數(shù)學(xué)模型，對(duì)13行17列的網(wǎng)格進(jìn)行求解，的到最少取出44個(gè)棋子。對(duì)此二維網(wǎng)格最優(yōu)方案的周期性進(jìn)一步研究并推廣到三維網(wǎng)格中，通過(guò)二維網(wǎng)格疊加形成三維網(wǎng)格的方式，從而建立了三維網(wǎng)格中的最優(yōu)方案的數(shù)學(xué)模型，并對(duì)6*7*6的網(wǎng)格進(jìn)行求解的到少取出50個(gè)棋子。關(guān)鍵字：0-1規(guī)劃，遞推模型，網(wǎng)格疊加

1問(wèn)題重述問(wèn)題1：在6×7的長(zhǎng)方形棋盤放滿棋子。從這42個(gè)棋子中取出一些棋子，使得棋盤上剩下的棋子，沒(méi)有五個(gè)在一條直線（橫、豎、斜方向）上依次相連，最少取出多少個(gè)棋子才能滿足要求？同時(shí)給出一種去掉棋子的方式。問(wèn)題2：?jiǎn)栴}1中使用數(shù)學(xué)證明的方法，只能解決規(guī)模很小的問(wèn)題?，F(xiàn)在從一般性的問(wèn)題考慮，一利用數(shù)學(xué)建模的方法建立一般模型，然后設(shè)計(jì)算或利用軟件求解。基于此，請(qǐng)針對(duì)任意規(guī)模的棋盤，滿足的條件與問(wèn)題1相同。問(wèn)至少去掉多少個(gè)棋子。問(wèn)題3：三維問(wèn)題將該二維平面網(wǎng)格擴(kuò)展到三維空間，得到一個(gè)的空間長(zhǎng)方體網(wǎng)格。在這些格子中同樣都填滿了棋子，現(xiàn)要從中抽取一部分，使得每種平面，包括橫向所截的m個(gè)平面，縱向所截的n個(gè)平面，豎直方向所截的p個(gè)平面，在每個(gè)平面上在橫向、縱向、斜方向上都不出現(xiàn)5子連珠。并且要求在空間斜線上也不出現(xiàn)5子連珠。問(wèn)最少去掉多少個(gè)棋子可以滿足要求。請(qǐng)建立一般問(wèn)題的數(shù)學(xué)模型。并給出具體的解結(jié)果。

2問(wèn)題分析2.1問(wèn)題（1）分析由題意可知，要求解一個(gè)取出的數(shù)量最少的取棋子方案。此問(wèn)題中可以通過(guò)0-1變量來(lái)表示每個(gè)位置上的棋子是否被取出，若取出，則用1表示，否則用0表示。那么就可以用一個(gè)0-1矩陣來(lái)表示方案，則含有1的個(gè)數(shù)最少，且滿足題目中三個(gè)條件的矩陣就表示的是最優(yōu)方案。因此可以建立0-1規(guī)劃模型，對(duì)問(wèn)題進(jìn)行求解。模型的目標(biāo)函數(shù)即為矩陣的行列變量總和。模型的約束條件可以通過(guò)題目中的三個(gè)條件來(lái)給定。而對(duì)于這三個(gè)條件，先考慮一維情況下的模型，并將一維情況下的模型的性質(zhì)推廣至二維，并由此性質(zhì)來(lái)建立對(duì)應(yīng)的約束條件。對(duì)于結(jié)果準(zhǔn)確性，可以通過(guò)軟件求解過(guò)程中的輸出信息來(lái)給與證明，也可以通過(guò)反證法來(lái)進(jìn)行理論證明。2.2問(wèn)題（2）分析本題目要求將問(wèn)題一的模型推廣至一般情況。先對(duì)問(wèn)題（1）的結(jié)論進(jìn)行分析，得出結(jié)論所具有的性質(zhì)，并加以理論證明，然后將其性質(zhì)推廣至一般情況。先將問(wèn)題一中的模型的行數(shù)推廣至一般情況，并在此基礎(chǔ)上，將列數(shù)也推廣至一般情況，從而建立一般情況下的模型。的模型還需要考慮特殊情況：行數(shù)小于5或者列數(shù)小于5。對(duì)此，很容易能得到在行數(shù)和列數(shù)都小于5的情況下，不需要取出任何點(diǎn)，即結(jié)果為零；對(duì)于只有列數(shù)小于5或者行數(shù)小于5的情況，規(guī)定每行或者每列的最優(yōu)結(jié)果的累加，即是最終結(jié)果。而對(duì)于每行或者每列的最優(yōu)結(jié)果，可以通過(guò)一般一維模型下的最優(yōu)結(jié)果的算法給出。2.3問(wèn)題（3）分析本題目要求將平面網(wǎng)格推廣至三維空間，建立一般模型，并計(jì)算6x6x7情況下的最優(yōu)結(jié)果。在問(wèn)題二模型的基礎(chǔ)上將結(jié)果的性質(zhì)經(jīng)一部推廣至三維網(wǎng)格，這樣，就可以直接應(yīng)用結(jié)果的性質(zhì)，通過(guò)二維到三維網(wǎng)格的二維網(wǎng)格擴(kuò)充的方式對(duì)三維模型進(jìn)行建立。3模型假設(shè)假設(shè)二維網(wǎng)格中的每個(gè)格子都是1x1的小正方形，在三維網(wǎng)格中，每個(gè)格子是1x1x1的小正方體。假設(shè)格子之間共頂點(diǎn)或者共邊時(shí)，兩個(gè)字相連。假設(shè)在相連的格子中的棋子的距離是1。假設(shè)每個(gè)小方格或者小正方體中只能放一個(gè)棋子。4符號(hào)說(shuō)明 表示0-1變量 表示方案矩陣的列向量 表示方案矩陣的行向量 表示n對(duì)m向上取整 表示n對(duì)m向下取整 表示二維網(wǎng)格最少可取棋子的數(shù)量 表示三維網(wǎng)格最少可取棋子的數(shù)量 表示n對(duì)m取余數(shù)5模型建立和求解5.1問(wèn)題1的模型建立與求解5.1.1模型建立前提理論為了在二維片面上建立模型，先來(lái)研究模型在一維情況下的性質(zhì)，要在n個(gè)方格中取棋子，則可以用一個(gè)n元素只有0和1的n維向量a來(lái)表示最取棋子方案。則為了使得取棋子總數(shù)最少，及方案最優(yōu)，就有結(jié)論：表示a向量的第i個(gè)分量） (1)其中，表示向下取整,表示向上取整。將此性質(zhì)推廣至二維網(wǎng)格，則對(duì)于二維網(wǎng)格的取棋子方案矩陣 (2)其中為矩陣W的列向量，為W的行向量則有如下結(jié)論： (3) (4)且在各行各列性質(zhì)在W各行，各列以及各對(duì)角線上仍然成立。這個(gè)結(jié)論很容易便可從一維的情況得到，只要證明ri和ci中的每個(gè)分量都和及的對(duì)應(yīng)分量相等即可，這從一維的情況中很容易就能得到。5.1.2模型建立對(duì)于6×7網(wǎng)格的問(wèn)題，先設(shè)取棋子方案矩陣位： (5)根據(jù)上述性質(zhì)式(3)、(4)可得： 將其帶入取棋子方案矩陣，并對(duì)位置變量進(jìn)行重新編號(hào)，則可對(duì)取棋子方案矩陣進(jìn)行簡(jiǎn)化，且簡(jiǎn)化后取棋子方案矩陣為： (6)為使方案各行滿足條件，可對(duì)此矩陣各行使用性質(zhì)式(2)，則可得式(7)所示約束條件；為使方案各列滿足條件，可對(duì)此矩陣各列使用性質(zhì)式(2)，可得式(8)所示約束條件；為使方案的各條對(duì)角線滿足條件，我們僅對(duì)長(zhǎng)度大于4的對(duì)角線使用式(2)，可得式(9)、(10)所示8條約束條件。 (7) (8) (9) (10)聯(lián)立以上各約束條件，并通過(guò)W矩陣建立模型如下： (11)求解模型，則可得最少的取棋子個(gè)數(shù)及最優(yōu)方案矩陣，其中Z的值就是最少可取走的棋子的數(shù)量。將，，帶入W則可得到最優(yōu)方案矩陣。5.1.3模型求解對(duì)于上述0-1規(guī)劃模型，我們可直接通過(guò)MATLAB軟件求解。我們得到的所有解如下:圖SEQ圖\*ARABIC1最優(yōu)方案示意圖通過(guò)求解模型得到最少取棋子數(shù)量為8個(gè)，一方面，通過(guò)軟件求解過(guò)程當(dāng)中的輸出的最優(yōu)解得類型來(lái)判定此結(jié)果就是最少的取棋子個(gè)數(shù)；另一方面，可通過(guò)反證法來(lái)證明8就是最少取棋子個(gè)數(shù)。反證法證明：假設(shè)七個(gè)棋子可以滿足條件，則有W矩陣的7個(gè)列向量中都只能有一個(gè)非零的分量，且有，不妨設(shè)，，，，則此時(shí)，W矩陣的最后一行全為零，此取棋子方案表示在6x7網(wǎng)格的第6行中不取走任何棋子，顯然，在第6行中出現(xiàn)7個(gè)棋子連續(xù)的情況。由此我們可以知道取走7個(gè)棋子是無(wú)法。即8個(gè)棋子為最少的取棋子數(shù)量。5.2問(wèn)題（2）的模型建立和求解5.2.1模型建立理論準(zhǔn)備根據(jù)問(wèn)題一中一維模型最優(yōu)方案的性質(zhì)到二維網(wǎng)格中最優(yōu)性質(zhì)的推廣結(jié)論式(3)、(4)，將其作適當(dāng)推廣可得如下(12)、(13)兩條性質(zhì)：對(duì)于m行n列的網(wǎng)格，其最優(yōu)方案矩陣W的行向量ri=和列向量cj (12)其中，； (13)其中，。此性質(zhì)說(shuō)明的是：在二維網(wǎng)格中，隨著行和列的擴(kuò)充，最優(yōu)方案和最優(yōu)取棋子矩陣的變化具有一定的周期性，且周期為5，即行數(shù)每增加5，或者列數(shù)每增加5，最優(yōu)方案矩陣將在矩陣的后邊拼接一個(gè)特定的矩陣。最優(yōu)方案對(duì)應(yīng)的取棋子個(gè)數(shù)也將以特定的值增加。據(jù)此，便可將二維網(wǎng)格中最優(yōu)方案的模型推廣至一般情況。5.2.2模型建立在以上理論基礎(chǔ)上，通過(guò)最優(yōu)方案的行周期性，可將二維網(wǎng)格的行數(shù)推廣到一般情況。以5×5網(wǎng)格為初始的網(wǎng)格狀態(tài)，可建立網(wǎng)格擴(kuò)充5×n時(shí)的最少取棋子個(gè)數(shù)模型如下：其中，表示在網(wǎng)格中最優(yōu)方案所對(duì)應(yīng)的取棋子個(gè)數(shù)，n%5表示n和5的求余數(shù)運(yùn)算。在此基礎(chǔ)上，建立將網(wǎng)格擴(kuò)充成為時(shí)，最優(yōu)取棋子個(gè)數(shù)的模型： 以上模型都是建立在m，n大于5的情況下，為保證模型的一般性，還需考慮m，n小于5的情況，當(dāng)m，n都小于5時(shí)，顯然有最優(yōu)方案為不去出任何棋子，即最優(yōu)取棋個(gè)數(shù)為0，最優(yōu)取棋矩陣為全零矩陣。而對(duì)于m，n中僅有一個(gè)小于5的情況，由式(2)可知為使達(dá)到最優(yōu)，故規(guī)定： 帶入上述，模型，則可得到完整的一般情況下的模型為：5.2.3模型求解對(duì)上述模型的求解，通過(guò)MATLAB軟件編寫函數(shù)fhanshu（m，n）來(lái)實(shí)現(xiàn)（函數(shù)具體代碼在附件二中），其返回值為最少的可取出的棋子數(shù)量，并且會(huì)根據(jù)結(jié)果的數(shù)量進(jìn)行二維示意圖繪制，如果返回值為零則不進(jìn)行繪圖且輸出不用取出任何棋子的說(shuō)明，否則，則繪制相應(yīng)的最優(yōu)取棋子方案示意圖。將m=13，n=17，帶入函數(shù)可得最少可取棋子數(shù)量為：44，其繪制出的最優(yōu)方案示意圖有多個(gè)，其中一個(gè)示意圖如圖所示，圖SEQ圖\*ARABIC213x17最優(yōu)方案示意圖5.3問(wèn)題（3）模型建立和求解5.3.1模型建立前的理論準(zhǔn)備1）對(duì)問(wèn)題二中，二維網(wǎng)格最優(yōu)解的周期性性質(zhì)可推廣至三維情況，即在三維網(wǎng)格中，隨著層數(shù)的擴(kuò)充，最優(yōu)方案和最優(yōu)取棋子矩陣的變化具有一定的周期性，且周期為5。此性質(zhì)在三維情況下可以通過(guò)面周期性加以證明。2）分析問(wèn)題二的結(jié)果，可得到如下結(jié)論，其中，‘+’為0-1向量的加法運(yùn)算，可參看符號(hào)說(shuō)明。將此性質(zhì)推廣至三維，即其中某一三維網(wǎng)格最優(yōu)方案的連續(xù)疊加在一起的五個(gè)二維網(wǎng)格的取棋子方案，則可保證空間斜線上不出現(xiàn)五顆棋子連續(xù)的情況。對(duì)此性質(zhì)，可考慮可通過(guò)反證法進(jìn)行證明。假設(shè)對(duì)于某三維網(wǎng)格最優(yōu)方案上述性質(zhì)不滿足，即在此最優(yōu)方案中有則不妨設(shè)則可由0-1變量‘+’運(yùn)算方法知：；由此可知此方案中有五個(gè)連續(xù)的棋子，那么這種方案就不是最優(yōu)解。由此，也就的到上述性質(zhì)在三維網(wǎng)格中成立。5.3.2模型建立對(duì)三維情況下模型的建立，只需要將問(wèn)題二中的模型在層數(shù)上進(jìn)行擴(kuò)充。以維初始網(wǎng)格狀態(tài)對(duì)網(wǎng)格進(jìn)行擴(kuò)充，并記此5x5x5網(wǎng)格的最少可取t個(gè)棋子，則可建立網(wǎng)格擴(kuò)充為時(shí)最少取棋子個(gè)數(shù)的模型：其中表示在空間網(wǎng)格中最少可取的棋子數(shù)量。同樣的我們規(guī)定：則可得到在三維空間網(wǎng)格中最少可取棋子個(gè)數(shù)的模型為：5.3.3模型求解對(duì)上述模型的求解，通過(guò)MATLAB軟件編寫函數(shù)3dimension（m，n，p）來(lái)實(shí)現(xiàn)（函數(shù)具體代碼在附件三中），其返回值為最少的可取出的棋子數(shù)量，并且會(huì)根據(jù)結(jié)果的數(shù)量進(jìn)行二維示意圖繪制，如果返回值為零則不進(jìn)行繪圖且輸出不用取出任何棋子的說(shuō)明，否則，則繪制相應(yīng)的最優(yōu)取棋子方案示意圖。將m=6，n=7，p=6，帶入函數(shù)可得最少可取棋子數(shù)量為：50。得到最優(yōu)方案對(duì)應(yīng)，x,y,z坐標(biāo)在附加的程序3；6模型的評(píng)價(jià)及改進(jìn)6.1問(wèn)題一的模型評(píng)價(jià)及改進(jìn)問(wèn)題一建立的模型是0-1規(guī)劃模型，通過(guò)了簡(jiǎn)單的方法去解決復(fù)雜的問(wèn)題，簡(jiǎn)單明了，容易理解。模型的建立在一維模型的基礎(chǔ)上，十分有利于模型向更高維數(shù)的推廣。解決了6x7二維網(wǎng)格的最少取旗子數(shù)量問(wèn)題。但是由于只能解決具體的問(wèn)題，模型不具有一般性，網(wǎng)格行列數(shù)不同的問(wèn)題不能進(jìn)行求解。問(wèn)題二中針對(duì)這一缺點(diǎn)給出了解決一般問(wèn)題的模型。6.2問(wèn)題二的模型評(píng)價(jià)及改進(jìn)問(wèn)題二模型是基于問(wèn)題一以及一維情況下的模型性質(zhì)的，并由此得到了二維網(wǎng)格在擴(kuò)充過(guò)程當(dāng)中周期性規(guī)律，并由此建立了相應(yīng)的最優(yōu)去棋子個(gè)數(shù)的模型。這樣就使得程序模型的求解在程序?qū)崿F(xiàn)等過(guò)程就變得相當(dāng)簡(jiǎn)單。將復(fù)雜的問(wèn)題，通過(guò)其規(guī)律性簡(jiǎn)化。但模型的缺點(diǎn)就是通過(guò)結(jié)果的規(guī)律性直接對(duì)問(wèn)題進(jìn)行了建模求解，從模型當(dāng)中看不出問(wèn)題結(jié)果的實(shí)際推導(dǎo)過(guò)程，是一個(gè)相對(duì)比較高度集中的模型。6.3問(wèn)題三的模型評(píng)價(jià)及改進(jìn)問(wèn)題三的模型是基于問(wèn)題二的模型的。通過(guò)二維模型的周期性性質(zhì)相三位情況的推廣，發(fā)現(xiàn)了三位情況下最優(yōu)方案仍然具有周期性，這對(duì)這一問(wèn)題模型的建立起到了極其重要的作用。和問(wèn)題二中的模型一樣，該模型通過(guò)的求解在程序?qū)崿F(xiàn)時(shí)是相當(dāng)簡(jiǎn)單的。同樣，由于模型只給出了最終結(jié)果的計(jì)算方式，是一個(gè)相對(duì)比較集中的模型，在模型中看不出結(jié)果的實(shí)際轉(zhuǎn)換過(guò)程。

7參考文獻(xiàn)姜啟源，葉其孝，數(shù)學(xué)建模，北京：機(jī)械工業(yè)出版社，2009.8.馬莉，MATLAB語(yǔ)言實(shí)用教程，北京：清華大學(xué)出版社，2010.1.薛定宇，陳陽(yáng)泉，高等數(shù)學(xué)問(wèn)題的MATLAB求解，北京：清華大學(xué)出版社,2008.汪曉銀，周保平，數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)（第二版），北京：科學(xué)出版式，2012.8.同濟(jì)大學(xué)數(shù)學(xué)系，高等數(shù)學(xué)（第二版）上冊(cè)，上海：同濟(jì)大學(xué)出版社，2009.10.占軍，張倩，MATLAB函數(shù)查詢手冊(cè)，北京：機(jī)械工業(yè)出版社，2011.1.

8附錄程序1a=zeros(4,25);a(1,3)=1;a(1,9)=1;a(1,15)=1;a(1,16)=1;a(1,22)=1;a(2,5)=1;a(2,6)=1;a(2,12)=1;a(2,18)=1;a(2,24)=1;a(3,3)=1;a(3,7)=1;a(3,11)=1;a(3,20)=1;a(3,24)=1;a(4,5)=1;a(4,9)=1;a(4,13)=1;a(4,17)=1;a(4,21)=1;c=[22111];b=zeros(14,25);b(1,1:5)=c;b(2,6:10)=c;b(3,11:15)=c;b(4,16:20)=c;b(5,21:25)=c;b(6,1)=2;b(6,7)=1;b(6,13)=1;b(6,19)=1;b(6,25)=1;b(7,2)=2;b(7,8)=1;b(7,14)=1;b(7,20)=1;b(7,21)=1;b(8,1)=2;b(8,10)=1;b(8,14)=1;b(8,18)=1;b(8,22)=1;b(9,2)=2;b(9,6)=1;b(9,15)=1;b(9,19)=1;b(9,23)=1;b(10,1)=2;b(10,6)=1;b(10,11)=1;b(10,16)=1;b(10,21)=1;b(11,:)=[0,b(10,1:24)];b(12,:)=[0,0,b(10,1:23)];b(13,:)=[0,0,0,b(10,1:22)];b(14,:)=[0,0,0,0,b(10,1:21)];f=ones(1,25);f(1:2)=[44];f(3:7)=[22222]f(11:12)=[22];f(16:17)=[22];f(21:22)=[22];A=[b;-b]d=[ones(14,1)*2;ones(14,1)*-1]aeq=a;beq=ones(4,1);[x,fv,exitflag,output]=bintprog(f,A,d,aeq,beq);程序2function[SA]=fhanshu(n,m)p=zeros(5,5);p(1,5)=1;p(2,3)=1;p(3,1)=1;p(4,4)=1;p(5,2)=1;B=[];C=[];D=[];%N<5,M>5;ifn<5||m==5ifm>5||m==5S=floor(m/5)*n;h=floor(m/5);k=mod(m,5);c=p(1:n,1:5);fori=1:hC=[C,c];endC=[C,c(1:n,1:k)]f=size(C,1);k=size(C,2);fori=1:fforj=1:kifabs(C(i,j)-1)<1e-5axis([1max(f,k)+11max(k,f)+1]);plot(j+0.5,i+0.5,'r*');title('五子連珠圖2')gridon;holdonelseaxis([1max(k,f)+11max(k,f)+1]);plot(j+0.5,i+0.5,'ko');gridon;holdonendendendendend%N<5,M<5時(shí)ifn<5ifm<5S=0;endend%N>=5,M>=5ifm>5ifn>5l=floor(m/5);k=mod(m,5);c=p(1:5,1:5);fori=1:lB=[B,c];endB=[B,p(1:5,1:k)];x=floor(n/5);y=mod(n,5);fori=1:xD=[D;B];endD=[D;B(1:y,1:length(B))];s=size(D,1)f=size(D,2)figure(1)fori=1:sforj=1:fifabs(D(i,j)-1)<1e-5axis([1max(s,f)+11max(s,f)+1]);%axis([1s+11f+1])plot(j+0.5,i+0.5,'r*');