数据结构与算法-看得见的算法 课程设计报告

1、信息工程系综合课程设计报告题 目:班 级:学 号:姓 名:指导老师:数据结构与算法.看得见的算法软件与信息服务四班19023038成林诗睿四、附件核心代码，图一：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 一、工程报告1 HYPERLINK l bookmark18 o Current Document 二、综合课程设计心得6 HYPERLINK l bookmark20 o Current Document 三、教师评价8 HYPERLINK l bookmark2 o Current Document 四、附件918Mecbon Son19Illil2021一、工程报告成果描述编译环境为：IDEA,用java语言，javab8的jdk配置环境诠释了“数据结构与算

19、 法7个个经典游戏诠释算法”的小游戏，本次创作成功共7个，分别为“ “概率模拟算 法”、“排序算法可视化”、“分形绘制”“扫雷”、通过“推箱子”、“走迷宫”以 及“随机迷宫的生成”，接下来我将逐个分析工程成功以及所运用技术。一、概率模拟算法概率模拟算法又称蒙特卡洛算法，是一个非常有意思的分钱模拟问题，通过 AlgoFrame, java中在render中设置数据，在AlgoVisual izer. java控制层中定义变 量，动画逻辑使用run方法，先建立MonleCarloPiDala对象data,然后随机模拟点， 使用data的方法addPoint加入每个点。每一百次计算兀值。点的坐标为（

20、01随机值）* 面板的宽高，frame的render方法不断调用PaintComonent方法刷新控件。在这一小节的编译中主要使用洛概率模拟的方式实现“三门问题”三门问题，亦称为 蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论三门问题，是一个源自博弈论的数学游戏问 题，大致出自美国的电视游戏节目。当参赛者选定了一扇门，但未去开启它的时候，节 目主持人开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不 要换另一扇仍然关上的门。问题是：换另一扇门会否增加参赛者赢得汽车的机率。换门 的话中奖率为2/3,不换中奖率为1/3程序编译模拟三门问题具体表现为运用一个run 函数中的for循环，在循

21、环的过程中想要到达换门或不换门的结果循环在run函数中需 传入一个叫changeDoor ”的参数，在for循环中设置的play值通过changeDoor来返 回中奖与否，假设中奖的话设立变量wins=0,假设中奖wins=+,否那么不动，我们设置三个 值代表三扇门，同时玩家选择的门也是随机，假设此时plaer函数指向的门后有奖品，用 户坚持不换门那么此时就必得奖品，这个游戏中的胜率等于影响的次数除以我们总共玩 的次数从而得出获奖概率，因此我们可以通过player策略，观察玩家是否换门，来完 成模拟三门问题的play过程。二、排序算法可视化首先插入排序算法就是将我们需要排序的数插入到前面我们以

22、及处理的数中，使得我 们处理的元素都是有序的。在数据层中构造一个numbers数组中有相应的构造函数，应 用swap这样的一个操作来交换数组通融量，元素的位置，为了让可视化过程更加清晰 在设置一些变量用于指示绘制不同的数据，设置。rderedindex变量，期望让这个前闭 后开的数组是有序的，为当前正在处理的元素设置一个叫currentindex的索引。绘制的过程，具体绘制过程对于ordcrcdindex, currentindex设置颜色将处在有序 和乱序的数组进行颜色的设置，另外如果当前的数据处于currentindex时，为它单独 设置一个特殊颜色，上述完成插入排序过程具体绘制。为了实现

23、“近乎有序：数组，在你内部添加一个没矩形变量 Type”，设置两种可能 参数，分别为default为默认情况，以及NearlyOrdered为近乎有序，为用户传入新的 变量，而随机抽取元素设置swap time决定随机抽取的次数。通过这样的过程形成一个近乎有 序的数据。另外为了解决数组中存在大量重复的元素使得在按基准值分成两局部时，重复元素都 集中分到其中一局部的问题(如果两局部元素数量相差太大，快速排序算法是会退化为 0(r2)的)，可以使用双路快速排序算法。双路快速排序算法的基本思路：设置一个变量i从最左边开始遍历直到找到第一 个比基准值大的数时停止，再设置个变量j从最右边开始遍历，直到找

24、到第一个比 基准值小的数时停止，这时候交换i与j所表示的元素数值。三路排序算法使用了 3个索引值来表示3个不同的位置，使用it索引来表示v局部 和二v局部的分界处使用i索引表示遍历的位置，使用gt索引来表示:v局部和v局部 的分界处。如果当前i指向的元素二v,那直接就将此元素归为7局部，i+即可，如果 当前i指向的元素v,将此元素与二v局部的第一个元素交换位置，也就是swap(arri, arrlt+U),之后将lt+,i+即可，此时局部就多了一个元素，如果当前i指向的元素v,那么将此元素与v局部的第一个元 素的前一个元素交换位置，也就是 swap(arri, arrgtT)然后gt-,表示v

25、局部多了一个元素此时i不用动，因为他 指向的元素是交换过来的，这个元素还没有遍历到。当gt与i重合的时候就表示便利 完毕了，那么此时我们只需要将1指向的元素v与It交换位置即可，就完成路三路算法。三、走迷宫以一个MXN的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程 序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。（1）根据二维数组，输出迷宫的图形。（2）探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，输出从 入口到出口的行走路径。例子：左上角（1, 1）为入口，右下角（8, 9）为出口。可使用回溯方法，即从入口出发，顺着某一个

