Warrior 68 Denunciar mensagem Publicado 28 de Janeiro de 2013 (editado) No outro dia deparei-me com um problema interessante e decidi partilhar. Não é propriamente fácil mas como tem motivação histórica achei curioso. Há muitos desafios que nos pedem para recuperarmos fracções tendo por base a sua representação decimal. A verdade é que a divisão de dois números A e B pode dar origem a uma dízima infinita com um período que pode ir no máximo até B. Por exemplo 1/7 = 0,142857 142857 142857... Recuperar 1/7 tendo este período já foi colocado como desafio no forum várias vezes (por exemplo aqui). Algo que menos pessoas sabem é que, tendo o resultado de uma fracção A/B, é possível recuperar eficientemente A e B se descobrirmos os primeiros NA+NB+1 dígitos. Ou seja, se nos disserem que o dividendo tem NA dígitos e o divisor NB, então podemos recuperar a fracção inicial muito rapidamente. No caso do 1/7, bastam-nos os 3 dígitos 142. O desafio é esse mesmo. Como recuperar A e B conhecendo só parte da representação decimal? Portanto eu pergunto, qual é a fracção A/B, com A e B de 5 dígitos cada, cuja representação decimal inicia com este número "16764004988"? Que método é que pode ser usado para o descobrir, sem recorrer ao computador? Contexto: ZAPMAIL Antes do Fax se ter difundido, a FedEx procurou instalar um serviço de entrega de correspondência mais rápido para as empresas. Os documentos eram digitalizados nos correios e enviados pela rede para outra estação FedEx que os imprimia e entregava no destinatário no mesmo dia. As empresas conseguiam entregar os documentos mais rapidamente e a FedEx poupava somas significativas ao reduzir a frota de transportes. (Este sistema foi descontinuado com elevados prejuízos quando poucos anos mais tarde o Fax se espalhou e as empresas não estavam dispostas a pagar para um serviço que tinham gratuito) Uma das primeiras preocupações foi a forma como poderiam encriptar os documentos pela rede. A proposta foi terem os dois terminais a escolherem dois números co-primos A e B, obterem a divisão A/B e com o seu resultado em binário fazerem XORs no documento, encriptando-o. Na outra extremidade, e conhecendo-se o mesmo A e B, a operação podia ser revertida aplicando exactamente o mesmo processo. Infelizmente os documentos por vezes continham espaços em branco consecutivos, sendo possível recuperar uma parte do resultado da divisão. Mais tarde se demonstrou que com B números consecutivos se conseguia quebrar a encriptação e este método foi abandonado. Editado 4 de Abril de 2014 por Warrior 1 Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Warrior 68 Denunciar mensagem Publicado 29 de Janeiro de 2013 Edit: mudado para os primeiros nA+nB+1 dígitos. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Pedro Ribeiro I 4 Denunciar mensagem Publicado 3 de Abril de 2014 Deveras interessante. Sorry for the bump, mas isto é deveras interessante Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Warrior 68 Denunciar mensagem Publicado 3 de Abril de 2014 Oh, nunca mais me lembrei de colocar aqui a solução.. Vou ver se arranjo um tempo para escrevê-la. Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Pedro Ribeiro I 4 Denunciar mensagem Publicado 4 de Abril de 2014 Se faz favor Warrior. Hoje vou tentar resolver Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Pedro Ribeiro I 4 Denunciar mensagem Publicado 4 de Abril de 2014 Bem, hoje em química descobri como achar o B, falta-me o A. Sem computador só fiz para números com um dígito, não sei como funciona com mais dígitos. Vou continuar a ver e depois digo algo. Obrigado pelo desafio Warrior Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Pedro Ribeiro I 4 Denunciar mensagem Publicado 4 de Abril de 2014 Afinal, não funciona xb funciona apenas em casos limitados... Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Warrior 68 Denunciar mensagem Publicado 8 de Abril de 2014 Ok, já passou demasiado tempo desde o post inicial, não vou entrar em grandes detalhes nesta explicação mas não hesitem em perguntar se não tiver ficado claro. O problema é aparentemente simples, temos um número X = A/B e sabemos que X = 0.16764004988... Queremos então encontrar A e B, cada um com no máximo 5 dígitos. Isto é a mesma coisa do que perguntar qual é a melhor aproximação de X usando uma fracção com até 5 dígitos no numerador e denominador. A resposta rápida é: podemos obter a resposta usando fracções contínuas. É um conceito bastante simples mas que normalmente não é muito abordado. Começamos com o nosso número X. Uma coisa evidente que nós sabemos, é que: Mas sendo X = 0.16764004988.., podemos substituir X na expressão acima: E agora temos o mesmo problema. Qual a melhor forma de representar 5.965161.. utilizando uma fracção? Podemos representar aquele número através da parte inteira + 1/parte_decimal: E o problema repete-se novamente: qual a melhor forma de representar 1.0360958..? Podemos repetir o passo anterior inúmeras vezes. Obteríamos algo deste género: Podemos ver facilmente porque motivo estas fracções se chamam fracções contínuas, porque se encadeiam continuamente umas nas outras. A questão aqui é: quão próximos de X estamos neste momento? Se ignorarmos as "reticências", podemos descobrir que Estamos perto de 0.16764004988, mas ainda não estamos lá! De qualquer modo, A e B ainda só têm 3 dígitos no máximo. O enunciado diz que podiam ir até 5. Para não se ocuparem páginas a escrever fracções na vertical, uma outra notação surgiu para representar fracções contínuas. A fracção anterior pode ser representada por [0; 5, 1, 27, 1, 2]. Muito mais compacto. O curioso sobre as fracções contínuas é que elas garantem que são a melhor aproximação até àquele denominador. Ou seja, 86/513 é a melhor aproximação de 0.16764004988 entre todas as fracções com denominador <= 513. Se continuarem o processo anterior, a fracção contínua que melhor descreve o nosso X é [0;5,1,27,1,2,2,1,1,1,3,1,2,1]. Se calcularem a fracção que representa, verão que obtêm 13577/80989 = 0.167640049883.. Começa com o nosso valor de X! Se quisessem prolongar a fracção, veriam que o próximo valor na sequência seria 45. Contudo, [0;5,1,27,1,2,2,1,1,1,3,1,2,1,45] = 620954/3704091 . Claramente fora dos 5 dígitos pedidos no problema! Este processo pode parecer muito moroso, mas é extremamente rápido de efectuar numa calculadora. Só têm de retirar a parte inteira ao resultado e dividir 1 por esse valor. As fracções contínuas têm muitas outras propriedades interessantes na representação de números. Todos os números racionais possuem uma fracção contínua finita. As fracções contínuas infinitas são nada mais do que soluções irracionais de equações quadradas (por exemplo, raiz quadrada de 3). 4 Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites
Pedro Ribeiro I 4 Denunciar mensagem Publicado 13 de Abril de 2014 Muito interessante... obrigado Warrior, vou tentar estudar isto Partilhar esta mensagem Ligação para a mensagem Partilhar noutros sites