Curso de Python


Laboratórios

0a) Para aqueles que foram apresentados ao Reeborg, faça-o resolver os problemas propostos nesta lista.

0b) Exercícios com funções.

0c) Exercícios com funções.

0d) Exercícios com ifs.

0e) Exercícios com 1 loop.

0f) Exercícios com 2 loops.

0g) Exercícios Turtle Graphics.

Links úteis:

1a) Escreva um programa que liste os primeiros "n" elementos da sequência de Fibonacci.

Exemplo: para n = 9: 0 1 1 2 3 5 8 13 21 ...

Links úteis:

1b) Escreva um programa para resolver equações do segundo grau.

Links úteis:

1c) Escreva um programa para converter strings com dígitos decimais para inteiros.
Em C, esta poderia ser a implementação da função atoi("1234") → 1234 e em Python int("1234") → 1234.

1d) Execute o programa abaixo para imprimir a tabela ASCII no intervalo [32,126]:

    for x in range(32, 127): print ("%d = %s" % (x,chr(x)))                 # python

    for ( int x = 32; x < 127; ++x ) printf ( "%d = %c\n", x, (char) x );   // C

    for ( int x = 32; x < 127; ++x ) System.out.println ( String.format ( "%03d = %c ", x, (char) x ) );  // Java

Links úteis:
1d) Escreva um programa para converter inteiros ou reais (ponto flutuante) para strings binárias ou hexadecimais e vice-versa.

Exemplos:

2009 = 11111011001 em binário e 2009 = 7D9 em hexadecimal.
-9.125 = -1001.001 = -1.001001 x 23 em binário = 1 10000010 00100100000000000000000 em ponto flutuante
        1 bit de sinal = negativo = 1
        8 bits de expoente [-127,127] mapeado em [0,255) = 127+3 = 130 = 10000010
        23 bits de mantissa = 001001 = 00100100000000000000000
        um número desnormalizado (expoente 0) é, por definição, da forma 0.MANTISSA * 2-126
-9.125 = C1120000 em hexadecimal.
Links úteis:
1e) Escreva um programa para multiplicar dois inteiros positivos usando apenas adição e deslocamento (multiplicação por 2).

Dica: pense em binário:

        1011 X         11
        1101           13
        ----     --------
        1011 +   1*1*1011  1011 << 0
       00000     0*2*1011  0000 << 1
      101100     1*4*1011  1011 << 2
     1011000     1*8*1011  1011 << 3
     -------     --------
    10001111          143

2a) Escreva uma função para somar os primeiros "n" elementos de uma progressão aritmética,
dados o primeiro elemento "a1" e a diferença "d" entre os elementos.

Exemplo: 1 + 4 + 7 + 10 + 13 + 16 + 19 = 70

Dica: S(n,a1,d) = n ⁄ 2 (2a1 + (n-1)d).

Links úteis:
2b) Escreva uma função para somar os primeiros "n" elementos de uma progressão geométrica,
dados o primeiro elemento "a" e a razão "r" entre os elementos.

Exemplo: 1 + 3 + 9 + 27 + 81 + 243 + 729 = 1093

Dica: S(n,a,r) = a(1 - rn) ⁄ (1-r).
Se |r| < 1, então ∑i=0 ai = a ⁄ (1-r).
Links úteis:

2c) Escreva um programa para converter números inteiros, menores do que 4000 e escritos em algarismos arábicos, para romanos.

Obs: evite escrever mais do que nove "if"s.

Dicas:

- A ideia é usar um comando while para analisar cada casa decimal e gerar os caracteres romanos diferentemente para cada iteração.

- Use uma string para armazenar as letras correspondentes a cada casa decimal.

Exemplo: 1666 corresponde a string "MDCLXVI", onde:
Links úteis:

2d) Escreva uma função que dado o capital inicial "c", a taxa de juros "t" e o número de períodos "n", retorne o valor da dívida corrigida, ao final de um certo número de períodos, utilizando juros compostos e juros continuamente compostos.

Exemplo: c+ct = c(1+t), c(1+t)+c(1+t)t = c(1+t)2, c(1+t)2+c(1+t)2t = c(1+t)3,...

Dica:
Juros compostos: J(n,c,t) = c(1 + t)n.
Juros continuamente compostos: J(n,c,r) = cern.

