13. ноября 2013
Andrei
C# , Алгоритмы
Уже давно знал алгоритм для нахождения НОД(наибольшего общего делителя) для двух чисел. Но задача найти НОД для большого количества чисел, вызвало небольшое замешательство...
После небольшого гугления нашёл нужный алгоритм. Мою реализацию на C# можно увидеть ниже.
using System;
using System.Linq;
namespace NOD
{
internal class Program
{
private static void Main()
{
string str = Console.ReadLine();
string[] strArray = null;
long[] array = null;
if (!String.IsNullOrEmpty(str))
{
str = str.Trim();
strArray = str.Split(' ');
array = new long[strArray.Length];
}
if (strArray != null && strArray.Length > 0)
for (int i = 0; i < array.Length; i++)
{
array[i] = long.Parse(strArray[i]);
}
if (array != null && array.Length > 0)
{
#region ArrayNOD
long nod = array.Min();
while (true)
{
long temp = nod;
foreach (long number in array)
{
long tDiv = number/nod;
if (!(tDiv > 0 && number%nod == 0))
nod = number/(tDiv + 1);
}
if (temp == nod) break;
}
#endregion
Console.WriteLine(nod);
Console.ReadKey();
}
else
{
Console.WriteLine("Array is null or empty");
}
}
}
}
Сам алгоритм находится в регионе ArrayNOD