注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

“青蛙跳跳”游戏程序解决代码  

2012-01-28 16:42:53|  分类: 算法思想 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、“青蛙跳跳”
这是一个简单的flash游戏,就是有三对青蛙面对面蹲着,每个一个坑,但是中间有一个空位,现在要它们换位。所有最左边的移动到最右边,最右边的移动到最左边。这个游戏本身是比较简单的,就是一个穷举的过程,但是由于我试了几次没有通过,所以感觉比较失败,这里的失败只能从其它地方弥补,那就写个简单的程序来穷举一下,好在也不算是太复杂,就把代码在这里列一下。
我这里关于这个游戏规则的描述肯定是让人搞不懂的(如果你没有玩过这个游戏的话),大家可以在网络上搜索一下“青蛙跳跳”来看一下这个游戏,自己玩一下就知道是啥意思了。
“青蛙跳跳”游戏程序解决代码 - Tsecer - Tsecer的回音岛
 
二、代码
[root@Harry jmpfrog]# cat jmpfrog.c
/*
*  Just a funny resolution for three pair of frogs jump around
*  Author: tsecer@163.com
*  Date  :2012.01.28
*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

enum FROG {
FROG_GREEN = 1,
FROG_NONE  = 0,
FROG_PINK = -1,};

struct FootPrint {
int pos;
int step;
} FootPrint[100];
/*
*判断一次跳转是否合法,主要考虑跳转目标槽位必须为空,并且不能越界。
*/
static inline int ValidJmp(enum FROG Road[],int slots,int pos,int step)
{
    return Road[pos] != FROG_NONE &&pos+ Road[pos]*step >= 0 && pos + Road[pos]*step < slots && FROG_NONE == Road[pos+Road[pos]*step];
}
/*
*判断该状态是否为一个合法的终结状态
*/
int ValidCombine(enum FROG Road[],int slots)
{
int pos = 0;
for(;pos < slots/2;pos++)
    if(Road[pos] != FROG_PINK)
    return 0;
for(pos++;pos<slots;pos++)
    if(Road[pos] != FROG_GREEN)
    return 0;
return 1;
}
/*
*这里为了让结果更加醒目,对不同的状态设置不同的颜色。由于唯一的一个空槽NONE最为重要,所以显示为红色。
*/
#define ESCBEGIN  "\033["
#define ESCEND     "m"

#define GREEN     ESCBEGIN  "01;32" ESCEND
#define PINK      ESCBEGIN  "01;36" ESCEND
#define RED       ESCBEGIN  "37;41" ESCEND
#define RESTORE   ESCBEGIN  "0"     ESCEND

static const char *FrogName[] =
{
PINK"PINK"RESTORE ,
RED"NONE"RESTORE,
GREEN"GREEN"RESTORE,
};
/*
* 显示当前系统中的所有操作状态
*/
void DumpRoad(enum FROG Road[],int slots)
{
    int i = 0;
    for(;i<slots;i++)
    printf("%s\t",FrogName[Road[i]+1]);
    printf("\n");
   
}
enum FROG const  *initState ;
/*
*这里打印出一个从开始状态到达结束状态的一个变化过程
*/
void DumpFootPrint(int depth,int slots)
{
enum FROG * mycopy = malloc(sizeof(enum FROG)*slots);
memcpy((void*)mycopy,(void*)initState,sizeof(enum FROG)*slots);
int i = 0;
printf("***************************************\nInit:\t");
DumpRoad(mycopy,slots);
for(;i<= depth;i++)
{
mycopy[FootPrint[i].pos + FootPrint[i].step] = mycopy[FootPrint[i].pos];
mycopy[FootPrint[i].pos] = FROG_NONE;
printf("%d:\t",i+1);
DumpRoad(mycopy,slots);
}
printf("***************************************\n\n");
free(mycopy);
}
/*
*递归程序主体
*/
int JmpOneFrog(enum FROG Road[],int slots,int depth)
{
    int pos = 0 , step = 1;
    depth++;
    for(; pos < slots;pos++)
        for(step = 1 ;step < 3;step++)
        {
            if (ValidJmp(Road,slots,pos,step))
            {
                enum FROG OrgFrog = Road[pos];
                Road[pos+Road[pos]*step] = Road[pos];
                Road[pos] = FROG_NONE;
                FootPrint[depth].pos = pos;
                FootPrint[depth].step = step*OrgFrog;
                if(ValidCombine(Road,slots))
                DumpFootPrint(depth,slots);
                JmpOneFrog(Road,slots,depth);
                Road[pos] =OrgFrog;
                Road[pos+Road[pos]*step] = FROG_NONE;
                FootPrint[depth].pos = -1;
                FootPrint[depth].step = -1;
               
            }
        }
}
int main()
{
enum FROG const  initial[] = {FROG_GREEN,FROG_GREEN,FROG_GREEN,FROG_NONE,FROG_PINK,FROG_PINK,FROG_PINK,};
initState = initial;
enum FROG copy[sizeof(initial)/sizeof(initial[0])];/*保留原始备份,用来打印路径*/
memcpy(copy,initial,sizeof(initial));
JmpOneFrog(copy,sizeof(copy)/sizeof(copy[0]),-1);
return 0;
}
[root@Harry jmpfrog]# cat Makefile
default:
    gcc jmpfrog.c -o jmpfrog.exe -g
    ./jmpfrog.exe
