Fraksi terdekat

24

Tugas:

Program Anda diberi fraksi sederhana positif dan tepat dalam format .<numerator>/<denominator>

Untuk input ini, ia harus menemukan dua fraksi.

  1. Sebagian kecil yang kurang dari input.
  2. Sebagian kecil yang lebih besar dari input.

Kedua fraksi harus memiliki penyebut yang lebih rendah daripada input. Dari semua fraksi yang mungkin, mereka harus memiliki perbedaan terendah ke input.

Keluaran:

Output program Anda harus:

  • Sebagian kecil dari input, dalam format <numerator>/<denominator>.
  • Diikuti oleh karakter spasi (ASCII-code 32).
  • Diikuti oleh fraksi yang lebih besar dari input, dalam format <numerator>/<denominator>.

Sebagai berikut:

«fraction that is < input» «fraction that is > input»

Aturan:

  • Semua fraksi yang dikeluarkan harus dalam nilai terendah .
  • Semua fraksi yang dihasilkan harus fraksi yang tepat.
  • Jika tidak ada fraksi yang tepat yang dimungkinkan oleh aturan, Anda harus mengeluarkan, 0bukannya input <pecahan, dan 1bukannya input pecahan>.
  • Anda dapat memilih apakah Anda ingin menerima fraksi sebagai argumen baris perintah (misalnya yourprogram.exe 2/5) atau meminta input pengguna.
  • Anda dapat menganggap program Anda tidak akan menerima input yang tidak valid.
  • Kode terpendek (dalam byte, dalam bahasa apa pun) menang.
  • Argumen baris perintah non-standar (argumen yang biasanya tidak diperlukan untuk menjalankan skrip) dihitung terhadap jumlah total karakter.

  • Apa yang tidak boleh dilakukan oleh program Anda :

    • Bergantung pada sumber daya eksternal apa pun.
    • Bergantung pada memiliki nama file tertentu.
    • Output apa pun selain output yang dibutuhkan.
    • Butuh waktu yang sangat lama untuk dijalankan. Jika program Anda berjalan lebih dari satu menit untuk pecahan dengan pembilang dan penyebut 6 digit (mis. 179565/987657) Pada komputer pengguna rumahan rata-rata, itu tidak valid.
    • Fraksi keluaran dengan 0sebagai penyebut. Anda tidak dapat membaginya dengan nol.
    • Fraksi keluaran dengan 0sebagai pembilang. Program Anda harus menampilkan 0bukan sebagian kecil.
    • Kurangi fraksi yang dimasukkan. Jika fraksi yang diberikan sebagai input dapat direduksi, Anda harus menggunakan fraksi seperti yang diinput.
  • Program Anda tidak boleh ditulis dalam bahasa pemrograman yang tidak ada kompiler / juru bahasa yang tersedia untuk umum sebelum tantangan ini diposting.

Contoh:

Input: 2/5
Keluaran: 1/3 1/2

Input: 1/2
Keluaran: 0 1

Input: 5/9
Keluaran: 1/2 4/7

Input: 1/3
Keluaran: 0 1/2

Input: 2/4
Keluaran: 1/3 2/3

Input: 179565/987657
Keluaran: 170496/937775 128779/708320

pengguna2428118
sumber
1
Contoh pertama Anda tidak sesuai dengan spesifikasi: Kedua fraksi harus memiliki penyebut yang lebih rendah daripada input.
Howard
1
Contoh pertama, output seharusnya 1/3 1/2.
Heiko Oberdiek
@ HeikoOberdiek Anda benar. Tetap.
user2428118
1
Tentukan "rata-rata komputer pengguna rumahan". Apakah 90 detik pada mesin Intel Atom 1.6GHz dapat diterima?
John Dvorak
2
Contoh terakhir Anda salah. Fraksi input sama dengan fraksi output pertama.
DavidC

Jawaban:

3

Sage - 119 117

x,X=map(int,raw_input().split('/'))
a=0
A=c=C=1
while C<X:exec("ab,,AB"[c*X>C*x::2]+"=c,C");c=a+b;C=A+B
print a/A,b/B

Sage hanya diperlukan di baris terakhir, yang menangani output. Segala sesuatu yang lain juga berfungsi dengan Python.

Ganti raw_input()dengan sys.argv[1]agar input dibaca dari argumen baris perintah alih-alih prompt. Ini tidak mengubah jumlah karakter. (Tidak berfungsi dengan Python tanpa mengimpor systerlebih dahulu.)

