A sequência 3n + 1¶
Como um exemplo de iteração indeterminada, vejamos uma sequência que tem fascinado os matemáticos há anos: a sequência 3n+1, também chamada de Conjectura de Collatz. A regra para criar a sequência é começar por um determinado número (n) e gerar o número seguinte através de uma regra simples:
Se
nfor par, o próximo número será o atual dividido por 2 (divisão inteira).Se
nfor ímpar, o próximo número será o atual multiplicado por 3 e adicionado a 1 (o valor 3n+1).
A sequência termina quando n chegar a 1.
O programa abaixo produz essa sequência. Tente executá-lo diversas vezes, fornecendo valores diferentes para n.
A condição desse loop é n != 1. Ou seja, o loop continuará executando até que n == 1.
A cada passagem pelo bloco, o programa mostra o valor de n e então verifica se ele é par ou ímpar usando o operador %. Se for par, o valor de n é dividido por 2 usando o operador de divisão inteira (//). Se for ímpar, o valor é substituído por n * 3 + 1.
Tente outros valores para n.
Uma vez que n às vezes aumenta e às vezes diminui, não há uma prova óbvia que n sequer chegará a 1, ou que o programa terminará. Para alguns valores particulares de n, nós podemos provar que o programa termina. Por exemplo, se o valor de n for uma potência de 2, então o valor de n será par a cada passagem, até que chegue a 1.
Você pode experimentar um pouco e verificar se consegue achar um número inicial pequeno que exija mais do que uma centena de passos antes de terminar…
- target
Valor específicos à parte, a questão interessante é se podemos provar que esta sequência termina para qualquer valor de n. Até hoje, ninguém conseguiu provar isso, ou o contrário!
Pense um pouco o que seria necessário para provar essa hipótese: todos os números inteiros irão eventualmente convergir para 1. Com os computadores rápidos que temos hoje, já foi possível testar números inteiros bem grandes, e até agora, todos chegaram em 1. Mas isso não significa que não haja um número ainda não testado que, por algum motivo desconhecido, não chegue em 1.
Você também irá notar que se não pararmos o loop ao atingirmos 1, a própria sequência entra em um loop: 1, 4, 2, 1, 4, 2, 1, 4, … Uma possibilidade é que possa haver outros ciclos que ninguém ainda encontrou.
Escolhendo entre for e while
Use um comando for se você sabe a quantidade de vezes que precisa executar os comandos. Por exemplo, se você está percorrendo uma lista de elementos ou se está utilizando a função range.
Portanto, o comando for é ideal para qualquer problema do tipo “execute 1000 vezes esse modelo de previsão climática”, ou “procure nesta lista de palavras…”, ou ainda “verifique quantos primos existem em todos os inteiros até 10000”.
Em contrapartida, se você precisa repetir determinado cálculo até que determinada condição seja atingida (como no problema do 3n +1), use um comando while.
Como observamos antes, o primeiro caso é denominado iteração determinada — nós sabemos quantas vezes deve repetir. O segundo caso é chamado de iteração indeterminada — nós não sabemos quantas vezes precisará repetir.
Veja se você entendeu
- Sim.
- Ninguém ainda conseguiu provar que a sequência 3n+1 termina para qualquer valor de n.
- Não.
- Ninguém conseguiu refutar que a sequência 3n+1 irá terminar para qualquer valor de n. Em outras palavras, pode ainda haver algum valor de n que não permita a sequência terminar - mas ele ainda não foi encontrado.
- Ninguém sabe.
- Ninguém provou ou refutou que a sequência termina para qualquer valor de n, portanto não é possível afirmar que o loop irá terminar para qualquer valor de n.
iter-5-1: Considere o programa que exiba a sequência 3n+1. A repetição neste código irá sempre terminar para qualquer valor de n?
while