Elemar DEV

Tecnologia e desenvolvimento

Calculando Mínimo Múltiplo Comum (MMC/LCM) e Máximo Divisor Comum (MDC/GCD)

Olá. Tudo certo?

Para variar, um post “just for fun”. Minha implementação para o cálculo do Mínimo Múltiplo Comum e para Máximo Divisor Comum.

Comecemos pelo MDC:

public struct Gcd
{
    private readonly int _a;
    public int A { get { return _a; } }

    private readonly int _b;
    public int B { get { return _b; } }

    private readonly int? _result;
    public int? Result { get { return _result; } }

    public Gcd(int a, int b) :
        this()
    {
        _a = a;
        _b = b;

        var pa = Math.Abs(a);
        var pb = Math.Abs(b);

        if (pa == 0 || pb == 0) return;

        if (pa == pb)
        {
            _result = pa;
        }
        else if (pa > pb && pa % pb == 0)
        {
            _result = pb;
        }
        else if (pb > pa && pb % pa == 0)
        {
            _result = pa;
        }
        else
        {
            var result = 1;
            while (b != 0)
            {
                result = b;
                b = a % b;
                a = result;
            }
            _result = result;
        }
    }

    public static implicit operator int(Gcd gcd)
    {
        if (gcd.Result.HasValue)
            return (int)gcd.Result;

        throw new InvalidCastException();
    }

    public static Gcd For(int a, int b)
    {
        return new Gcd(a, b);
    }
}

Testes:

[TestFixture]
public class GcdTests
{
    [TestCase(48, 180, 12)]
    [TestCase(10, 135, 5)]
    public void Basics(int a, int b, int expected)
    {
        int actual = Gcd.For(a, b);
        Assert.AreEqual(expected, actual);
    }

    [TestCase(0, 0)]
    [TestCase(0, 10)]
    [TestCase(10, 0)]
    [ExpectedException(typeof(InvalidCastException))]
    public void InvalidCase(int a, int b)
    {
        int result = Gcd.For(a, b);
    }
}

Agora MMC:

public struct Lcm
{
    private readonly int _a;
    public int A { get { return _a; } }

    private readonly int _b;
    public int B { get { return _b; } }

    private readonly int? _result;
    public int? Result { get { return _result; } }

    public Lcm(int a, int b) :
        this()
    {
        _a = a;
        _b = b;

        var pa = Math.Abs(a);
        var pb = Math.Abs(b);
        var gcd = Gcd.For(pa, pb);

        if (gcd.Result == null) return;

        _result = checked((pa / gcd) * b);
    }

    public static implicit operator int(Lcm lcm)
    {
        if (lcm.Result.HasValue)
            return (int)lcm.Result;

        throw new InvalidCastException();
    }

    public static Lcm For(int a, int b)
    {
        return new Lcm(a, b);
    }
}

Testes:

[TestFixture]
public class LcmTests
{
    [TestCase(48, 180, 720)]
    [TestCase(10, 135, 270)]
    public void Basics(int a, int b, int expected)
    {
        int actual = Lcm.For(a, b);
        Assert.AreEqual(expected, actual);
    }

    [TestCase(0, 0)]
    [TestCase(0, 10)]
    [TestCase(10, 0)]
    [ExpectedException(typeof(InvalidCastException))]
    public void InvalidCase(int a, int b)
    {
        int result = Lcm.For(a, b);
    }
}

Era isso.

8 comentários em “Calculando Mínimo Múltiplo Comum (MMC/LCM) e Máximo Divisor Comum (MDC/GCD)

  1. Flávio
    07/03/2013

    Parabéns, excelente implementação !

  2. Juan Lopes
    07/03/2013

    Sou muito menos defensivo com as minhas implementações :P

    gcd(a, b): b!=0 ? abs(gcd(b, a%b)) : a

    • elemarjr
      07/03/2013

      Se a e/ou b forem zero, então, não deveria haver GCD?! Estou errado?

      • Errado, eu acredito. gcd(a, 0) = a. Qualquer número é divisor de zero.

      • Pensando bem, mudo a minha implementação:

        gcd(a, b): b!=0 ? gcd(b, a%b) : abs(a)

        Ai fica coerente com gcd(a, 0) = |a|.

        • elemarjr
          09/03/2013

          0/0 é indeterminado. Não?!

          • Sim, é gcd(0, 0) é indeterminado, mas geralmente deixam como 0 por conveniência.

            • elemarjr
              09/03/2013

              Não acha esse tipo de conveniência algo perigoso. Digo, dependendo de onde aplique pode conduzir a resultados inesperados.

              Prefiro reconhecer a “exception”

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

Informação

Publicado em 07/03/2013 por em Post.

Estatísticas

  • 660,641 hits
%d blogueiros gostam disto: