Código em Java ajuda com Término do Códdigo

Escrevendo seu relatório João B Oliveira Marcelo Cohen Faculdade de Informática PUCRS 29 de julho de 2017 Resumo O abstract ou resumo deve dar uma descrição curta um ou dois parágrafos do que será tratado no texto para que o leitor possa decidir se o assunto interessa ou não Note também que a data está em português com o mês em minúscula Isso é a língua portuguesa e pode ser que seu editor de texto não saiba disso Este artigo descreve alternativas de solução para o primeiro problema proposto na disciplina de no semestre que trata da representação dos inteiros de 2 até 100 na forma 2i 3j São apresentadas três possibilidades de solução para o problema e sua eficiência é analisada Em seguida as representações obtidas para os números são mostradas Note que seu trabalho pode pedir mais que isso Você pode ter que oferecer exemplos de uso casos de teste e outros itens que não foram pedidos neste trabalho Introdução O papel da introdução é descrever o problema que vai ser resolvido de onde ele veio qual o seu contexto e se já sabemos algo a respeito dele se alguém já tentou resolver etc e depois descrever os passos que serão apresentados para a resolução mostrando uma espécie de roteiro do que vem a seguir Não esqueça de que o leitor deve entender o problema pra entender sua solução Dentro do escopo da disciplina de o primeiro problema de pode ser resumido assim dado um número a 1 outros números podem ser produzidos seguindose as duas regras 1 Multiplicando por 2 um número já produzido 2 Dividindo por 3 um número já produzido e descartando a parte fracionária divisão inteira Por exemplo seguindo estas regras temos que 10 1222223 323 O problema a ser resolvido é determinar a representação de todos os inteiros de 2 até 100 se guindo apenas estas regras Para a saída os números devem ser apresentados em ordem crescente apresentandose quantas vezes tivemos de usar cada regra Segundo o enunciado do trabalho a linha da saída para 10 seria a seguinte 10 25 31 oliveirainfpucrsbr marcelocohenpucrsbr 1 O enunciado também informa que os resultados possíveis não são únicos muitos números podem ser obtidos em mais de uma forma portanto devese dar preferência aos expoentes menores Algumas regras e considerações adicionais são 1 Não é permitido usar inteiros especiais como long BigInt e outros inteiros extralongos O maior tipo inteiro deve ter 32 bits 2 É permitido usar float real e double em tarefas auxiliares mas não é permitido calcular potências com eles 3 Se um número não precisa ser dividido por 3 podese apresentar 30 na saída Para resolver o problema proposto analisaremos três possíveis alternativas de solução bem como suas características optando por uma soluçao bastante eficiente ainda que pouco intuitiva Em seguida os resultados obtidos serão apresentados bem como as conclusões obtidas no decorrer do trabalho Talvez você tenha percebido que este texto é todo escrito no plural fizemos faremos analisare mos apresentaremos Nunca usamos o singular fiz analisei pensei etc mesmo que você esteja trabalhando sozinho Outra possibilidade melhor ainda é usar termos passivos fazse analizase demonstrase etc O texto é em espaço simples pois é muito chato ler um trabalho em espaço maior fica evidente que quem escreveu precisava encher papel Sobre o tamanho de letra recomendase 10 11 ou 12 Este texto foi originalmente feito em tamanho 12 porque iria ser reduzido Sobre o português não existe espaço antes de uma vírgula depois de dois pontos sempre vêm mi núscula e colocase espaço em branco antes de abrir um par de parênteses Por dentro dos parênteses não se coloca espaço o texto vem colado neles Procure estes detalhes no texto Primeira solução Depois de considerar o problema podemos perceber que o valor inicial a 1 serve apenas para fornecer um número inicial sobre o qual podem ser aplicadas as regras para gerar outros números e portanto seu valor não tem importância especial Com esta constatação e sabendo que em um inteiro de 32 bits podemos armazenar números até 231 ou até 320 obtivemos estes dados através de testes podemos propor uma solução bastante simples bastaria criar frações 2i3j com todas as possibilidades de expoentes para 2i ou seja 0 i 31 e para 3j ou seja 0 j 20 verificando quais números são gerados O total de números a serem testados é de apenas 3221 672 portanto o algoritmo deve ser executado com grande velocidade Um algoritmo implementando esta idéia seria parecido com este 1 registro tab100 2 int achei int exp2 int exp3 3 4 5 procedimento ALGORITMO1 6 para i 1 até 100 faça 7 tabi FALSE 8 fim 9 para i 1 até 100 faça 10 para j 0 até 20 faça 11 num 2i3j 12 Se está na faixa desejada e ainda não encontramos 13 se num 100 e tabnum FALSE então 14 tabnumachei TRUE 2 15 tabnumexp2 i 16 tabnumexp3 j 17 fim 18 fim 19 fim 20 fim Foi criada uma tabela para manter os resultados encontrados e a cada resultado encontrado seus expoentes são armazenados Ao final basta imprimir a tabela colocandoa no formato adequado de saída este algoritmo é simples e não será mostrado aqui Também é interessante perceber que a solução apresentada até o momento acha os menores ex poentes possíveis mas precisa manter o controle de que números já foram encontrados para não escrever expoentes maiores sobre valores já armazenados Uma maneira muito simples de descartar este tipo de controle é fazendo o loop externo decrescente garantindo assim que os menores expo entes serão encontrados por último e permitindo a escrita sobre valores já encontrados Esta solução seria 1 registro tab100 2 int exp2 int exp3 3 4 5 procedimento ALGORITMO2 6 para i 31 até 0 faça 7 para j 0 até 20 faça 8 num 2i3j 9 se num 100 então 10 tabnumexp2 i 11 tabnumexp3 j 12 fim 13 fim 14 fim 15 fim Esta idéia é bastante simples e eficiente porém um teste mostra que ela acha apenas 53 dos 99 números desejados Com isto podemos concluir que os outros 46 valores devem ser obtidos com expoentes maiores e os números envolvidos não podem ser representados em inteiros de 32 bits Note que esta seção dá uma idéia inicial analisaa de forma rápida e diz porque ela não serve também de forma rápida sem perder o tempo do leitor com papo furado Essa precisão e detalhe são sinais de um trabalho onde vem coisas mais interessantes mais tarde Veja que não foi usada uma linguagem de programação com todos os detalhezinhos Os algoritmos estão em uma linguagem simplificada que permite que se entenda rapidamente o que deve ser feito sem excesso de detalhes inúteis Perceba também que o código não é cheio de explicações óbvias e inúteis esta linha incrementa o contador esta linha calcula o número mas é clara o bastante para que outra pessoa entenda o que é feito e reproduza o algoritmo em sua linguagem preferida Uma falha terminamos dizendo que achamos 53 dos 99 números mas sem dizer quais foram nem falar do tempo necessário para encontrálos Moral quando terminar de falar de uma solução apresente os resultados comente o tempo e as possíveis falhas 3 Segunda solução Uma vez que a alternativa mais simples falha em quase metade dos casos optamos por desenvolver uma abordagem mais cuidadosa experimentando um truque bastante simples se já tivermos os ex poentes para certos números obtidos por exemplo com o método anterior podemos criar novos números a partir destes Por exemplo se sabemos que 2 21 30 e que 3 25 32 então podemos tentar produzir 6 através da combinação das duas representações 6 23 215 302 26 32 Infelizmente conferindo o resultado descobrimos que 26 32 649 71111 e portanto não obtemos 6 e sim 7 Tabulando os resultados e prestando atenção nos valores temos Valor truncado Fórmula Valor exato Excesso 2 21 30 2 0 3 25 32 35555 05555 6 26 32 71111 11111 O fenômeno parece bastante simples como a representação de 3 carrega consigo um erro ex cesso de 05555 ao multiplicar 3 por 2 o erro também dobra fazendo com que o valor obtido seja maior do que 6 Como se pode ver na tabela o erro para 6 é de 11111 exatamente o dobro de 05555 Desta maneira podemos perceber que um mecanismo simples de geração de novos números a partir de outros que já são conhecidos teria no mínimo os seguintes problemas 1 São necessários valores iniciais que são usados como sementes Estes valores iniciais podem ser obtidos com o método anterior por exemplo 2 Os números sendo procurados devem ser decompostos para que se saiba que outros números devem ser multiplicados para obtêlos da mesma forma que constatamos que 6 poderia ser produzido com 2 e 3 Esta decomposição é relativamente trabalhosa e envolve números primos e vários tipos de testes 3 É preciso conhecer a representação para os números primos pois estes não podem ser obtidos multiplicandose outros valores Por exemplo o valor 19 não poderá ser decomposto e sua representação tem que ser descoberta de forma independente 4 É preciso ter controle do erro sendo transmitido entre os números a fim de garantir que estamos chegando aos números corretos Por todos estes motivos optamos por não desenvolver esta solução mas com o raciocínio feito até o momento podemos elaborar uma solução aparentemente mais complexa mas que se revela mais simples quando analisada Esta solução será apresentada a seguir Veja como esta segunda solução se apoia sobre a primeira e é descrita em um pouco mais de detalhe Motivo além de ser menos óbvia ela serve de ponte para a terceira alternativa que será a verdadeira resposta e aqui precisamos deixar claro como funciona o mecanismo de propagação do erro Isto é fundamental para o que vem a seguir Note que esta solução é descartada com uma lista de motivos para que ninguém pergunte porque ela não foi implementada Terceira solução Se já sabemos como o erro se propaga quando a regra da multiplicação por 2 é usada podemos pensar em uma alternativa em vez de procurar individualmente cada número entre 2 e 100 podemos iniciar 4 uma busca que vai aplicando as regras que temos e controlando o erro envolvido anotando os números encontrados no decorrer do processamento É claro que para isto precisamos saber exatamente como se propaga o erro quando as regras são aplicadas mas já conhecemos o caso da primeira regra e agora só falta analisar o que acontece quando se aplica a segunda A maneira mais simples é fazendo um teste iniciando com 32 e dividindo duas vezes anotando os erros Valor truncado Fórmula Valor exato Erro 32 25 30 32 0 10 25 31 106666 06666 3 25 32 35555 05555 É bastante claro que o erro não é simplesmente dividido por três a cada aplicação da regra pois se assim fosse não haveria erro para 10 ou 3 já que o erro inicial era zero Assim imaginamos que o erro para a divisão seja calculado de forma mais complicada e depois de alguns testes a regra obtida é a seguinte dado um número n com erro en ao aplicarmos a regra de divisão obteremos um novo número n3 com erro dado por en3 n mod 33 en n mod 33 Embora esta regra pareça complicada podemos fazer um teste com os números anteriores Valor Valor exato Erro 32 32 0 10 106666 0332 mod 33 023 06666 3 35555 06666310 mod 33 0222203333 05555 Agora que sabemos como o erro se propaga quando as regras são aplicadas podemos facilmente propor uma solução que recebe um valor inicial e aplica repetidamente as regras dadas mantendo controle do erro e anotando novos valores encontrados Perceba que a fórmula apresentada não foi provada nem justificada de forma sólida Isto deve ser melhorado para que um leitor entenda por que ela funciona Este algoritmo pode funcionar de forma recursiva da seguinte forma 1 registro tab100 2 int achei int exp2 int exp3 3 4 5 para i 1 até 100 faça 6 tabiachei FALSE 7 fim 8 achados 0 9 10 procedimento PESQUISAint num int exp2 int exp3 real err 11 Verificamos se o erro ultrapassa 1 12 Se ultrapassa estamos falando de outro número 13 se err 1 então 14 num num 1 15 err err 1 16 fim 17 18 Armazenamos os expoentes 19 se num 100 e tabnumachei FALSE então 5 20 tabnumexp2 exp2 21 tabnumexp3 exp3 22 tabnumachei TRUE 23 achados achados 1 24 fim 25 26 Se ainda faltam números reaplicar regras 27 se achados 100 então 28 PESQUISAnum 2 exp2 1 exp3 err 2 29 PESQUISAnum 3 exp2 exp3 1 err n mod 3 3 30 fim 31 fim 32 33 Primeira chamada 34 PESQUISA1 0 0 0 A solução é quase essa mas afinal se você correr pra implementar e funcionar de cara seria muito fácil e isso não dá pra deixar Num artigo de verdade eu colocaria a solução certinha mas este é uma demonstração por isso você pode pensar a respeito Se você está usando linguagens orientadas a objetos dar uma lista de classes que você criou não é explicação pra nada Falar das classes não basta você deve esclarecer o que elas fazem Ou seja como trabalham que algoritmos usam como são interligadas Pense como é pouco informativo daí fiz umas classes A B e C que resolvem o problema Isso diz alguma coisa A primeira chamada para a função que pesquisa os números deve ser feita com um número inicial e é bastante simples determinar este número deve ser a o número fornecido inicialmente para o problema Desta forma passamos inicialmente o valor 1 com expoente 0 para 2 e 3 e com erro também zero A partir daí o algoritmo é executado até que 100 valores estejam na tabela e em seguida a tabela pode ser impressa no formato adequado Nesta versão de algoritmo não garantimos que estamos encontrando os menores expoentes pos síveis mas o algoritmo pode ser modificado para usar comparações com valores já existentes ou manter listas de expoentes em vez de apenas uma tabela Perceba que você não precisa ser a mãe do leitor explicando cada linha do código e detalhe por detalhe Se você acha que ja explicou o bastante e a idéia está clara deixe que o leitor pense um pouco para entender como as coisas funcionam Cuidado isso não quer dizer que você deve deixá lo perdido e no escuro Você também não pode colocar cinco páginas de código e esperar que ele simplesmente leia e entenda Resultados Depois de implementar o algoritmo acima em linguagem C e executálo num tempo de aproximada mente meio segundo obtivemos os seguintes resultados 6 1 20 30 26 219 39 51 258 333 76 276 344 2 21 30 27 246 326 52 239 321 77 257 332 3 25 32 28 28 32 53 220 39 78 238 320 4 22 30 29 216 37 54 266 338 79 219 38 5 24 31 30 262 336 55 247 326 80 284 349 6 29 34 31 224 312 56 29 32 81 265 337 7 26 32 32 25 30 57 274 343 82 2130 378 8 23 30 33 213 35 58 255 331 83 246 325 9 28 33 34 259 334 59 217 37 84 227 313 10 25 31 35 221 310 60 282 348 85 292 354 11 213 36 36 248 327 61 263 336 86 273 342 12 210 34 37 210 33 62 244 324 87 254 330 13 218 39 38 256 332 63 225 312 88 235 318 14 27 32 39 218 38 64 271 341 89 216 36 15 223 312 40 264 337 65 252 329 90 281 347 16 24 30 41 245 325 66 233 317 91 2146 388 17 220 310 42 226 313 67 214 35 92 262 335 18 29 33 43 253 330 68 279 346 93 243 323 19 217 38 44 215 36 69 260 334 94 224 311 20 244 325 45 280 347 70 241 322 95 289 352 21 26 31 46 242 323 71 222 310 96 2154 393 22 214 36 47 223 311 72 268 339 97 270 340 23 222 311 48 269 340 73 249 327 98 251 328 24 230 316 49 231 316 74 230 315 99 232 316 25 211 34 50 212 34 75 295 356 100 297 357 Após a obtenção destes valores estes foram testados com ferramentas capazes de lidar com os grandes números envolvidos e todos os resultados foram confirmados corretos Por favor não esqueça de apresentar os resultados afinal deve ser isso que seu leitor quer ver Conclusões As abordagens iniciais mesmo oferecendo apenas resultados parciais contribuíram bastante para o entendimento do problema e abriram caminho para a solução definitiva Esta se mostrou bastante simples e eficiente embora tenha exigido um estudo de como o erro se propaga quando as regras são aplicadas a novos números A solução implementada não se preocupou em achar sempre os menores expoentes possíveis mas mesmo assim ela foi bastante eficiente e os expoentes encontrados não são excessivamente grandes foram feitas comparações com o primeiro algoritmo apresentado e as diferenças foram poucas Além disso a solução recursiva adotada foi razoavelmente elegante e clara não precisando de uma implementação complicada Embora não tenham sido mostrados neste artigo foram feitos testes com outros valores iniciais a 1 e para números indo até bem mais do que 100 o algoritmo também funcionou bem Acreditamos ter desenvolvido uma solução interessante e barata a um problema relativamente complexo já que em uma linguagem de programação usual não existe suporte direto para tratar com os números envolvidos e conseguimos determinar resultados corretos que envolvem grandes núme ros Suas conclusões não precisam ser geniais nem mudar o mundo Veja que a parte inteligente do artigo já foi feita e veio antes Agora é a hora de fechar e dizer o que você acha que poderia vir depois etc etc E se você está pensando em dizer coisas como Provavelmente existem soluções 7 melhores então diga ao menos o que você pensa que pode melhorar por exemplo neste artigo eu gostaria de evitar o uso de números em ponto flutuante e preferiria trocar por algum tipo de controle com inteiros Se você não der opções e só disser que dá pra fazer melhor está se diminundo de graça Pra que isso A bibliografia abaixo não foi usada neste artigo e serve apenas de exemplo para a formatação Outros exemplos estão na página da biblioteca da PUCRS Referências 1 Brassard G Bratley P Fundamentals of algorithmics Prentice Hall Englewood Cliffs New Jersey 1996 2 Cormen T H Leiserson E C Rivest R L Introduction to Algorithms McGraw Hill Book Co The MIT Electrical Engineering and Computer Science Series Cambridge 1990 3 Graham R L Knuth D E Patashnik O Concrete mathematics AddisonWesley Rea ding 1989 4 Moret B M Shapiro H D Algorithms from P to NP design and efficiency Addison Wesley Reading 1990 5 Lueker G S Some techniques for solving recurrences Computing Surveys Vol 12 no 4 dezembro 1980 6 Rawlins Gregory J E Compared to what An introduction to the analysis of algorithms Computer Science Press New York 1992 Outros detalhes Coisas que não entram num artigo mas que vou escrever aqui porque deve ser ditas em algum lugar 1 Em primeiríssimo lugar você está numa Universidade e portanto deve ter ido à escola por uns onze anos pelo menos Você teve aulas de português por cerca de sete desses anos várias vezes por semana e ainda prestou prova para o vestibular Seu editor de texto por outro lado não teve aula nenhuma e provavelmente foi meio mal adaptado do inglês Mostre um pouco de respeito por si mesmo e desligue tudo o que puder Desligue todas as correções automáticas e assuma a responsabilidade pelo que você sabe 2 Acentos ainda existem em português e deverão continuar por muito tempo Useos 3 Note a consistência no que está escrito o valor inicial a por exemplo está sempre escrito da mesma forma em itálico para que o leitor não encontre cinco tipos de letra a diferentes e tenha de lembrar o que cada uma significa Isto mostra que o autor teve cuidado ao escrever 4 Note que os fontes são sempre coerentes texto em Times matemática em itálico algoritmos em Typewriter Não há fontes maiores ou menores nem paragrafos com fonte diferente margem ou espaçamento maiores ou menores do que os outros 5 Veja também que as potências estão sempre escritas corretamente no texto xy Não se usam notações como xy porque elas são feias Esta notação só é usada quando se fala do formato de saída pois ele é exigido desta forma Da mesma forma quando são necessários subscritos eles devem ser escritos corretamente Ai bi j etc Escrever Aj ou bij é um mau sinal 8 6 Se algo está nas referências deve estar citado no texto e se está citado no texto tem de aparecer nas referências A maneira correta de citar uma referência é Segundo 3 e 4 o algoritmo precisa 7 Tenha cuidado com seu texto ele deve transmitir a impressão de que foi escrito com todo o cuidado do mundo Dedique tempo a ele e tente deixálo melhor pois sua reputação e nota dependem disso 8 Este artigo foi totalmente escrito usando LYX um dos melhores editores de textos que existe fazendo uso de TEX e LATEX que são sem dúvida os melhores formatadores de texto do mundo Tudo isto é software livre rodando sob LINUX Aprenda a usálos vai fazer bem 9 Para ajudar na missão ingrata de fazer um trabalho agradável para a leitura este checklist pode ajudar 2 Artigos não tem capa 2 Coloquei título neste trabalho Coloquei meu nome 2 Usei um espaçamento legal e tamanho de fonte decente ou tem só cinco linhas por página e as letras parecem manchetes 2 O trabalho tem uma introdução para que se entenda do que estou falando Eu contei o que ia resolver 2 O desenvolvimento é coerente ou parece que recortei trechos de jornal e de meus colegas e grudei tudo 2 Dá pra entender minhas explicações ou tem que ter poderes paranormais 2 Tem o mínimo de código possível Não dá pra ter ainda menos Dá pra não ter nenhum Se não tem nenhum será que deveria ter um pouco mostrando as partes mais importantes Geralmente deveria 2 Se tem código eu fico falando durante páginas e páginas entorpecentes e sem fim pra explicar o que ele faz linha por linha Posso ser claro sem ser chato 2 Se o trabalho pedia a resposta para algum problema será que esqueci de dar o resultado Tinha que dar vários exemplos e testes 2 Usei figuras pra esclarecer coisas que eram confusas como aquelas listas que usei e agora eu mesmo mal consigo entender Como vou querer que outra pessoa entenda 2 Minhas figuras são claras Mostram coisas acontecendo passo a passo ou estão jogadas no papel As legendas são descritivas 2 Os dados ficam melhor se forem apresentados em tabelas Tenho gráficos de tempo e desempenho se preciso Com legendas eixos unidades ou está uma bagunça feita no Excel 2 Lembrei de colocar minhas conclusões ao final do trabalho 2 Coloque as minhas fontes de informação na bibliografia 9 O caminho das frutinhas saborosas Seu primo antropólogo acaba de retornar da África e conta sobre um bando de macaquinhos que moram em um local com árvores frutíferas que fornecem seu alimento Eles poderiam ser gulosos e comer tudo mas são ecologicamente conscientes e por isso fazem uma cuidadosa avaliação de cada árvore cada fruta recebe uma nota baseada em cor tamanho aparência aroma e os macaquinhos escolhem o caminho que dá pontuação máxima mas que vai apenas da raiz até uma das folhas Ou seja as frutas deste caminho de maior pontuação serão comidas e as que estão fora dele são poupadas para alimentar outros bichos e para que sementes se espalhem Seu primo diz que a descoberta é um pouco irritante por que os cientistas tem dificuldade de prever o caminho que será escolhido e essa é uma tarefa que os macaquinhos fazem com facilidade Ele pede a sua ajuda e para testar se você consegue ele traz desenhos de várias árvores diferentes A informação que os desenhos trazem é 1 A primeira informação é o tamanho da árvore em linhas e colunas que representam metros 2 A árvore inicia em algum ponto da parte inferior 3 Os galhos são representados por ou e podem passar uns na frente dos outros 4 Uma bifurcação ou trifurcação nos galhos é marcada com V ou W 5 As folhas finais são marcadas com 6 As avaliações das frutinhas estão anotadas nos galhos com notas de 0 a 9 No exemplo ao lado podese ver uma árvore cheia de frutinhas saborosas com galhos passando uns sobre os outros e várias bifurcações Claro se no cruzamento de dois galhos ainda existe uma bifurcaçãotrifurcação tudo fica ainda mais confuso Com todas estas informações sua missão é simples você deve analisar os desenhos que seu primo trouxe descobrindo qual a nota total do caminho que será escolhido pelos macaquinhos e ao final apresentar um relatório descrevendo Qual o problema sendo resolvido Como o problema foi modelado Como é o processo de solução apresentando exemplos e algoritmos Os resultados dos casos de teste Conclusões 20 29 3 9 44 1 V 5 0 4 8 9 V 6 8 7 W 0 V 3 9 2 V 2 7 W V 7