求解两个未知变量和两个函数

Question

两个不同定义的函数。

funcA:
a = a - 2;
b = b - 1;
funcB: 
a = a - 1;
b = b - 2;

我们的目标是在a = 0和b = 0时获得操作次数;

示例输入：a = 4, b = 2

call funcA:
a become 2, b become 1;
again call funcA
a become 0, b become 0;

因此返回2 + 0 = 2执行的操作总数为2;

示例输入 2：a = 3, b = 3

call funcA:
a become 1, b become 2;
call funcB
a become 0, b become 0;

因此返回21 + 1 = 2执行的操作总数;

Answer 1

让我们从特殊情况开始：

• 如果a < 0或b < 0我们没有解决方案
• 如果a = 0和b <> 0或a <> 0和b = 0我们没有解决方案
• 如果a > 2 * b或b > 2 * a我们没有解决方案

如果我们使用funcAx时间和funcBy时间，并从a和b中得到0，我们可以写

a - 2 * x - y = 0
b - 2 * y - x = 0

让我们求解这个x和y的线性方程组：

2 * x + y = a
2 * y + x = b

解决方案是

x = (2 * a - b) / 3
y = (2 * b - a) / 3

因此，如果我们有一个用于x和y的整数解，我们应该执行funcAx次、funcBy次

代码(爪哇)：

public static int Solve(int a, int b) {
// beware integer overflow! we use long in case a = 2_000_000_000 provided 
long x = (2L * a - b) / 3;
long y = (2L * b - a) / 3;
return ((x >= 0 && y >= 0 && (2L * b - a) % 3 == 0 && (2L * a - b) % 3 == 0))
? (int)(x + y)
: -1; // impossible
}

正如人们所看到的，我们有一个具有O(1)时间和空间复杂性的直接解决方案;不需要动态编程。