[Caça ao tesouro] Neste problema você deve escrever uma função que receba uma matriz de números naturais com exatamente dois dígitos. Cada entrada da matriz tem uma dica para a próxima posição a ser visitada. O dígito das dezenas indica a linha e o dígito das unidades indica a coluna da próxima posição. Começando na posição [1,1], siga as dicas até encontrar a posição onde o número leva à própria posição. Essa posição é onde o tesouro está escondido. Seu programa deve imprimir as posições visitadas durante a busca e, ao final, indicar onde o tesouro foi encontrado. Por exemplo, considere a seguinte matriz:
34 21 32 41 25
14 52 43 14 31
54 45 52 42 23
33 15 51 31 35
21 52 33 13 23
O programa deve imprimir as seguintes posições visitadas:
[1,1] \rightarrow[3,4] \rightarrow[4,2] \rightarrow \ldots

Passo 1

O que o enunciado pede e o que temos de dado.
  • Pede-se escrever uma função que, dada uma matriz cujas entradas são números naturais de exatamente dois dígitos, siga “dicas” contidas nas células até encontrar a posição que aponta para si mesma (o tesouro). A saída deve mostrar as posições visitadas durante a busca e, ao final, indicar onde o tesouro foi encontrado.
  • Regras da dica: se uma célula contém o número de dois dígitos ab (onde a é o dígito das dezenas e b o das unidades), então ela indica a próxima posição [a,b] (linha a, coluna b). As linhas e colunas são indexadas começando em 1.
  • Começa-se em [1,1] e segue-se as dicas até encontrar uma posição [r,c] tal que o número na posição [r,c] é exatamente 10r+c (ou seja, aponta para si mesma).
  • O enunciado fornece uma matriz de exemplo (peguei os valores do enunciado):
\begin{pmatrix} 34 & 21 & 32 & 41 & 25 \\\\ 14 & 52 & 43 & 14 & 31 \\\\ 54 & 45 & 52 & 42 & 23 \\\\ 33 & 15 & 51 & 31 & 35 \\\\ 21 & 52 & 33 & 13 & 23 \end{pmatrix}
  • Perguntas explícitas a responder: mostrar a sequência de posições visitadas a partir de [1,1] até o local do tesouro; indicar a posição do tesouro.

Passo 2

Ideia do método (sem resolver ainda) e ferramentas matemáticas básicas necessárias.
  • Estratégia escolhida: simular o passeio seguindo as dicas, guardando a sequência de posições visitadas até achar a célula que aponta para si mesma. Esta estratégia é direta, eficiente e apropriada para o problema.
  • Como extrair a próxima posição de um número de dois dígitos n:
    • o dígito das dezenas é \left\lfloor \dfrac{n}{10} \right\rfloor;
    • o dígito das unidades é n \bmod 10.
      Exemplo: para n=34, \left\lfloor \dfrac{34}{10} \right\rfloor=3 e 34\bmod 10=4, logo aponta para [3,4].
  • Condição de parada (tesouro): estando em [r,c] e com n o valor na célula [r,c], o tesouro está aqui se e somente se
n = 10r + c.
  • Prevenção contra loops infinitos (precaução prática): manter um conjunto/lista das posições já visitadas; se for encontrado novamente um próximo passo que já foi visitado e esse passo não é um ponto que aponta para si mesmo, isso indica um ciclo sem tesouro (mas o enunciado assume caso bem-formulado onde o tesouro é alcançável). Ainda assim, implementar a verificação evita laços infinitos na execução.

Passo 3

Pseudocódigo claro e comentado (passo a passo que você pode implementar na prova).
  • Representação: a matriz será chamada de M. Use indexação 1-based nas explicações. Comece em r=1, c=1.
  • Pseudocódigo (descrito em passos verbais fáceis de converter para qualquer linguagem):
    1. Inicialize \text{seq} \leftarrow lista vazia para armazenar as posições visitadas.
    2. Defina r \leftarrow 1, c \leftarrow 1.
    3. Enquanto verdadeiro:
      • Anexe [r,c] ao final de \text{seq}.
      • Leia n \leftarrow M[r,c].
      • Calcule r_{\text{prox}} \leftarrow \left\lfloor \dfrac{n}{10} \right\rfloor e c_{\text{prox}} \leftarrow n \bmod 10.
      • Se n = 10r + c então pare: encontrou o tesouro em [r,c].
      • Senão, se [r_{\text{prox}},c_{\text{prox}}] já está em \text{seq} então pare para evitar loop (opcional: reportar erro). Caso contrário, atualize r \leftarrow r_{\text{prox}}, c \leftarrow c_{\text{prox}} e repita.
  • Observações práticas:
    • Ao implementar em linguagens com indexação 0-based (ex.: C, Java, Python), faça a conversão apropriada ao acessar a matriz: M[r,c] na nossa notação 1-based corresponde a M[r-1][c-1].
    • A extração de dígitos é simples com operadores inteiros: em pseudocódigo, r_{\text{prox}} = n \div 10 e c_{\text{prox}} = n \bmod 10.

