. -- coding: utf-8 --

Repetições encaixadas

Tópicos e objetivos

  • identificar situações onde é necessário utilizar repetições encaixadas;

  • utilizar repetições encaixadas em seus programas;

  • utilizar indicadores de passagem em repetições encaixadas;

  • simular programas com repetições encaixadas.

Introdução

Uma característica importante dos computadores é executar ações repetitivas inúmeras vezes sem se cansar, sempre com a mesma precisão e desempenho. Ações complexas precisam ser decompostas para que possam ser mais facilmente descritas na forma de um algoritmo. A habilidade de resolver problemas computacionais depende muito da habilidade de decompor problemas em problemas mais simples e, uma vez que as soluções dos problemas mais simples forem desenvolvidas, precisamos compor essas soluções para resolver os problemas mais complexos.

Tanto os comandos de execução condicional quanto os de repetição podem ser “encaixados”, ou seja, um comando de repetição pode ser colocado dentro de outra repetição, como por exemplo:

while condição_1:
    # bloco do while 1

    while condição_2:
        # bloco do while 2

        while condição_3:
            # bloco do while 3

        # instruções após fim do while condição_3
    # instruções após fim do while condição_2
# instruções após fim do while condição_1

Problema de motivação

Considere a função \(y + x y - x^2\).

Uma forma computacional para estimar o máximo dessa função dentro de um intervalo é testar vários pares (x,y), “procurando” pela solução. A ideia é escrever um programa que gera todos os pares (x,y) para encontrar o par que corresponde ao máximo da função.

Exemplo

Vamos considerar apenas os números inteiros no intervalo 0 <= x <= 2 e 0 <= y <= 3. Para gerar todos os pares (x,y) nesse intervalo devemos varrer todos os valores de x e, para cada valor de x, varrer todos os valores de y, algo como:

Execute esse código no activecode. A saída é mostrada abaixo:

para x igual a 0
    ( 0 , 0 )
    ( 0 , 1 )
    ( 0 , 2 )
    ( 0 , 3 )
para x igual a 1
    ( 1 , 0 )
    ( 1 , 1 )
    ( 1 , 2 )
    ( 1 , 3 )
para x igual a 2
    ( 2 , 0 )
    ( 2 , 1 )
    ( 2 , 2 )
    ( 2 , 3 )

Estude o código acima e verifique que o bloco de comandos que controla a varredura dos valores de x é muito parecido com o de y, como no trecho a seguir.

# comandos que controlam a varredura dos valores de x
x_inicial = 0
x_final   = 2

x = x_inicial
while x <= x_final:

    x = x + 1

Calculando o ponto de máximo

Agora que sabemos varrer todos os pares (x,y), para determinar o ponto de máximo podemos usar a seguinte ideia:

  • No início, não sabemos qual é o ponto de máximo.
    • Assim, vamos assumir que o máximo é um ponto qualquer

    • como o ponto (0,0)

  • O valor máximo é iniciado com o valor da função nesse ponto inicial

  • Varremos agora todos os pontos, um de cada vez
    • calculamos o valor da função nesse ponto (x,y)

    • se o valor no ponto for maior que o valor visto até agora
      • atualizamos o valor com esse novo valor de máximo

Em pseudo código, mais perto de Python, podemos escrever:

# Vamos usar o ponto (0,0) como ponto máximo inicial
x_max = 0
y_max = 0
v_max = valor da função no ponto inicial (x_max, y_max)

para cada novo par (x,y) no intervalo:
    valor = valor da função em (x,y)
    se valor > máximo:
        v_max = valor
        x_max = x
        y_max = y

imprima o valor v_max e as coordenadas x_max e y_max

Lembre-se agora que, para varrer os pontos, usamos a repetição encaixada como vimos anteriormente e obtemos o seguinte código em Python:

Exercícios

Exercício 1

Dado um número inteiro n, n > 1, imprimir sua decomposição em fatores primos, indicando também a mutiplicidade de cada fator.

Por exemplo, para n = 600, a saída deverá ser:

fator 2 multiplicidade 3
fator 3 multiplicidade 1
fator 5 multiplicidade 2

Clique aqui para ver uma solução.

Exercício 2

Dados um número inteiro n > 0 e uma sequência com n números inteiros maiores do que zero, determinar o máximo divisor comum entre eles.

Por exemplo, para a sequência

3    42    105

o seu programa deve escrever o número 3.

Clique aqui para ver uma solução.

Exercício 3

Dados um número inteiro n, n > 0, e uma sequência com n números inteiros maiores do que zero, determinar o fatorial de cada número da sequência.

Clique aqui para ver uma solução.

Exercício 4

Dada uma sequência de números inteiros maiores que um, terminada por um zero, determinar quantos números primos há na sequência.

Clique aqui para ver uma solução.

Exercício 5

Sabe-se que cada número da forma n**3 é igual a soma de n ímpares consecutivos. Por exemplo,

1**3 = 2
2**3 = 3 + 5
3**3 = 7 + 9 + 11
4**3 = 13 + 15 + 17 + 19

Dado um número inteiro m, m > 0, determinar os ímpares consecutivos cuja soma é igual a n**3, para n assumindo valores de 1 a m.

Next Section - Números reais