Dobre racjonalne przybliżenia liczby pi

22

Napisz program, który drukuje wszystkie dobre racjonalne aproksymacje liczby pi o mianowniku <1000000, w rosnącej kolejności mianowników. a/bjest „dobrym racjonalnym przybliżeniem” pi, jeśli jest bliższe pi niż jakikolwiek inny wymierny o mianowniku nie większym niż b.

Dane wyjściowe powinny mieć łącznie 167 wierszy, a ich początek i koniec powinny wyglądać następująco:

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

Najkrótszy program wygrywa.

Keith Randall
źródło

Odpowiedzi:

23

Golfscript, 71 70 69 znaków

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

(Zakłada się, że nic nie przekazujesz na standardowe wyjście)

Nie chcę słyszeć więcej jęków ludzi, którzy nie mają wbudowanych stałych dla pi. Nie mam nawet liczb zmiennoprzecinkowych!

Zobacz http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations dla tła.

# 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
źródło
1
Technicznie GolfScript ma zarówno liczby zmiennoprzecinkowe, jak i stałą dla PI. To się nazywa "#{Math.PI}".
Konrad Borowski
2
@GlitchMr, w jaki sposób ciąg jest liczbą zmiennoprzecinkową?
Peter Taylor,
Naprawdę chciałbym zobaczyć, jak rozwija się z komentarzami.
primo
Niesamowity. Już pierwsza linia 2\!:^2^..292^15.2/3]zadziwiła mnie.
primo,
@PeterTaylor Tied . Czy możemy zrobić lepiej?
Eelvex
11

Mathematica, 67 63

To nie będzie szybkie, ale uważam, że jest technicznie poprawne.

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

Round[π, x]daje najbliższą część π w krokach co x. Jest to „możliwe do wyświetlenia”, podobnie Round[π,1/Range@1*^6]jak wszystkie ułamki 1/10^6w kolejności. Powstała lista z wieloma „złymi” racjonalnymi przybliżeniami jest następnie wielokrotnie //.przetwarzana ( ) przez usuwanie wszelkich elementów, które są dalej od π niż poprzedni.

Mr.Wizard
źródło
Całkiem fajnie, ale nie mogę tego przetestować, ponieważ nie mam Mathematica.
Keith Randall,
@ Keith, oto logika. Round[Pi, x]daje najbliższy ułamek Piw krokach co x. Jest to „możliwe do wyświetlenia”, podobnie Round[Pi,1/Range@1*^6]dzieje się w przypadku wszystkich ułamków do 1/10 ^ 6 w kolejności. Powstała lista z wieloma „złymi” racjonalnymi przybliżeniami jest następnie wielokrotnie ( //.) przetwarzana przez usunięcie wszelkich elementów, które są dalej od pi niż poprzedni.
Mr.Wizard,
Mathematica pokonuje GolfScript. Schludny.
SpellingD
W 61: Select[Round[f=Pi,1/Range@1*^6],If[#<f,f=#;True]&@Abs[#-Pi]&]... ale bezużyteczne, biorąc pod uwagę dominujące nastawienie
dr belizariusz
Yarr, Matie. Niech będzie magia w tym kodzie.
Michael Stern
7

Perl, 77 znaków

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

Drobne wyzwanie polega na tym, że Perl nie ma wbudowanej stałej π , więc najpierw musiałem ją obliczyć jako atan2(0,-1). Jestem pewien, że zostanie to pokonane przez języki bardziej odpowiednie dla tego zadania, ale nie jest źle dla języka przeznaczonego głównie do przetwarzania tekstu.

Ilmari Karonen
źródło
1
Można zmienić 999999się 1e6i zaoszczędzić 3 znaki.
Toto
@ M42: Dzięki! Teraz do 82 znaków.
Ilmari Karonen,
Naprawdę fajnie, $ = aby uzyskać liczbę całkowitą. Przepraszam, nie mogę głosować dwa razy.
Toto
Nie mogę tego uruchomić:String found where operator expected at prog.pl line 1, near "say"$=/$_""
Keith Randall,
@KeithRandall: Do polecenia potrzebny jest -M5.01przełącznik (i Perl 5.10.0 lub nowszy) say. Przepraszam, że o tym nie wspominałem.
Ilmari Karonen,
5

Python, 96 93 89 znaków

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 znaków, inny algorytm

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

Uwaga: Napisanie było mniej znaków p=3.14159265359;niż from math import*. Niech to szlag, import!

Steven Rumbalski
źródło
1
Niektóre skróty: 1.0-> 1., 10**6->1e6
Keith Randall,
Zaktualizowałem twoje ulepszenia. Dzięki wielkie.
Steven Rumbalski,
@KeithRandall, ale drugi z nich powoduje, że dane wyjściowe naruszają specyfikację.
Peter Taylor,
W drugim podejściu nie ma potrzeby zmiennej p. To są 4 znaki.
Ante
@PeterTaylor: Nie rozumiem. Jak to narusza specyfikację?
Steven Rumbalski,
4

JS (95 znaków)

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)

Drukuje 167 linii.

JiminP
źródło
4

Ruby 1.9, 84 znaków

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
źródło
@Peter Taylor Masz rację. Musisz użyć Ruby 1.9.
Howard,
4

C99, 113 znaków

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);}