Passo 4

Aplicando o método passo a passo no exemplo fornecido — vou seguir a sequência desde [1,1] e mostrar cada cálculo explicitamente.
  • Estado inicial: [r,c]=[1,1]. Anoto [1,1] na sequência.
    • n = M[1,1] = 34.
    • \left\lfloor \dfrac{34}{10} \right\rfloor = 3,\quad 34 \bmod 10 = 4.
    • Próxima posição: [3,4].
    • Verifico se 34 = 10\cdot 1 + 1 = 11. Não é, então não é tesouro.
  • Em [3,4]. Anoto [3,4].
    • n = M[3,4] = 42.
    • \left\lfloor \dfrac{42}{10} \right\rfloor = 4,\quad 42 \bmod 10 = 2.
    • Próxima posição: [4,2].
    • Verifico se 42 = 10\cdot 3 + 4 = 34. Não é.
  • Em [4,2]. Anoto [4,2].
    • n = M[4,2] = 15.
    • \left\lfloor \dfrac{15}{10} \right\rfloor = 1,\quad 15 \bmod 10 = 5.
    • Próxima posição: [1,5].
    • Verifico se 15 = 10\cdot 4 + 2 = 42. Não é.
  • Em [1,5]. Anoto [1,5].
    • n = M[1,5] = 25.
    • \left\lfloor \dfrac{25}{10} \right\rfloor = 2,\quad 25 \bmod 10 = 5.
    • Próxima posição: [2,5].
    • Verifico se 25 = 10\cdot 1 + 5 = 15. Não é.
  • Em [2,5]. Anoto [2,5].
    • n = M[2,5] = 31.
    • \left\lfloor \dfrac{31}{10} \right\rfloor = 3,\quad 31 \bmod 10 = 1.
    • Próxima posição: [3,1].
    • Verifico se 31 = 10\cdot 2 + 5 = 25. Não é.
  • Em [3,1]. Anoto [3,1].
    • n = M[3,1] = 54.
    • \left\lfloor \dfrac{54}{10} \right\rfloor = 5,\quad 54 \bmod 10 = 4.
    • Próxima posição: [5,4].
    • Verifico se 54 = 10\cdot 3 + 1 = 31. Não é.
  • Em [5,4]. Anoto [5,4].
    • n = M[5,4] = 13.
    • \left\lfloor \dfrac{13}{10} \right\rfloor = 1,\quad 13 \bmod 10 = 3.
    • Próxima posição: [1,3].
    • Verifico se 13 = 10\cdot 5 + 4 = 54. Não é.
  • Em [1,3]. Anoto [1,3].
    • n = M[1,3] = 32.
    • \left\lfloor \dfrac{32}{10} \right\rfloor = 3,\quad 32 \bmod 10 = 2.
    • Próxima posição: [3,2].
    • Verifico se 32 = 10\cdot 1 + 3 = 13. Não é.
  • Em [3,2]. Anoto [3,2].
    • n = M[3,2] = 45.
    • \left\lfloor \dfrac{45}{10} \right\rfloor = 4,\quad 45 \bmod 10 = 5.
    • Próxima posição: [4,5].
    • Verifico se 45 = 10\cdot 3 + 2 = 32. Não é.
  • Em [4,5]. Anoto [4,5].
    • n = M[4,5] = 35.
    • \left\lfloor \dfrac{35}{10} \right\rfloor = 3,\quad 35 \bmod 10 = 5.
    • Próxima posição: [3,5].
    • Verifico se 35 = 10\cdot 4 + 5 = 45. Não é.
  • Em [3,5]. Anoto [3,5].
    • n = M[3,5] = 23.
    • \left\lfloor \dfrac{23}{10} \right\rfloor = 2,\quad 23 \bmod 10 = 3.
    • Próxima posição: [2,3].
    • Verifico se 23 = 10\cdot 3 + 5 = 35. Não é.
  • Em [2,3]. Anoto [2,3].
    • n = M[2,3] = 43.
    • \left\lfloor \dfrac{43}{10} \right\rfloor = 4,\quad 43 \bmod 10 = 3.
    • Próxima posição: [4,3].
    • Verifico se 43 = 10\cdot 2 + 3 = 23. Não é.
  • Em [4,3]. Anoto [4,3].
    • n = M[4,3] = 51.
    • \left\lfloor \dfrac{51}{10} \right\rfloor = 5,\quad 51 \bmod 10 = 1.
    • Próxima posição: [5,1].
    • Verifico se 51 = 10\cdot 4 + 3 = 43. Não é.
  • Em [5,1]. Anoto [5,1].
    • n = M[5,1] = 21.
    • \left\lfloor \dfrac{21}{10} \right\rfloor = 2,\quad 21 \bmod 10 = 1.
    • Próxima posição: [2,1].
    • Verifico se 21 = 10\cdot 5 + 1 = 51. Não é.
  • Em [2,1]. Anoto [2,1].
    • n = M[2,1] = 14.
    • \left\lfloor \dfrac{14}{10} \right\rfloor = 1,\quad 14 \bmod 10 = 4.
    • Próxima posição: [1,4].
    • Verifico se 14 = 10\cdot 2 + 1 = 21. Não é.
  • Em [1,4]. Anoto [1,4].
    • n = M[1,4] = 41.
    • \left\lfloor \dfrac{41}{10} \right\rfloor = 4,\quad 41 \bmod 10 = 1.
    • Próxima posição: [4,1].
    • Verifico se 41 = 10\cdot 1 + 4 = 14. Não é.
  • Em [4,1]. Anoto [4,1].
    • n = M[4,1] = 33.
    • \left\lfloor \dfrac{33}{10} \right\rfloor = 3,\quad 33 \bmod 10 = 3.
    • Próxima posição: [3,3].
    • Verifico se 33 = 10\cdot 4 + 1 = 41. Não é.
  • Em [3,3]. Anoto [3,3].
    • n = M[3,3] = 52.
    • \left\lfloor \dfrac{52}{10} \right\rfloor = 5,\quad 52 \bmod 10 = 2.
    • Próxima posição: [5,2].
    • Verifico se 52 = 10\cdot 3 + 3 = 33. Não é.
  • Em [5,2]. Anoto [5,2].
    • n = M[5,2] = 52.
    • \left\lfloor \dfrac{52}{10} \right\rfloor = 5,\quad 52 \bmod 10 = 2.
    • Próxima posição calculada: [5,2] (a própria).
    • Verifico se 52 = 10\cdot 5 + 2 = 52. Sim! Condição de tesouro satisfeita → pare aqui.
  • Sequência completa de posições visitadas (na ordem):
    [1,1]\rightarrow[3,4]\rightarrow[4,2]\rightarrow[1,5]\rightarrow[2,5]\rightarrow[3,1]\rightarrow[5,4]\rightarrow[1,3]\rightarrow[3,2]\rightarrow[4,5]\rightarrow[3,5]\rightarrow[2,3]\rightarrow[4,3]\rightarrow[5,1]\rightarrow[2,1]\rightarrow[1,4]\rightarrow[4,1]\rightarrow[3,3]\rightarrow[5,2].
  • O tesouro ficou em [5,2] porque nessa posição o número é 52, que aponta exatamente para [5,2].

