Latar Belakang
Kebanyakan orang di sini harus terbiasa dengan beberapa sistem basis integer: desimal, biner, heksadesimal, oktal. Misalnya dalam sistem heksadesimal, angka abc.de 16 akan mewakili
a*16^2 + b*16^1 + c*16^0 + d*16^-1 + e*16^-2
Namun, kita juga dapat menggunakan basis non-integer, seperti bilangan irasional. Setelah dasar seperti menggunakan rasio emas φ = (1 + √5) / 2 ≈ 1,618 ... . Ini didefinisikan secara analog ke basis integer. Jadi angka abc.de φ (di mana a ke e adalah angka integer) akan mewakili
a*φ^2 + b*φ^1 + c*φ^0 + d*φ^-1 + e*φ^-2
Perhatikan bahwa pada prinsipnya salah satu digit bisa negatif (meskipun kami tidak terbiasa dengan itu) - kami akan mewakili digit negatif dengan yang terdepan ~
. Untuk tujuan pertanyaan ini kita membatasi diri untuk angka dari ~9
ke 9
, jadi kami jelas bisa menulis nomor sebagai satu string (dengan tildes di antara). Begitu
-2*φ^2 + 9*φ^1 + 0*φ^0 + -4*φ^-1 + 3*φ^-2
akan ditulis sebagai ~290.~43
. Kami menyebut nomor tersebut sebagai nomor telepon biasa .
Bilangan phinary selalu dapat direpresentasikan dalam bentuk standar , yang berarti bahwa representasi hanya menggunakan digit 1
dan 0
, tanpa mengandung di 11
mana pun, dan dengan tanda minus opsional untuk menunjukkan bahwa seluruh bilangan tersebut negatif. (Menariknya, setiap bilangan bulat memiliki representasi terbatas yang unik dalam bentuk standar.)
Representasi yang tidak dalam bentuk standar selalu dapat dikonversi menjadi bentuk standar menggunakan pengamatan berikut:
- 011 φ = 100 φ (karena φ 2 = φ + 1)
- 0200 φ = 1001 φ (karena φ 2 + 1 / φ = 2φ)
- 0 ~ 10 φ = ~ 101 φ (karena φ - 1 / φ = 1)
Tambahan:
- Jika digit paling signifikan adalah
~1
(dengan sisa angka menjadi bentuk standar), angka tersebut negatif, dan kita dapat mengubahnya menjadi bentuk standar dengan menukar semua1
dan~1
, menambahkan tanda minus, dan menerapkan tiga aturan di atas lagi sampai kita dapatkan formulir standar.
Berikut ini adalah contoh normalisasi (Saya menggunakan ruang tambahan untuk digit positif, untuk menjaga agar setiap posisi digit selaras):
1~3.2~1φ
1~3. 2~1φ Rule:
= 0~2. 3~1φ (3)
= ~1~1. 4~1φ (3)
= ~1 0 0. 4~1φ (3)
= ~1 0 0. 3 0 1φ (3)
= ~1 0 1. 1 0 2φ (2)
= ~1 1 0. 0 0 2φ (1)
= ~1 1 0. 0 1 0 0 1φ (2)
= - 1~1 0. 0~1 0 0~1φ (4)
= - 0 0 1. 0~1 0 0~1φ (3)
= - 0 0 1.~1 0 1 0~1φ (3)
= - 0 0 0. 0 1 1 0~1φ (3)
= - 0 0 0. 0 1 1~1 0 1φ (3)
= - 0 0 0. 0 1 0 0 1 1φ (3)
= - 0 0 0. 0 1 0 1 0 0φ (1)
Menghasilkan .-0.0101φ
Untuk bacaan lebih lanjut, Wikipedia memiliki artikel yang sangat informatif tentang topik ini.
Tantangan
Oleh karena itu, atau sebaliknya, tulis sebuah program atau fungsi yang, diberi string yang mewakili angka finary (seperti yang dijelaskan di atas), menampilkan bentuk standarnya, tanpa memimpin atau membuntuti nol. Input tidak harus mengandung titik faring, tetapi akan selalu berisi digit di sebelah kiri (jadi tidak .123
). Outputnya harus selalu menyertakan titik phinary dan setidaknya satu digit di sebelah kiri itu.
Anda dapat mengambil input melalui STDIN, ARGV atau argumen fungsi dan mengembalikan hasilnya atau mencetaknya ke STDOUT.
Anda dapat menggunakan algoritme yang berbeda dari prosedur di atas asalkan pada prinsipnya benar dan tepat untuk input yang sewenang-wenang - yaitu, satu-satunya batasan yang berpotensi memecah implementasi Anda haruslah batasan teknis seperti ukuran bawaan tipe data atau RAM yang tersedia. Misalnya, mengevaluasi input sebagai angka titik-mengambang dan kemudian memilih angka dengan rakus tidak diperbolehkan, karena orang dapat menemukan input yang ketidakakuratan titik-mengambang akan mengarah pada hasil yang salah.
Ini adalah kode golf, jawaban terpendek (dalam byte) menang.
Uji Kasus
Input Output
1 1.
9 10010.0101
1.618 10000.0000101
1~3.2~1 -0.0101
0.~1021 0. (or -0.)
105.~2 1010.0101
~31~5.~1 -100000.1001
sumber
Jawaban:
Javascript (ES6) -
446418422420 byteDiperkecil:
Diperluas:
Kode menghasilkan fungsi
F
yang melakukan konversi yang ditentukan.Ini masalah sulit untuk golf. Banyak kasus tepi merayap yang mencegah penyederhanaan kode. Secara khusus, berurusan dengan negatif adalah rasa sakit, baik dalam hal parsing dan dalam hal penanganan logis.
Saya harus mencatat bahwa kode hanya menangani "kisaran wajar" input. Untuk memperluas domain fungsi tanpa terikat, jumlah nol di
z
dapat ditingkatkan, dan konstanta yang membatasiwhile( c++ < 99 )
loop dapat ditingkatkan. Rentang yang saat ini didukung sudah berlebihan untuk kasus uji yang disediakan.Output Sampel
Tidak
-0.
cantik, tapi jawabannya masih benar. Saya bisa memperbaikinya jika perlu.sumber
n
input -digit akan berada di antaran
dann log(n)
. Bagaimanapun, jumlah lintasan dapat dinaikkan dengan faktor 10 untuk setiap karakter yang ditambahkan. Jumlah nol dalamz
konstanta juga merupakan masalah yang menarik. Saya menduga bahwa angka 9 adalah berlebihan untuk setiap input yang mungkin.$0
, Javascript tidak mendukungnya. Atau setidaknya Firefox tidak. : Pfor( i = e = 0; i < n-3; i = j )
byfor(; i < n-3; i = j )
dan memindahkan deklarasi ke atas,N = t = n = 0;
digantikan denganN = t = n = i = e = 0;
j
tidak dipegang konstan pada nilaii+1
. Perhatikan di tigaif
blok,j
diatur ulang ke0
. Karenanya pada titik mana pun setelahif
blok pertama itu tidak dapat digunakan sebagai proxy untuki+1
. Variabeli
itu sendiri tidak dapat diperbarui sampai akhir loop (menggunakan pernyataan ketiga dalamfor
) karena nilainya digunakan sampai akhir loop. Tapi setelah mengatakan itu, mungkin aku kehilangan sesuatu. Jika Anda dapat mempersingkat kodenya, mengujinya, dan memverifikasi kodenya masih berfungsi, silakan kirim salinannya ke pastebin.com dan tautan di sini. Saya akan memberikan kredit kepada Anda dalam jawabannya. :)Haskell, 336 byte
Ini adalah algoritma serakah, tetapi dengan representasi
[a,b]
angka yang tepat a + bφ ( a , b ∈ ℤ) untuk menghindari kesalahan floating-point.g[a,b]
menguji apakah a + bφ <0. Contoh penggunaan:sumber