Questão 10: Na sequência de Collatz, se n é par,
; se n é ímpar,
1. Crie uma função contar_passos_collatz (n) que retorne quantos “passos”(iterações do while) são necessários para n chegar até 1 .
Exemplo: contar_passos_collatz
deve retornar 8.
Passo 1
O enunciado pede para criar uma função chamada , aplique a regra da sequência de Collatz repetidamente até que
chegue a
, e retorne quantos “passos” (iterações do laço
contar_passos_collatz que, dada uma entrada inteira positiva
while) foram necessários. As regras são:- se
é par, substituir por ; - se
é ímpar, substituir por .
O enunciado dá um exemplo explícito: para
a sequência é
e a função deve retornar
(porque foram
iterações até alcançar
).
Informações relevantes dadas:
- entrada: um inteiro
(assumiremos ); - saída: um inteiro que é o número de iterações necessárias para
chegar a ; - as operações envolvidas são divisão inteira por
quando é par, e multiplicação por mais quando é ímpar; - a contagem deve considerar cada aplicação da regra como um passo (cada iteração do
while).
Passo 2
Definição clara do que vamos implementar (sem ainda programar): queremos um procedimento iterativo que:
- receba um inteiro
; - repita enquanto
: - testar paridade de
; - atualizar
conforme a regra de Collatz; - incrementar um contador de passos;
- testar paridade de
- ao sair do laço, retornar o contador.
Observações importantes e suposições:
- se
, não precisamos fazer nenhuma iteração e o resultado deve ser ; - assumimos
inteiro positivo; se recebermos outro tipo de entrada, é razoável sinalizar erro (vamos tratar isso na implementação final); - a conjectura de Collatz afirma que toda
positiva alcança , e aqui o enunciado assume que a sequência de fato chega a (ou seja, podemos usar while n != 1sem nos preocupar com um laço infinito para os casos do enunciado).
Passo 3
Vamos explicar cada parte do algoritmo com calma (aquelas coisas que costumam aparecer na prova).
-
Contador de passos: precisamos de uma variável inteira
inicializada em . Essa variável contabiliza quantas vezes aplicamos a regra até chegar em . -
Teste de paridade: para decidir se
é par ou ímpar usamos o resto da divisão por , ou seja, o operador .
-
é par se . -
é ímpar se .
Exemplos rápidos:
(par);
(ímpar).
- Atualização de
:
- se
é par, fazemos . Na maioria das linguagens de programação precisamos garantir divisão inteira; em Python usamos n //= 2para manterinteiro; - se
é ímpar, fazemos .
-
Estrutura de repetição: enquanto
repetimos os passos 2–3. Cada vez que entramos no corpo do laço incrementamos em . -
Caso base: se a entrada já for
, o whilenão é executado e retornamos.
Passo 4
Vamos ver o pseudocódigo e explicar linha a linha (é assim que eu faria numa prova se pedissem o algoritmo):
Pseudocódigo:
- receber
- se
então sinalizar erro (entrada inválida) -
- enquanto
faça: - se
então - senão
-
- se
- retornar
Explicação de cada linha:
- "receber
" indica que a função aceita um argumento inteiro; - checagem
: protege contra entradas inválidas (zero ou negativas); - inicialização
: conta a quantidade de iterações; - condição do
while: mantemos o laço enquanto não atingimos o objetivo; - dentro do
whileaplicamos a regra adequada (par/ímpar) e aumentamos o contador; - ao terminar, retornamos o total acumulado em
.
Passo 5
Traço detalhado do exemplo
(esse traço é o que facilita muito aprender pela prática — faça parecido na prova!):
Inicialmente
,
.
Iteração 1:
-
(par), então . -
.
Sequência até aqui:.
Iteração 2:
-
(ímpar), então . -
.
Sequência:.
Iteração 3:
-
é par, . -
.
Sequência:.
Iteração 4:
-
é ímpar, . -
.
Sequência:.
Iteração 5:
-
é par, . -
.
Sequência:.
Iteração 6:
-
é par, . -
.
Sequência:.
Iteração 7:
-
é par, . -
.
Sequência:.
Iteração 8:
-
é par, . -
.
Sequência final:.
Agora
, saímos do , que é exatamente o resultado esperado no exemplo.
while e retornamos
Passo 6
Dicas práticas e observações (úteis para a prova e para implementar sem erro):
- Use divisão inteira ao dividir por
para manter como inteiro (em Python use //). - Proteja a função contra entradas inválidas (por exemplo,
n <= 0) e explique na resposta que o domínio é. - Em Python não precisamos nos preocupar com overflow de inteiros (eles têm precisão arbitrária), então valores grandes de
não causarão erro de overflow, apenas podem necessitar de muitas iterações. - A conjectura de Collatz ainda não foi provada globalmente, mas para o contexto do exercício assumimos que a sequência chega a
em tempo finito para as entradas de interesse.
Passo 7
Preparação final para implementar em código: a versão que vou retornar é direta, clara e segue o pseudocódigo explicado. Ela:
- verifica se
é inteiro positivo; - inicializa o contador;
- executa o
while n != 1aplicando as regras de par/ímpar; - incrementa o contador a cada iteração;
- retorna o contador.
Agora eu disponibilizo a implementação final em Python abaixo na seção de resposta.
Resposta
def contar_passos_collatz(n):
“”"
Retorna o número de iterações necessárias para que n alcance 1
pela regra de Collatz:
- se n é par: n = n // 2
- se n é ímpar: n = 3*n + 1
Entrada: n (inteiro, n >= 1)
Saída: número inteiro de passos
“”"
if not isinstance(n, int) or n < 1:
raise ValueError(“n deve ser um inteiro positivo (n >= 1)”)
passos = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
n = 3 * n + 1
passos += 1
return passos
“”"
Retorna o número de iterações necessárias para que n alcance 1
pela regra de Collatz:
- se n é par: n = n // 2
- se n é ímpar: n = 3*n + 1
Entrada: n (inteiro, n >= 1)
Saída: número inteiro de passos
“”"
if not isinstance(n, int) or n < 1:
raise ValueError(“n deve ser um inteiro positivo (n >= 1)”)
passos = 0
while n != 1:
if n % 2 == 0:
n //= 2
else:
n = 3 * n + 1
passos += 1
return passos