Questão 53299
UFPR 2015
(UFPR - 2015 - 2ª FASE)
O tempo, em milissegundos, gasto por um programa num computador para processar n entradas diferentes de um problema é dado pela expressão
a) Quantas entradas esse programa é capaz de processar no tempo máximo de 1 segundo?
b) Sabe-se que esse programa é composto por dois blocos e que o tempo total de processamento é o produto do tempo de
processamento de cada um desses blocos. Se o tempo de processamento de um dos blocos é ,determine o polinômio
que fornece o tempo de processamento do outro bloco.
Gabarito:
Resolução:
a) Um segundo é igual a 1.000 milissegundos, sendo assim, teremos:
Como n é número inteiro, de cara podemos perceber que quando n = 10, a parte esquerda da equação fica maior do que 0. Logo o número máximo de entradas será 9, verificando, temos:
Com isso vemos que a solução da equação , está entre 9 e 10.
b) Fazendo a divisão por Briot-Ruffini, temos:
Com isso obtemos que , sendo portanto,
.