我是一個(gè)搞NOIP競(jìng)賽的人 也搞過(guò)一點(diǎn)開(kāi)發(fā),你可以聽(tīng)聽(tīng)我的意見(jiàn)(全手打的,很累?。?/p>
成都創(chuàng)新互聯(lián)是一家集網(wǎng)站建設(shè),郊區(qū)企業(yè)網(wǎng)站建設(shè),郊區(qū)品牌網(wǎng)站建設(shè),網(wǎng)站定制,郊區(qū)網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,郊區(qū)網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè),幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力??沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿,時(shí)刻以成就客戶成長(zhǎng)自我,堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己,讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。
我學(xué)的就是Pascal語(yǔ)言,面向過(guò)程,用的是Free Pascal
如果是面向?qū)ο螅陀肈elphi
至于Java的編譯器,可以試試NetBeans或者sun公司的jdk
像C也有面向過(guò)程和面向?qū)ο?/p>
面向過(guò)程是GCC
面向?qū)ο缶褪荲C之類的了
Pascal的確是一個(gè)起步很好的語(yǔ)言,一開(kāi)始就學(xué)C或C++會(huì)很累的
語(yǔ)言一般分3種:機(jī)器語(yǔ)言 匯編語(yǔ)言 高級(jí)語(yǔ)言
機(jī)器語(yǔ)言:能直接被CPU執(zhí)行,效率極高,但是可移植性極差(換臺(tái)電腦可能就不行了),寫(xiě)起來(lái)也很麻煩
匯編語(yǔ)言:不能直接被CPU執(zhí)行,加入了一些人性化的東西,如加法用ADD、減法用SUB,但還是很麻煩
高級(jí)語(yǔ)言:效率最低,但是很人性化,可移植性很強(qiáng) 像Pascal C C++ JAVA都是高級(jí)語(yǔ)言
高級(jí)語(yǔ)言不能直接被計(jì)算機(jī)執(zhí)行,所以就需要編譯器來(lái)幫忙,把這些語(yǔ)句翻譯一下,讓CPU能執(zhí)行
高級(jí)語(yǔ)言執(zhí)行方式分兩種:解釋執(zhí)行和編譯執(zhí)行
解釋執(zhí)行:編譯器運(yùn)行一句翻譯一句,調(diào)試的時(shí)候就是這樣的
編譯執(zhí)行:編譯器將源文件編譯成.exe的可執(zhí)行文件,然后執(zhí)行
像Free Pascal、Delphi、VB、VC這種,都是IDE
不僅可以編輯源代碼,編譯源代碼,還可以調(diào)試程序等等
要學(xué)好編程,個(gè)人覺(jué)得分三塊(把我下面講的東西全學(xué)透,要1-2年)
①語(yǔ)法:學(xué)好語(yǔ)法是基礎(chǔ)!學(xué)好了語(yǔ)法,才知道語(yǔ)言如何使用,這個(gè)不用我說(shuō)吧
②數(shù)據(jù)結(jié)構(gòu)(數(shù)據(jù)結(jié)構(gòu)是脫離語(yǔ)言的,也就是說(shuō)這些數(shù)據(jù)結(jié)構(gòu)每個(gè)語(yǔ)言都好實(shí)現(xiàn)):這是一個(gè)很抽象的東西,有 線性表、棧、隊(duì)列、堆、數(shù)、圖、串、集合 等等。
分為4種:線性結(jié)構(gòu)(一對(duì)一,如 棧、隊(duì)列)、樹(shù)形結(jié)構(gòu)(一對(duì)多,如 樹(shù))、離型結(jié)構(gòu)(沒(méi)有連接)、網(wǎng)狀結(jié)構(gòu)(多對(duì)多,如 圖)
像棧就是一種FILO表,只運(yùn)行在一頭進(jìn)行輸入輸出操作,應(yīng)用在 表達(dá)式求值、撤銷恢復(fù)操作上面
隊(duì)列是FIFO表,允許在一頭進(jìn)行插入操作,另一頭錯(cuò)刪除操作
樹(shù) 就復(fù)雜了 樹(shù)和二叉樹(shù)是兩種概念,具體的自己去看書(shū)吧
二叉樹(shù)有許多特殊形態(tài),如滿二叉樹(shù) 完全二叉樹(shù) 哈夫曼樹(shù) 最優(yōu)二叉樹(shù)(哈夫曼樹(shù)不等于最有二叉樹(shù)!這點(diǎn)有許多人弄錯(cuò)。因?yàn)楣蚵鼧?shù)不一定是二叉的)
二叉樹(shù)的三種遍歷方式一定要會(huì):前序遍歷(也稱先根遍歷)根左右, 中序遍歷(也稱中根遍歷)左根右, 后序遍歷(也稱后根遍歷)左右根
圖就更復(fù)雜了,分 連通與不連通 帶權(quán)與不帶權(quán) 有向與無(wú)向,所以就有了 (不)連通有(無(wú))向(不)帶權(quán)圖這種說(shuō)法 還有什么強(qiáng)連通圖,弱連通圖的,自己看書(shū)吧!
③算法(算法是脫離語(yǔ)言的,也就是說(shuō)這些算法每個(gè)語(yǔ)言都好寫(xiě)):
1.低級(jí)算法(立意上的,就像初等數(shù)學(xué)和高等數(shù)學(xué)):窮搜、深度優(yōu)先搜索(DFS)、廣度優(yōu)先搜索(BFS,也稱寬度優(yōu)先搜索),是三種不同的遍歷方式
2.高級(jí)算法:貪心,分支,動(dòng)態(tài)規(guī)劃(DP)。其他兩個(gè)不介紹了,就介紹一下動(dòng)態(tài)規(guī)劃吧!
動(dòng)態(tài)規(guī)劃:記憶化搜索,利用以前搜索留下的數(shù)據(jù),加快解決多階段決策最優(yōu)化問(wèn)題的速度。要能動(dòng)態(tài)規(guī)劃,問(wèn)題必須滿足兩個(gè)條件(我背了好長(zhǎng)時(shí)間才背出來(lái))
①:最優(yōu)化原理(也稱最優(yōu)性原理):無(wú)論過(guò)去的狀態(tài)或決策如何,對(duì)于當(dāng)前的決策所形成的狀態(tài)而言,余下的諸決策必須構(gòu)成最優(yōu)策略。
②:無(wú)后效性:一旦一個(gè)狀態(tài)的決策確定,則此后過(guò)程的演變不再受此前各狀態(tài)及決策的影響,當(dāng)前狀態(tài)時(shí)此前歷史的完整總結(jié),此前歷史只能通過(guò)當(dāng)前狀態(tài)去影響過(guò)程未來(lái)的演變。
學(xué)DP一般從背包開(kāi)始,背包一共有8個(gè):01背包、完全背包、多重背包、混合三種背包、二維費(fèi)用背包、分組背包、有依賴的背包、泛化物品背包。
然后再學(xué)樹(shù)形動(dòng)態(tài)規(guī)劃
還有排序算法:冒泡排序,選擇排序,插入排序,快速排序,堆排序,希爾排序,基數(shù)排序,序數(shù)排序,桶排序,鴿巢排序,二叉樹(shù)排序(應(yīng)用二叉排序樹(shù)),雞尾酒排序(就是雙向冒泡,在一次初賽的完善程序里出現(xiàn)過(guò))
還有數(shù)論算法(不展開(kāi)介紹了)
圖論算法:
最短路(顧名思義,就是一個(gè)點(diǎn)到另一個(gè)點(diǎn)的最短路程):迪杰斯特拉(Dijkstra)、弗洛伊德(Floyd)、SPFA(國(guó)人設(shè)計(jì)的,很不錯(cuò))等等 還會(huì)要解決SPFA的負(fù)權(quán)回路問(wèn)題 這幾個(gè)算法都是解決單源最短路徑問(wèn)題的,就是一個(gè)點(diǎn)到所有點(diǎn)的最短路)
最小生成樹(shù)(應(yīng)用在無(wú)向連通圖中,就是拿掉一些邊,在保證圖連通的情況下,使得剩下的邊權(quán)值之和最?。浩绽罚≒rim)、克魯斯卡爾(Kruskal)
關(guān)鍵路徑(在生產(chǎn)生活中應(yīng)用很廣,注意關(guān)鍵路徑之前一定要拓?fù)湟淮危。⑼負(fù)渑判颍捎糜谑欠裼协h(huán)路的檢測(cè))、網(wǎng)絡(luò)流等等
如果以上你都會(huì)了,那么恭喜你,你已經(jīng)可以算是一名初級(jí)程序員了!
可以繼續(xù)學(xué) 雙向深搜、雙向廣搜、周界搜索、迭代加深搜索、迭代加寬搜索、A*廣度優(yōu)先啟發(fā)搜索、A*迭代加深搜索 等高級(jí)的算法。
課程:
(1)基本算法: 二分,分治,貪心
(2) 離散數(shù)學(xué)離散數(shù)學(xué)動(dòng)態(tài)規(guī)劃
(3) 搜索算法:深度優(yōu)先 搜索,廣度優(yōu)先搜?A*算法 ,阿爾法貝塔剪枝
(4)數(shù)據(jù)結(jié)構(gòu):??線段樹(shù), 樹(shù)狀數(shù)組,并查集,Trie圖
(5)圖論問(wèn)題:最小生成樹(shù) 最短路 強(qiáng)連通分量、橋和割點(diǎn)
(6)網(wǎng)絡(luò)流算法:基本的網(wǎng)絡(luò)流算法,Dinic算法,帶上下界的網(wǎng)絡(luò)流,最小費(fèi)用流
(7)計(jì)算幾何:線與線求交,線與面求交,求凸包,半平面求交等
(8) 離散數(shù)學(xué),高等數(shù)學(xué),線性代數(shù),初等數(shù)論,計(jì)算幾何
(9)計(jì)算機(jī)專業(yè)英語(yǔ)
(10)C++;基礎(chǔ)的遞歸、枚舉算法
擴(kuò)展資料:
1.參賽隊(duì)伍最多由三名參賽隊(duì)員組成。
2.競(jìng)賽中命題10題左右,試題描述為英文,比賽時(shí)間為5個(gè)小時(shí),前四個(gè)小時(shí)可以實(shí)時(shí)看到排名,最后一小時(shí)封榜,無(wú)法看到排名。
3.競(jìng)賽可以使用的語(yǔ)言:Java, C, C++, Kotlin 和 Python。
4.重點(diǎn)考察選手的算法和程序設(shè)計(jì)能力,不考察實(shí)際工程中常用的系統(tǒng)編程,多線程編程等等;
5.選手可攜帶任何非電子類資料,包括書(shū)籍和打印出來(lái)的程序等,部分賽區(qū)會(huì)對(duì)選手?jǐn)y帶的紙質(zhì)資料做限制。
6.評(píng)委負(fù)責(zé)將結(jié)果(正確或出錯(cuò)的類型)通過(guò)網(wǎng)絡(luò)盡快返回給選手,除此之外不提供任何額外幫助;
7.每個(gè)題目對(duì)應(yīng)一種顏色的氣球,通過(guò)該題目的隊(duì)伍會(huì)得到對(duì)應(yīng)顏色氣球。每道題目第一支解決掉它的隊(duì)還會(huì)額外獲得一個(gè)“FIRST PROBLEM SOLVED”的氣球。
參考資料:北京大學(xué)暑期課:ACM/ICPC競(jìng)賽訓(xùn)練
百度百科-ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽
一、實(shí)驗(yàn)題目
五子棋游戲。
二、問(wèn)題分析
五子棋是雙人博弈棋類益智游戲,由圍棋演變而來(lái),屬純策略型。棋盤(pán)通常15*15,即15行,15列,共225個(gè)交叉點(diǎn),即棋子落點(diǎn);棋子由黑白兩色組成,黑棋123顆,白棋122顆。游戲規(guī)則為黑先白后,誰(shuí)先五子連成一條直線誰(shuí)贏,其中直線可以是橫的、縱的、45度、135度。
本次Java編程我的目的是現(xiàn)實(shí)人機(jī)對(duì)戰(zhàn),即游戲者一方是人,另一方計(jì)算機(jī)。這就要求程序不僅要具備五子棋的基本界面,還要編程指導(dǎo)計(jì)算機(jī)與人進(jìn)行對(duì)弈。為了使程序盡可能智能,我采用了貪心策略、傳統(tǒng)搜索算法、極大極小博弈樹(shù)算法,對(duì)應(yīng)游戲玩家的3個(gè)等級(jí):簡(jiǎn)單、中等、困難。
三、功能設(shè)計(jì)
我的程序基本功能是實(shí)現(xiàn)人機(jī)對(duì)弈五子棋。人和電腦交替下棋,誰(shuí)先五子連成一條直線誰(shuí)就贏。下面是我程序的功能模塊:
1.等級(jí)設(shè)置
核心功能是實(shí)現(xiàn)不同策略與算法的對(duì)比運(yùn)用,純貪心策略實(shí)現(xiàn)簡(jiǎn)單等級(jí)對(duì)手,直接搜索算法實(shí)現(xiàn)中等等級(jí)對(duì)手,極大極小博弈樹(shù)算法實(shí)現(xiàn)困難等級(jí)對(duì)手。對(duì)應(yīng)程序中的3選1單選按鈕。
2.悔棋功能
模擬棧機(jī)制實(shí)現(xiàn)人悔棋,不限步長(zhǎng)的悔棋。對(duì)應(yīng)程序中的悔棋按鈕。
3.棋面繪制
根據(jù)不同機(jī)計(jì)算機(jī)的屏幕分辨率,繪制逼真的棋盤(pán)。
4.圖片引入
兩張古典的人物圖片,生動(dòng)模擬對(duì)弈雙方。人物圖片旁的黑白棋缽圖片顯示黑白棋歸屬。
5.背景設(shè)置
支持用戶選擇背景,包括棋盤(pán)、棋盤(pán)邊框、窗口邊框,彰顯個(gè)性。
6.音樂(lè)播放
下棋時(shí)有棋子落地的聲音,一方勝利時(shí)有五子連成一片的聲音。同時(shí)在設(shè)置背景時(shí)相應(yīng)的改變整個(gè)對(duì)弈過(guò)程中的背景音樂(lè)。
7.時(shí)間顯示
在棋盤(pán)正上方有一模擬文本框顯示當(dāng)前棋局用時(shí)。
8.其他小功能
支持和棋、認(rèn)輸、開(kāi)啟新游戲、退出游戲等操作。
四、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)
數(shù)據(jù)結(jié)構(gòu)部分
1.當(dāng)前棋局的存儲(chǔ)結(jié)構(gòu)
我的五子棋程序選擇通常用到的15行*15列棋盤(pán),可以開(kāi)二維數(shù)組PositionFlag?=?new?int[15][15],PositionFlag[i][j]為0表示(i,j)點(diǎn)尚無(wú)棋,為1表示(i,j)點(diǎn)是人的棋子,為2表示(i,j)點(diǎn)是機(jī)器的棋子。之所以選擇二維數(shù)組,主要原因有兩點(diǎn):
1.本程序需要頻繁隨機(jī)訪問(wèn)15*15的交叉點(diǎn),對(duì)應(yīng)查詢?cè)擖c(diǎn)狀態(tài)以及改變?cè)擖c(diǎn)狀態(tài),隨機(jī)訪問(wèn)是數(shù)組的特點(diǎn)。
2.15*15=225開(kāi)二維數(shù)組的內(nèi)存需求相對(duì)現(xiàn)在內(nèi)存為2G及以上的計(jì)算機(jī)完全可以接受,且數(shù)組實(shí)現(xiàn)簡(jiǎn)單、操作方便。
基于以上兩點(diǎn),盡管創(chuàng)建動(dòng)態(tài)的順序表—鏈表可能可以節(jié)省少量?jī)?nèi)存(可以只存當(dāng)前有棋的點(diǎn),原數(shù)組對(duì)應(yīng)位置為0的點(diǎn)可以不存),但選擇數(shù)組的優(yōu)勢(shì)完全在上述兩點(diǎn)體現(xiàn)了出來(lái)。
2.實(shí)現(xiàn)悔棋操作的數(shù)據(jù)結(jié)構(gòu)
由于每次悔棋只需回退當(dāng)前幾步,后進(jìn)先出原則,這正是棧這種典型數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思想,于是我選擇棧。我自己先寫(xiě)了用自定義數(shù)組模擬的棧,但由于是學(xué)Java語(yǔ)言且由于悔棋的存儲(chǔ)空間需要隨當(dāng)前步數(shù)增大而增大(由于每局最多下225步,即最多要悔225步,所以自己開(kāi)個(gè)225的數(shù)組完全可以避免存儲(chǔ)空間自增長(zhǎng)的問(wèn)題且內(nèi)存完全可以接受,之所以不用自定義數(shù)組而用ArrayList類主要是為了嘗試Java中STL的用法),所有我最終改為用Java類庫(kù)中的ArrayList類。
確定用ArrayList類實(shí)現(xiàn)棧機(jī)制后就必須考慮每個(gè)ArrayList單元具體存儲(chǔ)什么。剛開(kāi)始我存儲(chǔ)的是當(dāng)前的棋局,即整個(gè)局面,而每個(gè)局面對(duì)應(yīng)一個(gè)二維數(shù)組,這樣是很占用內(nèi)存的。試想一下,在最壞情況下,225個(gè)ArrayList單元,每個(gè)單元存放一個(gè)15*15的二維數(shù)組,盡管225*15*15在Java的內(nèi)存管理機(jī)制下不會(huì)爆棧,但也是極不劃算的。之所以說(shuō)不劃算,是因?yàn)橛懈玫慕鉀Q方案。由于每次悔棋只是在回退倒數(shù)一步,多步悔棋只需循環(huán)回退,所以可以只存儲(chǔ)當(dāng)前棋局最后一步的下法,對(duì)應(yīng)一個(gè)二維點(diǎn),完全可以自定義一個(gè)二維坐標(biāo)類chessOneStep。
算法設(shè)計(jì)部分
Java語(yǔ)言是面向?qū)ο蟮恼Z(yǔ)言。我在進(jìn)行五子棋游戲編程是總共傳創(chuàng)建了11個(gè)自定義的類。在編寫(xiě)程序的過(guò)程中,我有一個(gè)明顯的體驗(yàn)就是面向?qū)ο缶幊叹褪且豁?xiàng)有關(guān)對(duì)象設(shè)計(jì)和對(duì)象接口技術(shù),很多關(guān)鍵的技術(shù)就是如何設(shè)計(jì)自定義的對(duì)象。
下面我先概括給出我的所有類的作用:
1.mainFrame類:主框架類,我應(yīng)用程序的入口;
2.chessPositon類:主控類,這個(gè)類是我程序的核心類,負(fù)責(zé)控制雙方的下棋,以及調(diào)用其他的類完成當(dāng)前棋局的顯示繪制;
3.chessPanel類:面板類,調(diào)用其他底層類完成當(dāng)前棋局的顯示繪制;
4.chessBoard類:棋盤(pán)繪制類,負(fù)責(zé)棋盤(pán)的繪制;
5.chessImage類:文件類,包含各種資源(背景圖片、背景音樂(lè))以及靜態(tài)全局變量(public?static?Type);
6.chessButton類:組件類,定義各種組件,包括按鈕、單選按鈕、文本框等;
7.chessMusic類:音樂(lè)類,負(fù)責(zé)調(diào)用Java庫(kù)類完成背景音樂(lè)、下棋音樂(lè)、取勝音樂(lè)等的播放;
8.chessPiece類:棋局類,定義棋局二維數(shù)組數(shù)據(jù)結(jié)構(gòu)并完成相關(guān)操作;
9.chessList類:棧類,完成悔棋等操作;
10.?chessOneStep類:棋子類,定義每步坐標(biāo)以及下在該處獲得的估價(jià)值;
11.myCompare類:排序類,完成chessOneStep類的自定義排序
詳細(xì)設(shè)計(jì)
1.mainFrame類
作為我的五子棋程序的主類,mainFrame類主要實(shí)例化相關(guān)的對(duì)象,如chessbutton,chessborad等,從而完成框架的創(chuàng)建。更重要的是實(shí)例化chessposition,這是本程序的核心類,控制游戲雙方行棋過(guò)程完成人機(jī)互動(dòng)下棋,然后將MyChessPosition與鼠標(biāo)響應(yīng)addMouseListener()關(guān)聯(lián)起來(lái)。
2.chessMusic類
一個(gè)好的游戲必須給人一種身臨其境的感覺(jué),而聲音是營(yíng)造這種氛圍的重要因素。參照網(wǎng)上各游戲運(yùn)行商的音樂(lè)配置,我選擇相關(guān)逼真的聲音。包括背景音樂(lè)、下棋棋子落到棋盤(pán)發(fā)出的聲音以及一方勝出的配樂(lè)。所有這些功能的實(shí)現(xiàn),依賴于自定義的chessMusic類,采用AudioInputStream配合Clip的方式完成音樂(lè)播放的軟硬件工作,然后定義兩個(gè)接口chessmusic(String?Name)和Stop(),前者完成播放功能,后者完成關(guān)閉當(dāng)前音樂(lè)功能。因?yàn)橐纛l文件相對(duì)較大,而我的程序提供在不同背景樂(lè)之間切換的功能,所以在打開(kāi)另一個(gè)音頻文件之前必須關(guān)閉前一個(gè)正在播放的音頻文件,防止出現(xiàn)溢出。
3.chessImage類
適當(dāng)?shù)膭?dòng)畫(huà)或圖片能給游戲玩家?guī)?lái)美的體驗(yàn)。所以我的五子棋程序界面在不失和諧的前提下引入了盡可能多的圖片,包括對(duì)弈雙方、棋缽等。圖片引入的具體工作通過(guò)語(yǔ)句import?javax.imageio.ImageIO完成。同時(shí),由于圖片要在用到它的類中被訪問(wèn),為了避免頻繁調(diào)用函數(shù),我直接將圖片相關(guān)聯(lián)的對(duì)象定義為public?static,表明是公用的、靜態(tài)的。進(jìn)一步引申開(kāi)去,我將程序中用到的靜態(tài)全局變量都定義在chessImage類中。具體如下:
public?static?Date?begin;//每局開(kāi)始時(shí)間
public?static?Date?cur;//每局結(jié)束時(shí)間
public?static?chessOneStep?LineLeft;//結(jié)束端點(diǎn)1
public?static?chessOneStep?LineRight;//結(jié)束端點(diǎn)2
public?static?boolean?IsGameOver;//是否只有一方獲勝
public?static?int?ColorOfBackGround[][]=?{{255,?227,?132},{0,255,127},{218,165,32}};//背景顏色
public?static?int?ColorOfWindows[][]=?{{?60,179,113},{245,245,245},{122,122,122}};//背景顏色
public?static?int?WitchMatch;//背景搭配
public?static?String?MusicOfBackGround;//背景音樂(lè)
public?static?int?CurrentStep;//記錄當(dāng)前步數(shù)
public?static?int?Rank;//設(shè)置難度等級(jí)
public?static?boolean?IsSurrender;//判斷是否認(rèn)輸
public?static?boolean?IsTie;//判斷是否認(rèn)輸
public?static?String?Message;//輸出提示信息
public?static?Image?IconImage;//?圖標(biāo)
public?static?Image?blackBoard;//白棋盤(pán)
public?static?Image?whiteBoard;//黑棋盤(pán)
public?static?Image?blackChess;//?白棋棋子圖片
public?static?Image?whiteChess;//?白棋棋子圖片
public?static?Image?RightPlayer;//白棋棋罐圖片
public?static?Image?LeftPlayer;//白棋玩家頭像圖片
public?static?String?path?=?"src/";//?圖片的保存路徑
4.chessButton類
這個(gè)是程序的組件類。定義了各種功能鍵,完善程序功能,營(yíng)造逼真的人機(jī)對(duì)戰(zhàn)游戲效果。分為3類:效果。。
(1)、按鈕組件
本程序有5個(gè)按鈕,支持和棋、認(rèn)輸、新游戲、退出、悔棋等。認(rèn)輸和和棋按鈕終止當(dāng)前的棋局,給出相應(yīng)的提示信息;退出按鈕調(diào)用系統(tǒng)System.exit(0)的函數(shù)正常返回;悔棋按鈕調(diào)用后面要介紹的chessList類實(shí)現(xiàn)悔棋;新游戲按鈕則刷新當(dāng)前棋局準(zhǔn)備下一輪,要將記錄當(dāng)前棋局的二維數(shù)組全部置0,刷新當(dāng)前棋局開(kāi)始時(shí)間等。
(2)、單選按鈕組件
游戲界面支持設(shè)置個(gè)性化界面,包括背景顏色與背景音樂(lè),跟重要的一點(diǎn)是設(shè)置難度(簡(jiǎn)單、中等、困難)。單選按鈕只能多選一。背景顏色主要是存儲(chǔ)相關(guān)顏色搭配方案的RGB顏色,開(kāi)2維數(shù)組,即對(duì)應(yīng)RGB3原色數(shù)組的一維數(shù)組,然后通過(guò)改變WitchMatch全局變量的值來(lái)有用戶自己選擇顏色搭配,不同的顏色搭配對(duì)應(yīng)不同的背景音樂(lè)表達(dá)一致的主題。難度設(shè)置主要是改變計(jì)算機(jī)的下棋算法,不同難度通過(guò)Rank判斷進(jìn)入不同的程序分支,實(shí)現(xiàn)不同智能等級(jí)的計(jì)算機(jī)下棋水平。
(3)、文本框
在不同的單選按鈕前添加相應(yīng)的文本框,提示用戶可以實(shí)現(xiàn)的功能。同時(shí)我用顏色模擬出顯示當(dāng)前棋局耗用時(shí)間的文本框。
不論按鈕還是單選按鈕都要關(guān)聯(lián)相應(yīng)的消息,把相應(yīng)功能的實(shí)現(xiàn)放在消息響應(yīng)處理函數(shù)理。這些主要是實(shí)現(xiàn)Java庫(kù)提供的消息響應(yīng)接口里的方法。
5.chessPiece類
主要完成當(dāng)前棋面的存儲(chǔ),存儲(chǔ)棋面的數(shù)據(jù)結(jié)構(gòu)為二維數(shù)組int[][]?PositionFlag;然后定義獲取、設(shè)置某點(diǎn)以及整個(gè)棋面的狀態(tài)的方法。
(1)、SetPositionFlag(int?x,?int?y,?int?flag)//設(shè)置(x,y)處的狀態(tài)為flag
(2)、GetPositionFlag(int?x,?int?y)//獲?。▁,y)處的狀態(tài)
(3)、SetAllFlag(int?[][]NewFlag)//設(shè)置當(dāng)前整個(gè)棋面的狀態(tài)為NewFlag
(4)、GetAllFlag()//獲取當(dāng)前整個(gè)棋面的狀態(tài)
(5)、DrawChessPiece(Graphics?g)//繪制當(dāng)前局面的棋子
由于本類比較重要,所以附上了代碼,見(jiàn)源代碼1。
6.chessBoard類
功能為繪制棋盤(pán)線。由于圍棋的棋盤(pán)比較復(fù)雜,橫線、豎線較多,且為了使棋盤(pán)美觀,還要自定義窗口邊框、棋盤(pán)邊框、對(duì)弈雙方邊框等,對(duì)線寬、線型也有一定要求。有時(shí)要單像素線條,有時(shí)要多像素線條。對(duì)于多像素線條,我主要用了2種方法。
方法一:
在需要繪制多像素線條處首先繪制一條單像素線,然后根據(jù)線寬要求上下平移適當(dāng)像素達(dá)到繪制多像素的目的。這樣的方法適合繪制水平線或豎直線,繪制其他斜率的線條容易造成走樣。在沒(méi)有想到比較好的反走樣編程思想后我選擇了調(diào)用Java庫(kù)中已經(jīng)封裝好的函數(shù)。
方法二:
為了克服方法一繪制非水平或豎直線時(shí)造成的走樣,同時(shí)也為了更進(jìn)一步學(xué)習(xí)Java語(yǔ)言,我猜想肯定會(huì)有類似OpenGL中設(shè)置線寬的畫(huà)刷,于是上網(wǎng)百度找到了相應(yīng)的畫(huà)刷Stroke類。通過(guò)Java庫(kù)實(shí)現(xiàn)繪制不同線寬的直線,達(dá)到了反走樣效果。
7.chessOneStep類
這個(gè)類是為了配合chessList類實(shí)現(xiàn)悔棋以及在計(jì)算機(jī)下棋算法實(shí)現(xiàn)返回有效狀態(tài)點(diǎn)而設(shè)計(jì)的。主要數(shù)據(jù)成員為
private??int??x,y,weight;//其中x,y表示點(diǎn)坐標(biāo),weight表示將棋下到該點(diǎn)獲得的估價(jià)值。
主要方法如下:
(1)、GetX()//獲得當(dāng)前對(duì)象的x坐標(biāo)
(2)、GetY()//獲得當(dāng)前對(duì)象的y坐標(biāo)
(3)、GetWeight()//獲得當(dāng)前對(duì)象的(x,y)處的估價(jià)值
8.chessList類
程序支持悔棋功能,為了實(shí)現(xiàn)悔棋,自定義了chessList類。這個(gè)類主要通過(guò)引入java.util.ArrayList和java.util.List實(shí)現(xiàn)集合的數(shù)據(jù)類型。然后自定義一些方法,如下:
(1)、AddStep(chessOneStep?OneStep)//添加一步棋到List中
(2)、GetSize()//獲得當(dāng)前List的大小
(3)、ClearList()//清空List
(4)、RemoveLast()//刪去List中的最后元素
由于每次刪除當(dāng)前List中的最后一個(gè)元素,實(shí)現(xiàn)后進(jìn)先出,所以可以模擬棧的功能實(shí)現(xiàn)悔棋。
9.myCompare類
由于在計(jì)算機(jī)下棋的極大極小博弈樹(shù)算法中需要對(duì)自定義對(duì)象chessOneStep按weight進(jìn)行排序,所以引入了myCompare類,通過(guò)實(shí)現(xiàn)Comparator接口中的compare方法完成自定義對(duì)象排序。
10.chessPanel類
程序的自定義面板類,主要負(fù)責(zé)完成當(dāng)前框架內(nèi)容的顯示。這是一個(gè)重要的與框架和圖形顯示密切相關(guān)的類。主要數(shù)據(jù)成員為
private?chessboard?MyChessBoard;//當(dāng)前顯示棋盤(pán)
private?chesspiece?MyChessPiece;//當(dāng)前顯示整個(gè)棋面的狀態(tài)
主要方法如下:
(1)、chesspanel(chessboard?MyChessBoard1,?chesspiece?MyChessPiece1)//構(gòu)造函數(shù),分別用MyChessBoard1和MyChessPiece1初始化MyChessBoard和MyChessPiece
(2)display(chessboard?MyChessBoard1,?chesspiece?MyChessPiece1)//自定義顯示回調(diào)函數(shù),調(diào)用repaint()完成重新繪制游戲界面
(3)、paintComponent(Graphics?g)//核心方法,調(diào)用各種函數(shù)完成具體的繪制工作
11.chessPositon類
程序算法核心類,總的功能是控制人和計(jì)算機(jī)輪流下棋,以及調(diào)用chessPanel類中的display(chessboard?,?chesspiece?)方法完成界面的實(shí)時(shí)刷新。關(guān)于chessPositon類,我在此將重點(diǎn)介紹。chessPosition類的主要數(shù)據(jù)成員如下:
private?static?chessboard?MyChessBoard;//當(dāng)前顯示棋盤(pán)
public?static?chesspiece?MyChessPiece;//當(dāng)前顯示整個(gè)棋面的狀態(tài)
private?static?chesspanel?Mychesspanel;////當(dāng)前顯示面板
public?static?chesslist?MyChessList=new?chesslist();//當(dāng)前下棋集合,用于悔棋
final?private?static?int?INF?=?(1??30);?//?表示正無(wú)窮大的常量,用于極大極小博弈數(shù)搜索算法
public?static?boolean?CanGo;//控制當(dāng)前下棋一方
類的設(shè)計(jì)集中體現(xiàn)在成員方法的設(shè)計(jì)上。實(shí)現(xiàn)人機(jī)對(duì)戰(zhàn),只有語(yǔ)言是遠(yuǎn)遠(yuǎn)不夠的,還要加入算法,用算法引導(dǎo)計(jì)算機(jī)下棋。下面介紹該類的方法成員:
(1)、chessposition(chesspanel?,?chessboard?,chesspiece?)?//帶有參數(shù)的構(gòu)造函數(shù)
(2)、chessposition()
不帶參數(shù)的構(gòu)造函數(shù)
(3)、mouseClicked(MouseEvent?event)
鼠標(biāo)響應(yīng)函數(shù),負(fù)責(zé)人的下棋,根據(jù)鼠標(biāo)點(diǎn)擊的位置轉(zhuǎn)換得到所在棋盤(pán)的相對(duì)位置。如果該位置不合法,即超出棋盤(pán)有效范圍,點(diǎn)擊無(wú)響應(yīng);如果該位置上已有棋,彈出消息框給出提示。這二者都要求重新給出下棋位置,即當(dāng)前鼠標(biāo)響應(yīng)無(wú)效…直到點(diǎn)擊到棋盤(pán)有效區(qū)域。
(4)、IsOver(int[][]?Array,int?x,int?y)
判斷當(dāng)前int[][]Array對(duì)應(yīng)的棋局是否結(jié)束,即一方五子連成一條直線。此處有兩種思路,一種對(duì)當(dāng)前棋面上的所有棋子都進(jìn)行一次判斷,具體為水平方向、豎直方向、與水平線成45度方向、與水平線成135度方向,只要有一個(gè)方向五子連成一條直線就說(shuō)明有一方獲勝,游戲結(jié)束;另一種思路為只在當(dāng)前下棋的4個(gè)方向進(jìn)行判斷,我的程序采用的是第二種,所以IsOver方法除了int[][]Array參數(shù)外,還有x,y參數(shù),(x,y)表示當(dāng)前下棋的坐標(biāo)點(diǎn)。
(5)display()
通過(guò)調(diào)用自定義面板類的顯示回調(diào)函數(shù)用于重新顯示游戲界面,達(dá)到每下一步棋及時(shí)更新游戲界面的目的。
(6)、GetValue(int?flag,?int?num)
估值函數(shù),根據(jù)經(jīng)驗(yàn)把棋局分成只有1顆棋相連,2顆棋相連且兩端被封死,2顆棋相連且一端封死另一端活的,2顆棋相連且兩端都是活的,同理3顆棋、4顆棋也各自可分3種情況。不同的情況對(duì)應(yīng)不同的估價(jià)值。估價(jià)值的設(shè)定是決定計(jì)算機(jī)一方是否智能的一個(gè)關(guān)鍵因素。
(7)、GetPredictValue(int?flag,?int?num)
對(duì)未連成一片但通過(guò)再下一顆子就能連成一片的局面進(jìn)行估值,這在雙方下棋的有限步驟內(nèi)是能產(chǎn)生重要影響的。如果每局棋僅考慮當(dāng)前一步,是不可取的。
(8)、Evaluate(int[][]?Array,?int?x,?int?y)
根據(jù)棋面具體情況以及預(yù)先設(shè)定的估值函數(shù),對(duì)某個(gè)點(diǎn)對(duì)應(yīng)的局面進(jìn)行評(píng)估。由于每次雙方只能下一顆棋,所以可以每次取當(dāng)前局面的所有點(diǎn)中對(duì)應(yīng)估值最大值點(diǎn)的估值作為整個(gè)局面的估值。
(9)、GetGreedNext()
計(jì)算機(jī)下棋方法1,對(duì)應(yīng)難度等級(jí)為簡(jiǎn)單,采用貪心思想。每次下棋前在求得最有利點(diǎn)下棋,而是否最有利只是通過(guò)一步評(píng)估。算法偽碼描述為:
Max取負(fù)無(wú)窮大
for(行i從0到15)
{
For(列j從0到15)
{
If((i,j)對(duì)應(yīng)的位置無(wú)棋)
{
a.假設(shè)放上一顆由人控制的棋,求估價(jià)值;
b.假設(shè)放上一顆由計(jì)算機(jī)控制的棋,求估價(jià)值;
c.取二者中較大值作為(i,j)處的估價(jià)值tmp;
d.取tmp與Max較大值賦值給Max.
}
}
}
最終Max對(duì)應(yīng)的點(diǎn)就是當(dāng)前整個(gè)局面中最大的估值點(diǎn)。至于上述為什么要考慮雙方都在該點(diǎn)下棋的情況呢?主要原因?yàn)橄挛遄悠迨莻€(gè)攻防兼?zhèn)涞倪^(guò)程,不僅要考慮自己對(duì)自己最有利,還要考慮對(duì)對(duì)手最不利,通俗來(lái)講就是在自己贏的時(shí)候不能讓對(duì)手先贏。
(10)、GetSearchNext(int?LookLength)
derectSearch(int?[][]Array,boolean?who,int?deepth)
計(jì)算機(jī)下棋方法2:直接搜索法,對(duì)應(yīng)難度等級(jí)為中等。
每步棋最多有225個(gè)不同下法,若采用直接搜索法則對(duì)應(yīng)的孩子節(jié)點(diǎn)有225個(gè)(在下棋過(guò)程中會(huì)逐漸減少),即每層有最多225個(gè)節(jié)點(diǎn)待擴(kuò)展,這就決定了直接搜索進(jìn)行不超過(guò)2次—主要原因有兩點(diǎn):
a.采用深度優(yōu)先搜索需要遞歸,遞歸中狀態(tài)過(guò)多可能會(huì)爆棧,我們知道遞歸是用棧機(jī)制來(lái)實(shí)現(xiàn)的;采用寬度優(yōu)先搜索又需要存儲(chǔ)為擴(kuò)展的節(jié)點(diǎn),這對(duì)內(nèi)存容量要求很高。
b.不管深搜還是廣搜,在時(shí)間復(fù)雜度為O(N^m)的情況下都是不能接受的。其中N為當(dāng)前棋局的待擴(kuò)展節(jié)點(diǎn),最大225;m為搜索的深度。
綜上所述,在采用直接搜索法時(shí)搜索深度不能太深,嚴(yán)格來(lái)說(shuō)是應(yīng)該控制在2層以內(nèi),在計(jì)算機(jī)運(yùn)算速度在10^7次每秒的情況下,理論和實(shí)驗(yàn)都表明超過(guò)2層就會(huì)變得很慢且這種趨勢(shì)成指數(shù)級(jí)增長(zhǎng)。
直接搜索算法偽代碼為
GetSearch(boolean?flag,int?deep)
{
如果deep等于0,返回當(dāng)前棋局估值;
for(行i從0到15)
{
For(列j從0到15)
{
If((i,j)對(duì)應(yīng)的位置無(wú)棋)
{
如果輪到計(jì)算機(jī)下棋,置標(biāo)志位為2
GetSearch(!flag,deep-1);
如果輪到人下棋,置標(biāo)志位為1;
GetSearch(!flag,deep-1);
}
}
}
}
(11)、GetMinMaxsearchNext(int?LookLength)
MinMaxsearch(int?[][]Array,boolean?who,?int?deepth)
計(jì)算機(jī)下棋算法3:極大極小博弈樹(shù)法,對(duì)應(yīng)難度等級(jí)為困難。五子棋是個(gè)博弈游戲,當(dāng)前在尋找對(duì)自己最有利的下棋點(diǎn)時(shí)要盡可能保證對(duì)對(duì)手最不利,這種思想可以用極大極小博弈樹(shù)
遞歸的話就是深度優(yōu)先搜索(可以理解成不撞南墻不回頭,撞了墻就原路返回)可以加上剪枝(就是做標(biāo)記,如果之前某一次走過(guò)但不通的路下次再走到就不用走了)
用棧的話應(yīng)該是廣度優(yōu)先搜索(大概就是分裂無(wú)數(shù)個(gè)你,每次向所有方向走一步),不過(guò)廣搜要用隊(duì)列實(shí)現(xiàn),用棧本質(zhì)還是深搜了
具體算法可以搜百度
網(wǎng)頁(yè)名稱:廣搜代碼Java 廣搜代碼實(shí)現(xiàn)
本文網(wǎng)址:http://www.muchs.cn/article2/hjepoc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供微信小程序、網(wǎng)站排名、品牌網(wǎng)站建設(shè)、外貿(mào)建站、定制開(kāi)發(fā)、網(wǎng)站營(yíng)銷
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來(lái)源: 創(chuàng)新互聯(lián)