Nota: t = er-1 ou r = ln(1+t), onde r é taxa de juros continuamente composta.

Links úteis:

2e) Escreva uma função que dado o capital inicial "c", o número de períodos "n", e o capital final f, retorne o valor dos juros aplicados.

Dica:
Juros compostos: ln(f ⁄ c) ⁄ n = ln(1 + t) ou t = eln(f ⁄ c) ⁄ n - 1 = (f ⁄ c) 1 ⁄ n - 1.
Juros continuamente compostos: r = ln(f ⁄ c) ⁄ n.
Links úteis:
2f) Suponha que:
  1) o preço de uma mercadoria a prazo é "x" reais e que o preço à vista é "y" reais.
  2) o valor é pago em "p" prestações mensais iguais a (x/p) reais, com uma de entrada (1+(p-1))
  3) que o mercado esteja adotando uma remuneração bancária fixa de "t"% ao mês (taxa).

Faça um programa para determinar se vale a pena comprar a prazo ou não,
ou seja, descobrir o quanto o comerciante ou a financeira estão cobrando a mais.

A fórmula para atualizar o preço no instante da compra, levando em conta a remuneração aplicada a cada prestação, é:

    xatualizado = (x⁄p) * [(1+t)p-1] ⁄ [t(1+t)(p-1)] = f * x.

O seu programa deve aceitar três opções:

Dica: Este programa implementa o que o mercado financeiro chama de


Desconto Racional por Dentro.


    O preço atualizado, voltando cada parcela para o tempo inicial A, 
    é a soma de uma P.G. de razão q = 1⁄(1+t) e cujo primeiro termo é q:

               A = R[(1+t)-1+(1+t)-2+...+(1+t)-n]
                     
               A = R q(1-qn)⁄1-q, onde R = x⁄p é o valor de cada parcela.

    Como, neste exercício, a primeira parcela é paga no ato da compra,
    na realidade, n = p-1 e deve-se somar x⁄p (a entrada):

               A = (x⁄p) (1 + q(1-q(p-1))⁄(1-q)).

    Fazendo-se as substituições necessárias, chega-se a fórmula
    usada no programa:

               q(1 - 1⁄(1+t)(p-1)) ⁄ (1-1⁄(1+t)) = q((1+t)(p-1) - 1)⁄(1+t)(p-1) ⁄ (t⁄(1+t)) = 
               (1⁄(1+t)) ((1+t)(p-1) - 1) (1+t) ⁄ t(1+t)(p-1) = ((1+t)(p-1) - 1) ⁄ t(1+t)(p-1)

               1 + ((1+t)(p-1) - 1) ⁄ t(1+t)(p-1) = (t(1+t)(p-1) + (1+t)(p-1) - 1) ⁄ t(1+t)(p-1)
               ((t+1)(1+t)(p-1) - 1) ⁄ t(1+t)(p-1) = ((1+t)p - 1) ⁄ t(1+t)(p-1)
Nota: Achar a taxa "t" que produz o preço à vista "y" requer o método de Newton:
               xn+1 = xn - f(xn)⁄f'(xn) 

        y     = (x⁄p) (c-1) / tb,         onde a = (1+t)(p-2), b = (1+t)(p-1), c = (1+t)p
        f(t)  = ytb - (x⁄p) (c-1)         o problema é equivalente a encontrar um zero da função f
        f'(t) = y (b + t (p-1) a) - xb    derivando f

               tn+1 = tn - f(t)⁄f'(t), to = x⁄y
A função é decrescente e converge para t quando n→∞.
Links úteis:

3a) Escreva um programa para converter números escritos em algarismos romanos para arábicos.

Obs: não esqueça de tratar os símbolos entre parêntesis, que devem ser multiplicados por 1000.

Exemplos:

CMXLVIII = -100 + 1000 - 10 + 50 + 5 + 1 + 1 + 1 = 948.
(DXXXIV)CMXLVIII = (534)*1000 + 948 = 534948.

Dicas:

- Quando o próximo caracter romano corresponder a um decimal maior/menor (dependendo do sentido de percurso), o valor decimal deve ser subtraído ao invés de ser adicionado.

- Use uma lista ou um dicionário, para mapear os caracteres romanos em decimais.