Passo 5

Como imprimir/formatar a resposta na prática e dicas finais rápidas.
  • Formato sugerido (exatamente o que o enunciado pediu): imprimir a sequência de posições visitadas com setas ( \rightarrow) e, em seguida, indicar a posição do tesouro.
  • Em código: construa a lista \text{seq} durante a simulação e depois mostre algo como
    • primeira linha: [1,1] \rightarrow [3,4] \rightarrow \cdots \rightarrow [5,2]
    • segunda linha: [5,2] (ou uma legenda curta, por exemplo, “Tesouro em [5,2]”).
  • Dica de prova: memorize a operação para extrair dezenas e unidades (divisão inteira por 10 e resto por 10). Sempre registre as posições visitadas para evitar laços infinitos durante código/manual.

Resposta

[1,1] \rightarrow[3,4] \rightarrow[4,2] \rightarrow[1,5] \rightarrow[2,5] \rightarrow[3,1] \rightarrow[5,4] \rightarrow[1,3] \rightarrow[3,2] \rightarrow[4,5] \rightarrow[3,5] \rightarrow[2,3] \rightarrow[4,3] \rightarrow[5,1] \rightarrow[2,1] \rightarrow[1,4] \rightarrow[4,1] \rightarrow[3,3] \rightarrow[5,2]
[5,2]

Exercícios relacionados