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

Question

两个定义不同的函数。

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

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

我们的目标是得到当botha = 0andb = 0;[=19时的操作次数=]

示例输入：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;

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

Answer 1

让我们从特殊情况开始：

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

如果我们使用 funcA x 次和 funcB y 次并从 both 得到 0 a 和 b 我们可以写成

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 的整数解决方案，我们应该执行 funcA x 次，funcB y 次

代码(Java):

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)，复杂度为 space； 动态规划

不需要

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

Solve for two unknown variables and two functions

java

algorithm

dynamic-programming