设为首页收藏本站

LinuxSir.cn，穿越时空的Linuxsir!

 找回密码
 注册
搜索
热搜: shell linux mysql
LinuxSir.cn，穿越时空的Linuxsir!»论坛 › 编程开发讨论区 —— LinuxSir.cn › Linux 程序设计专题讨论 › 请教大家一种游戏的算法和代码，谢谢了 ...
12下一页
返回列表 发新帖
查看: 1118|回复: 13

请教大家一种游戏的算法和代码，谢谢了

[复制链接]
发表于 2005-5-19 18:07:24 | 显示全部楼层 |阅读模式
[php]
【游戏说明】
    有一种游戏，其规则如下：有一个３×３的方格，每个方格中只可画‘＋’符号或‘－’符号，表示该方格的值。图（ａ）定义了各方格的位置，表１为每个方格位置定义了与其相关联的位置集，各方格的初值如图（b）所示。游戏开始后，每次可选一个值为‘＋’的方格位置，然后根据表１将该位置所对应的每个相关联的位置上的符号重画成与其不同的符号，即将‘＋’重画成‘－’，将‘－’重画成‘＋’。重画操作可用所选的位置编号来描述。例如在图（ｂ）所示的情况下，选择位置４时，重画结果如图（c）所示。经过连续的若干次这样的操作后，当3×3方格呈现出图（ｄ）所示的图形时，表示获胜；当呈现出图（ｅ）所示的图形时，表示失败。
下列流程图旨在输出从初始状态出发直至获胜的重画操作（即所选的位置编号）序列。图中假定数组A［0..8］存放3×3方格的值，数组c［0..8］［1..5］存放表 １所示的各方格位置的相关联的位置集、数组d［0..8］存放各方格位置的相关联的位置个数，数组元素 S［1］~ S［k］存放各次重画操作所对应的位置编号，变量Ｎ存放3×3 方格中当前的‘＋’符号的个数。
              ０１２        ———    －＋－         ＋＋＋                 ——－
              ３４５        －＋－    ＋－＋         ＋－＋                 ―――
              ６７８        ———    一＋一         ＋＋＋                 ——一
             图（ａ）    图（b）     图（Ｃ）      图（ｄ）        图（ｅ）




方格位置      相关位置集
０                ０１３４
１                ０１２
２                １２４５
３                ０３６
４                １３４５７
５                ２５８
６                ３４６７
７                ６７８
８                ４５７８

[/php]

还有一个流程图，不知道怎么弄上来了，这好象某年的程序员考试题，我想了7.72小时还是没有什么头绪，请大家帮提示提示，谢谢了
回复

使用道具 举报

发表于 2005-5-20 12:48:14 | 显示全部楼层
查《数据结构》——图的遍历，或《人工智能导论》——盲目搜索或启发式搜索。
回复 支持 反对

使用道具 举报

锋锋
发表于 2005-5-20 19:35:08 | 显示全部楼层
有限状态机（FSM）
回复 支持 反对

使用道具 举报

 楼主| 发表于 2005-5-20 19:57:35 | 显示全部楼层

re

唉，等于没回，算了也等于我没问吧
回复 支持 反对

使用道具 举报

锋锋
发表于 2005-5-20 20:18:31 | 显示全部楼层

