Boas aproximações racionais de pi

22

Escreva um programa que imprima todas as boas aproximações racionais de pi com denominador <1000000, em ordem crescente de denominador. a/bé uma "boa aproximação racional" de pi se estiver mais próxima de pi do que qualquer outro racional com denominador não maior que b.

A saída deve ter 167 linhas no total e iniciar e terminar assim:

3/1
13/4
16/5
19/6
22/7
179/57
...
833719/265381
1146408/364913
3126535/995207

O programa mais curto vence.

Keith Randall
fonte

Respostas:

23

Golfscript, 71 70 69 caracteres

2\!:^2^..292^15.2/3]{(.)2/.9>+{\+.((}*;.}do;;]-1%{^0@{2$*+\}/"/"\n}/;

(Supõe que você não passa nada no stdin)

Não quero mais ouvir lamentações de pessoas que não têm constantes internas para pi. Eu nem tenho números de ponto flutuante!

Veja http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations para obter mais informações.

# No input, so the stack contains ""
2\!:^2^..292^15.2/3]
# ^ is used to store 1 because that saves a char by allowing the elimination of whitespace
# Otherwise straightforward: stack now contains [2 1 2 1 1 1 292 1 15 7 3]
# Pi as a continued fraction is 3+1/(7+1/(15+1/(...)))
# If you reverse the array now on the stack you get the first 10 continuants followed by 2
# (rather than 3)
# That's a little hack to avoid passing the denominator 1000000

{
    # Stack holds: ... [c_n c_{n-1} ... c_0]
    (.)2/.9>+
    # Stack holds ... [c_{n-1} ... c_0] c_n (1+c_n)/2+((1+c_n)/2 > 9 ? 1 : 0)
    # (1+c_n)/2 > 9 is an ad-hoc approximation of the "half rule"
    # which works in this case but not in general
    # Let k = (1+c_n)/2+((1+c_n)/2 > 9 ? 1 : 0)
    # We execute the next block k times
    {
        # ... [c_{n-1} ... c_0] z
        \+.((
        # ... [z c_{n-1} ... c_0] [c_{n-1} ... c_0] z-1
    }*
    # So we now have ... [c_n c_{n-1} ... c_0] [(c_n)-1 c_{n-1} ... c_0] ...
    #                    [(c_n)-k+1 c_{n-1} ... c_0] [c_{n-1} ... c_0] c_n-k
    ;
    # Go round the loop until the array runs out
    .
}do

# Stack now contains all the solutions as CFs in reverse order, plus two surplus:
# [2 1 2 1 1 1 292 1 15 7 3] [1 2 1 1 1 292 1 15 7 3] ... [6 3] [5 3] [4 3] [3] [2] []
# Ditch the two surplus ones, bundle everything up in an array, and reverse it
;;]-1%

# For each CF...
{
    # Stack holds ... [(c_n)-j c_{n-1} ... c_0]
    # We now need to convert the CF into a rational in canonical form
    # We unwind from the inside out starting with (c_n)-j + 1/infinity,
    # representing infinity as 1/0
    ^0@
    # ... 1 0 [c_n-j c_{n-1} ... c_0]
    # Loop over the terms of the CF
    {
        # ... numerator denominator term-of-CF
        2$*+\
        # ... (term-of-CF * numerator + denominator) numerator
    }/

    # Presentation
    "/"\n
    # ... numerator "/" denominator newline
}/

# Pop that final newline to avoid a trailing blank line which isn't in the spec
;
Peter Taylor
fonte
1
Bem, tecnicamente, o GolfScript possui números de ponto flutuante e constante para o PI. É chamado "#{Math.PI}".
Konrad Borowski
2
@GlitchMr, de que maneira uma string é um número de ponto flutuante?
21412 Peter Taylor
Eu realmente gostaria de ver isso desenrolado com comentários.
Primo
Surpreendente. A primeira linha 2\!:^2^..292^15.2/3]já me impressionou.
Primo
@PeterTaylor Amarrado . Podemos fazer melhor?
Eelvex 20/02
11

Mathematica, 67 63

Isso não vai ser rápido, mas acredito que é tecnicamente correto.

Round[π,1/Range@1*^6]//.x_:>First/@Split[x,#2≥#&@@Abs[π-{##}]&]

Round[π, x]dá a fração mais próxima de π em passos de x. Isso é "listável", o mesmo Round[π,1/Range@1*^6]ocorre com todas as frações 1/10^6em ordem. A lista resultante com muitas aproximações racionais "ruins" é //.processada repetidamente ( ) removendo quaisquer elementos que estejam mais distantes de π do que o anterior.

