Pendekatan rasional yang baik dari pi

22

Tulis sebuah program yang mencetak semua perkiraan rasional yang baik dari pi dengan penyebut <1000000, dalam urutan penyebut yang meningkat. a/badalah "perkiraan rasional yang baik" dari pi jika lebih dekat ke pi daripada rasional lainnya dengan penyebut tidak lebih besar dari b.

Outputnya harus memiliki total 167 baris, dan mulai dan berakhir seperti ini:

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

Kemenangan program terpendek.

Keith Randall
sumber

Jawaban:

23

Golfscript, 71 70 69 karakter

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

(Menganggap bahwa Anda tidak memberikan apa pun pada stdin)

Saya tidak ingin mendengar lagi desahan oleh orang-orang yang tidak memiliki konstanta bawaan untuk pi. Saya bahkan tidak memiliki angka floating point!

Lihat http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations untuk latar belakang.

# 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
sumber
1
Nah, secara teknis GolfScript memiliki angka floating point dan konstanta untuk PI. Itu disebut "#{Math.PI}".
Konrad Borowski
2
@ GritchMr, dengan cara apa string adalah angka floating point?
Peter Taylor
Saya benar-benar ingin melihat ini terbuka dengan komentar.
primo
Luar biasa. Baris pertama 2\!:^2^..292^15.2/3]sudah mengejutkan saya.
Primo
@PeterTaylor Terikat . Bisakah kita berbuat lebih baik?
Eelvex
11

Mathematica, 67 63

Ini tidak akan cepat, tetapi saya percaya secara teknis benar.

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