用邻接表表示的图来解决也很不错。

  1. using System;
  2. using System.Collections;
  3. using System.Text;

  5. namespace myWorkFlow.kernel
  6. {
  7.         //边表结点类
  8.         public class EdgeNode
  9.         {
  10.                 public int adjvex;
  11.                 public EdgeNode next;

  13.                 public EdgeNode()
  14.                 {
  15.                         next=null;
  16.                 }


  19.         }

  21.         ////顶点表结点类
  22.         public class VertexNode
  23.         {
  24.                 public object vertex;
  25.                 public EdgeNode firstedge;

  27.                 public VertexNode()
  28.                 {
  29.                         firstedge=null;
  30.                 }


  33.         }

  35.         //图的类型
  36.         public enum GraphType
  37.         {
  38.                 UnDiGraph = 0,//无向图       
  39.                 DiGraph = 1//有向图
  40.         }
  41.        
  42.         //图类
  43.         public class ALGraph
  44.         {
  45.                 public VertexNode[] AdjList;//顶点表

  47.                 public  int VertexNodeCount;//顶点数
  48.                 public  int BordeCount;//边数

  50.                 public GraphType theType;//图的类型
  51.         
  52.                 public ALGraph( int n,int e ,GraphType cuType)
  53.                 {
  54.                        
  55.                         VertexNodeCount = n;
  56.                         BordeCount= e;
  57.                         AdjList = new VertexNode[n];
  58.                         theType = cuType;
  59.                 }

  61.                
  62.         }

  64.         //图对象操作类
  65.         public class GraphOperation
  66.         {
  67.                 private bool[] visited;
  68.                 private StringBuilder sb ;

  70.                 public GraphOperation()
  71.                 {

  73.                 }

  75.                 /// <summary>
  76.                 /// 建全一个有向图对象
  77.                 /// (不是建立 ^_^)
  78.                 /// </summary>
  79.                 /// <param name="G"></param>
  80.                 public   void CreateALGraph(ALGraph G)
  81.                 {
  82.                         int i,j,k;

  84.                         EdgeNode s;

  86.                         for(int vnc = 0 ;vnc < G.VertexNodeCount; vnc++)
  87.                         {
  88.                                 VertexNode cuVN = new VertexNode();
  89.                                 Console.Write("请输入顶点的编号 : ");
  90.                                 cuVN.vertex = Console.ReadLine();
  91.                                 cuVN.firstedge = null;
  92.                                 G.AdjList[vnc]=cuVN;
  93.                         }

  95.                         for(k = 0; k < G.BordeCount; k++)
  96.                         {
  97.                                 Console.Write("请输入边开始顶点的序号 : ");

  99.                                 i = int.Parse(Console.ReadLine());

  101.                                 Console.Write("请输入边结束顶点的序号 : ");

  103.                                 j =int.Parse(Console.ReadLine());

  105.                                 s = new EdgeNode();

  107.                                 s.adjvex = j;

  109.                                 s.next = G.AdjList[i].firstedge;
  110.                                 //邻接表头插法
  111.                                 G.AdjList[i].firstedge = s;
  112.                                
  113.                                 //建立无向图
  114.                                 if(G.theType == GraphType.UnDiGraph)
  115.                                 {
  116.                                         s = new EdgeNode();

  118.                                         s.adjvex = i;
  119.                                         s.next = G.AdjList[j].firstedge;
  120.                                         G.AdjList[j].firstedge = s;
  121.                                 }
  122.                                
  123.                                
  124.                        
  125.                         }
  126.        
  127.                        
  128.                 }
  129.                
  130.                 /// <summary>
  131.                 /// 深度优先遍历以邻接表表示的图G.
  132.                 /// </summary>
  133.                 /// <param name="G"></param>
  134.                 public  void DFSTraverse(ALGraph G)
  135.                 {
  136.                         visited = new bool[G.VertexNodeCount];
  137.                         sb = new StringBuilder();
  138.                         for(int i = 0;i < G.VertexNodeCount;i++)
  139.                         {
  140.                                 visited[i] = false;

  142.                         }

  144.                         for(int i = 0;i < G.VertexNodeCount;i++)
  145.                         {
  146.                                 if(!visited[i])
  147.                                 {
  148.                                         DFS(G,i);
  149.                                 }

  151.                         }
  152.                         Console.Write("深度优先遍历以邻接表表示的图G 的结果:\n ");
  153.                        
  154.                         Console.Write(sb);


  157.                 }

  159.                 private void DFS(ALGraph G,int i)
  160.                 {
  161.                         EdgeNode p;
  162.                         sb.Append(G.AdjList[i].vertex.ToString()+"--->");
  163.                        
  164.                         visited[i] = true;
  165.                         p = G.AdjList[i].firstedge;
  166.                         while(p != null)
  167.                         {
  168.                                 if(!visited[p.adjvex])
  169.                                 {
  170.                                         DFS(G,p.adjvex);//递归
  171.                                 }
  172.                                 p = p.next;
  173.                         }

  175.                 }

  177.                 /// <summary>
  178.                 /// 广度优先遍历以邻接表表示的图G
  179.                 /// </summary>
  180.                 /// <param name="G"></param>
  181.                 public  void BFSTraverse(ALGraph G)
  182.                 {
  183.                         visited = new bool[G.VertexNodeCount];
  184.                         sb = new StringBuilder();
  185.                         for(int i = 0;i < G.VertexNodeCount;i++)
  186.                         {
  187.                                 visited[i] = false;

  189.                         }

  191.                         for(int i = 0;i < G.VertexNodeCount;i++)
  192.                         {
  193.                                 if(!visited[i])
  194.                                 {
  195.                                         BFS(G,i);
  196.                                 }

  198.                         }
  199.                         Console.Write("广度优先遍历以邻接表表示的图G 的结果:\n ");
  200.                        
  201.                         Console.Write(sb);


  204.                 }
  205.                 private void BFS(ALGraph G,int k)
  206.                 {
  207.                         int i;
  208.                         Queue Q;
  209.                         EdgeNode p;

  211.                         Q = new Queue();

  213.                         sb.Append(G.AdjList[k].vertex.ToString()+"--->");
  214.                        
  215.                         visited[k] = true;
  216.                         Q.Enqueue(k);

  218.                         while(Q.Count != 0)
  219.                         {
  220.                                 i = (int)Q.Dequeue();
  221.                                 p = G.AdjList[i].firstedge;

  223.                                 while(p != null)
  224.                                 {
  225.                                         if(!visited[p.adjvex])
  226.                                         {
  227.                                                 sb.Append(G.AdjList[p.adjvex].vertex.ToString()+"--->");
  228.                                                 visited[p.adjvex] = true;
  229.                                                 Q.Enqueue(p.adjvex);
  230.                                         }
  231.                                         p = p.next;
  232.                                 }
  233.                         }
  234.                 }

  236.                 /// <summary>
  237.                 /// 有向图无前驱的顶点优先之拓扑排序
  238.                 /// </summary>
  239.                 /// <param name="G"></param>
  240.                 public void NonPreFirstTopSort(ALGraph G)
  241.                 {
  242.                         if(G.theType == GraphType.UnDiGraph)
  243.                         {
  244.                                 Console.Write("对无向图进行拓扑排序是不对的!");
  245.                                 return;

  247.                         }
  248.                         StringBuilder SB = new StringBuilder() ;
  249.                         int [] indegree = new int[G.VertexNodeCount];


  252.                         Stack S;

  254.                         int i,j,count = 0;

  256.                         EdgeNode p;

  258.                         for(i = 0;i < G.VertexNodeCount;i++)
  259.                         {
  260.                                 indegree[i] = 0;
  261.                         }

  263.                         for(i = 0;i < G.VertexNodeCount;i++)
  264.                         {
  265.                                 for(p = G.AdjList[i].firstedge; p != null;p = p.next)
  266.                                 {
  267.                                         indegree[p.adjvex]++;
  268.                                 }

  270.                         }

  272.                         S = new Stack();

  274.                         for(i = 0;i < G.VertexNodeCount; i++)
  275.                         {
  276.                                 if(indegree[i] == 0)
  277.                                 {
  278.                                         S.Push(i);
  279.                                 }
  280.                         }

  282.                         while(S.Count != 0)
  283.                         {
  284.                                 i = (int)S.Pop();

  286.                                 SB.Append(G.AdjList[i].vertex.ToString()+"--->");

  288.                                 count++;

  290.                                 for(p = G.AdjList[i].firstedge; p != null; p = p.next)
  291.                                 {
  292.                                         j = p.adjvex;
  293.                                         indegree[j]--;
  294.                                         if(indegree[j] == 0)
  295.                                         {
  296.                                                 S.Push(j);
  297.                                         }

  299.                                 }
  300.                                

  302.                         }
  303.                         if(count < G.VertexNodeCount)
  304.                         {
  305.                                 Console.Write("图中有环,排序失败");
  306.                         }
  307.                         else
  308.                         {
  309.                                 Console.Write("拓扑排序结果如下 : \n"+SB);
  310.                        

  312.                         }



  316.                 }

  318.        
  319.         }

  321. }