[root@Harry jmpfrog]# make
gcc jmpfrog.c -o jmpfrog.exe -g
./jmpfrog.exe
***************************************
Init:    GREEN    GREEN    GREEN    NONE    PINK    PINK    PINK   
1:    GREEN    GREEN    NONE    GREEN    PINK    PINK    PINK   
2:    GREEN    GREEN    PINK    GREEN    NONE    PINK    PINK   
3:    GREEN    GREEN    PINK    GREEN    PINK    NONE    PINK   
4:    GREEN    GREEN    PINK    NONE    PINK    GREEN    PINK   
5:    GREEN    NONE    PINK    GREEN    PINK    GREEN    PINK   
6:    NONE    GREEN    PINK    GREEN    PINK    GREEN    PINK   
7:    PINK    GREEN    NONE    GREEN    PINK    GREEN    PINK   
8:    PINK    GREEN    PINK    GREEN    NONE    GREEN    PINK   
9:    PINK    GREEN    PINK    GREEN    PINK    GREEN    NONE   
10:    PINK    GREEN    PINK    GREEN    PINK    NONE    GREEN   
11:    PINK    GREEN    PINK    NONE    PINK    GREEN    GREEN   
12:    PINK    NONE    PINK    GREEN    PINK    GREEN    GREEN   
13:    PINK    PINK    NONE    GREEN    PINK    GREEN    GREEN   
14:    PINK    PINK    PINK    GREEN    NONE    GREEN    GREEN   
15:    PINK    PINK    PINK    NONE    GREEN    GREEN    GREEN   
***************************************

***************************************
Init:    GREEN    GREEN    GREEN    NONE    PINK    PINK    PINK   
1:    GREEN    GREEN    GREEN    PINK    NONE    PINK    PINK   
2:    GREEN    GREEN    NONE    PINK    GREEN    PINK    PINK   
3:    GREEN    NONE    GREEN    PINK    GREEN    PINK    PINK   
4:    GREEN    PINK    GREEN    NONE    GREEN    PINK    PINK   
5:    GREEN    PINK    GREEN    PINK    GREEN    NONE    PINK   
6:    GREEN    PINK    GREEN    PINK    GREEN    PINK    NONE   
7:    GREEN    PINK    GREEN    PINK    NONE    PINK    GREEN   
8:    GREEN    PINK    NONE    PINK    GREEN    PINK    GREEN   
9:    NONE    PINK    GREEN    PINK    GREEN    PINK    GREEN   
10:    PINK    NONE    GREEN    PINK    GREEN    PINK    GREEN   
11:    PINK    PINK    GREEN    NONE    GREEN    PINK    GREEN   
12:    PINK    PINK    GREEN    PINK    GREEN    NONE    GREEN   
13:    PINK    PINK    GREEN    PINK    NONE    GREEN    GREEN   
14:    PINK    PINK    NONE    PINK    GREEN    GREEN    GREEN   
15:    PINK    PINK    PINK    NONE    GREEN    GREEN    GREEN   
***************************************

[root@Harry jmpfrog]#
下面是一个带颜色的截图:
“青蛙跳跳”游戏程序解决代码 - Tsecer - Tsecer的回音岛
 
三、一个类似的“分酒问题”
记得在大学课程设计的时候,做过一个“分酒问题”的程序搜索程序,当时使用的是Dijstra算法进行了正面搜索而没有进行递归,所以当时找到的也一定是一个最短路径(如果有多种解决方法的话)。对于这个问题,虽然看起来比较简单,但是如果使用Dijstra算法搜索的话,其中的状态将会非常多。这里共有7个槽位,每个操作可以有三个状态,所以总共有3^7种组合,如果使用连通图来表示它们的状态关系,那么这个图的大小为(3^7)^2,当然使用每个bit表示一位可能会节省比较都的空间,但是代码的维护性将会降低,所以对于这个问题,使用递归应该是一个比较折中的方法。

问题描述为
已知有三个容量分别为3千克、5千克和8千克的并且是没有刻度的酒瓶,3千克和5千克的瓶子均装满了酒,而8千克的瓶子为空。现要求仅用这三个酒瓶将这些酒均分为两个4千克并分别装入5千克和8千克的瓶子中。

这个问题在我毕业时找工作的一家公司的笔试题中出现过(最终也进入了这家公司),当时是手动算出来了,但是作为一个计算机专业的学生,还是最好用程序实现一下更有意思,锻炼一下编程序的能力。
  评论这张
 
阅读(1643)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017