Round[π, x]memberikan fraksi terdekat ke π dalam langkah-langkah x. Ini "dapat didaftar" begitu Round[π,1/Range@1*^6]juga untuk semua fraksi sampai ke 1/10^6urutan. Daftar yang dihasilkan dengan banyak perkiraan rasional "buruk" kemudian berulang kali ( //.) diproses dengan menghapus elemen yang lebih jauh dari π daripada yang sebelumnya.

Tuan Wisaya
sumber
Cukup keren, tetapi saya tidak dapat mengujinya karena saya tidak memiliki Mathematica.
Keith Randall
@Keith, ini logikanya. Round[Pi, x]memberikan fraksi terdekat ke Pidalam langkah x. Ini "dapat didaftar" demikian Round[Pi,1/Range@1*^6]juga untuk semua fraksi hingga 1/10 ^ 6 secara berurutan. Daftar yang dihasilkan dengan banyak perkiraan rasional "buruk" kemudian berulang kali ( //.) diproses dengan menghapus elemen yang lebih jauh dari pi daripada yang sebelumnya.
Mr.Wizard
Mathematica mengalahkan GolfScript. Rapi.
SpellingD
Dalam 61: Select[Round[f=Pi,1/Range@1*^6],If[#<f,f=#;True]&@Abs[#-Pi]&]... tapi tidak berguna karena bias dominan
Dr. belisarius
Yarr, Matie. Jadilah keajaiban dalam kode ini.
Michael Stern
7

Perl, 77 karakter

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

Tantangan kecil adalah bahwa Perl tidak memiliki konstanta built-in π yang tersedia, jadi saya pertama-tama harus menghitungnya atan2(0,-1). Saya yakin ini akan dikalahkan oleh bahasa yang lebih cocok untuk pekerjaan itu, tapi itu tidak buruk untuk bahasa yang terutama dirancang untuk pemrosesan teks.

Ilmari Karonen
sumber
1
Anda bisa mengubah 999999ke 1e6dan menyimpan 3 karakter.
Toto
@ M42: Terima kasih! Turun ke 82 karakter sekarang.
Ilmari Karonen
Sangat bagus, $ = untuk mendapatkan integer. Maaf, saya tidak dapat memilih dua kali.
Toto
Saya tidak bisa menjalankan ini:String found where operator expected at prog.pl line 1, near "say"$=/$_""
Keith Randall
@KeithRandall: Anda memerlukan -M5.01sakelar (dan Perl 5.10.0 atau lebih baru) untuk sayperintah. Maaf karena tidak menyebutkan itu.
Ilmari Karonen
5

Python, 96 93 89 karakter

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 karakter, algoritma berbeda

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

Catatan: Itu lebih sedikit karakter untuk ditulis p=3.14159265359;daripada from math import*. Sialan impor bertele-tele itu!

Steven Rumbalski
sumber
1
Beberapa penyingkatan: 1.0-> 1., 10**6->1e6
Keith Randall
Saya telah memperbarui dengan peningkatan Anda. Terimakasih banyak.
Steven Rumbalski
@ KeithRandall, tetapi yang kedua membuat output melanggar spec.
Peter Taylor
Dalam pendekatan kedua tidak perlu untuk variabel p. Itu adalah 4 karakter.
Ante
@ PeterTaylor: Saya tidak mengerti. Bagaimana cara melanggar spesifikasi?
Steven Rumbalski
4

JS (95 karakter)

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)

Itu mencetak 167 baris.

JiminP
sumber
4

Ruby 1.9, 84 karakter

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
sumber
@ Peter Taylor Kau benar. Anda harus menggunakan Ruby 1.9.
Howard
4

C99, 113 karakter

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

Perlu dikompilasi dengan -lm, dan mungkin penuh dengan perilaku yang tidak terdefinisi, tetapi berhasil bagi saya.

Thomas
sumber
2

Scala - 180 karakter

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

Anotasi tailrec hanyalah sebuah cek, untuk memverifikasi, bahwa itu ekor-rekursif, yang seringkali merupakan peningkatan kinerja.

Pengguna tidak diketahui
sumber
Saya tidak bisa mengaktifkan ini:pi.scala:1 error: not found: value math
Keith Randall
Apakah Anda menggunakan Scala 2.8?
pengguna tidak diketahui
Scala saya mengatakan "versi tidak dikenal", aneh. Di ideone.com, mereka menggunakan 2.8.0 dan saya masih mendapatkan kesalahan.
Keith Randall
Cobalah di simplyscala.com - bekerja untuk saya. Untuk scala-2.8, mengganti mathdengan Mathmungkin sudah cukup. Saya menyebutkan simplyscala pada metathread ini, jika Anda mencarinya lagi: meta.codegolf.stackexchange.com/a/401/373
pengguna tidak diketahui
Oke, itu berhasil.
Keith Randall
2

Mathematica 18 17 karakter

Saya memilih untuk menggunakan, sebagai ukuran "terbaik", jumlah istilah dalam representasi fraksi lanjutan π. Dengan kriteria ini, perkiraan rasional terbaik dari π adalah konvergennya.

Ada 10 konvergensi π dengan penyebut kurang dari satu juta. Ini kurang dari persyaratan 167 yang diminta, tapi saya memasukkannya di sini karena mungkin menarik bagi orang lain.

Convergents[π, 10] 

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

Jika Anda benar-benar ingin melihat penyebut untuk konvergen pertama, akan dikenakan biaya tambahan 11 karakter:

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}

Bagi mereka yang tertarik, berikut ini menunjukkan hubungan antara konvergensi, negosiasi parsial, dan ekspresi fraksi lanjutan dari konvergensi π:

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]

fraksi lanjutan

Maafkan pemformatan fraksi lanjutan yang tidak konsisten.

DavidC
sumber
Itu sekitar setengah jalan menuju solusi, tetapi itu adalah setengah yang termudah. Solusi GolfScript saya mengkodekan representasi yang sesuai dari fraksi lanjutan hanya dalam 2 karakter.
Peter Taylor
Tetapi Anda tidak menggunakan pecahan lanjutan untuk solusi Anda untuk pertanyaan ini, bukan?
DavidC
Iya nih. Itu adalah cara yang jelas untuk melakukannya.
Peter Taylor
Selain ringkas, ini jauh lebih cepat daripada sebagian besar atau semua solusi lain yang telah diposting.
Michael Stern
1

C # 140 129 karakter

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

Kode tidak terkompresi

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
sumber
2
vartidak selalu temanmu. Dengan menghapusnya demi doubleAnda, Anda dapat menggabungkan deklarasi, kehilangan persyaratan untuk menggunakan literal ganda, dan dapat menghemat 16 karakter. OTOH pertanyaannya meminta program, jadi Anda akan kehilangan beberapa untuk menambahkan deklarasi kelas dan Mainmetode.
Peter Taylor
1

J, 69 65

Baru

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

Masih pendekatan yang kasar tetapi jauh lebih cepat dan sedikit lebih pendek.

Tua

"Kekuatan kasar" yang sederhana:

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

buat daftar a/bs dan kemudian buang yang lebih jauh dari π untuk beberapa orang b'<b.

Catatan: Ubah 1e3ke 1e6untuk daftar lengkap. Pergi lakukan sesuatu yang lain dan kembali lagi nanti.

Eelvex
sumber