复制代码


这个是我前段时间写的一个图数据结构实现（使用C#,你把它转的JAVA用吧）
回复 支持 反对

使用道具 举报

锋锋
发表于 2005-5-20 20:25:36 | 显示全部楼层
本来想用有向图来解决工作流中的前后动作依赖关系，想做一个.NET下的WFMS,
赫赫。。
回复 支持 反对

使用道具 举报

发表于 2005-5-21 00:16:38 | 显示全部楼层
Post by menglianjing
唉，等于没回，算了也等于我没问吧

那就再详细一点，一种盲目搜索算法：

首先，从初始状态开始，穷举所有可能的选择（这里没有考虑原题中的具体数据，假设0-8都可以选），可以得到 9 种新状态（如果有重复的要去掉，则结果少于 9 种），比较新状态是否目标状态。

然后，从每种新状态出发，穷举（假设0-8），又各得到 9 种新状态（如果与已经出现过的状态重复，要去掉，或称合并），比较新状态是否目标状态。

依次类推......形成一个图：状态就是图节点，如果从一个状态一步可以到达另一状态，这两个状态（节点）之间就有一条弧（有向的）。最终，会找到一个状态和目标状态一致。建立图的过程到此为止。

最后，在图上找到一条从初始状态到目标状态的路径，输出。如果用深度优先搜索并及时释放没用的路径也可以避免最后这一步。（完毕）


