package org.bluebridge.topics;

/*泊松分酒
 泊松是法国数学家、物理学家和力学家。他一生致力科学事业,成果颇多。
 有许多著名的公式定理以他的名字命名,比如概率论中著名的泊松分布。

 有一次闲暇时,他提出过一个有趣的问题,后称为:“泊松分酒”。
 在我国古代也提出过类似问题,遗憾的是没有进行彻底探索,其中流传较多是:“韩信走马分油”问题。
 有3个容器,容量分别为12升,8升,5升。其中12升中装满油,另外两个空着。
 要求你只用3个容器操作,最后使得某个容器中正好有6升油。

 下面的列表是可能的操作状态记录:
 12,0,0
 4,8,0
 4,3,5
 9,3,0
 9,0,3
 1,8,3
 1,6,5
 每行3个数据,分别表示12,8,6升容器中的油量
 第一行表示初始状态,第二行表示把12升倒入8升容器后的状态,第三行是8升倒入5升,...
 当然,同一个题目可能有多种不同的正确操作步骤。
 本题目的要求是,请你编写程序,由用户输入:各个容器的容量,开始的状态,和要求的目标油量,
 程序则通过计算输出一种实现的步骤(不需要找到所有可能的方法)。如果没有可能实现,则输出:“不可能”。

 例如,用户输入:
 12,8,5,12,0,0,6
 用户输入的前三个数是容器容量(由大到小),接下来三个数是三个容器开始时的油量配置,
 最后一个数是要求得到的油量(放在哪个容器里得到都可以)
 则程序可以输出(答案不唯一,只验证操作可行性):
 12,0,0
 4,8,0
 4,3,5
 9,3,0
 9,0,3
 1,8,3
 1,6,5
 每一行表示一个操作过程中的油量状态。*/

/*思路:观察例子:
 *1、发现优先填补0的瓶子,把有酒的传给与其相邻的且是0的瓶子;
 *2、当所有瓶子都有酒的时候,考虑哪个瓶子是满的了
 *   如果a瓶满,那么分给b瓶一部分;如果b瓶满,分给c瓶一部分;如果c瓶满,那么分给a瓶一部分;
 */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

public class BoSongFenJiu {

	private static int targ, Va, Vb, Vc;
	private static ArrayList<String> proce = new ArrayList<String>();

	public static void main(String[] args) {

		Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));

		String data[] = sc.nextLine().split("\\,");
		sc.close();

		Va = Integer.parseInt(data[0]);
		Vb = Integer.parseInt(data[1]);
		Vc = Integer.parseInt(data[2]);
		int Wone = Integer.parseInt(data[3]);
		int Wtwo = Integer.parseInt(data[4]);
		int Wthree = Integer.parseInt(data[5]);
		targ = Integer.parseInt(data[6]);

		if (Wone + Wtwo + Wthree < targ)
			System.out.println("不可能");
		else
			search(Wone, Wtwo, Wthree);
	}

	private static void search(int a, int b, int c) {

		String p = a + "," + b + "," + c;

		// 判断集合里是有过p这个过程,如果有那就说明会一直循环下去
		if (proce.contains(p)){
			System.out.println("不可能");
			return;
		}

		proce.add(p);// 将过程都存到集合里头

		// 分到了targ这个目标值了就输出
		if (check(a, b, c)) {
			for (int i = 0; i < proce.size(); i++)
				System.out.println(proce.get(i));
			return;
		}

		if (a != 0 && b == 0)// 优先填补0
			search(a > Vb ? a - Vb + b : 0, a > Vb ? Vb : a, c);
		else {
			if (b != 0 && c == 0)
				search(a, b > Vc ? b - Vc + c : 0, b > Vc ? Vc : b);
			else if (c == Vc)
				search(a + c > Va ? Va : a + c, b, c + a > Va ? c + a - Va : 0);
			else if (b == Vb)
				search(a, b + c > Vc ? b + c - Vc : 0, c + b > Vc ? Vc : c + b);
			else if (a == Va)
				search(a + b > Vb ? a + b - Vb : 0, b + a > Vb ? Vb : b + a, c);
		}
	}

	private static boolean check(int a, int b, int c) {
		if (a == targ || b == targ || c == targ)
			return true;
		return false;
	}
}

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