| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1990 人关注过本帖
标题:网上找的分酒问题的代码,但是程序运行不出来,请各位大神帮忙看看!
只看楼主 加入收藏
weihuachao
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2017-5-1
结帖率:0
收藏
已结贴  问题点数:20 回复次数:10 
网上找的分酒问题的代码,但是程序运行不出来,请各位大神帮忙看看!
程序代码:
#include<stdio.h>
#include<string.h>
#define N 3   //酒杯数
#define MAX_SIZES 100  //状态表中的最大状态数



 typedef struct node //边节点
 {
    int adjvex;   //邻接点的位置
    node*next;  //指向下一个节点
 }ARCNODE;  //邻接表中的结点类型


 typedef struct   //顶点节点
 {  
    int vexdata[N];        //各酒杯的存储状态
    ARCNODE*next;      //指向下一个邻接点
 }VEXNODE;//表头结点类型
 

 int A[MAX_SIZES];//用于存储路径的数组
 int top=0;//数组中的个数 
 int full[N];//各酒杯的最大容量 
 int part[N];//各酒杯的当前容量 
 int end[N];//最终状态


 VEXNODE s[MAX_SIZES];  //状态表
 int sta;//状态表当前状态数 
  

 int sum=0;//所有解的个数
 int end_vex;//结束的状态点 
 bool visited[MAX_SIZES];//标记状态是否被访问
   
  

 bool compare(int a[],int b[])   //比较状态
  {  
    int i;  
    for(i=0;i<N;i++) 
        if(a[i]!=b[i])  
          return true;//两数组不相等,返回true 
    return false;//相等,返回false 
  } 
  void save(int number)  

 {   //保存状态,如果状态存在则仅仅加入领接表,如果不存在则加入状态表,并加入邻接表
     ARCNODE*p; 
     int i;  
     for(i=0;i<=sta;i++) 
     {  
        if(!compare(part,s[i].vexdata));  
             break;//该状态存在,跳出for循环
     } 
  
     if(i>sta)//将该状态加入状态表
     {  
        sta++; 
        for(int j=0;j<N;j++) 
        s[sta].vexdata[j]=part[j]; 
        s[sta].next=NULL;  
        if(!compare(part,end))  
           end_vex=sta;//该状态是最终状态,记住在状态表中的位置
     } 


     p=new ARCNODE; 
     p->adjvex=i;  
     p->next=s[number].next;  
     s[number].next=p;//加入邻接表
  } 
  

 void jisuan(int number)//求出某状态的所有邻接点
 {  
    int i,j,I,J;  
    for(i=0;i<N;i++)//编号为i的酒杯与其他酒杯交换
    {   
        for(j=0;j<N;j++) 
       {  
            if(j==i)     continue;//同一酒杯,无法变换
            I=part[i];//保存i酒杯的当前的容量
            J=full[j]-part[j];//j酒杯的空闲量
               if(I<=J)//若i酒杯的当前容量小于等于j酒杯的空闲量 
               {  
                part[i]=0;  
                part[j]+=I;//将i酒杯的酒倒向j酒杯  
                save(number);//调用save()函数,保存当前的状态
                part[i]=I;  
                part[j]-=I;//恢复各酒杯的原始状态
               }  
           else//若i酒杯的当前容量大于j酒杯的空闲量
           {  
                part[i]-=J;  
                part[j]=full[j];//把j酒杯加满  
                save(number);//调用save()函数,保存当前的状态
                part[i]+=J;  
                part[j]-=J;//恢复各酒杯的原始状态
           } 
        } 
    } 

 } 

 
  

 void create()//建立状态的函数 
 {  
    int i;
    int number=i; 

 printf("输入各个酒杯的容积:"); 
    for(i=0;i<N;i++)      
     scanf("%d",&full[i]); 

 printf("输入对应酒杯的起始状态:"); 
    for(i=0;i<N;i++)  

 scanf("%d",&s[0].vexdata[i]);//初始状态即状态表中的s[0] 


 printf("输入对应酒杯的最终状态:"); 
    for(i=0;i<N;i++) 
     scanf("%d",&end[i]);//所求的状态
    number=0; sta=0;   
      s[0].next=NULL; 
  
    while(number<=sta) 
    {      
        for(i=0;i<N;i++) 
          part[i]=s[number].vexdata[i];//将s[number]的状态赋给各酒杯当前的容量  
          jisuan(number);//调用jisuan(),求出该状态所有的邻接点
          number++; 
    } 
    
    for(number=0;number<=sta;number++) 
         visited[number]=false; 

 } 
  

 void prtf()   //输出路径 
 {  

 int i,j,k; 

 printf("方案%d:\n",sum);  
    for(i=0;i<top;i++) 
    {  printf(" ");  
        j=A[i];//路径中的位置
        for(k=0;k<N;k++) 
        printf("%d",s[j].vexdata[k]);//输出该状态
    printf(" "); 
   }  

 printf("\n"); 

 } 

 
  

 void dfs(int v0)//深度优先搜索遍历函数 
 {  
  if(!visited[v0])//判断该状态是否被访问过
   {  
        if(v0==end_vex)//判断该状态是否是最终状态
        {  
            sum++;  
           prtf();//调用输出函数
        }  
        else//若不是,深度搜索
        {  
            ARCNODE *p; 
            p=s[v0].next;  
            visited[v0]=true;//标记该状态已访问
           while(p) 
           {  
              A[top++]=p->adjvex;   //记录路径
              dfs(p->adjvex);//递归调用遍历函数
              A[--top];//清空路径
              p=p->next; 
            }  
           visited[v0]=false;//标记该状态未访问,用于其它路径中访问
 
        } 
  } 

 } 
  

 void findpath() 

 {  
    A[top++]=0;         //选择深度所搜遍历的起点
    dfs(0);           //进行深度所搜遍历 
 } 
  

 void  main()  

 {int i,k;  
    create();        //建立模型的状态 
 printf("状态表中的%d中状态:\n",sta+1); 
    for(i=0;i<=sta;i++) 
   {for(k=0;k<N;k++)  
     printf("%d",s[i].vexdata[k]); 
     printf("\t"); 
    }  
    printf("\n共得到如下解法:\n");  
    findpath();              //输出得到的解 
 }