- A lista deve ter cerca de 100 posições para não haver problema de indexação, pois ord("X") = 88,

       l = [0]*100
       l[ord("M")] = 1000
       l[ord("D")] = 500
       l[ord("C")] = 100
       l[ord("L")] = 50
       l[ord("X")] = 10
       l[ord("V")] = 5
       l[ord("I")] = 1
- O dicionário é mais simples:
       l = {"M":1000, 
            "D":500, 
            "C":100, 
            "L":50, 
            "X":10, 
            "V":5, 
            "I":1}

3b) Repita o exercício 2c) mas agora usando duas listas para mapear os dígitos decimais em símbolos romanos:

        symbols  = ["M",  "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] 
        decimals = [1000,  900, 500,  400, 100,   90,  50,   40,  10,    9,   5,    4,   1]

3c) Repita o exercício 2c) mas agora usando uma tabela para mapear os dígitos decimais em símbolos romanos:

        symbols = [
            ["",  "I",   "II",   "III",   "IV",   "V",   "VI",   "VII",   "VIII",   "IX" ],  # units
            ["",  "X",   "XX",   "XXX",   "XL",   "L",   "LX",   "LXX",   "LXXX",   "XC" ],  # tens
            ["",  "C",   "CC",   "CCC",   "CD",   "D",   "DC",   "DCC",   "DCCC",   "CM" ],  # hundreds
            ["",  "M",   "MM",   "MMM",  "(IV)", "(V)", "(VI)", "(VII)", "(VIII)", "(IX)"],  # thousands
            ["", "(X)", "(XX)", "(XXX)", "(XL)", "(L)", "(LX)", "(LXX)", "(LXXX)", "(XC)"],  # ten thousands
            ["", "(C)", "(CC)", "(CCC)", "(CD)", "(D)", "(DC)", "(DCC)", "(DCCC)", "(CM)"],  # hundred thousands
            ["", "(M)", "(MM)", "(MMM)",     "",    "",     "",      "",       "",     ""]   # millions
        ]
Links úteis:

3d) Escreva um programa para imprimir o triângulo de Pascal entre dois níveis dados.

O seu programa deve ser capaz de imprimir a expansão, em série de potências, da expressão (x+y)n, para qualquer n.
Por fim, implemente a função de distribuição cumulativa CDF, e em particular a probabilidade de em n lançamentos de uma moeda, obterem-se no máximo n/3 coroas.

Dicas:

- O número de espaços em branco no início de cada linha é (last_level-len(row)+2).

    0 ------ 1          <---- first_level (0)                               C(0,0)
    1 ----- 1 1                                                         C(1,0)  C(1,1)
    2 ---- 1 2 1        <---- level (2) = len(row) - 1              C(2,0)  C(2,1)  C(2,2)
    3 --- 1 3 3 1                                               C(3,0)  C(3,1)  C(3,2)  C(3,3)
    4 -- 1 4 6 4 1                                           C(4,0)  C(4,1)  C(4,2)  C(4,3)  C(4,4)
    5 - 1 5 10 10 5 1   <---- last_level (5)             C(5,0)  C(5,1)  C(5,2)  C(5,3)  C(5,4)  C(5,5)
Uma forma melhor, de centrar o triângulo, é calculando o comprimento da última linha e usando o método center da classe string:
   lenmax = len(' '.join(map(str,last_line)))            # transforma uma lista de inteiros numa string e calcula número de caracteres
   for line in pascal_triangle:
       print (' '.join(map(str,line)).center(lenmax))

                                                          1                                                          
                                                         1 1                                                         
                                                        1 2 1                                                        
                                                       1 3 3 1                                                       
                                                      1 4 6 4 1                                                      
                                                    1 5 10 10 5 1                                                    
                                                   1 6 15 20 15 6 1                                                  
                                                 1 7 21 35 35 21 7 1                                                 
                                                1 8 28 56 70 56 28 8 1                                               
                                             1 9 36 84 126 126 84 36 9 1                                             
                                         1 10 45 120 210 252 210 120 45 10 1                                         
                                       1 11 55 165 330 462 462 330 165 55 11 1                                       
                                     1 12 66 220 495 792 924 792 495 220 66 12 1                                     
                                 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1                                 
                              1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1                             
                          1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1                          
                      1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1                      
                  1 17 136 680 2380 6188 12376 19448 24310 24310 19448 12376 6188 2380 680 136 17 1                  
               1 18 153 816 3060 8568 18564 31824 43758 48620 43758 31824 18564 8568 3060 816 153 18 1               
           1 19 171 969 3876 11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876 969 171 19 1           
     1 20 190 1140 4845 15504 38760 77520 125970 167960 184756 167960 125970 77520 38760 15504 4845 1140 190 20 1    
