高分:分油问题,c++怎么编程?
发布网友
发布时间：2022-04-30 18:31
共3个回答
热心网友
时间：2022-06-29 06:03
#include <string.h>
int vol1,vol2,vol3,cur1,cur2,cur3,flag=0,goal,curb1,curb2,curb3;
int map[100][100][100];
int x[10000]; //记录每一步的倒油操作,1到2表示为1，1到3表示为2,2到1表示为3,2到3表示为4,3到1表示为5,3到2表示为6
void push(int *t1, int *t2,int v2) //把 *t1和*t2为当前油量,v2为*t2所在容器的容量。
{if( v2>*t1+*t2){*t2=*t2+*t1;*t1=0;}
else { *t2=*t2+*t1;*t1=*t2-v2;*t2=v2;}
}
void print(int step)
{printf("%d %d %d\n",curb1,curb2,curb3);
for(int i=1; i<step;i++)
switch(x[i])
{ case 1:
push(&curb1,&curb2,vol2);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
case 2:
push(&curb1,&curb3,vol3);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
case 3:
push(&curb2,&curb1,vol1);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
case 4:
push(&curb2,&curb3,vol3);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
case 5:
push(&curb3,&curb1,vol1);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
case 6:
push(&curb3,&curb2,vol2);
printf("%d %d %d\n",curb1,curb2,curb3);
break;
}
}
void backtrack(int step)
{ int t1=cur1,t2=cur2,t3=cur3;
if(flag) return;
if( t1==goal||t2==goal||t3==goal)
{ print(step);flag=1;return; }
//开始尝试1倒到2
push(&cur1,&cur2,vol2);
if(!map[cur1][cur2][cur3])
{x[step]=1;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束1倒到2，恢复各容器的原来油量
//开始尝试1倒到3
push(&cur1,&cur3,vol3);
if(!map[cur1][cur2][cur3])
{ x[step]=2;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束1倒到3，恢复各容器的原来油量
//开始尝试2倒到1
push(&cur2,&cur1,vol1);
if(!map[cur1][cur2][cur3])
{x[step]=3;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束2倒到1，恢复各容器的原来油量
//开始尝试2倒到3
push(&cur2,&cur3,vol3);
if(!map[cur1][cur2][cur3])
{x[step]=4;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束2倒到3，恢复各容器的原来油量
//开始尝试3倒到1
push(&cur3,&cur1,vol1);
if(!map[cur1][cur2][cur3])
{x[step]=5;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束3倒到1，恢复各容器的原来油量
//开始尝试3倒到2
push(&cur3,&cur2,vol2);
if(!map[cur1][cur2][cur3])
{x[step]=6;map[cur1][cur2][cur3]=1;
backtrack(step+1);
}
cur1=t1;cur2=t2;cur3=t3;
//结束3倒到2，恢复各容器的原来油量
}
int main()
{scanf("%d%d%d%d%d%d%d",&vol1,&vol2,&vol3,&cur1,&cur2,&cur3,&goal);
memset(map,0,sizeof(map));
map[cur1][cur2][cur3]=1;
curb1=cur1;curb2=cur2;curb3=cur3;
backtrack(1);
if( !flag)
printf("impossible");
}
输入：
3行
第1行是3个整数，由大到小，表示3个容器的容量
第1行是3个整数，表示3个容器的原有油量
第3行是1个整数，表示要求得到的油量（放在哪个容器里得到都可以）
输出：
实现过程中的各个状态(即各个容器的油量)。答案不唯一。
如果没有可能实现，则输出：“impossible”。
热心网友
时间：2022-06-29 06:03
热心网友
时间：2022-06-29 06:04
