1、信息工程系綜合課程設(shè)計(jì)報(bào)告題 目:班 級(jí):學(xué) 號(hào):姓 名:指導(dǎo)老師:數(shù)據(jù)結(jié)構(gòu)與算法.看得見(jiàn)的算法軟件與信息服務(wù)四班19023038成林詩(shī)睿四、附件核心代碼，圖一：koch雪花分形public AlgoVisualizer(int depth, int side)A8 * vdata = new FractalData(depth);int scenewidth = 3*side+3; int sceneHeight = side;EventQueue.invokeLater() - -frame = new AlgoFrame( title： Fractal Visualizer1, scen

2、ewidth、sceneHeiqht): frame.addKeyListener(new AlgoKeyListenerO);二new Thread() - run(); ?).start(); ?)； ? private void run() setData(data.depth); ? private void setData(int depth) data.depth = depth; frame.render(data); AlgoVisHelper.pause(DELy);throw new IllegalArgumentException(Text is null in draw

3、Text function!);FontMetrics metrics = g.getFontMetricsO;int w = metrics.stringWidth(text);int h = metrics.getDescentO;g.drawstring(text, x： centerx - w/2, y： centery + h);?public static void fillTriangle(Graphics2D g, int xl, int yl, int x2, int y2, int x3GeneralPath path = new GeneralPathO;path.mov

4、eToCxl, yl);path.lineTo(x2r y2);path.lineToCxS, y3);path.closePathO;g.filKpath);public static void drawLine(Graphics2D g, double xl, double yl, double x2, double y2：Line2D line = new Line2D.Double(xlr yl, x2, y2);g.draw(line);Fractal Visualizer二：掃雷2347707172737475767778790Override public String toSt

5、ringO return Person +name= + name +,age= + age +,gender= + gender + ,id=H + id +public static void main(String args) List personList = new ArrayList( initialcapacity： 3);-Scanner scanner = new Scanner(System.in); int n = scamuer.nextlntO;-for (int i = 0; i System. out. printin (person. toStringO);10

6、6789 ie ii121314151617181926212223242526272829A 10private static int DELAY = 5;private static int blockside = 32;private MineSweeperData data;private AlgoFrame frame;private static final int d =public AlgoVisualizer(int N, int M, int mineNumberXdata = new MineSweeperData(N, M, mineNumber);int scenew

7、idth = M * blockside;int sceneHeight = N * blockSide;EventQueue.invokeLater(.O - frame = new AlgoFrame( title： HMine Sweeper, scenewidth、sceneHeiqht):new Thread() - run();) .start。；)；private void run()11JJJJIIkJnMine Sweeperr*-U制rrir圜J三：推箱子J廠廠廠JllJ12JJIJ*B且JJrir hjJJiIBiLJFlI8916private private6 pub

8、lic class AlgoVisualizer static int DELA=5；static int blockSide = 89121314161819 2G042324282930private privateGameData data;AlgoFrame frame;public AlgoVisualizer(String filename) data = new GameData(filename);int scenewidth = data.NO * blockSide)int sceneHeight = data.NO * blockSide;EventQueue.invok

9、eLater() - frame = new AlgoFrame( title： Move the Box Solver, scenewidth,sceneHeiqht):new Thread() - run();),start();)；private void run()13public AlgoVisualizer(String filename)(data = new GameData(filename);int scenewidth = data.MO * blockSide)int sceneHeight = data.NO * blockSide;EventQueue.invoke