Muszę się skompilować -lmi prawdopodobnie nieokreślone zachowanie, ale działa dla mnie.

Tomasz
źródło
2

Scala - 180 znaków

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)

// nie golfił: 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) 
  }  
}

Adnotacja tailrec to tylko sprawdzenie, czy ma ona charakter rekurencyjny, co często stanowi poprawę wydajności.

nieznany użytkownik
źródło
Nie mogę tego uruchomić:pi.scala:1 error: not found: value math
Keith Randall,
Czy używasz Scali 2.8?
użytkownik nieznany
Moja scala mówi „nieznana wersja”, dziwne. Na ideone.com używają wersji 2.8.0 i nadal występują błędy.
Keith Randall
Wypróbuj na simplyscala.com - działa dla mnie. Dla scala-2.8 zastępując mathprzy Mathmoże być wystarczająca. Wspomniałem po prostu scscala na tej metatece, jeśli zdarzy się, że będziesz go szukać ponownie: meta.codegolf.stackexchange.com/a/401/373
użytkownik nieznany
OK, to działa.
Keith Randall
2

Mathematica 18 17 znaków

Jako miarę „najlepszej” wybrałem liczbę terminów w ciągłym ułamkowym przedstawieniu π. Według tego kryterium najlepszymi racjonalnymi przybliżeniami π są jego zbieżności.

Istnieje 10 zbieżności π o mianowniku mniejszym niż milion. Jest to mniej niż wymagane 167 warunków, ale zamieszczam je tutaj, ponieważ mogą być interesujące dla innych.

Convergents[π, 10] 

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

Jeśli naprawdę chcesz zobaczyć mianownik dla pierwszego zbieżnego, będzie to kosztować dodatkowe 11 znaków:

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}

Dla tych, którzy są zainteresowani, poniżej pokazano relacje między zbieżnymi, ilorazami cząstkowymi i ciągłym wyrażaniem ułamkowym zbieżności π:

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]

kontynuowane frakcje

Proszę wybaczyć niespójne formatowanie kontynuowanych ułamków.

DavidC
źródło
To około połowy rozwiązania, ale to najłatwiejsza połowa. Moje rozwiązanie GolfScript koduje odpowiednią reprezentację ciągłego ułamka tylko w 2 znakach.
Peter Taylor,
Ale nie użyłeś ciągłych frakcji do rozwiązania tego pytania, prawda?
DavidC
Tak. To był oczywisty sposób na zrobienie tego.
Peter Taylor,
Oprócz tego, że jest zwięzły, jest to znacznie szybsze niż większość lub wszystkie inne opublikowane rozwiązania.
Michael Stern
1

C # 140 129 znaków

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++;}

Nieskompresowany kod

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
źródło
2
varnie zawsze jest twoim przyjacielem. Usuwając go na swoją korzyść, doublezyskujesz możliwość scalania deklaracji, tracisz wymóg używania podwójnych literałów i możesz zapisać 16 znaków. OTOH pytanie dotyczy programu, więc stracisz kilka dodając deklarację klasy i Mainmetodę.
Peter Taylor,
1

J, 69 65

Nowy

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

Nadal podejście brutalnej siły, ale znacznie szybsze i odrobinę krótsze.

Stary

Prosta „brutalna siła”:

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

sporządzić listę a/bs, a dla niektórych odrzucić te, które są dalej od π b'<b.

Uwaga: Zmiana 1e3na 1e6pełną listę. Zrób coś innego i wróć później.

Eelvex
źródło