改进方程算法ax + by = c,| xy |之间的差最小

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在他的第一个答案中写道,使用欧几里德算法使用inear diophantine方程也可以解决这个问题但你需要反转欧几里德算法,我更喜欢保持简单.如果有人感兴趣,这里有一个关于该主题的精彩视频:数论:Diophantine方程: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-y°-3k|的制约下x°-5k>0,y°+3k>0.最小值将通过8k最接近x°-y°的值或使其中一个约束饱和的值来实现.

例如,为n=173000,x°=57665并且y°=1是一种解决方案.然后k=(57665-1)/8=7208收益率|x-y|=0.该解决方案是可接受的,因为满足约束条件.

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

Answer 2

目标是尽量减少|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.