附：上面只是个粗略的过程，翻翻书还是有好处的。是你要解决问题，如果你都不想翻书，又怎能期望别人花时间帮你。
回复 支持 反对

使用道具 举报

锋锋
发表于 2005-5-21 04:21:54 | 显示全部楼层

用JAVA做了一个，见笑了。

[PHP]/*
* 创建日期 2005-5-20
*
* TODO 要更改此生成的文件的模板，请转至
* 窗口 － 首选项 － Java － 代码样式 － 代码模板
*/
package menglianjingGame;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
/**
* @author 锋锋
*
* TODO 要更改此生成的类型注释的模板，请转至
* 窗口 － 首选项 － Java － 代码样式 － 代码模板
*/
class VertexNode {
       
        public boolean vertex ;//顶点数据
        public int[]  correlativeList ;//关联顶点列表

        public VertexNode()
        {
               
        }
}
class ALGraph {
       
        public VertexNode[] AdjList ;//顶点表

        public  int VertexNodeCount;//顶点数
       
        public ALGraph( int n )
        {
                VertexNodeCount = n;
                AdjList = new VertexNode[n];
       
        }

}

public class PlayGame {
       
        private static ALGraph g = new ALGraph(9);
        //游戏当前状态
        private static boolean[] cuState = new boolean[9];
        //游戏胜利状态
        private static boolean[] winState = new boolean[]{true,
                                                                     true,
                                                                     true,
                                                                     true,
                                                                                                                 false,
                                                                                                                 true,
                                                                                                                 true,
                                                                                                                 true,
                                                                                                                 true };
        //游戏失败状态
        private static boolean[] failState = new boolean[]{false,
                                                          false,
                                                          false,
                                                          false,
                                                                      false,
                                                                      false,
                                                                      false,
                                                                      false,
                                                                      false };
       
       
        public static void main(String[] args) {
               
                initGameData();
               
                PrintGameState(cuState);
                System.out.println("游戏开始...\n 请选择\n 请输入一个0-8之间的整数！\n");
               
                while(true){
                       
                        int guess = -1;
                       
                        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
                        try
                        {
                           guess = Integer.parseInt(input.readLine());
                        }
                        catch (NumberFormatException e)
                        {
                           System.out.println("请输入一个0-8之间的整数！");
                           continue;
                       
                        }
                        catch (IOException e)
                        {
                           System.out.println("程序发生异常错误将被关闭！");
                           e.printStackTrace();
                        }

                        if ((guess > 8)||(guess == -1)||(!cuState[guess])){
                        System.out.println("输入无效！请重输..");
                        continue;
                        }

                       
                        GameAction(guess);
                        UpDataGameCuState();
                        PrintGameState(cuState);
                       
                        if(Arrays.equals(cuState,winState)){
                               
                                System.out.println("恭喜！你赢了！");
                               
                                break;
                               
                        }
                       
                        if(Arrays.equals(cuState,failState)){
                               
                                System.out.println("恭喜！你输了！");
                               
                                break;
                               
                        }
                       
                        System.out.println("游戏继续\n 请输入一个0-8之间的整数！\n");
                       
                }
       
        }
       
       
        private static void initGameData(){
               
                System.out.println("初始化游戏...");
               
                g.AdjList[0] = new VertexNode();
                g.AdjList[0].vertex =false;
        g.AdjList[0].correlativeList = new int[]{0,1,3,4};
        
        g.AdjList[1] = new VertexNode();
        g.AdjList[1].vertex =false;
        g.AdjList[1].correlativeList = new int[]{0,1,2};
        
        g.AdjList[2] = new VertexNode();
        g.AdjList[2].vertex =false;
        g.AdjList[2].correlativeList = new int[]{1,2,4,5};
        
        g.AdjList[3] = new VertexNode();
        g.AdjList[3].vertex =false;
        g.AdjList[3].correlativeList = new int[]{0,3,6};
        
        g.AdjList[4] = new VertexNode();
        g.AdjList[4].vertex =true;
        g.AdjList[4].correlativeList = new int[]{1,3,4,5,7};
        
        g.AdjList[5] = new VertexNode();
        g.AdjList[5].vertex =false;
        g.AdjList[5].correlativeList = new int[]{2,5,8};
        
        g.AdjList[6] = new VertexNode();
        g.AdjList[6].vertex =false;
        g.AdjList[6].correlativeList = new int[]{3,4,6,7};
        
        g.AdjList[7] = new VertexNode();
        g.AdjList[7].vertex =false;
        g.AdjList[7].correlativeList = new int[]{6,7,8};
        
        g.AdjList[8] = new VertexNode();
        g.AdjList[8].vertex =false;
        g.AdjList[8].correlativeList = new int[]{4,5,7,8};
        
        UpDataGameCuState ();
        
        System.out.println("初始化游戏完成!");

        }
       
//根据用户输入（动作），改变游戏当前状态.
        private static void  GameAction(int choose){
               
                for(int i = 0;i < g.AdjList[choose].correlativeList.length; i++){
                       
                g.AdjList[g.AdjList[choose].correlativeList].vertex =
                        !g.AdjList[g.AdjList[choose].correlativeList].vertex;
               
                }
               
                UpDataGameCuState ();//更新游戏当前状态
               
        }
//更新游戏当前状态
        private static void UpDataGameCuState (){
               
                for(int i = 0;i < g.VertexNodeCount;i++){
                       
                        cuState = g.AdjList.vertex;       
                       
                }
               
        }
       
//打印游戏当前状态(其中布尔值和字符转换）       
        private static void PrintGameState(boolean[] custate){
               
                for( int c = 0 ;c < custate.length;c+=3)
                {
                        for(int i =0 ;i < 3;i++){
                               
                                if(custate[c+i]){
                                        System.out.print("+ ");       
                                }else{
                                        System.out.print("- ");       
                                }
                        }
                       
                        System.out.print("\n");
                       
                }
        }
       
       
}