1 21 210 1330 5985 20349 54264 116280 203490 293930 352716 352716 293930 203490 116280 54264 20349 5985 1330 210 21 1


- É importante perceber a relação do triângulo de Pascal com o binômio de Newton:
    (x+y)0 = 1
    (x+y)1 = x + y
    (x+y)2 = x2 + 2xy + y2
    (x+y)3 = x3 + 3x2y + 3xy2 + y3
    (x+y)4 = x4 + 4x3y + 6x2y2 + 4xy3 + y4
    (x+y)5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5
Na área de probabilidade, uma distribuiçcão de Bernoulli é a distribuição discreta de espaço amostral {0, 1}, que tem valor 1, com probabilidade de sucesso p ∈ [0,1], e valor 0, com probabilidade de falha q=1-p.
- A probabilidade de em n experimentos de Bernoulli, consecutivos e independentes, obterem-se k sucessos, em qualquer ordem, é dada por:
             P(X=k) = C(n,k) pk qn-k = (n! ⁄ (k!(n-k)!)) pk qn-k. 
- Consequentemente, a CDF, que é a probabilidade de obterem-se no máximo k sucessos, em n experimentos, é dada por: P(X<=k) = ∑i=0k C(n,i) pi qn-i.
- Por exemplo, (p+q)4 = p(0 sucessos) p(4 fracassos) + (no máximo 0 sucessos) 4 p(1 sucesso) p(3 fracassos) + (no máximo 1 sucesso) 6 p(2 sucessos) p(2 fracassos) + (no máximo 2 sucessos) 4 p(3 sucessos) p(1 fracasso) + (no máximo 3 sucessos) p(4 sucessos) p(0 fracassos) = 1 (no máximo 4 sucessos)
- Tabela da distribuição binomial cumulativa.

- O somatório dos termos da linha n é 2n.

- O somatório dos k primeiros termos da coluna n é:

	C(n, n) + C(n+1, n) +... + C(n+k, n) = C(n+k+1, n+1).
- Uma linha pode ser determinada conhecendo-se o conteúdo da linha anterior:
   linhai[0] = linhai[i] = 1  
   linhai[j] = linhai-1[j-1] + linhai-1[j], 1 < j < i.

- Implemente uma função getNextRow ( curr_row ), que devolve a linha que sucede "curr_row"

- Implemente uma função printRow ( last_level, r ), que imprime a linha "r".

row = [1]                                # Top of Pascal triangle
for l in range (0, last_level+1):
    if l >= first_level:                 # l is now in the range [first_level, last_level]. 
       printRow ( last_level, row )
    row = getNextRow ( row )             # new row 

Dica:

>>> line=[1,3,3,1]
>>> [0] + line
[0, 1, 3, 3, 1]
>>> line + [0]
[1, 3, 3, 1, 0]
>>> list(zip([0] + line, line + [0]))
[(0, 1), (1, 3), (3, 3), (3, 1), (1, 0)]
>>> list(map(sum, zip([0] + line, line + [0])))
[1, 4, 6, 4, 1]
Links úteis:

3e) Escreva um programa para multiplicar duas matrizes.

Dicas:

- Use a função zip(*M) para percorrer as colunas de uma matriz "M" e sum(L), para somar os elementos de uma lista "L".

- Use três "for" aninhados:

- Entenda porque o seguinte código funciona:
    matMultiply = lambda m1, m2: [[sum(i*j for i, j in zip(row, col)) for col in zip(*m2)] for row in m1]
Links úteis:

3f) Escreva um programa para intercalar listas.


4a) Escreva um programa que dado um número natural "n" diga se ele é primo ou composto.

Obs: o seu programa deve ser capaz de lidar com entradas grandes.

Exemplo: 261-1 é primo (2305843009213693951).