Ini pada dasarnya secara rekonstruk membangun urutan Farey masing-masing dengan menggunakan mediasi dari elemen yang ada, tetapi membatasi diri pada elemen yang paling dekat dengan input. Dari sudut pandang lain, ia menjalankan pencarian bersarang-interval pada urutan Farey masing-masing.

Itu benar memproses semua contoh dalam waktu kurang dari satu detik di mesin saya.

Berikut ini adalah versi yang tidak dikoleksi:

x,X = map(Integer,sys.argv[1].split('/'))
x = x/X
a = 0
c = b = 1
while c.denominator() < X:
    if c > x:
        b = c
    else:
        a = c
    c = ( a.numerator() + b.numerator() ) / ( a.denominator() + b.denominator() )
print a,b
Wrzlprmft
sumber
Saya sudah takut bahwa saya tidak akan mendapatkan kiriman baru untuk karunia ini. Kerja bagus.
user2428118
Trik yang bagus dengan exec!
xnor
Sebagai satu-satunya jawaban yang diajukan dalam periode hadiah, saya dengan ini memberikan hadiah tersebut kepada Anda. Selamat.
user2428118
Aku hanya tetap sebuah kesalahan di salah satu contoh. Anda mungkin ingin memperbaiki kiriman Anda (meskipun sudah setengah tahun sejak Anda mengirimkannya).
user2428118
12

Python 2.7 - 138

x,y=n,d=map(int,raw_input().split('/'))
while y:x,y=y,x%y
def f(p,a=d):
 while(a*n+p)%d:a-=1
 print`(a*n+p)/d`+('/'+`a`)*(a>1),
f(-x);f(x)

Saya mulai dengan solusi brute-force yang jelas, tetapi saya menyadari bahwa karena OP ingin dapat menyelesaikan contoh dengan enam digit pembilang dan penyebut dalam waktu kurang dari satu menit, saya memerlukan solusi yang lebih baik daripada mencoba satu triliun kemungkinan. Saya menemukan formula praktis di halaman Wikipedia untuk urutan Farey: Jika a / b, c / d adalah tetangga dalam salah satu urutan Farey, dengan a/b<c/d, maka b*c-a*b=1. Loop sementara di dalam f dalam program saya memperluas fakta ini ke angka-angka yang tidak berkurang, menggunakan gcd, yang dihitung loop lain.

Saya sudah bermain golf ini cukup sulit, tapi saya ingin sekali mendengar saran.

Suntingan:

166-> 162: Dihapus adan bdari program luar. Mereka tidak perlu.
162-> 155: str()-> ``
155-> 154: Ditambahkan k.
154-> 152: Dihapus xdari dalam fungsi, bukan sebagai argumen.
152-> 150: Memberikan anilai default alih-alih memberikannya sebagai argumen.
150-> 146: Mengubah inisialisasi xdan y.
146-> 145: Dihapus k.
145-> 144: Berubah ... dan ... atau ... menjadi (..., ...) [...], dengan demikian menghemat ruang.
144-> 138: Berubah (..., ...) [...] menjadi ... + ... * (...). Terima kasih kepada @ mbomb007.

Kasus uji:

2/5
1/3 1/2

1/2
0 1

2/4
1/3 2/3

179565/987657
170496/937775 128779/708320

12345678/87654321
12174209/86436891 11145405/79132382

Tes kedua hingga terakhir berlangsung di bawah satu detik di komputer saya, sedangkan yang terakhir membutuhkan waktu sekitar 5-10 detik.

isaacg
sumber
Ini k=1adalah kejahatan murni.
Evpok
1
@Evpok: Saya mencoba agar k = y = n berfungsi, tetapi ternyata jika Anda memodifikasi variabel di dalam suatu fungsi, python menginginkannya menjadi lokal. Ini adalah satu-satunya cara untuk mendapatkan variabel lokal dalam 4 karakter. Juga, karena pecahannya positif dan layak, penyebutnya tidak boleh 1.
isaacg
Argumen command-line mudah dengan Python, sehingga seharusnya digunakan untuk input seperti yang diperintahkan di sini.
Alex Thornton
1
" Anda dapat memilih apakah Anda ingin menerima fraksi sebagai argumen baris perintah (mis. Program Anda 2/5) atau meminta input pengguna ."
isaacg
Hemat 6 karakter:print`(a*n+p)/d`+('/'+`a`)*(a>1),
mbomb007
5

