File contents

import time

# ----------------------------------------------------------------------
# CALCULO DO MDC DE DOIS INTEIROS (a e b) DE MODO RECURSIVO
# ----------------------------------------------------------------------
# Sera utilizada a propriedade: mdc(a,b) = mdc(b,r), quando a = b.q + r
# Sua utilidade pode ser justificada quando |r| < |b|, pois em mdc(b,r)
# estaremos utilizando valores menores que em mdc(a,b)
# ----------------------------------------------------------------------



# ----------------------------------------------------------------------
# FUNCAO MDC1 - TOMAREMOS r COMO SENDO O RESTO DA DIVISAO DE a POR b
# ----------------------------------------------------------------------

def mdc1(a,b):      # Nome da funcao e parametros (a,b)
    if a<0: a = -a  # Tornar a nao-negativo
    if b<0: b = -b  # Tornar b nao-negativo

    if a<b:         # Garantir que a>=b. Nao ocorrendo isso, trocar os valores
        temp = a    # Armazenar temporariamente o menor valor (a)
        a = b       # Atribuir ao a o maior valor (b)
        b = temp    # Recuperar o menor valor (temp) e coloca-lo em b
        
    # ------------------------------------------------------------------
    # Caso base da recursao
    if b==0:        # Verificar se b=0 para usar a propriedade:
        return a    # mdc(a,0) = a (quando a>0)
    # ------------------------------------------------------------------
    # Processo recursivo
    else:                  # Caso b nao seja zero (b!=0)
        return mdc1(b,a%b) # Propriedade a = b.q + r (em python, r = a%b)
    
# **********************************************************************




# ----------------------------------------------------------------------
# FUNCAO MDC2 - TOMAREMOS r COMO SENDO O RESTO DA DIVISAO DE a POR b
# Funcao identica a anterior, mas que mostra os valores de (a,b,r)
# a cada iteracao
# ----------------------------------------------------------------------

def mdc2(a,b):      # Nome da funcao e parametros (a,b)
    if a<0: a = -a  # Tornar a nao-negativo
    if b<0: b = -b  # Tornar b nao-negativo

    if a<b:         # Garantir que a>=b. Nao ocorrendo isso, trocar os valores
        temp = a    # Armazenar temporariamente o menor valor (a)
        a = b       # Atribuir ao a o maior valor (b)
        b = temp    # Recuperar o menor valor (temp) e coloca-lo em b
        
    # ------------------------------------------------------------------
    # Caso base da recursao
    if b==0:        # Verificar se b=0 para usar a propriedade:
        print a     # Mostra o valor do mdc
        return a    # mdc(a,0) = a (quando a>0)
    # ------------------------------------------------------------------
    # Processo recursivo
    else:                  # Caso b nao seja zero (b!=0)
        print a,b,a%b      # Mostrar os valores de a,b,r
        return mdc2(b,a%b) # Propriedade a = b.q + r (em python, r = a%b)
    
# **********************************************************************



# ----------------------------------------------------------------------
# FUNCAO MDC3 - TOMAREMOS r COMO SENDO O MENOR INTEIRO, EM MODULO, QUE
# SATISFAZ A IGUALDADE a = b.q + r
# Funcao identica a anterior, mas que mostra os valores de (a,b,r)
# a cada iteracao
# ----------------------------------------------------------------------

def mdc3(a,b):      # Nome da funcao e parametros (a,b)
    if a<0: a = -a  # Tornar a nao-negativo
    if b<0: b = -b  # Tornar b nao-negativo

    if a<b:         # Garantir que a>=b. Nao ocorrendo isso, trocar os valores
        temp = a    # Armazenar temporariamente o menor valor (a)
        a = b       # Atribuir ao a o maior valor (b)
        b = temp    # Recuperar o menor valor (temp) e coloca-lo em b
        
    # ------------------------------------------------------------------
    # Caso base da recursao
    if b==0:        # Verificar se b=0 para usar a propriedade:
        print a     # Mostra o valor do mdc
        return a    # mdc(a,0) = a (quando a>0)
    # ------------------------------------------------------------------
    # Processo recursivo
    else:                        # Caso b nao seja zero (b!=0)
        if a%b <= b/2:           # Nada muda quando r <= b/2
            print a,b,a%b        # Mostrar os valores de a,b,r
            return mdc3(b,a%b)   # Propriedade a = b.q + r (Nesse caso, r= a%b)
        else:                    # Agora o caso r > b/2
            print a,b,a%b-b      # Mostrar os valores de a,b,r-b
            return mdc3(b,a%b-b) # Propriedade a = b.q + r (Agora r= a%b-b)
    