Dicas:

Números primos são os números naturais que têm apenas dois divisores diferentes: o 1 e ele mesmo.

Por definição, 1 não é primo.

Lema de Euclides: se um número primo p dividir o produto de dois inteiros ab, então p divide a ou p divide b.
    Se p divide ab e MDC ( a, p ) = 1 então p divide b.

No algoritmo de divisões sucessivas, só é necessário testar até √ n .
    Se n = ab (a e b inteiros > 1), então apenas um fator pode ser maior do √ n . 
    Caso contrário, ab > n, o que é um absurdo. Logo, se um fator a é maior do que √ n ,
    o seu cofator b = n/a deve ser menor do que √ n .

Teorema de Fermat: seja p um primo que não divide o inteiro a, então: ap-1 = 1 (mod p) ou ap-1 % p = 1.

Tempos:

Assumindo que 261-1 (2305843009213693951 = 1FFFFFFFFFFFFFFF em hexadecimal) é primo, o algoritimo executa cerca de 260 divisões (dividindo só pelos ímpares e não usando o limite de √ n ).
Esse número possui 61 bits e requer uma palavra de 64 bits para poder ser armazenado como um inteiro simples.

Supondo que o computador pode executar 109 divisões por seg (1 gigaflop), então os cálculos levarão aproximadamente 36 anos.

       2305843009213693951 / (2 * 109/s * 31536000 s/ano) = 36.558901085 anos
Usando o limite de √ n , isto cai para
 2305843009213693951  / (2 * 109/s) = (1518500249) / (2*1000000000) = 0.759s

Em um Intel Core(TM)2 Quad CPU Q6600 @ 2.40GHz (64 bits):
- o programa escrito em Python gastou 100s.
- o mesmo programa, escrito em C, gastou 17s.

Em um Intel Core(TM) i7-3770 CPU @ 3.40GHz (64 bits):
- o programa escrito em Python gastou 32.40s
- o mesmo programa, escrito em C, gastou 6.21s.

Portanto, o programa C é quase 6 vezes mais rápido.

Em um Intel Pentium 4 @ 2.60GHz (32 bits):
- o mesmo programa em Pyhton gastou 1295.3035109s (21.5 min).

Links úteis:
4b) Implemente uma função que retorne a raiz quadrada inteira de um número natural "n" para ser usada no exercício 4a).

Dica:

- Aplique o método de Newton:
       xn+1 = xn - f(xn)/f'(xn)
- Considere f(x) = x2 − n = 0. Logo:
       xk+1 = 1/2 (xk + n/xk), k >= 0, x0 > 0. 
- Faça x0 = n, e pare a iteração quando: | xk+1 − xk | < 1.
Links úteis:
4c) Escreva um programa que leia um número e diga se ele é perfeito.

Obs: um número perfeito é aquele que é igual a soma dos seus divisores.

Exemplo: 28 = 14 + 7 + 4 + 2 + 1.
   Euclides (300 AC) provou que sempre que n é primo E 2n-1 também é primo (chamado primo de Mersenne), 
   então 2(n−1)(2n-1) é perfeito, e Euler (1707-1783) mostrou que todos os números perfeitos pares são da forma, 
   2(n-1)(2n-1). Um número perfeito ímpar nunca foi encontrado. Foram descobertos, até hoje, apenas 50 primos de Mersenne.
   
   # A lista dos 50 primos "p" conhecidos para os quais M(p) = 2p-1 é um primo de Mersenne.
   # Pode haver outros entre 43° e o 50° ainda não encontrados.
   # M(2) = 3,     M(3) = 7,   M4   = 15,   M(5) = 31,   M6   = 63,   M(7)  = 127,
   # M8   = 255,   M9   = 511, M10  = 1023, M11  = 2047, M12  = 4095, M(13) = 8191

   mprimes = [
             2,        3,       5,         7,       13,       17,       19,
            31,       61,      89,       107,      127,      521,      607,
          1279,     2203,     2281,     3217,     4253,     4423,     9689,
          9941,    11213,    19937,    21701,    23209,    44497,    86243,
        110503,   132049,   216091,   756839,   859433,  1257787,  1398269,
       2976221,  3021377,  6972593, 13466917, 20996011, 24036583, 25964951, 
      30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 
      77232917 <-- gera um primo de 23.249.425 dígitos que corresponde a um n° perfeito de 46.498.850 dígitos.
   ]  

   Dickson: Introduction to The Theory of Numbers, página 5, ex. 8
   E.g., 6 = 2 * 3, 28 = 4 * 7, 496 = 16 * 31, 8128 = 64 * 127

   Números primos gigantes são importantes na criptografia (ex. 5d).
   Há um prêmio de $150.000 dólares a primeira pessoa ou grupo que
   descobrir um primo de 100 milhões de dígitos!
