题目

1、油壶里有10升油，现在只有两个分别能装3升和7升油的瓶子，需要将10 升油等分成2 个5 升油。程序输出分油次数最少的详细操作过程。

选作：将油壶的容量改为L 升，两个瓶子的容量分别为M 和N 升，其中：L、M和N 均为正整数，且L 为正偶数、L = M + N，输出利用这两个瓶子将油壶中油等分的最少操作过程，如果不能等分，输出“None”。

按照下面的思路进行模拟

image-20231016201325358

输出None时的判断

参考倒水问题,这里相当于是倒水问题的特解

倒水问题的万能解法（扩展欧几里得算法）

Java算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
//package src.main.com.hantouInWIT2021.test1;

public class test1 {
    public static void main(String[] args) {
        System.out.println("请输入大壶,和两个杯子的容量: ");
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String[] s1 = s.split(" ");
        int l = Integer.parseInt(s1[0]);
        int m = Integer.parseInt(s1[1]);
        int n = Integer.parseInt(s1[2]);

        System.out.println("第 1 种方案：");
        int min1 = pull(l, m, n);
        System.out.println("第 2 种方案：");
        int min2 = pull(l, n, m);

        if (min1==-1&&min2==-1) return;
        if (min1==-1&&min2!=-1){
            System.out.println("第 2 种方案步骤最少。");
        } else if (min1 != -1 && min2 == -1) {
            System.out.println("第 1 种方案步骤最少。");
        }else {
            if (min1 > min2) {
                System.out.println("第 2 种方案步骤最少。");
            } else {
                System.out.println("第 1 种方案步骤最少。");
            }
        }
    }

    public static int gcd(int a,int b) {
        return b==0?a:gcd(b, a%b);
    }

    public static int pull(int l, int m, int n) {

        if((l/2)%gcd(m,n)!=0) {
            System.out.println("None");
            return -1;
        }

        int a = l;
        int b = 0;
        int c = 0;
        int cnt = 0;

        while (a != l / 2) {
            if (a + b <= m) {
                a = 0;
                b += a;
                System.out.println(++cnt + ": " + l + "L容器向 " + m + " L容器倒入 " + m + " L油");
            } else {
                System.out.println(++cnt + ": " + l + "L容器向 " + m + " L容器倒入 " + (m - b) + " L油");
                a -= (m - b);
                b = m;
            }
            if (b == l / 2) continue;

            while (b != 0) {
                if (b + c <= n) {
                    c += b;
                    System.out.println(++cnt + ": " + m + " L容器向 " + n + " L容器倒入 " + b + " L油");
                    b = 0;
                } else {
                    b -= (n - c);
                    System.out.println(++cnt + ": " + m + " L容器向 " + n + " L容器倒入 " + (n - c) + " L油");
                    c = n;
                }
                if (c == n) {
                    a += n;
                    c = 0;
                    System.out.println(++cnt + ": " + n + " L容器向 " + l + " L容器倒入 " + n + " L油");
                }
                if(b==l/2) break;
            }
        }
        return cnt;
    }
}