# **********************************************************************




# ======================================================================
# Imprimir texto centralizado em uma linha
# "Tipo" serao os caracteres que completarao a linha
# (Funcao auxiliar)
# ======================================================================
def cprint(s,tamlinha,tipo): # tipo eh quaquer caractere
    esq = (tamlinha-len(s))/2
    dir = tamlinha-esq-len(s)
    temp = ''
    for i in range(esq-2): temp += tipo
    print temp,
    print ' '+s+' ',
    temp = ''
    for i in range(dir-2): temp += tipo
    print temp    
# ----------------------------------------------------------------------




# ======================================================================
# Verificar se uma string representa um inteiro
# (Funcao auxiliar)
# ======================================================================
def isint(s):
    try: 
        int(s)
        return True
    except ValueError:
        return False
# ----------------------------------------------------------------------




# ======================================================================
# Menu principal
# ======================================================================
def menu():
    linhadupla = ''
    linhasimples =''
    for i in range(70):
        linhadupla += '='
        linhasimples +='-'
    print
    print linhadupla
    cprint("MAXIMO DIVISOR COMUM",70,"=")
    print linhadupla
    print
    print 'Escolha uma opcao:'
    print linhasimples
    print '0 -> Encerrar o programa'
    print '1 -> Calcular o MDC pelo algoritmo euclideano simples'
    print '2 -> Calcular o MDC utilizando menores restos absolutos'
    print linhasimples
    return raw_input('Opcao: ')
# ----------------------------------------------------------------------



# ======================================================================
# Menu operacoes
# ======================================================================
def operacoes(opcao):
    linhadupla = ''
    for i in range(70): linhadupla += '='
    print linhadupla
    # ------------------------------------------------------------------
    if opcao==1:
        cprint("Calculo de mdc(a,b) pelo algoritmo euclideano simples",70,"=")
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else:
                print
                print 'O valor de "a" deve ser inteiro'

        print
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else:
                print
                print 'O valor de "b" deve ser inteiro'


        linhasimples =''
        for i in range(70): linhasimples +='-'


        print
        print
        print linhasimples
        cprint("mdc utilizando o algoritmo euclideano simples",70," ")
        cprint("Sequencia: a - b - resto",70," ")
        print linhasimples
        mdc2(int(a),int(b))
        print linhasimples
        print 'mdc({0} , {1}) = {2}'.format(a,b,mdc1(int(a),int(b)))
        print linhasimples
    # ------------------------------------------------------------------
    if opcao==2:
        cprint("Calculo de mdc(a,b) utilizando menores restos absolutos",70,"=")
        print linhadupla
        print
        while True:
            a = raw_input('Informe o valor de a: ')
            if isint(a): break
            else:
                print
                print 'O valor de "a" deve ser inteiro'

        print
        while True:
            b = raw_input('Informe o valor de b: ')
            if isint(b): break
            else:
                print
                print 'O valor de "b" deve ser inteiro'


        linhasimples =''
        for i in range(70): linhasimples +='-'


        print
        print
        print linhasimples
        cprint("mdc utilizando menores restos absolutos",70," ")
        cprint("Sequencia: a - b - 'resto' ",70," ")
        print linhasimples
        mdc3(int(a),int(b))
        print linhasimples
        print 'mdc({0} , {1}) = {2}'.format(a,b,mdc1(int(a),int(b)))
        print linhasimples        
# ----------------------------------------------------------------------




# ======================================================================
# Execucao
# ======================================================================
while True:
    opcao = ''
    while not(opcao in ['0','1','2']):
        for i in range(5): print
        opcao = menu()
    if int(opcao)==0:
        break
    else:
        print
        operacoes(int(opcao))
        print
        print 'Reiniciando: ',
        for i in range(28):
            print '.',
            time.sleep(0.2)