Links úteis:
4d) Escreva uma função que receba um número natural "n" e retorne uma lista com todos os primos menores do que "n".

Obs: a sua função NÃO pode usar as operações de divisão (/) ou resto (%), mas apenas adição.

Dicas: Utilize o crivo de Eratóstenes (276-194 AC).
     - É suficiente eliminar os múltiplos de um número i <= √ n , a partir de i2.
       De fato, i*(i-1), i*(i-2), ... i*2 já foram marcados no processamento dos números
       menores do que i: 2*i, 3*i, ..., (i-1)*i

     - Use uma lista L = list(range(n)) = [None, None, 2, 3, ..., n-1], onde L[i] = i, para marcar os números compostos como None. 
       Ao final, basta retornar: list(filter(None,L))

     - [lua:~/html/python/labs] _04d_sieve.py 144
       Run time: 5.79357e-05s
       The list of primes lesser than 144 is:
       [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139]


Crivo
Links úteis:

4e) Ordene uma lista com 20 elementos, gerados de forma aleatória, pelo método da bolha.

A ordenação por bolha (bubble sort) é um algoritmo simples de ordenação que funciona iterando sobre a lista a ser ordenada, comparando cada par de elementos adjacentes e trocando as suas posições se estiverem na ordem errada.

- Varreduras sucessivas da lista são executadas, até que nenhuma troca seja necessária, o que indica que a lista está ordenada.

- O nome do algoritimo advém do modo como os elementos maiores “borbulham” para o final da lista.

Algoritmo
    1) Itere sobre todos os elementos da lista, começando com os 2 primeiros elementos.
    2) Se o elemento à esquerda for maior do que o elemento à direita, troque as posições.
    3) Repita os passos #1 e #2 até não haver mais trocas.
Links úteis:

5a) Escreva uma função para encontrar o máximo divisor comum e o mínimo múltiplo comum de dois inteiros positivos n1 e n2.

Exemplo: MDC (35, 1134) = 7 e MMC (35, 1134) = 5670.

Dicas:

- O mínimo múltiplo comum é o menor natural que é divisível por n1 e n2.

- O máximo divisor comum de dois números n1 e n2 é o produto dos seus fatores primos comuns.

- O mesmo fator pode ser usado várias vezes. Por exemplo,

       1386             = 2 × 3 × 3 × 7 × 11
       3213             = 3 × 3 × 3 × 7 × 17
       MDC (1386, 3213) =     3 × 3 × 7 = 63

- Se dois números não possuem fatores comuns, o MDC é 1

- Se a é divisível por b então MDC (a, b) = b

- Se a = bt + r, para dois inteiros positivos t (quociente) e r (resto), então MDC (a, b) = MDC (b, r).

       De fato, todo divisor comum de a e b também divide r. Logo, MDC (a, b) divide r.
       Como MDC (a,b) divide b, temos que MDC (a, b) ≤ MDC (b, r).
       Como todo divisor de b e r também divide a, temos que MDC (b, r) ≤ MDC (a, b).
       Logo, MDC (a, b) = MDC (b, r). 

       Portanto, como b < a e r < b, fazendo a = b e b = r = a % b,
       e repetindo este processo enquanto b != 0, irá encontrar o MDC rapidamente:

       def MDC (a,b):  # Euclid's algorithm
           while b:
               (a,b) = (b,a%b)
           return a

- O MDC entre três ou mais números é igual ao produto dos fatores primos comuns de todos os números:

       MDC(a, b, c) = MDC(a, MDC(b, c)) = MDC(MDC(a, b), c) = MDC(MDC(a, c), b)

- MMC (n1,n2) * MDC (n1,n2) = n1 * n2.