搜索更多相关主题的帖子: 网上 
2017-05-01 09:45
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:7 
感觉这题思路不难理解~就难点就是判断重复状态~至于具体细节还是有时间再去弄弄~

[此贴子已经被作者于2017-5-1 12:18编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-01 12:06
简单点点
Rank: 1
等 级:新手上路
帖 子:4
专家分:7
注 册:2017-5-1
收藏
得分:7 
回复 2楼 九转星河
大神请问我按这个做的N为4时运行时间太长出不来结果怎么办谢谢啦
2017-05-01 13:24
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 3楼 简单点点
那也没啥办法~毕竟搜索状态太多了~只能通过优化判断重复条件的时间(改进储存当前每个杯子的酒量的结构)来优化~别以为每一条问题都有一个高效的解法~有些NPC问题还是要老老实实搜索的~~

PS: 感觉用广搜虽然会麻烦一点~不过较容易理解不会出错~不像深搜一样自己搜索到哪里都要判断一番~如果用深度搜索递归遍历可能会导致栈空间不足~这个要注意一下~其实感觉深搜能得到其中一个解并且能记录其遍历路径~而广搜则可以得到最优解不过输出遍历路径要另行处理~所以在深搜和广搜之间如何选择要斟酌一下了~

[此贴子已经被作者于2017-5-1 13:49编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-01 13:38
简单点点
Rank: 1
等 级:新手上路
帖 子:4
专家分:7
注 册:2017-5-1
收藏
得分:0 
回复 4楼 九转星河
谢谢谢谢谢谢啦
2017-05-01 14:04
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
修改了几个小问题~这个代码要用CPP后缀运行~虽然感觉格式不咋的~ 不过凑合看看还是可以的~
程序代码:
#include<stdio.h>
#include<string.h>
#define N 3   //酒杯数
#define MAX_SIZES 100  //状态表中的最大状态数



 typedef struct node //边节点
{
    int adjvex;   //邻接点的位置
    node*next;  //指向下一个节点
}ARCNODE;  //邻接表中的结点类型


 typedef struct   //顶点节点
{  
    int vexdata[N];        //各酒杯的存储状态
    ARCNODE*next;      //指向下一个邻接点
}VEXNODE;//表头结点类型


 int A[MAX_SIZES];//用于存储路径的数组
int top=0;//数组中的个数 
int full[N];//各酒杯的最大容量 
int part[N];//各酒杯的当前容量 
int end[N];//最终状态


 VEXNODE s[MAX_SIZES];  //状态表
int sta;//状态表当前状态数 
  

 int sum=0;//所有解的个数
int end_vex;//结束的状态点 
bool visited[MAX_SIZES];//标记状态是否被访问
   
  
bool compare(int a[],int b[])   //比较状态
{  
    int i;  
    for(i=0;i<N;i++) 
        if(a[i]!=b[i])  
          return true;//两数组不相等,返回true
        
        return false;//相等,返回false 
 } 
void save(int number)  
{   //保存状态,如果状态存在则仅仅加入领接表,如果不存在则加入状态表,并加入邻接表
     ARCNODE*p; 
     int i;  
     for(i=0;i<=sta;i++) 
     {  
        if(!compare(part,s[i].vexdata)) 
             break;//该状态存在,跳出for循环
     } 
  
     if(i>sta)//将该状态加入状态表
     {  
        sta++; 
        for(int j=0;j<N;j++) 
        s[sta].vexdata[j]=part[j]; 
        s[sta].next=NULL;  
        if(!compare(part,end))  
           end_vex=sta;//该状态是最终状态,记住在状态表中的位置
     } 


     p=new ARCNODE; 
     p->adjvex=i;  
     p->next=s[number].next;  
     s[number].next=p;//加入邻接表
  } 
  
void jisuan(int number)//求出某状态的所有邻接点
{  
    int i,j,I,J;  
    for(i=0;i<N;i++)//编号为i的酒杯与其他酒杯交换
    {   
        for(j=0;j<N;j++) 
       {  
            if(j==i)     continue;//同一酒杯,无法变换
            I=part[i];//保存i酒杯的当前的容量
            J=full[j]-part[j];//j酒杯的空闲量
               if(I<=J)//若i酒杯的当前容量小于等于j酒杯的空闲量 
               {  
                part[i]=0;  
                part[j]+=I;//将i酒杯的酒倒向j酒杯  
                save(number);//调用save()函数,保存当前的状态
                part[i]=I;  
                part[j]-=I;//恢复各酒杯的原始状态
               }  
           else//若i酒杯的当前容量大于j酒杯的空闲量
           {  
                part[i]-=J;  
                part[j]=full[j];//把j酒杯加满  
                save(number);//调用save()函数,保存当前的状态
                part[i]+=J;  
                part[j]-=J;//恢复各酒杯的原始状态
           } 
        } 
    } 
} 

 
  
void create()//建立状态的函数 
{  
    int i;
    int number=0; 

     printf("输入各个酒杯的容积:"); 
    for(i=0;i<N;i++)      
     scanf("%d",&full[i]); 

 printf("输入对应酒杯的起始状态:"); 
    for(i=0;i<N;i++)  

 scanf("%d",&s[0].vexdata[i]);//初始状态即状态表中的s[0] 


 printf("输入对应酒杯的最终状态:"); 
    for(i=0;i<N;i++) 
     scanf("%d",&end[i]);//所求的状态
    number=0; sta=0;   
      s[0].next=NULL; 
  
    while(number<=sta) 
    {      
        for(i=0;i<N;i++) 
          part[i]=s[number].vexdata[i];//将s[number]的状态赋给各酒杯当前的容量  
          jisuan(number);//调用jisuan(),求出该状态所有的邻接点
          number++; 
    } 
    
    for(number=0;number<=sta;number++) 
         visited[number]=false; 

 } 
  

 void prtf()   //输出路径 
{  

 int i,j,k; 

 printf("方案%d:\n",sum);  
    for(i=0;i<top;i++) 
    {  printf(" ");  
        j=A[i];//路径中的位置
        for(k=0;k<N;k++) 
        printf("%d",s[j].vexdata[k]);//输出该状态
    printf(" "); 
   }  

 printf("\n"); 

 } 

 
  

 void dfs(int v0)//深度优先搜索遍历函数 
{  
  if(!visited[v0])//判断该状态是否被访问过
   {  
        if(v0==end_vex)//判断该状态是否是最终状态
        {  
            sum++;  
           prtf();//调用输出函数
        }  
        else//若不是,深度搜索
        {  
            ARCNODE *p; 
            p=s[v0].next;  
            visited[v0]=true;//标记该状态已访问
           while(p) 
           {  
              A[top++]=p->adjvex;   //记录路径
              dfs(p->adjvex);//递归调用遍历函数
              A[--top];//清空路径
              p=p->next; 
            }  
           visited[v0]=false;//标记该状态未访问,用于其它路径中访问

        } 
  } 

 } 
  

 void findpath() 

 {  
    A[top++]=0;         //选择深度所搜遍历的起点
    dfs(0);           //进行深度所搜遍历 
} 
  

 void  main()  

 {int i,k;  
    create();        //建立模型的状态 
printf("状态表中的%d中状态:\n",sta+1); 
    for(i=0;i<=sta;i++) 
   {for(k=0;k<N;k++)  
     printf("%d",s[i].vexdata[k]); 
     printf("\t"); 
    }  
    printf("\n共得到如下解法:\n");  
    findpath();              //输出得到的解 
}

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-01 14:06
简单点点
Rank: 1
等 级:新手上路
帖 子:4
专家分:7
注 册:2017-5-1
收藏
得分:0 
回复 6楼 九转星河
这个还是运行不了~~能帮忙再看看吗。。我们已经把这个改好了就是四个杯子的不好弄出不来结果哈哈哈。。谢谢~~
2017-05-01 14:29
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 7楼 简单点点
#define MAX_SIZES 10000

这个原来100要改大点试试~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-01 14:45
简单点点
Rank: 1
等 级:新手上路
帖 子:4
专家分:7
注 册:2017-5-1
收藏
得分:0 
回复 7楼 简单点点
还是不行~~放弃治疗了
2017-05-01 15:24
lhbnwpu
Rank: 1
等 级:新手上路
帖 子:1
专家分:7
注 册:2017-5-1
收藏
得分:7 
回复 9楼 简单点点
数模节快乐
2017-05-01 23:34
快速回复:网上找的分酒问题的代码,但是程序运行不出来,请各位大神帮忙看看!
数据加载中...
 
   



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

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