EDIT: Saya mendapatkan banyak komentar tentang ini tidak berakhir - saya akan memberikan tag "jawaban yang benar" baik kepada orang pertama yang memberi saya FF(3)(seperti dalam memberikannya dalam jawaban mereka) atau membuktikan bahwa FF(3)memang memang meledak tanpa batas.

Tugas:

Tugas Anda adalah membuat program sekecil mungkin yang menghasilkan daftar kebalikan dari fungsi Fraction Frenzy ( FF(n)) yang diberi bilangan bulat positif n.

Pengantar:

Sebelum saya dapat memperkenalkan fungsi FF, saya harus terlebih dahulu menjelaskan pecahan Mesir.

Pecahan Mesir:

Fraksi Mesir adalah cara mengekspresikan fraksi sebagai jumlah fraksi unit yang berbeda - jadi salah satu cara untuk mengungkapkan fraksi 5/8adalah 1/2 + 1/8. Ini bukan jumlah pecahan lain seperti

1/4 + 1/4 + 1/8
1/2 + 1/16 + 1/16

karena tidak semua fraksi mereka berbeda ( 1/4diulang dalam contoh pertama, dan 1/16di kedua).

Dalam definisi kami tentang fraksi Mesir, kami menyertakan penggunaan penyebut negatif dalam fraksi satuan juga.

Fungsi FF:

Fungsi FF (Fraction Frenzy) dijelaskan seperti ini:

FF(1)adalah fraksi Mesir 1/2 + 1/3 + 1/5 + 1/-30.

FF(2)sama dengan FF(1)"dikalikan" dengan sendirinya ( FF(1)"kuadrat"):

  (1/2 + 1/3 + 1/5 + 1/-30)(1/2 + 1/3 + 1/5 + 1/-30)
= 1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900

Ini bukan fraksi Mesir yang sepenuhnya berkurang, karena ada "pengulangan" dalam fraksi. Untuk menguranginya, prosedur berikut dilakukan:

1. Jumlahkan semua fraksi unit "suka" bersama.
2. Kurangi jumlah menjadi bentuk paling sederhana - jadi misalnya, jika jumlah dari langkah 1adalah 2/6, itu dapat dikurangi menjadi 1/3.
3. Ulangi 1 dan 2 sampai semua penyebut berbeda: misalnya 1/2 + 2/3 + 1/5, sebagai lawan dari 1/2 + 1/3 + 1/3, yang memiliki penyebut berulang 3.
4. Jika ada pasangan dari satu fraksi positif dan satu negatif yang memiliki nilai absolut yang sama, hapus keduanya (misalnya 1/-5dan 1/5keduanya harus dihilangkan).
5. Jika pecahan bukan satuan dan tidak dapat direduksi lebih jauh, pisahkan menjadi pecahan satuan dengan penyebut yang sama, dan pertahankan satu pecahan seperti apa adanya. Dengan yang lain, kalikan mereka dengan FF(1): (1/2 + 1/3 + 1/5 + 1/-30).
6. Ulangi langkah 1-5 hingga jumlah fraksi akhir adalah fraksi Mesir yang valid - yaitu semua fraksi berbeda satu sama lain, dan semuanya fraksi satuan.

Ini adalah pengurangan dari FF(2):

  1/4 + 1/6 + 1/10 + 1/-60 + 1/6 + 1/9 + 1/15 + 1/-90 +
  1/10 + 1/15 + 1/25 + 1/-150 + 1/-60 + 1/-90 + 1/-150 + 1/900
= 1/4 + 2/6 + 1/9 + 2/10 + 2/15 + 1/25 + 2/-60 + 2/-90 + 2/-150 + 1/900 (step 1)
= 1/4 + 1/3 + 1/9 + 1/5 + 2/15 + 1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900   (step 2)
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/15(1/2 + 1/3 + 1/5 + 1/-30) +        (step 5)
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/30 + 1/45 + 1/75 + 1/-450 +
  1/25 + 1/-30 + 1/-45 + 1/-75 + 1/900
= 1/3 + 1/4 + 1/5 + 1/9 + 1/15 + 1/25 + 1/-450 + 1/900                  (step 4)

Untuk semua n(kecuali untuk 1), FF(n)didefinisikan dengan "kuadrat" FF(n-1).

Masukan dan keluaran:

Diberikan bilangan bulat n, Anda harus menampilkan daftar semua resiprokal FF(n), diurutkan dalam urutan nilai absolut yang naik:

1 -> [2, 3, 5, -30]
# 1/2 + 1/3 + 1/5 + 1/-30 = FF(1), reciprocals = [2, 3, 5, -30]

2 -> [3, 4, 5, 9, 15, 25, -450, 900]

Anda diizinkan menggunakan string dengan pembatas apa pun, atau interpretasi bahasa Anda dari suatu daftar, sehingga output ini semua dapat diterima dengan input 1:

2 3 5 -30   (Space-delimited)
2,3,5,-30   (Comma-delimited)
[2 3 5 -30] (Lisp-like lists)
etc. etc.

Spesifikasi:

• Anda harus menampilkan hasil FF(n)fungsi persis seperti yang ditentukan di atas.
• Anda dijamin bahwa input akan berupa bilangan bulat positif - tidak akan pernah di bawah nol, dan itu tidak akan pernah menjadi desimal (atau fraksi).

Ini adalah kode-golf , jadi kode terpendek dalam byte menang!

Haskell , 365 byte

import Data.Function;import Data.List;import Data.Ratio;n=numerator;d=denominator
r=until=<<((==)=<<)$filter(/=0).map(sum).groupBy((==)`on`d).sortBy(compare`on`d)
p s=let(o,q)=span((<2).abs.n)s in case q of []->o;(a:b)->let j=a-1%d a*signum a in p.r$o++[a-j]++map(*j)e++b
s s=(*)<$>s<*>s;e=(1%)<$>[2,3,5,-30];f=iterate(p.r.s)e;o i=[abs(d q)*signum(n q)|q<-f!!(i-1)]

Cobalah online!