Mathematica, 163 byte

{a,b}=FromDigits/@InputString[]~StringSplit~"/";r=Range[b-1];""<>Riffle[#~ToString~InputForm&/@(#@DeleteCases[#2[a/b*r]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}})," "]

Ini sangat dibatasi oleh persyaratan input / output sebagai input dan string pengguna. Berurusan dengan string benar-benar rumit di Mathematica (setidaknya ketika Anda ingin bermain golf). Melakukan ini dengan cara alami di Mathematica, (hanya menggunakan bilangan bulat dan rasional) saya mungkin akan mendapatkan ini hingga 50% dari ukuran.

Ia dapat melakukan angka 6 digit dalam beberapa detik di komputer saya.

Sedikit lebih mudah dibaca (meskipun tidak benar-benar tidak ungolf):

{a, b} = FromDigits /@ InputString[]~StringSplit~"/";
r = Range[b - 1];
"" <> Riffle[#~ToString~
     InputForm & /@ (#[DeleteCases[#2[a/b*r]/r, a/b]] & @@@ {{Max, 
       Floor}, {Min, Ceiling}}), " "]

Untuk bersenang-senang, melakukan ini "cara alami", yaitu sebagai fungsi mengambil pembilang dan penyebut dan mengembalikan dua rasional, ini hanya 84 karakter (jadi perkiraan 50% saya sebenarnya cukup dekat):

f[a_,b_]:=#@DeleteCases[#2[a/b*(r=Range[b-1])]/r,a/b]&@@@{{Max,Floor},{Min,Ceiling}}
Martin Ender
sumber
3

Julia - 127 125 byte

Saya telah mendekati ini dari perspektif matematika untuk menghindari perlunya loop, jadi kode ini berjalan cukup cepat untuk input besar (catatan: jika a / b adalah input, maka a * b harus sesuai dengan Int64 (Int32 pada sistem 32 bit) , jika tidak, jawaban yang tidak masuk akal dihasilkan - jika a dan b keduanya dapat diekspresikan dalam Int32 (Int16 pada sistem 32 bit), tidak ada masalah yang terjadi).

PEMBARUAN: Tidak perlu lagi membebani backslash untuk div, dengan menggunakan ÷, penghematan bersih 2 byte.

a,b=int(split(readline(),"/"));k=gcd(a,b);f=b-invmod(a÷k,b÷k);d=2b-f-b÷k;print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1))

Tidak Disatukan:

a,b=int(split(readline(),"/")) # Read in STDIN in form a/b, convert to int
k=gcd(a,b)           # Get the greatest common denominator
f=b-invmod(a÷k,b÷k)  # Calculate the denominator of the next biggest fraction
d=2b-f-b÷k           # Calculate the denominator of the next smallest fraction
print(a*d÷b,d<2?" ":"/$d ",a*f÷b+1,"/$f"^(f>1)) # Calculate numerators and print

Ide dasarnya: temukan d terbesar dan f kurang dari b yang memenuhi ad-bc = gcd (a, b) (terkecil berikutnya) dan be-af = gcd (a, b) (terbesar berikutnya), lalu hitung c dan e dari sana. Output yang dihasilkan adalah c / de / f, kecuali jika d atau f adalah 1, dalam hal ini / d atau / f dihilangkan.

Menariknya, ini berarti bahwa kode tersebut juga berfungsi untuk pecahan positif yang tidak benar, asalkan inputnya bukan bilangan bulat (yaitu, gcd (a, b) = a).

Di sistem saya, menginput 194857602/34512958303tidak membutuhkan waktu untuk menghasilkan171085289/30302433084 23772313/4210525219

