三数的 GCD（不使用数组）欧氏算法

Question

我有一个任务，这让我有点头疼。目标是用三个整数找到最大公约数，我用两个很容易就成功了，但是用三个整数就有点复杂了，因为我不能使用任何数组。

这是我使用的完整代码，从两个整数中找到 gcd，测试全部为绿色：

public static int GetGcdByEuclidean(int a, int b)
        {
            if (a == 0 && b == 0)
            {
                throw new ArgumentException(null);
            }
            else if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a));
            }
            else if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b));
            }
            else
            {
                int abs1 = Math.Abs(a);
                int abs2 = Math.Abs(b);
                a = abs1;
                b = abs2;

                while (a != 0 && b != 0)
                {
                    if (a > b)
                    {
                        a %= b;
                    }
                    else
                    {
                        b %= a;
                    }
                }

                return a | b;
            }
        }

现在我对三个 GCD 使用了相同的原理，但使用了我在网上找到的一些东西：gcd(a, b, c) = gcd(a, gcd(b, c) ) = gcd(gcd(a, b), c) = gcd(gcd(a, c), b)..

public static int GetGcdByEuclidean(int a, int b, int c)
        {
            int result = 0;

            if ((a == 0 && b == 0) && c == 0)
            {
                throw new ArgumentException(null);
            }
            else if (a == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(a));
            }
            else if (b == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(b));
            }
            else if (c == int.MinValue)
            {
                throw new ArgumentOutOfRangeException(nameof(c));
            }
            else
            {
                int abs1 = Math.Abs(a);
                int abs2 = Math.Abs(b);
                int abs3 = Math.Abs(c);
                a = abs1;
                b = abs2;
                c = abs3;

                while (a != 0 && b != 0 && c != 0)
                {
                    if (a > b && a > c && b > c)
                    {
                        b %= c;
                        a %= b;
                        result = a;
                    }
                    else if (a > b && a > c && b < c)
                    {
                        c %= b;
                        a %= c;
                        result = a;
                    }
                    else if (b > a && b > c && a > c)
                    {
                        a %= c;
                        b %= a;
                        result = b;
                    }
                    else if (b > a && b > c && a < c)
                    {
                        c %= a;
                        b %= c;
                        result = b;
                    }
                    else if (c > a && c > b && a > b)
                    {
                        a %= b;
                        c %= a;
                        result = c;
                    }
                    else
                    {
                        b %= a;
                        c %= b;
                        result = c;
                    }
                }

                return result;
            }
        }

Answer 1

只需保留 2 个数字的解决方案，然后使用以下公式从 3 个数字的一个解决方案调用它：gcd(a, b, c) = gcd(a, gcd(b, c) )

public static int GetGcdByEuclidean(int a, int b)
{
    // Your working solution for two numbers...
}

public static int GetGcdByEuclidean(int a, int b, int c)
{
    return GetGcdByEuclidean(a, GetGcdByEuclidean(b, c)); 
}

请注意，在 C# 中，您可以有多个同名方法，只要参数列表不同即可。参数的名称无关紧要，只是参数的数量或类型必须不同。这叫做overloading.

具有任意数量数字（但至少两个）的解决方案：

public static int GetGcdByEuclidean(int a, int b, params int[] other)
{
    int gcd = GetGcdByEuclidean(a, b);
    foreach (int x in other) {
        gcd = GetGcdByEuclidean(gcd, x);
    }
    return gcd; 
}

三数的 GCD（不使用数组）欧氏算法

GCD of three numbers (without using array) euclidean algorithm

c#

if-statement

while-loop

greatest-common-divisor