|x-y|之间差值最小的改进方程算法ax+by=c

Question

我为改进我的算法苦苦挣扎了一段时间，但没有任何进展。

我需要一个可重复使用的函数来计算 x*3+y*5=n。

约束：

n>=7
x,y,n 总是整数正整数
我需要找到 x 和 y 之间距离最短的组合（绝对值）|x-y|

这是我编写的控制台应用程序草稿，它可以编译并运行，但如您所见，在处理大量数据时效率很低。

我想我缺乏数学知识来改进代码：

static void Main(string[] args)
{
    GetWarAfterMath(5000000);
    Console.ReadLine();
}

const int FIRST = 3;
const int SECOND = 5;

static void GetWarAfterMath(int n)
{
    int x = 0;
    int y = 0;
    int delta = 0;

    int i = 0;
    int j = 0;

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if ((i * FIRST) + (j * SECOND) == n)
            {
                // Console.WriteLine(i + "*" + FIRST + "+" + j + "*" + SECOND + "=" + n);
                if (Math.Abs(i - j) < delta)
                {
                    x = i;
                    y = j;
                    delta = Math.Abs(x - y);
                }
                break;
            }

            else if ((j * FIRST) + (i * SECOND) == n)
            {
                // Console.WriteLine(j + "*" + FIRST + "+" + i + "*" + SECOND + "=" + n);
                if (j - i < delta)
                {
                    x = j;
                    y = i;
                    delta = Math.Abs(x - y);
                }
                break;
            }
        }
    }

    Console.WriteLine("THE WINNERS ARE:" + x + "*" + FIRST + "+" + y + "*" + SECOND + "=" + n);
}

编辑：

最后结合@Yves Daoust、@user3386109 和@Hasson 的回答。
时间复杂度显着降低，
数字 8000000 的执行时间：127 毫秒！
这是最终算法：

static void Main(string[] args)
{
    GetMatch(34);
    Console.ReadLine();
}

const double FIRST = 3;
const double SECOND = 5;

static void GetMatch(double n)
{
    int x = 0;
    int y = 0;
    int finalX = 0;
    int finalY = int.MaxValue;
    for (int i = 0; i < n / FIRST; i++)
    {
        if (((n - FIRST * i) / SECOND) % 1 == 0)
        {
            y = Convert.ToInt32(((n - FIRST * i) / SECOND));
            x = i;
            if(Math.Abs(x-y) < Math.Abs(finalX-finalY))
            {
                finalX = x;
                finalY = y;
            }
        }
    }

    Console.WriteLine("THE WINNERS ARE:" + finalX + "*" + FIRST + "+" + finalY + "*" + SECOND + "=" + n + "    Calc: " +  (finalX * FIRST + finalY * SECOND));
}

请注意，正如@Yves Daoust 在他的第一个答案中所写，也可以使用欧几里德算法通过线性丢番图方程求解此问题，但您需要反转欧几里德算法，我更愿意保持简单。如果有人感兴趣，这里有一个关于该主题的精彩视频和解决方案：数论：Diophantine Equation: ax+by=gcd(a,b)
非常感谢您的帮助。

Answer 1

您不必对 x 和 y 都进行循环，这是一个您知道 n 的简单等式，因此如果您考虑 x = 1..n ，那么您可以计算 y = (n-3* x)/5 并测试它是否为整数（更好的是你可以测试 n-3*x 是否以 5 或 0 结尾，如果是，那么这是一个有效的组合，否则它不是。总而言之是一个循环，我认为我们可以添加更多优化。

顺便说一句，delta 必须用非常大的数字初始化，例如 n。

Answer 2

如果您需要一个高效的算法，那么从 x == y 的实数值（例如双精度或浮点数）的解决方案开始。然后将 x 舍入到下一个整数并将其作为起点。仅测试接下来的几对 (x,y) 整数。当你的三角洲变得更糟时休息。

Answer 3

目标是最小化 |x-y|。所以从 y=x 开始求解方程

3x + 5x = n
   8x = n

如果 n 是 8 的倍数，那么你找到了一个整数解。

否则，尝试y=x+1

3x + 5(x+1) = n
  8x + 5 = n

如果 n-5 是 8 的倍数，那么你找到了一个整数解。

否则，反过来试试

3(y+1) + 5y = n
  8y + 3 = n

如果 n-3 是 8 的倍数，那么你找到了整数解。

冲洗并重复得到以下结果

|x-y|==0 works if n is a multiple of 8
|x-y|==1 works if (n-3) or (n-5) is a multiple of 8
|x-y|==2 works if (n-2) or (n-6) is a multiple of 8
|x-y|==3 works if (n-1) or (n-7) is a multiple of 8
|x-y|==4 works if (n-4) is a multiple of 8

这些条件中至少有一个必须为真，因此 |x-y| 将始终小于或等于 4。

Answer 4

这个问题ax+by = c在数论中非常有名（它是一个线性丢番图方程）。

只有gcd(3,5)|n才能有解，当然总是这样

然后，如果您知道 3x°+5y°=n 的一些解法，所有解的形式都是 x=x°-5k、y=y°+3k.

很容易找到解决方案，因为n、n-5、n-10中的一个肯定是3的倍数。

剩下的就是在约束 x°-5k>0、y°+3k>0 下最小化 |x°-5k-y°-3k|。最小值将通过最接近 x°-y° 的 8k 值或使约束之一饱和的值来实现。

例如，对于n=173000，x°=57665和y°=1是一个解。然后 k=(57665-1)/8=7208 产生 |x-y|=0。该解决方案是可以接受的，因为满足了约束条件。

我没有提供案例研究的全部细节，但主要的教训是：不需要循环！

Answer 5

虽然我的其他解决方案已被接受，但还有更简单的方法。

如果允许有理数，您总是可以用 x = y = n / 8 达到最小值 0。由于对整数的限制，x = y = floor(n / 8) 产生 |x - y| = n mod 8，这是 0..7 之一。你可以通过adding/subtracting5从x调整到subtracting/adding3调整到y，你只需要解决[=19]的问题=] 在 0..7.

|x-y|之间差值最小的改进方程算法ax+by=c

Improving equation algorithm ax+by=c with the smallest difference between |x-y|

c#

algorithm

math

equation