26、方向进行探索，假设能走通，那么继续往前进; 否那么沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可 能的通路都探索到而未能到达出口，那么所设定的迷宫没有通路。四、随机迷宫生成本质上，地图的障碍逻辑层是由一个二维数组保存的。障碍标记在二维数组中的数据 值以0或者1表示，我们首先需要做的就是随机产生这样的二维数组。在生成中最有效 简单的方法就是循环这个二维数组，然后在每一个位置随机地产生0或者1,但是这样 生成图形比拟简单不美观，并且不一定保证图中的任意两点可以相连通。在随机生成的 迷宫中要求任意两点，都可以找到一条路径相通，所以在图论中可以认为迷宫就是一个 连通图。在程序

27、编译中这个工程我定义为6x6的迷宫，先假设迷宫中所有的通路都是完全封闭 的，黄色的格子表示可以通过，黑色的格子表示墙壁或者障碍不能通过。随机选择一个 黄色的格子作为当前正在访问的格子，同时把该格子放入一个已经访问的列表中。循环 以下操作，直到所有的格子都被访问到。得到当前访问格子的四周（上下左右）的格子， 在这些格子中随机选择一个没有在访问列表中的格子，如果找到，那么把该格子和当前访 问的格子中间的墙打通（置为0）,把该格子作为当前访问的格子，并放入访问列表。如 果周围所有的格子都已经访问过，那么从已访问的列表中，随机选取一个作为当前访问的 格子。通过以上的迷宫生成算法，可以生成一个自然随机的

28、迷宫。五、扫雷游戏在编译过程中我将扫雷游戏定义为20 x20的矩阵，20颗雷，而扫雷的核心算法，有 Fisher - Yates随机算法和Floofill算法。随机雷区的生成，如何在雷区生成随机的假设干的雷，运用generateMines函数传入 mineNumber参数，运用的是private的方法，运用一个for循环，做一个随机横坐标 的值，再用Math, random乘以M形成纵坐标的值，每次生成随机坐标后不应该有雷，如 果没有雷才能放心设置mines X Y为true,有雷再从新执行一遍，再设置break跳出 循环。洗牌算法Fisher_Yates的原理就是把从1到n的顺序候选集随机打

29、乱，做法就是第 1次从l-n的候选集合随机选个数，拿出此数，并把它从候选集合剔除（候选集合1）。 第2次从的候选集合随机选个数，拿出此数，并把它从候选集合剔除（候选集合 n-2）o第2次从l-n-2的候选集合随机选个数，拿出此数，并把它从候选集合剔除（候 选集合n-3） o在为迷宫添加来交互后只将一个位置的雷区翻开，这样的程序是不能满足扫雷的正确 游戏规那么的，如果左键点击的位置为雷那这个扫雷游戏结束。如果点的位置不是雷，那 么要怎么构建逻辑呢，将data封装在新函数open中，此时添加一个函数，翻开一片 雷区的算法就是门oodfill。FloodFill算法呢，最直接的一个应用就是颜色填充，

30、 就是Windows绘画本中那个小油漆桶的标志，可以把一块被圈起来的区域全部染色。深度优先的方法遍历，当已经遍历过当地方就退回上面，遇到边界时寻找全体的遍历 点此时考虑八个方向拓展，运用一个for循环，在九宫格这个范围内的坐标进行遍历， 假设之前已经翻开过的位置那么不用再翻开，因此此时。pen坐标应该返回，这个位置不应 该为雷，mines坐标也应该为false当回到了 floodfill的起始点时整个floodfill的 算法遍历完成，在扫雷游戏中，就是这样深度优先遍历回朔。六、分形图的绘制分形图就是在这个图案中存在自相似的地方，科赫曲线是一种外形像雪花的几何曲 线，所以又称为雪花曲线，它是分

31、形曲线中的一种，在分形图的绘制这一小节中主要绘 制了一个雪花图形。Sieepinski三角形的绘制中，我们其实是将三角形分成四局部，中间的三角形不做 绘制，其他的正向三角形进行绘制，绘制三个正向的三角形时进行递归的调用，对于每 个三角形又分成绘制，这个递归过程以此类推，形成这个递归结构。为了绘制这个三角形，具体需要这样绘制，具体代码绘制从数据层开始分析，在控制 层将窗口设成2的塞次方，在绘制层里根据传进的Ax和Ay坐标绘制我们要计算的side 值来计算其他点的坐标，第一种情况的第一种递归到底的情况假设sided时三角形不能 分割，只需要绘制一个像素点就行。另外一种递归到底的情况当前的递归深度到

32、达了用 户指定的深度，在之前的代码种传入一个path的接口调用fill参数在写出A B C三 个坐标的代码定义便可绘制出一个完整的三角形。而Koch雪花具体的递归过程需要当前的线段除以3,在计算出X2 Y2的值后可以用 递归的方式来绘制从XI Y1到X2Y2对应的直线，递归调用的方式，首先传入绘图环境 g,传入运动坐标xl yl ,这样完成一段递归的绘制。在X3和Y3坐标后递归的绘制从x2y2 x3y3这一段的长度完成来第二段的递归，完 成X4 Y4可以递归的调用drawFracta求出X3 Y3的长度。最后一段线段的坐标也是只 用调用drawFracta,整个递归过程如上，关键是对几个坐标的计算。利用分形绘制树，在初次递归绘制一颗直线在屏幕中央，在控制层中修改