c# - |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

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°+下最小化|x°-5k-y°-3k| 3k>0。最小值将通过最接近 x°-y° 的 8k 值或使约束之一饱和的值来实现。

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

---

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