Logo Passei Direto
Buscar
A técnica de divisão e conquista é uma estratégia que envolve resolver problemas aplicando três etapas gerais, a de dividir um problema em subproblemas menores, conquistar ou resolver cada subproblema e depois combinar os resultados dos subproblemas para compor a solução do problema geral. Esta técnica pode ser aplicada em diversos tipos de problemas: de ordenação (MergeSort e QuickSort), de pesquisa e na multiplicação de matrizes. O algoritmo a seguir é um exemplo da aplicação da divisão e conquista concretizada em uma função recursiva para multiplicação de matrizes. Ele está expresso em pseudocódigo, por exemplo, percebe-se que para manter compatibilidade de chamada, as invocações internas de MMQ-Recursivo deve considerar o parâmetro n divided by 2. O objetivo é uma compreensão geral do algoritmo estudado. Assinale a alternativa que calcula a quantidade de vezes que a função MMQ-Recursivo será executada para multiplicar duas matrizes 4x4. a. 73 b. 41 c. 129 d. 9 e. 17
User badge image
cesar correa

mês passado

User badge image
cesar correa

mês passado

Respostas

User badge image

Ed Verified user icon

mês passado

Para calcular a quantidade de vezes que a função MMQ-Recursivo será executada para multiplicar duas matrizes 4x4 usando a técnica de divisão e conquista, precisamos entender como a recursão funciona nesse contexto. A multiplicação de matrizes usando divisão e conquista geralmente envolve dividir as matrizes em submatrizes menores. Para matrizes 4x4, a divisão resulta em 4 submatrizes 2x2. Cada chamada recursiva para multiplicar essas submatrizes também envolve mais chamadas recursivas. A quantidade de chamadas recursivas pode ser expressa pela relação de recorrência. Para multiplicar duas matrizes de tamanho n x n, a relação é: T(n) = 8T(n/2) + O(1) Para n = 4, temos: T(4) = 8T(2) + O(1) E continuando: T(2) = 8T(1) + O(1) T(1) é uma operação básica, então podemos considerar que T(1) = 1. Substituindo: T(2) = 8(1) + O(1) = 8 + O(1) = 8 T(4) = 8(8) + O(1) = 64 + O(1) = 64 Portanto, a quantidade total de chamadas da função MMQ-Recursivo para multiplicar duas matrizes 4x4 é 64. Nenhuma das alternativas apresentadas (73, 41, 129, 9, 17) corresponde a esse resultado. Parece que a pergunta pode estar faltando informações ou a relação de recorrência pode ser diferente da que consideramos. Dessa forma, você precisa criar uma nova pergunta.

Essa resposta te ajudou?

0
Dislike0
left-side-bubbles-backgroundright-side-bubbles-background

Crie sua conta grátis para liberar essa resposta. 🤩

Já tem uma conta?

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina