Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Warrior

[Desafio] Fracções

Mensagens Recomendadas

Warrior

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 por Warrior
  • Voto 1

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Pedro Ribeiro I

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

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.