c# - 计算两个以上值的最大公约数 (GCD)

问题描述

在 VB.NET 或 C# 中，我希望能够动态计算一个或多个值的最大公约数 (GCD)，而无需使用递归方法。

我以C# 中的这个解决方案为指导来计算两个值的 GCD。现在，我想调整该解决方案以能够计算不确定数量的值（一个或多个包含在传递给下面函数的值数组中的值）......

这就是我目前所做的：

VB.NET（原代码）：

<DebuggerStepperBoundary>
Private Shared Function InternalGetGreatestCommonDivisor(ParamArray values As Integer()) As Integer

    ' Calculate GCD for 2 or more values...
    If (values.Length > 1) Then
        Do While Not values.Contains(0)
            For Each value As Integer In values
                Dim firstMaxValue As Integer = values.Max()
                Dim secondMaxValue As Integer = values.OrderByDescending(Function(int As Integer) int)(1)
                values(values.ToList.IndexOf(firstMaxValue)) = (firstMaxValue Mod secondMaxValue)
            Next value
        Loop

        Return If(values.Contains(0), values.Max(), values.Min())

    Else ' Calculate GCD for a single value...
        Return ...

    End If

End Function

C#（在线代码转换，我完全没有测试过）：

[DebuggerStepperBoundary]
private static int InternalGetGreatestCommonDivisor(params int[] values)
{

    // Calculate GCD for 2 or more values...
    if (values.Length > 1)
    {
        while (!values.Contains(0))
        {
            foreach (int value in values)
            {
                int firstMaxValue = values.Max();
                int secondMaxValue = values.OrderByDescending((int @int) => @int).ElementAtOrDefault(1);
                values[values.ToList().IndexOf(firstMaxValue)] = (firstMaxValue % secondMaxValue);
            }
        }

        return (values.Contains(0) ? values.Max() : values.Min());

    }
    else // Calculate GCD for a single value...
    {
        return ...;

}

我知道类型转换为 List 会影响大量值的整体性能，但最优先的事情是使该算法按预期工作，最后对其进行优化/重构。

我的适应对某些值组合按预期工作，但对另一些组合不起作用。例如在这个在线 GCD 计算器中，如果我们输入这些值：{1920, 1080, 5000, 1000, 6800, 5555} 理论上 GCD 是 5，或者至少这是那个在线服务计算的 GCD，但是我的算法返回 15。

标签： c#.netvb.netmath

// pass all the values in array and call findGCD function int findGCD(int arr[], int n) { int gcd = arr[0]; for (int i = 1; i < n; i++) { gcd = getGcd(arr[i], gcd); } return gcd; } // check for gcd int getGcd(int x, int y) { if (x == 0) return y; return gcd(y % x, x); }

c# - 计算两个以上值的最大公约数 (GCD)

问题描述

解决方案

推荐阅读