Links úteis:
5b) Escreva um programa para validar CPFs ou CNPJs.
Links úteis:
5c) Escreva em uma linha, como calcular o menor inteiro que possui como fatores todos os inteiros no intervalo [1,n].

Dica: use a função reduce e o MMC do ítem 5a) na forma de uma função lambda.
Links úteis:
5d) Escreva um programa para criptografar e decriptografar números pelo método RSA.

Dica: use o método de Euclides estendido para calcular o máximo divisor comum.
     O algoritmo de Euclides estendido é uma extensão do algoritmo de Euclides. 
     Além de encontrar o Máximo Divisor Comum dos inteiros a e b, como o algoritmo de Euclides 
     faz, ele também encontra dois inteiros x e y (um deles tipicamente negativo) 
     que satisfaz a identidade de Bézout: ax + by = MDC(a,b). 

     Este método computa expressões da forma ri = axi + byi 
     para o resto em cada passo i do algoritmo de Euclides. 

     ri = ri-2 - qiri-1

     ri = (axi-2 + byi-2) - qi(axi-1 + byi-1), que pode ser escrito como

     ri = a(xi-2 - qixi-1) + b(yi-2 - qiyi-1), que é da forma axi + byi

     Os dois valores iniciais são os argumentos iniciais do algoritmo:

     r1 = a = a*1 + b*0
     r2 = b = a*0 + b*1

     Então os coeficientes começam como x1 = 1, y1 = 0, x2 = 0, e y2 = 1, e os outros são dados por

     xi = xi-2 - qi*xi-1
     yi = yi-2 - qi*yi-1

     A expressão para o último resto não nulo fornece os resultados, 
     visto que este método computa cada resto em função de a e b, como desejado.
Exemplo: Compute o MDC de 120 e 23.
             a  b    q       r = a%b
     (1)    120÷23 = 5 resto 5
     (2)     23÷5  = 4 resto 3  a = b e b = r = a%b
     (3)      5÷3  = 1 resto 2
     (4)      3÷2  = 1 resto 1
     (5)      2÷1  = 2 resto 0 

     quando r = 0, em (5), tem−se que b = MDC(120,23) = 1

     Levando-se em conta apenas os restos encontrados, pode-se dizer que:

     (1)     5 = 1*120 - 5*23
     (2)     3 = 1*23 - 4*5   Substituindo o 5 temos
             3 = 1*23 - 4*(1*120 - 5*23)
             3 = -4*120 + 21*23
     (3)     2 = 1*5 - 1*3    Substituindo o valor de 5 e 3 temos
             2 = 1(1*120 - 5*23) - 1(-4*120 + 21*23)
             2 = 5*120 - 26*23
     (4)     1 = 1*3 - 1*2    Novamente substituindo 3 e 2
             1 = 1(-4*120 + 21*23) - 1(5*120 - 26*23)
             1 = -9*120 + 47*23

     portanto, x = -9 e y = 47 e temos: MDC(120,23) = 120 * (-9) + 47 * 23
Links úteis:

6a) Escreva um programa que leia uma palavra e diga se é um palíndromo.
Uma palavra é um palíndromo se é idêntica quando soletrada da direita para a esquerda.

Exemplo: "reler" é um palíndromo.

6b) Escreva um programa que leia duas palavras e responda se são palíndromos mútuos.
Duas palavras são palíndromos mútuos se são idênticas, quando uma delas é soletrada da direita para a esquerda.

Exemplo: "roma" e "amor" são palíndromos mútuos.

6c) Repita os exercícios acima, mas agora considerando frases anacíclicas (que formam palíndromos).
A única dificuldade adicional deste exercício reside em desconsiderar os espaços em branco, acentos e pontuação.

Exemplo: a frase "LUZA ROCELINA, A NAMORADA DO MANUEL, LEU NA MODA DA ROMANA: ANIL É COR AZUL" é anacíclica.

6d) Repita os exercícios acima, mas agora testando se palavras e frases são anagramas.
Um anagrama de uma palavra é outra palavra escrita com os mesmos caracteres.

Exemplo: "porta" e "tropa" são anagramas.

Obs: todos os palíndromos são também anagramas.

Links úteis:

7) Escreva um alarme que toque um arquivo MP3 em um hora pré-determinada do dia.