10、Loter() - frame = new AlgoFrame( title: Move the Box Solver, scenewidth, sceneHeight);new Thread() - run();).start();)； private void run()setDataO;if (data.solveO)System.out.println(The game has a solution!;elseSystem.out.printin(The game does NOT have a solution.);setDataO;, BCB., BCB.ADA.BDECBDFAF

11、CBAAEFEB.A. B A. . B BAB. .BAB. .ABA.14四：走迷宮nMr35go(data.getEntranceX(), data.getEntranceY();ak - setData( x： -1, y： -1);_39Tprivate void go(int x, int41if(!data.inArea(x,y)throw new IH.egalArgumentException(x,y are out of index in go furtC 44data.visitedxy = true;setData(x( y);47if(x = data.getExit

12、XO & y = data.getExitYO)49return;for(int i = 9 ; i 4 ; i +)int newX = x + di6; int newY = y dll； if(data.inArea(newX, newY) & data.getMaze(newX,newY) = NazeData.ROAD & !data.visitednewXnewY)57 0goCnewX, newY);60returl；private boolean go(int x, int y)-aif(!data.inArea(x,y)throw new IllegalArgumentExc

13、eption(x,y are out of index in go fuirt Idata.visitedxy = true; setData(x, y, isPath： true);if(x = data.getExitXO & y = data.getExitYO) return true;for(int i. = 8 ; i v 4 ; i +)int newX = x di0;int newY = y dil;if(data.inArea(newX, newY) &data.getMaze(newX,newY) = MazeData.R04D & !data.visitednewXne

14、wY) if(go(newX, newY) return true;/回溯setData(x, y, isPath： false);return false;15鼻二二-一1”.一堆甘郢氏，01,令)；AW A1 * V XI TOC o 1-5 h z Stack stack = new Stack();_ gPosition entrance = new Position(data.getEntranceXO, data.getEntranceY | stack.push(entrance);一,data.visitedentrance.getX()entrance.getY() = tr

15、ue;while(! stack, empty ()Position curPos = stack.pop();二setData(curPos.getX(), curPos.getY(), isPath： true);if(curPos.getX() = data.getExitXO & curPos.getY() = data.getExT break;for(int i = 0 ; i A ; i +) int newX = curPos.getX() + di0; int newY = curPos.getY() + di1;if(data.inArea(newX, newY)& (da

16、ta.visitednewXnewY& data.getMaze(newX, newY) = NazeData.R04DX stack.push(new Position(newX, newY);data.visitednewXnewY = true;?for(int i = 0 ; i 4 ; 1 +) int newX = curPos.getX() + di6; int newY = curPos.getY() + di1;if(data.inArea(newX, newY)& !data.visitednewXnewY& data.getMaze(newX, newY) = MazeD

17、ata./?04D)- stack.push(new Position(newX, newY, curPos); data.visitednewXnewY = true;if(lisSolYed)System.out.printin(The maze has no Solution!);setData( x: -1, y： T, isPath： false);private void findPath(Position des)Position cyr = des;while(cur 1=data.result(cur.getX()cue.getY() = true;cur = cur.get

18、PrevO;1617 TOC o 1-5 h z HYPERLINK l bookmark4 o Current Document 一、工程報(bào)告1 HYPERLINK l bookmark18 o Current Document 二、綜合課程設(shè)計(jì)心得6 HYPERLINK l bookmark20 o Current Document 三、教師評(píng)價(jià)8 HYPERLINK l bookmark2 o Current Document 四、附件918Mecbon Son19Illil2021一、工程報(bào)告成果描述編譯環(huán)境為：IDEA,用java語(yǔ)言，javab8的jdk配置環(huán)境詮釋了“數(shù)據(jù)結(jié)構(gòu)與算

19、 法7個(gè)個(gè)經(jīng)典游戲詮釋算法”的小游戲，本次創(chuàng)作成功共7個(gè)，分別為“ “概率模擬算 法”、“排序算法可視化”、“分形繪制”“掃雷”、通過(guò)“推箱子”、“走迷宮”以 及“隨機(jī)迷宮的生成”，接下來(lái)我將逐個(gè)分析工程成功以及所運(yùn)用技術(shù)。一、概率模擬算法概率模擬算法又稱蒙特卡洛算法，是一個(gè)非常有意思的分錢模擬問(wèn)題，通過(guò) AlgoFrame, java中在render中設(shè)置數(shù)據(jù)，在AlgoVisual izer. java控制層中定義變 量，動(dòng)畫(huà)邏輯使用run方法，先建立MonleCarloPiDala對(duì)象data,然后隨機(jī)模擬點(diǎn)， 使用data的方法addPoint加入每個(gè)點(diǎn)。每一百次計(jì)算兀值。點(diǎn)的坐標(biāo)為（

20、01隨機(jī)值）* 面板的寬高，frame的render方法不斷調(diào)用PaintComonent方法刷新控件。在這一小節(jié)的編譯中主要使用洛概率模擬的方式實(shí)現(xiàn)“三門問(wèn)題”三門問(wèn)題，亦稱為 蒙提霍爾問(wèn)題、蒙特霍問(wèn)題或蒙提霍爾悖論三門問(wèn)題，是一個(gè)源自博弈論的數(shù)學(xué)游戲問(wèn) 題，大致出自美國(guó)的電視游戲節(jié)目。當(dāng)參賽者選定了一扇門，但未去開(kāi)啟它的時(shí)候，節(jié) 目主持人開(kāi)啟剩下兩扇門的其中一扇，露出其中一只山羊。主持人其后會(huì)問(wèn)參賽者要不 要換另一扇仍然關(guān)上的門。問(wèn)題是：換另一扇門會(huì)否增加參賽者贏得汽車的機(jī)率。換門 的話中獎(jiǎng)率為2/3,不換中獎(jiǎng)率為1/3程序編譯模擬三門問(wèn)題具體表現(xiàn)為運(yùn)用一個(gè)run 函數(shù)中的for循環(huán)，在循

21、環(huán)的過(guò)程中想要到達(dá)換門或不換門的結(jié)果循環(huán)在run函數(shù)中需 傳入一個(gè)叫changeDoor ”的參數(shù)，在for循環(huán)中設(shè)置的play值通過(guò)changeDoor來(lái)返 回中獎(jiǎng)與否，假設(shè)中獎(jiǎng)的話設(shè)立變量wins=0,假設(shè)中獎(jiǎng)wins=+,否那么不動(dòng)，我們?cè)O(shè)置三個(gè) 值代表三扇門，同時(shí)玩家選擇的門也是隨機(jī)，假設(shè)此時(shí)plaer函數(shù)指向的門后有獎(jiǎng)品，用 戶堅(jiān)持不換門那么此時(shí)就必得獎(jiǎng)品，這個(gè)游戲中的勝率等于影響的次數(shù)除以我們總共玩 的次數(shù)從而得出獲獎(jiǎng)概率，因此我們可以通過(guò)player策略，觀察玩家是否換門，來(lái)完 成模擬三門問(wèn)題的play過(guò)程。二、排序算法可視化首先插入排序算法就是將我們需要排序的數(shù)插入到前面我們以

22、及處理的數(shù)中，使得我 們處理的元素都是有序的。在數(shù)據(jù)層中構(gòu)造一個(gè)numbers數(shù)組中有相應(yīng)的構(gòu)造函數(shù)，應(yīng) 用swap這樣的一個(gè)操作來(lái)交換數(shù)組通融量，元素的位置，為了讓可視化過(guò)程更加清晰 在設(shè)置一些變量用于指示繪制不同的數(shù)據(jù)，設(shè)置。rderedindex變量，期望讓這個(gè)前閉 后開(kāi)的數(shù)組是有序的，為當(dāng)前正在處理的元素設(shè)置一個(gè)叫currentindex的索引。繪制的過(guò)程，具體繪制過(guò)程對(duì)于ordcrcdindex, currentindex設(shè)置顏色將處在有序 和亂序的數(shù)組進(jìn)行顏色的設(shè)置，另外如果當(dāng)前的數(shù)據(jù)處于currentindex時(shí)，為它單獨(dú) 設(shè)置一個(gè)特殊顏色，上述完成插入排序過(guò)程具體繪制。為了實(shí)現(xiàn)

23、“近乎有序：數(shù)組，在你內(nèi)部添加一個(gè)沒(méi)矩形變量 Type”，設(shè)置兩種可能 參數(shù)，分別為default為默認(rèn)情況，以及NearlyOrdered為近乎有序，為用戶傳入新的 變量，而隨機(jī)抽取元素設(shè)置swap time決定隨機(jī)抽取的次數(shù)。通過(guò)這樣的過(guò)程形成一個(gè)近乎有 序的數(shù)據(jù)。另外為了解決數(shù)組中存在大量重復(fù)的元素使得在按基準(zhǔn)值分成兩局部時(shí)，重復(fù)元素都 集中分到其中一局部的問(wèn)題(如果兩局部元素?cái)?shù)量相差太大，快速排序算法是會(huì)退化為 0(r2)的)，可以使用雙路快速排序算法。雙路快速排序算法的基本思路：設(shè)置一個(gè)變量i從最左邊開(kāi)始遍歷直到找到第一 個(gè)比基準(zhǔn)值大的數(shù)時(shí)停止，再設(shè)置個(gè)變量j從最右邊開(kāi)始遍歷，直到找

24、到第一個(gè)比 基準(zhǔn)值小的數(shù)時(shí)停止，這時(shí)候交換i與j所表示的元素?cái)?shù)值。三路排序算法使用了 3個(gè)索引值來(lái)表示3個(gè)不同的位置，使用it索引來(lái)表示v局部 和二v局部的分界處使用i索引表示遍歷的位置，使用gt索引來(lái)表示:v局部和v局部 的分界處。如果當(dāng)前i指向的元素二v,那直接就將此元素歸為7局部，i+即可，如果 當(dāng)前i指向的元素v,將此元素與二v局部的第一個(gè)元素交換位置，也就是swap(arri, arrlt+U),之后將lt+,i+即可，此時(shí)局部就多了一個(gè)元素，如果當(dāng)前i指向的元素v,那么將此元素與v局部的第一個(gè)元 素的前一個(gè)元素交換位置，也就是 swap(arri, arrgtT)然后gt-,表示v

25、局部多了一個(gè)元素此時(shí)i不用動(dòng)，因?yàn)樗?指向的元素是交換過(guò)來(lái)的，這個(gè)元素還沒(méi)有遍歷到。當(dāng)gt與i重合的時(shí)候就表示便利 完畢了，那么此時(shí)我們只需要將1指向的元素v與It交換位置即可，就完成路三路算法。三、走迷宮以一個(gè)MXN的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程 序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通路的結(jié)論。（1）根據(jù)二維數(shù)組，輸出迷宮的圖形。（2）探索迷宮的四個(gè)方向：RIGHT為向右，DOWN向下，LEFT向左，UP向上，輸出從 入口到出口的行走路徑。例子：左上角（1, 1）為入口，右下角（8, 9）為出口。可使用回溯方法，即從入口出發(fā)，順著某一個(gè)

26、方向進(jìn)行探索，假設(shè)能走通，那么繼續(xù)往前進(jìn); 否那么沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可 能的通路都探索到而未能到達(dá)出口，那么所設(shè)定的迷宮沒(méi)有通路。四、隨機(jī)迷宮生成本質(zhì)上，地圖的障礙邏輯層是由一個(gè)二維數(shù)組保存的。障礙標(biāo)記在二維數(shù)組中的數(shù)據(jù) 值以0或者1表示，我們首先需要做的就是隨機(jī)產(chǎn)生這樣的二維數(shù)組。在生成中最有效 簡(jiǎn)單的方法就是循環(huán)這個(gè)二維數(shù)組，然后在每一個(gè)位置隨機(jī)地產(chǎn)生0或者1,但是這樣 生成圖形比擬簡(jiǎn)單不美觀，并且不一定保證圖中的任意兩點(diǎn)可以相連通。在隨機(jī)生成的 迷宮中要求任意兩點(diǎn)，都可以找到一條路徑相通，所以在圖論中可以認(rèn)為迷宮就是一個(gè) 連通圖。在程序

27、編譯中這個(gè)工程我定義為6x6的迷宮，先假設(shè)迷宮中所有的通路都是完全封閉 的，黃色的格子表示可以通過(guò)，黑色的格子表示墻壁或者障礙不能通過(guò)。隨機(jī)選擇一個(gè) 黃色的格子作為當(dāng)前正在訪問(wèn)的格子，同時(shí)把該格子放入一個(gè)已經(jīng)訪問(wèn)的列表中。循環(huán) 以下操作，直到所有的格子都被訪問(wèn)到。得到當(dāng)前訪問(wèn)格子的四周（上下左右）的格子， 在這些格子中隨機(jī)選擇一個(gè)沒(méi)有在訪問(wèn)列表中的格子，如果找到，那么把該格子和當(dāng)前訪 問(wèn)的格子中間的墻打通（置為0）,把該格子作為當(dāng)前訪問(wèn)的格子，并放入訪問(wèn)列表。如 果周圍所有的格子都已經(jīng)訪問(wèn)過(guò)，那么從已訪問(wèn)的列表中，隨機(jī)選取一個(gè)作為當(dāng)前訪問(wèn)的 格子。通過(guò)以上的迷宮生成算法，可以生成一個(gè)自然隨機(jī)的

28、迷宮。五、掃雷游戲在編譯過(guò)程中我將掃雷游戲定義為20 x20的矩陣，20顆雷，而掃雷的核心算法，有 Fisher - Yates隨機(jī)算法和Floofill算法。隨機(jī)雷區(qū)的生成，如何在雷區(qū)生成隨機(jī)的假設(shè)干的雷，運(yùn)用generateMines函數(shù)傳入 mineNumber參數(shù)，運(yùn)用的是private的方法，運(yùn)用一個(gè)for循環(huán)，做一個(gè)隨機(jī)橫坐標(biāo) 的值，再用Math, random乘以M形成縱坐標(biāo)的值，每次生成隨機(jī)坐標(biāo)后不應(yīng)該有雷，如 果沒(méi)有雷才能放心設(shè)置mines X Y為true,有雷再?gòu)男聢?zhí)行一遍，再設(shè)置break跳出 循環(huán)。洗牌算法Fisher_Yates的原理就是把從1到n的順序候選集隨機(jī)打

29、亂，做法就是第 1次從l-n的候選集合隨機(jī)選個(gè)數(shù)，拿出此數(shù)，并把它從候選集合剔除（候選集合1）。 第2次從的候選集合隨機(jī)選個(gè)數(shù)，拿出此數(shù)，并把它從候選集合剔除（候選集合 n-2）o第2次從l-n-2的候選集合隨機(jī)選個(gè)數(shù)，拿出此數(shù)，并把它從候選集合剔除（候 選集合n-3） o在為迷宮添加來(lái)交互后只將一個(gè)位置的雷區(qū)翻開(kāi)，這樣的程序是不能滿足掃雷的正確 游戲規(guī)那么的，如果左鍵點(diǎn)擊的位置為雷那這個(gè)掃雷游戲結(jié)束。如果點(diǎn)的位置不是雷，那 么要怎么構(gòu)建邏輯呢，將data封裝在新函數(shù)open中，此時(shí)添加一個(gè)函數(shù)，翻開(kāi)一片 雷區(qū)的算法就是門oodfill。FloodFill算法呢，最直接的一個(gè)應(yīng)用就是顏色填充，

30、 就是Windows繪畫(huà)本中那個(gè)小油漆桶的標(biāo)志，可以把一塊被圈起來(lái)的區(qū)域全部染色。深度優(yōu)先的方法遍歷，當(dāng)已經(jīng)遍歷過(guò)當(dāng)?shù)胤骄屯嘶厣厦妫龅竭吔鐣r(shí)尋找全體的遍歷 點(diǎn)此時(shí)考慮八個(gè)方向拓展，運(yùn)用一個(gè)for循環(huán)，在九宮格這個(gè)范圍內(nèi)的坐標(biāo)進(jìn)行遍歷， 假設(shè)之前已經(jīng)翻開(kāi)過(guò)的位置那么不用再翻開(kāi)，因此此時(shí)。pen坐標(biāo)應(yīng)該返回，這個(gè)位置不應(yīng) 該為雷，mines坐標(biāo)也應(yīng)該為false當(dāng)回到了 floodfill的起始點(diǎn)時(shí)整個(gè)floodfill的 算法遍歷完成，在掃雷游戲中，就是這樣深度優(yōu)先遍歷回朔。六、分形圖的繪制分形圖就是在這個(gè)圖案中存在自相似的地方，科赫曲線是一種外形像雪花的幾何曲 線，所以又稱為雪花曲線，它是分

31、形曲線中的一種，在分形圖的繪制這一小節(jié)中主要繪 制了一個(gè)雪花圖形。Sieepinski三角形的繪制中，我們其實(shí)是將三角形分成四局部，中間的三角形不做 繪制，其他的正向三角形進(jìn)行繪制，繪制三個(gè)正向的三角形時(shí)進(jìn)行遞歸的調(diào)用，對(duì)于每 個(gè)三角形又分成繪制，這個(gè)遞歸過(guò)程以此類推，形成這個(gè)遞歸結(jié)構(gòu)。為了繪制這個(gè)三角形，具體需要這樣繪制，具體代碼繪制從數(shù)據(jù)層開(kāi)始分析，在控制 層將窗口設(shè)成2的塞次方，在繪制層里根據(jù)傳進(jìn)的Ax和Ay坐標(biāo)繪制我們要計(jì)算的side 值來(lái)計(jì)算其他點(diǎn)的坐標(biāo)，第一種情況的第一種遞歸到底的情況假設(shè)sided時(shí)三角形不能 分割，只需要繪制一個(gè)像素點(diǎn)就行。另外一種遞歸到底的情況當(dāng)前的遞歸深度到

32、達(dá)了用 戶指定的深度，在之前的代碼種傳入一個(gè)path的接口調(diào)用fill參數(shù)在寫(xiě)出A B C三 個(gè)坐標(biāo)的代碼定義便可繪制出一個(gè)完整的三角形。而Koch雪花具體的遞歸過(guò)程需要當(dāng)前的線段除以3,在計(jì)算出X2 Y2的值后可以用 遞歸的方式來(lái)繪制從XI Y1到X2Y2對(duì)應(yīng)的直線，遞歸調(diào)用的方式，首先傳入繪圖環(huán)境 g,傳入運(yùn)動(dòng)坐標(biāo)xl yl ,這樣完成一段遞歸的繪制。在X3和Y3坐標(biāo)后遞歸的繪制從x2y2 x3y3這一段的長(zhǎng)度完成來(lái)第二段的遞歸，完 成X4 Y4可以遞歸的調(diào)用drawFracta求出X3 Y3的長(zhǎng)度。最后一段線段的坐標(biāo)也是只 用調(diào)用drawFracta,整個(gè)遞歸過(guò)程如上，關(guān)鍵是對(duì)幾個(gè)坐標(biāo)的計(jì)算。利用分形繪制樹(shù)，在初次遞歸繪制一顆直線在屏幕中央，在控制層中修改