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

Question

在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计算器中，如果我们输入以下值：{1920100805000100068005555}理论上，GCD是5，或者至少是该在线服务计算的GCD，但我的算法返回15。

Answer 1

// 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); 
} 

Answer 2

您所面临的问题是由于您过早地离开内部循环而导致的。检查是否有任何值为0是不够的，因为实际上必须检查除一个值外的所有值是否为0。

C#代码可能看起来像这样：

private static int InternalGetGreatestCommonDivisor(params int[] values)
{
// Calculate GCD for 2 or more values...
if (values.Length > 1)
{
while (values.Count(value => value > 0) != 1)
{
int firstMaxValue = values.Max();
int secondMaxValue = values.OrderByDescending((int @int) => @int).ElementAtOrDefault(1);
values[values.ToList().IndexOf(firstMaxValue)] = (firstMaxValue % secondMaxValue);
}
return values.Max();
}
else
{
// Calculate GCD for a single value...
}
}

对于您的示例，代码返回5。恐怕我不能给你VB.NET代码的确切表示形式。

Answer 3

您可以使用Linq:来完成此操作

static int GCD2(int a, int b){
return b == 0 ? Math.Abs(a) : GCD2(b, a % b);
}
static int GCD(int[] numbers){
return numbers.Aggregate(GCD2);
}