dimanche 5 septembre 2021

GCD of three numbers (without using array) euclidean algorithm

I have a task, that gives me a little headache here. The goal is to find Greatest Common Divisor with three integers, I succeded in doing it with two fairly easily, but with three it get's a little complicated when I can't use any arrays.

Here is the full code I used, finding gcd from two integers, tests all green:

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

And now I used the same principle for the GCD by three, but used something I found on web: 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;
            }
        }

Aucun commentaire:

Enregistrer un commentaire