| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3866 人关注过本帖
标题:算法倒水问题,求教高手。
只看楼主 加入收藏
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:10 
我晕,那一页的跟帖里就解释了你的编译器不能编译的原因和解决办法

我最近比较忙,不过把你的代码贴上来肯定没坏处

重剑无锋,大巧不工
2013-03-15 22:50
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 11楼 beyondyf
#include <stdio.h>
typedef struct Node{
    int have_v[3];//状态的水量
    int size_v[3];//对应瓶子的容量
    int step;
    int father;
}Node;
typedef struct dumpWaterTable{
    int v[2];
}dumpWaterTable;//倒水表单元结构
dumpWaterTable table_dump_methods[6] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};//倒水方法表
Node queue[100000];//存储各个状态量的队列
int front,rear;
void Init(int &a, int &b, int &c, Node & root,bool flag);//初始化搜索根结点
bool bfs(Node & root,int x);//宽度优先搜素
void Print_L(int index,int now);//按照找到的结点,递归打印倒水过程
bool isequal(Node &a,int &b);//判断是否出现合法的且有水杯的水等于b
bool isvalid(int i,Node v,Node & dumped);//判断倒水表中第i中方法是否合适
int min(int a, int b);//返回最小值
//void testout(Node & v);
int a,b,c;
int main(){
    int x;
    while(scanf("%d%d%d%d",&a,&b,&c,&x)!=EOF){//输入各个瓶子的容量,已经目标容量的为x
        Node root;//根结点
        Init(a,b,c,root,true);//根结点初始化
        front = rear =  0;
        bfs(root,x);//开始搜索
    }
    return 0;
}

void Print_L(int index,int now){//递归打印
    int key = queue[index].step;
    int fa = queue[index].father;
    if(key != 0){
        Print_L(fa,now + 1);
    }
    if(index == 0)
        printf("至少需要%d步\n",now);
    printf("(%d,%d,%d)\n",queue[key].have_v[0],queue[key].have_v[1],queue[key].have_v[2]);
}

void Init(int &a, int &b, int &c, Node & root,bool flag){
    if(flag){
        root.have_v[0] = a;
        root.have_v[1] = 0;
        root.have_v[2] = 0;
        root.size_v[0] = a;
        root.size_v[1] = b;
        root.size_v[2] = c;
        root.step = root.father= 0;
    }
    else{
        root.size_v[0] = a;
        root.size_v[1] = b;
        root.size_v[2] = c;
    }
}

bool bfs(Node & root,int x){
    queue[rear++] = root;//根结点入队列
    int step = 0;
    bool Have_Find = false;//没发现目标结点
    while(front < rear){
        Node v = queue[front++];//出队列  
        if(isequal(v,x)){
            Have_Find = true;
            break;
        }
        for(int i = 0; i < 6; i++){//尝试各种倒水法,合法就拓展入队列
            Node dumped;
            Init(a,b,c,dumped,false);
            if(isvalid(i,v,dumped)){
                dumped.step = ++step;
                dumped.father = v.step;
                queue[rear++] = dumped;
            }
        }
    }
    if(Have_Find){
        Print_L(front - 1,0);
    }
    else{
        printf("亲,无解\n");
    }
}
bool isequal(Node &a,int & b){
    for(int i =0; i < 3 ;i++){
        if(a.have_v[i] == b)
            return true;
    }
    return false;
}
bool isvalid(int i,Node v,Node & dumped){
    dumpWaterTable m = table_dump_methods[i];//取得倒水表第i中方式,m为方式变量,m.v[0]倒到m.v[1]
    if(v.have_v[m.v[0]] != 0 && v.have_v[m.v[1]] != v.size_v[m.v[1]]){//可倒水
        int d = min(v.have_v[m.v[0]],v.size_v[m.v[1]] - v.have_v[m.v[1]]);
        dumped.have_v[m.v[0]] = v.have_v[m.v[0]] - d;
        dumped.have_v[m.v[1]] = v.have_v[m.v[1]] + d;
        int j;
        for(j = 0; j < 3; j++){//搜索没有参与倒水的瓶子
            if(j != m.v[0] && j != m.v[1])
                break;
        }
        dumped.have_v[j] = v.have_v[j];//保存没参与倒水的瓶子
        return true;//返回合法该方法合法,并且已经执行。
    }
    return false;
}
int min(int a,int b){
    return a < b ? a : b;
}

