Найти НОД для трех чисел с помощью бинарного алгоритма Евклида

Question

Выполняю задание по нахождению Нод по алгоритму Стейна. Ниже решение работает для двух целых чисел, но проблема возникает в методе для трех чисел, не все значения теста проходят (в задании есть юнит тесты ) а именно 0 , 0, -1; выкидывает исключение ArgumentException. Понимаю почему вылетает исключение но не понимаю что с этим делать , как сделать так чтобы проходили эти значения тоже?

  public static int GetGcdByStein(int a, int b)
    {
        if (a == 0 && b == 0)
            throw new ArgumentException("all numbers are 0 at the same time ");
        
        else if (a == int.MinValue || b == int.MinValue)
            throw new ArgumentOutOfRangeException(nameof(a), nameof(b), "numbers are int.MinValue");
        

        a = Math.Abs(a);
        b = Math.Abs(b);

        if (a == b)
            return a;
           
        if (a == 0)
            return b;
          
        if (b == 0)
            return a;
        
            
        if (a % 2 == 0)
        {
            if (b % 2 == 0)
                return 2 * GetGcdByStein(a / 2, b / 2);
            else
                return GetGcdByStein(a / 2, b);
        }

        if (b % 2 == 0)
            return GetGcdByStein(a, b / 2);
        
        if (a > b)
            return GetGcdByStein((a - b) / 2, b);
            
        return GetGcdByStein(a, (b - a) / 2);
    }

    // метод для трех чисел .

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

Answer 1

Не знаю насколько актуально, но привожу небольшую модификацию вашего кода.

private static int GetGcdByStein(int a, int b)
{
  //if (a == 0 && b == 0) throw new ArgumentException("all numbers are 0 at the same time "); 
  //Здесь ошибка, т.к. НОД(n, n) = n

  if (a == int.MinValue)
    throw new ArgumentOutOfRangeException(nameof(a), int.MinValue, "number is int.MinValue");
  if (b == int.MinValue)
    throw new ArgumentOutOfRangeException(nameof(b), int.MinValue, "number is int.MinValue");

  a = Math.Abs(a);
  b = Math.Abs(b);
  if (a == b) return a;
  if (a == 0) return b;
  if (b == 0) return a;
        
  if (a % 2 == 0) //четное
  {
    if (b % 2 == 0) return 2 * GetGcdByStein(a / 2, b / 2);
    return GetGcdByStein(a / 2, b);
  }
  if (b % 2 == 0) return GetGcdByStein(a, b / 2);
  if (a > b) return GetGcdByStein((a - b) / 2, b);
  return GetGcdByStein(a, (b - a) / 2);
}

public static int GetGcdByStein(int a, int b, int c)
{
  int ab;
  try
  {
    ab = GetGcdByStein(a, b);
  }
  catch (Exception e)
  {
    //Console.WriteLine("Exception detected when calculating Gcd of two parameters.");
    Console.WriteLine(e.Message);
    throw;
  }
  return GetGcdByStein(ab, c);
}

private static void Main()
{
  int a = 34, b = 17, c = 68;
  int[][] ar = {
    new[] {a, b},
    new[] {-a, b},
    new[] {a, -b},
    new[] {-a, -b},
    new[] {0, b},
    new[] {a, 0},
    new[] {0, 0},
    new[] {1, b},
    new[] {a, 1},
    new[] {a, b, c},
    new[] {a, int.MaxValue, c},
    new[] {a, int.MinValue, c},
    new[] {0, a, c},
    new[] {a, 0, c},
    new[] {a, b, 0},
    new[] {0, 0, c},
    new[] {a, 0, 0},
    new[] {0, b, 0},
    new[] {0, 0, 0},
  };

  for (int i = 0; i < ar.Length; i++)
  {
    int[] subAr = ar[i];
    try
    {
      if (subAr.Length == 2)
        Console.WriteLine($"{i}. Gcd({subAr[0]}, {subAr[1]}) = {GetGcdByStein(subAr[0], subAr[1])}");
      else if (subAr.Length == 3)
        Console.WriteLine(
          $"{i}. Gcd({subAr[0]}, {subAr[1]}, {subAr[2]}) = {GetGcdByStein(subAr[0], subAr[1], subAr[2])}");
    }
    catch (ArgumentException e)
    {
      Console.WriteLine(e);
    }
    finally
    {
      Console.WriteLine("********************");
    }
  }

  Console.WriteLine("Press Enter to exit...");
  Console.ReadLine();
}

Кстати, деление на 2 можно было заменить сдвигом, как это чаще всего и делают.

БЛОГ НА HUSL

Найти НОД для трех чисел с помощью бинарного алгоритма Евклида

Ответы (1 шт):