[/PHP]



控制台下测试结果如下：

[PHP]初始化游戏...
初始化游戏完成!
- - -
- + -
- - -
游戏开始...
请选择
请输入一个0-8之间的整数！

4
- + -
+ - +
- + -
游戏继续
请输入一个0-8之间的整数！

1
+ - +
+ - +
- + -
游戏继续
请输入一个0-8之间的整数！

2
+ + -
+ + -
- + -
游戏继续
请输入一个0-8之间的整数！

3
- + -
- + -
+ + -
游戏继续
请输入一个0-8之间的整数！

4
- - -
+ - +
+ - -
游戏继续
请输入一个0-8之间的整数！

5
- - +
+ - -
+ - +
游戏继续
请输入一个0-8之间的整数！

6
- - +
- + -
- + +
游戏继续
请输入一个0-8之间的整数！

7
- - +
- + -
+ - -
游戏继续
请输入一个0-8之间的整数！

8
- - +
- - +
+ + +
游戏继续
请输入一个0-8之间的整数！

5
- - -
- - -
+ + -
游戏继续
请输入一个0-8之间的整数！

1
+ + +
- - -
+ + -
游戏继续
请输入一个0-8之间的整数！

2
+ - -
- + +
+ + -
游戏继续
请输入一个0-8之间的整数！

3
- - -
+ + +
- + -
游戏继续
请输入一个0-8之间的整数！
[/PHP]


回复 支持 反对

使用道具 举报

Tetris
发表于 2005-5-21 04:35:29 | 显示全部楼层
我faint，楼主要的是让机器自动的找到一个求解方法，不是让用户输入123然后显示结果。
回复 支持 反对

使用道具 举报

锋锋
发表于 2005-5-21 04:39:15 | 显示全部楼层
这样啊，那就很有难度了，真的要搞人工智能啊？！

我还以为是做个游戏来玩的，哈哈。。
回复 支持 反对

使用道具 举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

快速回复 返回顶部 返回列表