蓝桥杯历届决赛之分红酒

原题:

有4个红酒瓶子,它们的容量分别是:9升, 7升, 4升, 2升

 
开始的状态是 [9,0,0,0],也就是说:第1个瓶子满着,其它的都空着。

 
允许把酒从1个瓶子倒入另外一个瓶子,但只能把1个瓶子倒满或把1个瓶子倒空,不能有中间状态。这样的1次
倒酒动作称为1次操作。

 
假定瓶子的容量和初始状态不变,对给定的目标状态,最少需要多少次操作才能实现?

 
本题就是要求你编程实现最小操作次数的计算。

 
 
输入:终究状态(逗号分隔)

 
输出:最小操作次数(如没法实现,则输出⑴)

例如:
输入:
9,0,0,0
应当输出:
0
输入:
6,0,0,3
应当输出:

输入:
7,2,0,0
应当输出:

2


思路:跟我上1篇博客是1样的思路。BFS广度优先搜索。在状态类中由于不需要打印路径,将last值改成存储次数。将瓶子改成4个,容量肯定。不懂的可以先去看我上1篇博客。

java code:

package package1;
import java.util.*;
public class T201207_03 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);

//肯定初始状态
int[] s = new int[4];
for(int i = 0;i<s.length;i++)
s[i] = cin.nextInt();
Zt start = new Zt(s,0);

//肯定结束状态
int[] ans = new int[4];
for(int i = 0;i<ans.length;i++)
ans[i] = cin.nextInt();
Zt ansZt = new Zt(ans,⑴);

//创建队列,初始状态入队
Queue<Zt> queue = new LinkedList<Zt>();
queue.add(start);

//声明出队中间变量
Zt temp = null;
Zt newZt = null;

int p = 0;
if(start.equals(ansZt)){
sop("last = "+start.last);
return;
}
while(!queue.isEmpty())
{
//出队
temp = queue.poll();
temp.show();

//倒酒,1->2,1->3,1->4
// 2->1,2->3,2->4
// 3->1,3->2,3->4
//<span style="white-space:pre"> </span>4->1,4->2,4->3
for(int i = 0;i<3;i++)
for(int j = 0;j<3;j++)
{
//相等跳过
if(i == j)
continue;
//产生新的状态
newZt = temp.move(i,j,temp.last+1);
//为空则跳过
if(newZt == null)
continue;
queue.add(newZt);

if(newZt.equals(ansZt))
{
//newZt.show();
sop("last = "+newZt.last);
return;
}
}
}
sop("⑴");
}
private static void sop(String string) {
System.out.println(string);
}
}
//状态类
class Zt
{
//静态容量
public static int[] rl = {9,7,4,2};

//记录次数
int last;
//当前状态
int[] zt = new int[4];

Zt(int[] pz,int p)
{
last = p;
for(int i = 0;i<zt.length;i++)
zt[i] = pz[i];
}
//判断key值是不是存在当前状态
public int indexOf(int key)
{
for(int i = 0;i<zt.length;i++)
{
if(zt[i] == key)
return i;
}
return ⑴;
}

//将i的酒到入j中
public Zt move(int i,int j,int p)
{//比较i瓶的剩余量和j瓶的空闲量

//建立新的状态
int[] newzt = new int[4];
for(int k = 0;k<zt.length;k++)
{
newzt[k] = zt[k];
}
Zt newZt = new Zt(newzt,p);
//没法倒酒返回null
if(newZt.zt[i] == 0||newZt.zt[j] == newZt.rl[j])
return null;

if(newZt.zt[i]<= newZt.rl[j]-newZt.zt[j])
{//i的酒量小于j的剩余量,i清空,j += i
newZt.zt[j] += newZt.zt[i];
newZt.zt[i] = 0;
return newZt;
}
else
{//i的酒量大于j的剩余量,倒满j后i有剩余
newZt.zt[i] -= (newZt.rl[j] – newZt.zt[j]);
newZt.zt[j] = newZt.rl[j];
return newZt;
}
}
public void show()
{
System.out.print("zt = "+this.last+" ");
for(int i = 0;i<zt.length;i++)
System.out.print(zt[i]+",");
sop("");
}

public boolean equals(Object arg0) {
Zt e = (Zt)arg0;
for(int i = 0;i<zt.length;i++){
if(zt[i]!=e.zt[i])
return false;
}
return true;
}
private static void sop(String string) {
System.out.println(string);
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 蓝桥杯历届决赛之分红酒

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