Glen O
sumber
Menguji dengan 55552/999999memberi saya -396/920632 486/936509.
user2428118
@ user2428118 - Apakah Anda menggunakan sistem 32 bit (atau menggunakan 32 bit Julia)? Saya telah menggunakan "int", yang berarti bahwa pada sistem 32 bit, ia akan menggunakan Int32 daripada Int64. int32(55552*999999)memberi -282630400. Bagi saya, dengan tes itu, saya dapat 51143/920632 52025/936509- perhatikan bahwa penyebutnya sama, dan bahwa 52025-51143 = 486 - (- 396). Saya akan menambahkan catatan untuk menyebutkan masalah ini.
Glen O
Jika Anda ingin memastikan bahwa kode tersebut akan berfungsi untuk semua input ukuran Int64, Anda dapat mengganti "int" dengan "int128". Dengan perubahan itu, memasukkan 1234567891234567/2145768375829475878hasil dalam 869253326028691/1510825213275018197 365314565205876/634943162554457681. Perubahan ini menambahkan hanya 3 karakter tambahan.
Glen O
Ya, saya menggunakan komputer 32-bit. Saya akan mencobanya di mesin 64-bit kapan ketika saya punya waktu untuk itu.
user2428118
Pengujian pada komputer 64-bit memberikan hasil yang benar, jadi saya menerima jawaban ini.
user2428118
2

JavaScript, 131

Dengan notasi panah gemuk dan evalpanggilan:

m=>{for(e=eval,n=e(m),i=p=0,q=1;++i</\d+$/.exec(m);)if(n*i>(f=n*i|0))g=f+1,p=f/i>e(p)?f+'/'+i:p,q=g/i<e(q)?g+'/'+i:q;return p+' '+q}

The 179565/987657stress test dilaksanakan di sekitar 35 detik pada Firefox, lebih banyak pada Chrome (~ 6 menit)

Metode lebih cepat dan tanpa evaldan notasi panah gemuk

for(n=eval(m=prompt(a=i=p=0,b=c=d=q=1));++i<m.match(/\d+$/);)if(n*i>(f=n*i|0))g=f+1,p=f*c>i*a?(a=f)+'/'+(c=i):p,q=g*d<i*b?(b=g)+'/'+(d=i):q;alert(p+' '+q)

The 179565/987657stress test dilaksanakan di sekitar 5 detik.

Tidak golf:

m=prompt(); //get input
a=0; c=1; //first fraction
b=1; d=1; //second fraction
n=eval(m); //evaluate input
for (i=1; i<m.match(/\d+$/); i++) { //loop from 1 to input denominator
  f=Math.floor(n*i);
  if (n*i > f) { //if fraction not equal to simplification of input
    g=f+1; // f/i and g/i are fractions closer to input
    if (f/i>a/c) a=f, c=i;
    if (g/i<b/d) b=g; d=i; 
  }
}
alert(a+'/'+c+' '+b+'/'+d); //output values handling 0 and 1 correctly
Michael M.
sumber
terlalu ... banyak ... eval. EEK
John Dvorak
3
Pengujian dengan 2/6memberikan 1/3 2/5, namun 1/3tidak kurang dari tetapi sama untuk 2/6 .
user2428118
@ user2428118 diperbaiki
Michael M.
Mengapa jawaban ini diterima begitu awal?
Evpok
1
@ user2428118: Anda tahu, Anda dapat membiarkan beberapa hari berlalu sebelum menerima solusi. Juga, solusi ini bukan lagi yang terpendek.
isaacg
2

perl, 142 byte (155 tanpa CPAN)

use bare A..Z;$/="/";N=<>;D=<>;F=N/D;K=G=1;for$H(1..D){J<F&&J>E?(E,I):J>F&&J<G?(G,K):()=(J=$_/H,"$_/$H")for(Z=int F*H)..Z+1}print I||0," $K\n"

Atau jika modul CPAN tidak diizinkan / 3-4 kali kode lebih cepat diperlukan:

$/="/";$N=<>;$D=<>;$F=$N/$D;$g=$G=1;for$d(1..$D){$f<$F&&$f>$E?($E,$e):$f>$F&&$f<$G?($G,$g):()=($f=$_/$d,"$_/$d")for($z=int$F*$d)..$z+1}print$e||0," $g\n"

Versi sebelumnya membutuhkan 9,55 detik pada mesin saya, versi terakhir 2,44 detik.

Kurang terbaca:

($N, $D) = split(m[/], <>);
$F = $N / $D;
$G = 1;
foreach $d (1 .. $D) {
    $z = int $F * $d;
    foreach $_ ($z .. $z + 1) {
        $f = $_ / $d;
        ($f < $F && $f > $E ? ($E, $e) :
        ($f > $F && $f < $G ? ($G, $g) : ())) = ($f, "$_/$d");
    }
}
print $e || 0, ' ', $g || 1, "\n";
skibrianski
sumber