Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente…

Questão

Projete em pseudocódigo uma função recursiva que verifica se uma lista de inteiros L está estritamente crescente (cada elemento maior que o anterior). Explique a correção da recursão e analise sua complexidade temporal.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: func crescente(L): se len(L) <= 1 então retorne verdadeiro se L[0] >= L[1] então retorne falso retorne crescente(L[1:]) Corretude (esboço): - Caso base: listas de tamanho 0 ou 1 são estritamente crescentes por definição, então função retorna verdadeiro. - Passo indutivo: suponha que crescente(L[1:]) verifica corretamente a propriedade para listas menores. Se L[0] < L[1] e a sublista L[1:] é estritamente crescente, então toda L é estritamente crescente. Se L[0] >= L[1] função detecta e retorna falso imediatamente. - Assim, por indução, a função é correta. Complexidade temporal: - Cada chamada recursiva faz uma comparação e reduz o tamanho da lista em 1, resultando em O(n) comparações para lista de tamanho n. O custo espacial depende da profundidade de recursão O(n) na chamada de pilha (ou O(1) se transformada em iteração).

Explicação

A função verifica a propriedade de estrita crescente ao comparar elementos adjacentes e, se necessário, chama a si mesma com a sublista restante. O caso base garante que listas pequenas são tratadas corretamente, enquanto o passo indutivo assegura que a propriedade se mantém ao longo da lista. A análise da complexidade temporal demonstra que a função é linear em relação ao tamanho da lista, o que é eficiente para essa tarefa.

Raio-X da questão

Questões parecidas com resolução

• Em uma usina, cada estado de uma turbina é registrado com um código de dois bits: | Estado | Código | |---|---| | Parada…
• No controle de um satélite, um gráfico de barras descrito pela equipe registra: com o sistema operacional iniciado, o…
• O clube de jogos da escola vai usar um programa simples para registrar cada participante. Em cada cadastro, a pessoa…
• Na horta da escola, uma estação simples registra a temperatura informada por um sensor. O programa deve mostrar essa…
• Pesquisadores acompanham o funcionamento de um robô que cuida de seis placas solares em uma estação de pesquisa. O robô…
• Por que alguns tablets de um centro cultural aparecem como disponíveis, embora estejam guardados para conserto? Para…

Todas as questões de Programação - Linguagem de programação