找出两个方程的可能值

Question

2x + 4y + 6z = 1200
x + y + z = 300

如何在 c# 方法中找到可能的 x、y、z integer 值？，我正在尝试找到更好的解决方案，而不是使用蛮力 嵌套循环，因为这不是一个好的解决方案。

public List<Tuple<int, int, int>> Calculate()
{
    var result = new List<Tuple<int, int, int>>();
    int maxValue = 300;

    for(int i = 0; i< maxValue; i++)
        for (int j = 0; j < maxValue; j++)
            for (int k = 0; k < maxValue; k++)
                if (i + j + k == maxValue && 2 * i + 4 * j + 6 * k == 1200)
                    result.Add(new Tuple<int, int, int>(i, j, k));

    return result;
}

提前致谢。

Answer 1

嗯，有了

2x + 4y + 6z = 1200
x + y + z = 300

你可以把它写成

x + 2y + 3z = 600
x + y + z = 300

用第一个减去第二个得到

y + 2z = 300

或

y = 300 - 2z

因为x = 300 - y - z我们可以把它写成

x = 300 - y - z =
  = 300 - (300 - 2z) - z =
  = 300 - 300 + 2z - z =
  = z

最后，对于任意z（即自由变量）

x = z
y = 300 - 2 * z;

可能c#代码：

private static (int x, int y, int z) Solution(int x) => (x, 300 - 2 * x, x);

演示：

string solutions = string.Join(Environment.NewLine, Enumerable
  .Range(0, 10)
  .Select(x => Solution(x)));

...

// 10 solutions for x = 0..9 
string solutions = string.Join(Environment.NewLine, Enumerable
  .Range(0, 10)
  .Select(x => Solution(x)));

Console.Write(solutions);

结果：

(0, 300, 0)
(1, 298, 1)
(2, 296, 2)
(3, 294, 3)
(4, 292, 4)
(5, 290, 5)
(6, 288, 6)
(7, 286, 7)
(8, 284, 8)
(9, 282, 9)

如果您只寻找非负解决方案（您在代码的注释中提到了概率），那么在 [0..150] 范围内使用 x：

(0, 300, 0)
(1, 298, 1)
(2, 296, 2)
...
(148, 4, 148)
(149, 2, 149)
(150, 0, 150)

编辑： 您的 Calculate() 方法得到改进：

public static List<Tuple<int, int, int>> Calculate() {
  var result = new List<Tuple<int, int, int>>();
  const int maxValue = 300;

  int start = Math.Max(150 - maxValue / 2, 0);

  for (int x = start; ; ++x) {
    int y = 300 - 2 * x;
    int z = x;

    if (y < 0 || x > maxValue)
      break;

    result.Add(new Tuple<int, int, int>(x, y, z));
  }

  return result;
}

Answer 2

数学理论

如果你想要一个通用的方法，你应该使用一些线性代数理论。让我们将矩阵形式的方程重写为 A(x,y) + bz = c，其中：

A: 是包含 x,y 坐标系数的矩阵 A = (2,4,1,1)

b = (6,1)（转置）是包含 z 系数的向量。

c = (1200, 300)（转置）是包含常数项的向量。

然后 (x,y) = AInverse * (c - bz)。这是 z 的函数（比方说 f(z)）。因此，对于每个 z，您都会获得一个有效的解决方案：(f(z),z)。 f(z) 是一个包含 2 个分量的向量。

备注如果 A 不可逆，因为方程（限制为 x 和 y）是线性相关的（即 2 个方程是 x 和 y 中的“相同”方程），则此方法失败。

代码

我们可以这样编码：

步骤 1 我们必须对 Matrix2x2 进行编码。我现在从头开始做，但如果你真的需要在生产中使用一些框架：

public record struct Matrix2x2 (float A00, float A01, float A10, float A11)
{
    public float Determinant => A00 * A11 - A01 * A10;
    public Matrix2x2 Invert() => Determinant != 0
            ? 1 / Determinant * new Matrix2x2() { A11 = A00, A00 = A11, A01 = -A01, A10 = -A10 }
            : throw new InvalidOperationException($"Cannot Invert this matrix");

    public static Matrix2x2 operator *(Matrix2x2 a, float number) => new()
    {
        A00 = a.A00 * number,
        A01 = a.A01 * number,
        A10 = a.A10 * number,
        A11 = a.A11 * number,
    };
    public static Matrix2x2 operator *(float number, Matrix2x2 a) => a * number;
    public static Vector2 operator *(Matrix2x2 a, Vector2 vector)
    {
        var x = a.A00 * vector.X + a.A01 * vector.Y;
        var y = a.A10 * vector.X + a.A11 * vector.Y;
        return new(x, y);
    }
}

步骤2 我们必须对等式进行编码。我们需要矩阵 A、z 系数和 b，以及常数项向量 c：

public delegate Vector3 SolutionSpace(float z);

public static class EquationHelper
{
    public static SolutionSpace SolveEquation(Matrix2x2 equationMatrix, Vector2 b, Vector2 c) => z =>
    {
        var v = equationMatrix.Invert() * (c - z * b);
        return new Vector3(v.X, v.Y, z);
    };
}

注意：此函数返回的对象是解决方案space，它取决于 1 个参数（z 值）。因此我们可以将其视为映射 (float z) => (x(z), y(z), z) 的函数，在 c# 中它是一个代表 returns 一个 Vector3 并接受一个浮点数的输入。

用法

var A = new Matrix2x2(2, 4, 1, 1);
var b = new Vector2(6, 1);
var c = new Vector2(1200, 300);
var solution = EquationHelper.SolveEquation(A, b, c);
foreach(var z in Enumerable.Range(-10, 21))
    Console.WriteLine(solution(z));

输出

找出两个方程的可能值

Find the possible values for two equations

c#

algorithm

math

equation