Dicas:

- Utilize o módulo time:

>>> import time
>>> t=list(time.localtime())
>>> t
[2012, 2, 22, 6, 46, 46, 2, 53, 1]
>>> ano = t[0]
>>> mes = t[1]
>>> dia = t[2]
>>> hora = t[3]
>>> minutos = t[4]
>>> segundos = t[5]

O programa deve testar continuamente se a hora corrente é igual a hora
do disparo do alarme. Para controlar a periodicidade deste teste,
a chamada time.sleep(0.1) suspende a execução do programa por 0.1 segundos.
- Utilize o player mpg123, ou o próprio Windows Media Player:
player = "C:\\Program Files\\Windows Media Player\\wmplayer.exe" # na versão em português está em "Arquivos de Programas"

player = "/usr/bin/mpg123"                                       # Linux

player = "/opt/local/bin/mpg123"                                 # MacOS
- Salve uma música qualquer, em C:\temp e use no programa da seguinte forma:
musica = "\"C:\\temp\\01 - Minha Musica.mp3\""                   # Windows

musica = "/tmp/01 - Minha Musica.mp3"                            # Linux
ou use diretamente o link da música e toque via protocolo http (streaming):
musica = "\"http://dl.lcg.ufrj.br/python/videos/01 - Minha Musica.mp3\""    # Windows

musica = "http://dl.lcg.ufrj.br/python/videos/01 - Minha Musica.mp3"        # Linux
- Execute o player com o método spawnv do módulo os:
os.spawnv (os.P_WAIT, player, ["mpg123", musica])

O argumento os.P_WAIT faz com que o programa continue apenas quando a música acabar. 
Links úteis:

8a) Escreva um programa que leia um texto, linha a linha, e o imprima emoldurado por asteriscos.

Dica: termine a entrada do texto quando for digitada uma linha vazia.

Exemplo: para a entrada

Digite linhas de texto (linha nula termina)
Python enables programs
to be written
compactly and readably

>>> 
o programa imprime:
 
**************************
*Python enables programs *
*to be written           *
*compactly and readably  *
**************************

8b) Considere a seguinte sessão com o interpretador Python:

    >>> help(xis)
Help on function xis in module __main__: xis(n) Gera uma string que, se impressa, corresponde a uma letra xis maiúscula escrita com asteriscos. A matriz de asteriscos tem tamanho (2n + 1) x (2n + 1) >>> xis(2) '* *\n * *\n *\n * *\n* *\n' >>> print xis(2) * * * * * * * * * >>> print xis(3) * * * * * * * * * * * * *
Pede-se: escreva a função xis(n).

8c) Implemente uma função que receba como entrada um número n e imprima o triângulo reto com comprimento de dois de seus lados iguais a n, usando os símbolos + e =, em suas quatro possíveis orientações. Por exemplo, se n=5, a saída deverá ser:

    +====  +++++  ====+  +++++
    ++===  ++++=  ===++  =++++
    +++==  +++==  ==+++  ==+++
    ++++=  ++===  =++++  ===++
    +++++  +====  +++++  ====+
Pede-se: escreva as funções rightTriangle(n, orientation) e getAllTriangles(n).

- A primeira retorna uma string com a representação do triângulo em uma das quatro possíveis orientações e

- a segunda intercala as quatro strings para imprimir os quatro triângulos.


9) Implemente o jogo conhecido como "Torres de Hanoi".

Links úteis:

10) Escreva um programa para decompor números naturais em fatores primos.

Exemplo: 173248246132375748867198458668657948626531982421875 = ['3^24', '5^14', '7^33', '13^1']

Links úteis:


11) Desafio:

Considere alguma sequência de elementos (difere de um mero conjunto de elementos por definir uma ordem entre os seus membros).
Enumere, então, todas as subsequências não-contínuas de uma dada sequência.

Dicas:

- Uma subsequência sempre contém algum subconjunto de elementos da sequência, na mesma ordem.

- Uma subsequência contínua é aquela em que nenhum elemento está faltando, entre o primeiro e o último elemento da subsequência.

Exemplo: (1,2,3,4) → [[1, 2, 4], [1, 3, 4], [1, 3], [1, 4], [2, 4]]
Links úteis:


/Paulo Roma.