Mr.Wizard
fonte
Muito legal, mas não posso testá-lo porque não tenho o Mathematica.
Keith Randall
@ Keith, aqui está a lógica. Round[Pi, x]dá a fração mais próxima de Piem etapas de x. Isso é "listável", o mesmo Round[Pi,1/Range@1*^6]ocorre com todas as frações até 1/10 ^ 6 em ordem. A lista resultante com muitas aproximações racionais "ruins" é então //.processada repetidamente ( ) removendo quaisquer elementos que estejam mais longe de pi do que o anterior.
Mr.Wizard
Mathematica superando o GolfScript. Arrumado.
SpellingD
Em 61: Select[Round[f=Pi,1/Range@1*^6],If[#<f,f=#;True]&@Abs[#-Pi]&]... mas inútil dado o viés dominante
Dr. belisarius
Yarr, Matie. Ser mágico neste código.
Michael Stern
7

Perl, 77 caracteres

$e=$p=atan2 0,-1;($f=abs$p-($==$p*$_+.5)/$_)<$e&&($e=$f,say"$=/$_")for 1..1e6

Um pequeno desafio é que o Perl não tem uma constante π embutida disponível, então primeiro tive que calculá-la como atan2(0,-1). Tenho certeza de que isso será superado por idiomas mais adequados para o trabalho, mas não é ruim para um idioma projetado principalmente para processamento de texto.

Ilmari Karonen
fonte
1
Você poderia mudar 999999para 1e6e salvar 3 caracteres.
Toto
@ M42: Obrigado! Abaixo de 82 caracteres agora.
Ilmari Karonen
Muito bom, $ = para obter um número inteiro. Desculpe, não posso votar duas vezes.
Toto
Não consigo fazer isso funcionar: #String found where operator expected at prog.pl line 1, near "say"$=/$_""
Keith Randall
@KeithRandall: Você precisa da -M5.01opção (e do Perl 5.10.0 ou posterior) para o saycomando. Desculpe por não mencionar isso.
Ilmari Karonen
5

Python, 96 93 89 caracteres

a=b=d=1.
while b<=1e6:
 e=3.14159265359-a/b;x=abs(e)
 if x<d:print a,b;d=x
 a+=e>0;b+=e<0

Python, 95 93 caracteres, algoritmo diferente

p=3.14159265359;d=1
for a in range(3,p*1e6):
 b=round(a/p);e=abs(p-a/b)
 if e<d:print a,b;d=e

Nota: Havia menos caracteres para escrever do p=3.14159265359;que from math import*. Droga essas importações prolixo!

Steven Rumbalski
fonte
1
Algumas diminuições: 1.0-> 1., 10**6->1e6
Keith Randall
Eu atualizei com suas melhorias. Muito obrigado.
Steven Rumbalski
@KeithRandall, mas o segundo faz com que a saída viole as especificações.
Peter Taylor
Na segunda abordagem, não há necessidade da variável p. Isso é 4 caracteres.
Ante
@ PeterTaylor: Eu não entendo. Como isso viola as especificações?
Steven Rumbalski
4

JS (95 caracteres)

for(i=k=1,m=Math;i<1e6;i++)if((j=m.abs((x=m.round(m.PI*i))/i-m.PI))<k)k=j,console.log(x+'/'+i)

Imprime 167 linhas.

JiminP
fonte
4

Ruby 1.9, 84 caracteres

m=1;(1..1e6).map{|d|n=(d*q=Math::PI).round;k=(n-q*d).abs/d;k<m&&(m=k;puts [n,d]*?/)}
Howard
fonte
@ Peter Taylor Você está certo. Você precisa usar o Ruby 1.9.
Howard
4

C99, 113 caracteres

main(d,n){double e=9,p=2*asin(1),c,a=1;for(;n=d*p+.5,c=fabsl(p-a*n/d),d<1e6;++d)c<e&&printf("%d/%d\n",n,d,e=c);}

Precisa compilar com -lm, e provavelmente cheio de comportamento indefinido, mas funciona para mim.

Thomas
fonte
2

Scala - 180 caracteres

import math._
def p(z:Int,n:Int,s:Double):Unit=
if(n==1e6)0 else{val q=1.0*z/n
val x=if(abs(Pi-q)<s){println(z+"/"+n)
abs(Pi-q)}else s
if(Pi-q<0)p(z,n+1,x)else p(z+1,n,x)}
p(3,1,1)

// ungolfed: 457

val pi=math.Pi
@annotation.tailrec
def toPi (zaehler: Int = 3, nenner: Int = 1, sofar: Double=1): Unit = {
  if (nenner == 1000000) () 
  else {
    val quotient = 1.0*zaehler/nenner
    val diff = (pi - quotient)
    val adiff= math.abs (diff)
    val next = if (adiff < sofar) {
      println (zaehler + "/" + nenner) 
      adiff 
    }
    else sofar
    if (diff < 0) toPi (zaehler, nenner + 1, next) 
    else toPi (zaehler + 1, nenner, next) 
  }  
}

A anotação do tailrec é apenas uma verificação, para verificar se é recursiva da cauda, ​​o que geralmente é uma melhoria de desempenho.

Usuário desconhecido
fonte
Não consigo fazer isso funcionar:pi.scala:1 error: not found: value math
Keith Randall
Você está usando o Scala 2.8?
usuário desconhecido
Minha escala diz "versão desconhecida", estranha. No ideone.com, eles usam o 2.8.0 e ainda recebo erros.
Keith Randall
Experimente em simplyscala.com - funciona para mim. Para scala-2.8, substituir mathpor Mathpode ser suficiente. Mencionei simplyscala neste metathread, se você procurá-lo novamente: meta.codegolf.stackexchange.com/a/401/373
usuário desconhecido
OK, isso funciona.
Keith Randall
2

Mathematica 18 17 caracteres

Eu escolhi usar, como uma medida do "melhor", o número de termos em uma representação de fração contínua de π. Por esse critério, as melhores aproximações racionais de π são seus convergentes.

Existem 10 convergentes de π com um denominador menor que um milhão. Isso é menor do que os 167 termos solicitados, mas eu o incluo aqui porque pode ser do interesse de outras pessoas.

Convergents[π, 10] 

(* out *)
{3, 22/7, 333/106, 355/113, 103993/33102, 104348/33215, 208341/66317,
312689/99532, 833719/265381, 1146408/364913}

Se você realmente deseja ver o denominador para o primeiro convergente, custará 11 caracteres adicionais:

Convergents[π, 10] /. {3 -> "3/1"}
(* out *)
{"3/1", 22/7, 333/106, 355/113, 103993/33102, 104348/33215,
208341/66317, 312689/99532, 833719/265381, 1146408/364913}

Para aqueles interessados, a seguir, são mostradas as relações entre convergentes, quocientes parciais e expressão contínua da fração de convergentes de π:

Table[ContinuedFraction[π, k], {k, 10}]
w[frac_] := Row[{Fold[(#1^-1 + #2) &, Last[#], Rest[Reverse[#]]] &[Text@Style[#, Blue, Bold, 14] & /@ ToString /@ ContinuedFraction[frac]]}];
w /@ FromContinuedFraction /@ ContinuedFraction /@ Convergents[π, 10]

frações continuadas

Por favor, desculpe a formatação inconsistente das frações continuadas.

DavidC
fonte
Isso é meio caminho para uma solução, mas é a metade mais fácil. Minha solução GolfScript codifica uma representação adequada da fração continuada em apenas 2 caracteres a mais.
Peter Taylor
Mas você não usou frações contínuas para sua solução para essa questão, usou?
21412
Sim. Era a maneira óbvia de fazer isso.
21412 Peter Taylor
Além de conciso, isso é muito mais rápido do que a maioria ou todas as outras soluções postadas.
Michael Stern
1

C # 140 129 caracteres

double n=3,d=1,e=d;while(n<4e5){double w=n/d-Math.PI,a=Math.Abs(w);if(a<e){e=a;Console.WriteLine(n+"/"+d);}if(w>0)d++;else n++;}

Código não compactado

var numerator = 3d;
var denominator = 1d;
var delta = 4d;
while (numerator < 4e5) 
{
    var newDelta = (numerator / denominator) - Math.PI;
    var absNewDelta = Math.Abs(newDelta);
    if (absNewDelta < delta)
    {
        delta = absNewDelta;
        Console.WriteLine(string.Format("{0}/{1}", numerator, denominator));
    }

    if (newDelta > 0)
    {
        denominator++;
    }
    else
    {
        numerator++;
    }
}
Jader Dias
fonte
2
varnem sempre é seu amigo. Ao removê-lo a favor, doublevocê ganha a capacidade de mesclar declarações, perde o requisito de usar literais duplos e pode salvar 16 caracteres. OTOH a pergunta pede um programa, então você perderá alguns adicionando uma declaração de classe e um Mainmétodo.
Peter Taylor
1

J, 69 65

Novo

]`,@.(<&j{.)/({~(i.<./)@j=.|@-l)@(%~(i:3x)+<.@*l=.1p1&)"0>:_i.1e3

Ainda uma abordagem de força bruta, mas muito mais rápida e um pouco mais curta.

Velho

Uma simples "força bruta":

(#~({:<<./@}:)\@j)({~(i.<./)@j=.|@-l)@(%~(i:6x)+<.@*l=.1p1&)"0>:i.1e3

faça uma lista de a/bs e depois descarte aqueles que estão mais distantes de π para alguns b'<b.

Nota: Altere 1e3para 1e6para a lista completa. Vá fazer outra coisa e volte mais tarde.

Eelvex
fonte