Os quebradinhos - potencias perfeitas

Disponível somente no TrabalhosFeitos
  • Páginas : 7 (1688 palavras )
  • Download(s) : 0
  • Publicado : 21 de outubro de 2012
Ler documento completo
Amostra do texto
O número secreto

Eduardo Rutkoski Didio

Faculdade de Informática - PUCRS

13 de abril de 2012

Resumo
Este artigo mostra alternativas para a solução do primeiro problema proposto pela disciplina, de encontrar “O número secreto”, que consiste em achar o 3º menor número que é uma quinta potência perfeita, um cubo perfeito e um quadrado perfeito.
O mesmo também apresentará análise de tempo edesempenho do algoritmo, juntamente com notações de simplificação e economia de cálculos para sua melhor performance.

Introdução
A disciplina de Algoritmos e Programações III, teve como primeiro trabalho a ser desenvolvido um algoritmo, que de forma eficiente, calculá-se um número x, e assim fazer uma análise do mesmo. Esta tarefa se resume em encontrar o terceiro menor número que é uma quintapotência perfeita, um cubo perfeito e um quadrado perfeito.
Exemplificando:
* Caso 1: 2x2x2x2x2=32 é o mesmo que 25=32. Logo o número 32 é uma quinta potência perfeita.
* Caso 2: 2x2x2=8 é o mesmo que 2³=8. Logo o número 8 é um cubo perfeito.
* Caso 3: 2x2=4 é o mesmo que 2²=4. Logo o número 4 é um quadrado perfeito
Para uma melhor notação, quando tratarmos de expontes usaremos ^ paramostrar a elevação de um número.
Estando ao par do problema, nos deparamos com o número 1, que obedece as regras acima, pois qualquer expoente que eleve o número 1, seu resultado sera 1.
Exemplo:
1²=1; 1³=1; 15=1.


Sabendo isto, eliminaremos o número 1 e partiremos para encotrar o segundo menor número que corresponde as especificações acima.
Dividiremos este artigos em 3 fases
*Fase 1: Combinações
1.1 Entendimento prévio
1.2 Análise de um algoritmo não eficiente
1.3 Análise de um algoritmo eficiente
* Fase 2: Resultados
1.1 Algoritmo não eficiente
1.2 Algoritmo eficiente
* Fase 3: Conclusão

Fase 1: Combinações
1.1 Entendimento prévio
Partindo de um princípio de eficiência e agilidade, não faremos calculos desnescessários, mas paraum maior entendimento, a tabela abaixo mostrará o princípio lógico da resolução do problema.

Elevado na 5 | Elevado na 3 | Elevado na 2 |
2^5= 32 | 2^3= 8 | 2^2= 4 |
3^5= 243 | 3^3= 27 | 3^2= 9 |
4^5= 1024 | 4^3= 64 | 4^2= 16 |
5^5= 3125 | 5^3= 125 | 5^2= 25 |
6^5= 7776 | … | … |
7^5= 16807 | 31^3= 29791 | 181^2= 32761 |
8^5= 32768 | 32^3= 32768 | 182^2= 33124 |
9^5= 59049 | 33^3= 35937 |183^2= 33489 |

Esta tabela acima, mostra os resultados de números elevados nos expoentes cinco, três e dois, que são os expoentes que procuramos. Podemos vizualizar que o número 32768 aparece duas vezes como resultado de números elevados exponencialmente,85 e 32³. Logo o número 32768 é uma quinta potência perfeita e um cubo perfeito, porém, não satisfaz as condições que buscamos, pois nãoexiste um número que elevado na segunda potência que dê este mesmo resultado(vizualizar na coluna 3).
O nosso problema é encontrar o segundo menor caso(descartando o número 1), que satisfaça as 3 colunas, este número x é o que iremos a partir de agora explorar como podemos encontrá-lo.

Fase 1: Combinações
1.2 Análise de um algoritmo não eficiente
Em uma primeira análise, podemos pensar em fazer comque um número percorra até um certo n, salvando todos os resultados, e assim podendo compará-los entre eles. Esta idéia poderia ser implementada por um algoritmo assim:
Leia na referência|1| para mais informações sobre algoritmos.

quadrados [ ] = new int [n];
para i de 2 até n
quadrados[i] = i^2;

Sabemos assim, que do número 2 até um número n, estarão todos os resultados das exponenciaiselevados ao quadrado, salvos em um vetor. Tendo isto, podemos pensar em fazer o mesmo com os outros expoentes:

quadrados [ ] = new int [n];
cubos [ ] = new int [n];
quintos [ ] = new int [n];
para i de 2 até n{
quadrados[i] = i^2;
cubos[i] = i^3;
quintos[i] = i^5;
}

Agora basta apenas compará-los, para ver se um mesmo número está dentro dos três vetores. Caso esteja, retornaremos o número...
tracking img