共有回帖数 0 个
-
法国数学家Poisson在青年时代研究过一个有趣的数学问题：某人有１２品脱的啤酒一瓶，想从中倒出６品脱，但他也没有６品脱的容器，仅有一个８品脱和５品脱的容器，怎样倒才能将啤酒分为两个６品脱呢？建个数学模型，编个程序求一下倒酒的过程！
我这有一个，大家看一下：
/*有四个人喝酒，有两个八两装满酒的瓶，
只有一个三两的杯子。他们要平分这些酒，
但是不能借用其它的工具，你觉得应该怎么做？
*/
#includeiostream.h
int position[6354][8];//状态集
long ptop=0;
//后来实验的结果是，在求解的过程中可能出现6354种状态
int object[7]={8,8,0,0,0,0,0};//0,1瓶,2杯,3~6人，写在一起只是为了便于搜索
int solution[60][3];//保存解过程：a,b,n a-b(n)
int cmin=100;//最少步数
int scount=0;
int pour(int a,int b)
//从a编号对象往b编号对象转移时，反回可行转移的酒量,返回0表示非法
{
int empty;
if(object[a]==0)return 0;
if(a==b)return 0;
//if(a2)return 0;//不能从人往容器转移
if(b3)//容器往容器
{
empty=b2?8-object:3-object;
if(object[a]empty)return object[a];
return empty;
}
else//容器往人
{
empty=4-object;
if(object[a]empty)return 0;
return object[a];
}
}
inline void move(int a,int b,int n)//转移
{
object[a]-=n;
object+=n;
}
bool oldposition(int c)//判断是否是曾经出现过的状态
{
int i,j;
for(i=0;iptop;++i)
{
for(j=0;j7;++j)
if(object[j]!=position[j])
break;
if(j==7)
{
if(cposition[7])
{
position[7]=c;
return false;
}
else
return true;
}
}
for(i=0;i7;++i)
position[ptop]=object;
position[ptop][7]=c;
++ptop;
return false;
}
void resolve(int c)
{
if(object[0]==0&&object[1]==0&&object[2]==0)
//得到一个解，输出
{
if(ccmin)cmin=c;
cout"第"(++scount)"个解，共"c"步实现:"endl;
for(int i=0;ic;++i)
coutsolution[0]"-"solution[1]":"solution[2]endl;
cout"-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+"endl;
return;
}
if(oldposition©)return;//好汉不走回头路
int a,b,n;
for(a=0;a3;++a)
for(b=0;b7;++b)
if((n=pour(a,b))0)
{
solution[c][0]=a;
solution[c][1]=b;
solution[c][2]=n;
move(a,b,n);
resolve(c+1);//下一步搜索
move(b,a,n);
}
}
void main()
{
resolve(0);
cout"完成需要的最少步数是:"cminendl;
}
值得解释一下的，程序中object[0]和[1]是两瓶酒，object[2]是那个杯子，object[3]到[6]是那四个人的肚子，程序没什么新鲜玩艺简单的搜索。
运行时间比较长，输出结果用重定向到文件：cpp1solution.txt
拿出其中一种解：
第816个解，共24步实现:
start: 8800000
0-2:3 5830000
2-4:3 5800300
0-2:3 2830300
0-5:2 0830320
2-0:3 3800320
1-2:3 3530320
2-0:3 6500320
1-2:3 6230320
2-0:2 8210320
2-4:1 8200420
0-2:3 5230420
1-0:2 7030420
2-1:3 7300420
0-2:3 4330420
2-1:3 4600420
0-2:3 1630420
2-1:2 1810420
2-6:1 1800421
1-2:3 1530421
2-0:3 4500421
1-2:3 4230421
1-5:2 4030441
2-6:3 4000444
0-3:4 0004444
楼主 2016-03-09 12:34 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