//void testout(Node &v){
//    printf("testing(%d,%d,%d)\n",v.have_v[0],v.have_v[1],v.have_v[2]);
//}

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-15 23:21
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 11楼 beyondyf
程序代码:
#include <stdio.h>
typedef struct Node{
    int have_v[3];//状态的水量 
    int size_v[3];//对应瓶子的容量 
    int step;
    int father;
}Node;
typedef struct dumpWaterTable{
    int v[2]; 
}dumpWaterTable;//倒水表单元结构 
dumpWaterTable table_dump_methods[6] = {{0,1},{0,2},{1,0},{1,2},{2,0},{2,1}};//倒水方法表 
Node queue[100000];//存储各个状态量的队列 
int front,rear;
void Init(int &a, int &b, int &c, Node & root,bool flag);//初始化搜索根结点 
bool bfs(Node & root,int x);//宽度优先搜素 
void Print_L(int index,int now);//按照找到的结点,递归打印倒水过程 
bool isequal(Node &a,int &b);//判断是否出现合法的且有水杯的水等于b 
bool isvalid(int i,Node v,Node & dumped);//判断倒水表中第i中方法是否合适 
int min(int a, int b);//返回最小值 
//void testout(Node & v);
int a,b,c;
int main(){ 
    int x;
    while(scanf("%d%d%d%d",&a,&b,&c,&x)!=EOF){//输入各个瓶子的容量,已经目标容量的为x 
        Node root;//根结点 
        Init(a,b,c,root,true);//根结点初始化 
        front = rear =  0;
        bfs(root,x);//开始搜索 
    }
    return 0;
}

void Print_L(int index,int now){//递归打印 
    int key = queue[index].step;
    int fa = queue[index].father;
    if(key != 0){
        Print_L(fa,now + 1);
    }
    if(index == 0)
        printf("至少需要%d步\n",now);
    printf("(%d,%d,%d)\n",queue[key].have_v[0],queue[key].have_v[1],queue[key].have_v[2]);
}

void Init(int &a, int &b, int &c, Node & root,bool flag){
    if(flag){
        root.have_v[0] = a;
        root.have_v[1] = 0;
        root.have_v[2] = 0;
        root.size_v[0] = a; 
        root.size_v[1] = b;
        root.size_v[2] = c;
        root.step = root.father= 0;
    }
    else{
        root.size_v[0] = a;
        root.size_v[1] = b;
        root.size_v[2] = c;
    }
}

bool bfs(Node & root,int x){
    queue[rear++] = root;//根结点入队列 
    int step = 0;
    bool Have_Find = false;//没发现目标结点 
    while(front < rear){
        Node v = queue[front++];//出队列  
        if(isequal(v,x)){
            Have_Find = true;
            break;
        }
        for(int i = 0; i < 6; i++){//尝试各种倒水法,合法就拓展入队列 
            Node dumped;
            Init(a,b,c,dumped,false);
            if(isvalid(i,v,dumped)){
                dumped.step = ++step;
                dumped.father = v.step; 
                queue[rear++] = dumped;
            }
        }
    }
    if(Have_Find){
        Print_L(front - 1,0);
    }
    else{
        printf("亲,无解\n");
    }
}
bool isequal(Node &a,int & b){
    for(int i =0; i < 3 ;i++){
        if(a.have_v[i] == b)
            return true;
    }
    return false;
}
bool isvalid(int i,Node v,Node & dumped){
    dumpWaterTable m = table_dump_methods[i];//取得倒水表第i中方式,m为方式变量,m.v[0]倒到m.v[1] 
    if(v.have_v[m.v[0]] != 0 && v.have_v[m.v[1]] != v.size_v[m.v[1]]){//可倒水 
        int d = min(v.have_v[m.v[0]],v.size_v[m.v[1]] - v.have_v[m.v[1]]); 
        dumped.have_v[m.v[0]] = v.have_v[m.v[0]] - d;
        dumped.have_v[m.v[1]] = v.have_v[m.v[1]] + d;
        int j;
        for(j = 0; j < 3; j++){//搜索没有参与倒水的瓶子 
            if(j != m.v[0] && j != m.v[1])
                break;
        }
        dumped.have_v[j] = v.have_v[j];//保存没参与倒水的瓶子 
        return true;//返回合法该方法合法,并且已经执行。 
    }
    return false;
}
int min(int a,int b){
    return a < b ? a : b;
}

//void testout(Node &v){
//    printf("testing(%d,%d,%d)\n",v.have_v[0],v.have_v[1],v.have_v[2]);
//}

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-15 23:22
fourleaves
Rank: 2
等 级:论坛游民
帖 子:194
专家分:99
注 册:2010-5-8
收藏
得分:0 
回复 11楼 beyondyf
对啦,顺便问一下B版,8数码问题,模型是图的最短路~~~,这个是这么看的~~~,小菜不懂,B版能否提醒一二。。。

再复杂的问题也基于最简单的原理。耐心,耐心!丰富自己!等待时机!
2013-03-15 23:34
邓士林
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:淮河河畔
等 级:贵宾
威 望:61
帖 子:2392
专家分:13384
注 册:2013-3-3
收藏
得分:0 
版主好厉害啊。赞一个

Maybe
2013-03-15 23:53
快速回复:算法倒水问题,求教高手。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.027334 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved