Considere a função
e o seguinte cabeçalho desta função escrito na linguagem C:
int pot( int n, int k ) {
}
Escreva a função pot de forma iterativa.
int pot( int n, int k ) {
}
Passo 1
O enunciado pede para implementar de forma iterativa a função que calcula a potência inteira
usando o cabeçalho em C
int pot( int n, int k ) {
}
Informações relevantes que o enunciado dá:
-
e são parâmetros do tipo inteiro. - A função deve retornar um inteiro que representa
. - Não foi dito nada sobre
negativo; vou considerar que o enunciado está formulado corretamente para uso em prova, então assumimos que é um inteiro não negativo ( ). Se for negativo, o resultado em geral não é um inteiro (seria fração), portanto essa implementação iterative básica não trata expoentes negativos.
O que se pede explicitamente: escrever a função iterativa que calcule
e retorne o resultado como um inteiro.
Passo 2
Ideia básica (explicação didática): calcular
multiplicando
por si mesmo
vezes. Para isso usamos:
- Uma variável acumuladora chamada de resultado inicializada em
. Isto porque é o elemento neutro da multiplicação: para qualquer inteiro vale . - Um laço que repete exatamente
vezes: a cada iteração multiplicamos o acumulador por .
Por exemplo, para calcular
fazemos:
- inicio: res =
- 1ª iteração: res = res
(aqui res = ) - 2ª iteração: res = res
(res = ) - 3ª iteração: res = res
(res = ) - 4ª iteração: res = res
(res = )
Ou seja, depois de
iterações teremos res =
. Assim, após
iterações res =
.
Passo 3
Detalhes importantes para implementar corretamente:
- Inicializar o acumulador com
: int res = 1;. - Fazer um laço que execute exatamente
vezes. Em C uma forma comum é for (int i = 0; i < k; ++i). - Em cada iteração actualizar
rescomres *= n;. - Ao final, retornar
res.
Propriedade de correção (intuição rápida): invariantemente, no início de cada iteração com índice
(com
) temos e aumenta em
e multiplicamos por
, então a propriedade se mantém. Ao terminar com
,
res == n^i. Inicialmente
res=1=n^0. A cada iteração
res = n^k.Observações práticas:
- Caso
o laço não roda e retornamos , que é correto pois para qualquer inteiro (implementação também retorna para o caso ambíguo ; muitos exercícios de programação aceitam esse comportamento). - Se
e o algoritmo retorna (correto: para ). - Cuidado com overflow: se
exceder o intervalo de int, o resultado vai “estourar”. Em prova você cite (se pedirem) que há risco de overflow, mas a implementação padrão é essa. - Complexidade: tempo
e espaço .
Passo 4
Exemplo passo a passo numérico para fixar (usei
e
):
- res = 1
- i=0: res = 1 * 2 = 2
- i=1: res = 2 * 2 = 4
- i=2: res = 4 * 2 = 8
- i=3: res = 8 * 2 = 16
- i=4: res = 16 * 2 = 32
Fim do laço: res = 32 que é.
Observação sobre alternativas: existe um método mais rápido chamado “exponentiação por repetição rápida” (exponentiation by squaring) com complexidade
. Ele é útil se
é grande, mas é um pouco mais sofisticado. Como a questão pediu uma implementação iterativa simples, o método por multiplicação repetida é o esperado em provas iniciais.
Passo 5
Implementação em C (iterativa simples). Esta é a resposta pronta para colar no seu código de prova:
Resposta
int pot( int n, int k ) {
int res = 1;
for ( int i = 0; i < k; ++i ) {
res *= n;
}
return res;
}