Tantangan ini diinspirasi oleh blog pemrograman yang sering saya kunjungi. Silakan lihat posting asli di sini: Puzzle Pemrograman
Tantangan
Tetapkan fungsi f:Q->Q
sedemikian rupa f(f(n)) = -n
untuk semua bilangan bulat bukan nol n
, dan di mana Q
himpunan bilangan rasional.
Detail
Dalam bahasa apa pun yang Anda inginkan, sebutkan satu fungsi atau program f
yang menerima sebagai parameter satu nomor n
dan mengembalikan atau menampilkan satu nomor f(n)
.
Input dapat diberikan melalui mekanisme apa pun yang paling alami untuk bahasa Anda: argumen fungsi, baca dari STDIN, argumen baris perintah, posisi tumpukan, input suara, tanda-tanda geng, dll.
Output harus berupa nilai balik dari fungsi / program atau dicetak ke STDOUT.
Saya ingin membatasi jawaban untuk fungsi yang tidak memanfaatkan status program atau memori / data global yang terlihat dari luar fungsi f
. Misalnya, menjaga penghitung di luar f
itu dihitung berapa kali f
dipanggil dan hanya melakukan negasi berdasarkan perhitungan ini tidak terlalu menantang atau menarik bagi siapa pun. Keputusan yang diambil f
harus hanya bergantung pada data dalam f
lingkup leksikal.
Namun, batasan ini mungkin tidak sesuai untuk beberapa bahasa berorientasi tumpukan atau jenis bahasa lain yang tidak membedakan tipe data atau cakupan ini. Silakan gunakan penilaian terbaik Anda untuk tetap dengan semangat tantangan ini.
Mencetak gol
Aturan golf kode umum berlaku - skor Anda adalah jumlah byte dalam kode sumber Anda.
Jawaban minimal membutuhkan domain dan kode f
untuk menjadi subset dari rasional Q
. Jika Anda membatasi domain dan kode domain Anda f
ke bilangan bulat Z
, maka skor Anda adalah batas tertinggi 90% dari jumlah byte dalam kode sumber Anda.
Tiebreak
Dalam hal seri, berikut ini akan digunakan secara berurutan:
- Jumlah simbol non-spasi putih yang dapat dicetak dalam kode sumber Anda
- Tanggal dan waktu paling awal pengiriman jawaban
Edit
Anda tidak diharuskan untuk mendukung angka-angka berukuran sewenang-wenang. Silakan mengartikan set Z
dan Q
sebagai tipe data dalam bahasa yang Anda pilih (biasanya integer dan floating point, masing-masing).
Jika solusi Anda sepenuhnya bergantung pada struktur atau pola bit dari tipe data, mohon jelaskan keterbatasannya dan bagaimana itu digunakan.
f:Q->Q
artinya?f
adalah fungsi pemetaan anggotaQ
(angka rasional) ke anggota lain (mungkin sama) dariQ
. lihat en.wikipedia.org/wiki/Function_(mathematics)#NotationJawaban:
J, 9 poin (10 karakter)
Berdasarkan jawaban stackoverflow :
Ide pertama (13 karakter):
sumber
Python:
61 34 30 2927 poinf: Q -> Q
dalam matematika:
dalam Python:
diuji dengan
logika di balik ini:
Saat Anda mengambil bilangan bulat
n
dan memasukkannya ke dalam,f
Anda akan mendapatkannyax+0.5
. Ini bukan bilangan bulat lagi, jadi aplikasi selanjutnya0.5-(x+0.5)
adalah-x
.Kredit
Terimakasih untuk
Catatan
Pertama saya pikir ini akan baik-baik saja
tapi itu f: N-> C dan itu tidak diperbolehkan: - /
sumber
f=lambda x:x%1>0and(-x+x%1)or x+.1
yang hanya 34 karakter.f=lambda x:[x+.1,x%1-x](x%1>0)
hanya 30f=lambda x:[x+.5,.5-x][x%1>0]
. Perhatikan penggunaan 0,5 bukannya 0,1 untuk mengatasi masalah presisif:Q->Q
tidak hanya berarti bahwa f memetakan bilangan rasional ke bilangan rasional. Yang definisi saya tentang f tidak.C, 41 poin (41 atau 45 karakter)
Bekerja menggunakan 32- dan 64-bit.
f : Z -> Z
(kecualiINT_MAX
):Jika kita tidak harus memasukkan,
0
kita dapat mencukur beberapa karakter (41 karakter):f : Z -> Z
(kecuali0
&INT_MAX
):Fungsi ini berfungsi dengan membagi semua bilangan bulat menjadi 4 kelompok berdasarkan tanda dan paritasnya.
Jadi kami memiliki 4 kombinasi berbeda:
Karena kita perlu mengganti tanda nomor, tetapi bukan paritas setelah dua lintasan, kita mendapatkan dua kemungkinan urutan yang berbeda:
Dalam contoh ini saya telah memilih yang pertama.
Pertama kita perlu memetakan semua bahkan bilangan bulat positif ke bilangan bulat negatif ganjil. Kami melakukan ini dengan mengubah tanda dan menambah nomor (Anda juga dapat memilih untuk mengurangi angka):
Kita kemudian perlu memetakan semua bilangan bulat negatif ganjil ke bahkan bilangan bulat negatif. Kita perlu memastikan bahwa
f2(f1(n)) = -n
:Menggunakan metode yang sama kami temukan
f3
danf4
:Untuk menggabungkan fungsi-fungsi ini menjadi satu fungsi tunggal, kami mengamati bahwa setiap kali
n
bahkan kami mengganti tandan
dan setiap kalin
positif kami bertambah satu dan jika tidak, kami mengurangi satu:Dengan demikian ini dapat ditulis ulang sebagai:
tempat
odd(n)
pengembalian1
untuk angka ganjil dan-1
untuk angka genap.Ada 4 solusi total:
INT_MIN
mungkin selalu dianggap sebagai tepi kasus dalam semua 4 fungsi sebagai-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.sumber
0
dan 3 nomor lainnya.Z
bonus jika Anda mencakup 0, setidaknya.Ini dia.
Contoh langsung :
Jenis input cn dapat secara sewenang-wenang disesuaikan dengan kebutuhan Anda. Versi ini berfungsi untuk bilangan bulat integer yang lebih kecil besarnya dari 2 ^ 32-1.
sumber
f:Q->Q
, tidakf:Z->Z
.f:Z->Z
, maaf untuk katareturn -i
JavaScript, 18
Menggunakan notasi panah lemak baru (Firefox 22).
Versi lain (18):
Versi sebelumnya (20):
Contoh:
sumber
Mathematica 18
Inilah
⌊...⌋
fungsi lantai. Hanya menggunakan bilangan rasional (bukan daftar, bilangan kompleks, dll)sumber
x86 bahasa rakitan (FASM). Argumen dan hasilnya ada di eax register.
Ini berfungsi dengan baik untuk -2 ^ 30 <N <+ 2 ^ 30-1
16 byte kode yang dapat dieksekusi.
sumber
Gangguan Umum: 35 byte
Skema (dan Racket): 36 byte
Tidak digabungkan dengan komentar dan penjelasan:
Untuk angka apa pun
x
di[1,->]
dalamif
akan berubah menjadi fraksi1/2
yang merupakan angka persis nyata dalam kedua bahasaBagian bagi kemudian akan menjadi
(/ 1/2 x)
sehingga pecahan akan menjadi1/(x*2)
yang selalu di bawah ini1
. Untuk1
itu akan1/2
, untuk2
itu1/4
, dll.Untuk angka apa pun di bawah 1,
if
akan berubah menjadi fraksi-1/2
, yang membuat fungsi melakukan(/ -1/2 x)
yang mana-1/(2*x)
tetapi karena kita dapat mengharapkan nilai sebagai hasil dari menjalankan sebelumnya kita dapat mengganti x untuk 1 / (x * 2) membuat aplikasi ganda-1/((1/(x*2))*2) = -x
Misal sejak
1
berubah menjadi1/2
aplikasi kedua ini(/ -1/2 1/2) ==> -1
sumber
C, 60 (⌈66 * .9⌉)
Ini adalah versi yang tidak dikondensasi:
Metode ini hanya bekerja menggunakan bilangan bulat, sehingga mendapat bonus skor 90%. Saya awalnya menulis dalam java, tetapi menyadari bahwa program ini khususnya bisa mendapatkan keuntungan dari operator logis C-style.
Karena tidak ada bilangan bulat yang sesuai dengan
-INT_MIN
, sebaliknyaf(f(INT_MIN))
mengembalikanINT_MIN
.Pemetaan yang mendasari secara aljabar agak sederhana. Mengeksekusi pernyataan tersebut
x=f(x)
menggantikan x dengan:x+1
, jikax
positif dan aneh-x+1
, jikax
positif dan genapx-1
, jikax
negatif dan ganjil-x-1
, jikax
negatif dan genapHasil dari setiap kasus akan jatuh di bawah kasus berikutnya saat fungsi berikutnya diterapkan ke x.
Seperti yang Anda lihat, membuat kasing dengan kasing yang menghasilkannya
-x
.Kode ini adalah hasil dari beberapa penyederhanaan fungsi untuk memanfaatkan struktur bit dari integer pujian dua.
sumber
> <> , 21 + 3 = 24 byte, 22 poin
Gunakan juru bahasa Python resmi , dan gunakan
-v
opsi baris perintah untuk memasukkan input, dengan biaya 3 byte.Saya punya perasaan bahwa ini bisa lebih baik - saya akan terus melihatnya dan mencoba untuk menurunkannya.
Input yang diberikan
n
, output programdi mana
(n>0)
dan(n<0)
adalah booleans. Ini sama dengan jawaban Python Gelatintetapi
><>
tidak memiliki operator eksponensial bawaan sehingga kami gunakan(1 - 2*(n%2))
sebagai pengganti(-1)**n
.Berikut ini adalah teori matematika - baca jika (dan hanya jika) Anda tertarik:
Dengan fungsi apa pun
f: Z -> Z
sehinggaf(f(n)) = -n
untuk semua yang adan
diZ
dalamnya, kita segera melihat bahwaf(f(f(f(n)))) = n
, atau dengan kata lain,f^4
adalah fungsi identitas. Secara khusus,f
dapat dibalik, dan fungsi kebalikannya adalahf^3
. Dengan demikianf
adalah permutasi dariZ
, dan karenaf^4 = Id
itu berikut bahwa setiap orbit (atau siklus) darif
memiliki ukuran baik1
,2
atau4
.Selanjutnya, kita melihatnya
f(0) = 0
. Bukti:,f(0) = f(-0) = f(f(f(0))) = -f(0)
jadif(0) = 0
, seperti yang diinginkan. Sebaliknya, anggaplahx
dalam siklus panjang1
atau2
, jadif(f(x)) = x
. Lalu-x = x
begitux = 0
.Dengan demikian
f
seluruhnya terdiri dari 4 siklus, kecuali untuk titik tetap (1 siklus) di0
.Selanjutnya, setiap 4 siklus harus memiliki bentuk
(x, y, -x, -y)
, dan dengan memutar siklus di sekitar kita dapat mengasumsikan itux
dany
keduanya positif. Sebaliknya, setiap produk seperti partisi 4-siklus bilangan bulat nol menentukan pilihanf
.Dengan demikian setiap pilihan
f
koresponden secara unik dengan grafik berarah yang simpulnya adalah bilangan bulat positif, sehingga setiap simpul adalah kejadian tepat satu panah, baik yang masuk atau keluar. Lebih tepatnya, dalam grafik tak berarah yang mendasarinya, setiap simpul memiliki derajat tepat1
. (Setiap 4 siklus(x y -x -y)
denganx
dany
positif sesuai dengan panahx --> y
.)Fungsi dalam jawaban ini (dan beberapa jawaban lain di sini) sesuai dengan grafik di mana
1 --> 2
,3 --> 4
dan pada umumnya2k-1 --> 2k
.Grafik tersebut di bijection dengan urutan yang tak terbatas dari pasangan memerintahkan
(a_n, p_n)
, di mana masing-masinga_n
adalah bilangan bulat positif dan masing-masingp_n
adalah baik0
atau1
: diberikan berurutan(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, pertama kita pasangan1
dengan1 + a_1
, dan kemudian kita membentuk baik panah1 --> 1 + a_1
atau panah1 + a_1 --> 1
tergantung pada apakahp_1
ini0
atau1
. Pada dasarnya, panah adalah<
tanda atau>
tanda, tergantung pada paritasp_1
.Selanjutnya, ambil bilangan bulat positif terkecil yang tidak berpasangan
k
, dan hitung darik
, persisa_2
langkah-langkah, MEMASANG angka yang sudah dipasangkan dengan sesuatu. Pasangkank
dengan hasilnya, dan atur arah panah tergantungp_2
seperti di atas. Kemudian ulangi dengan(a_3, p_3)
, dll.Setiap panah pada akhirnya akan ditentukan dengan cara ini, sehingga prosesnya didefinisikan dengan baik. Fungsi dalam jawaban ini sesuai dengan urutan
(1,0), (1,0), (1,0), ...
, karena pada langkahn
bilangan bulat tidak berpasangan terkecil adalah2n-1
dan tidak ada bilangan bulat yang lebih besar daripada yang2n-1
telah dipasangkan dengan apa pun, jadi kita dapatkan2n-1 --> 2n
untuk masing-masingn
(panah diorientasikan dengan cara ini karena masing-masingp_n
sama dengan0
).Kardinalitas himpunan ini adalah
(N*2)^N = N^N
, yang pada paragraf terakhir jawaban ini sama dengan2^N
, kardinalitas bilangan real.sumber
Untuk memperbaiki jawaban J sebelumnya (saya tidak memiliki reputasi yang cukup untuk mengomentari yang asli):
Itu hanya menggantikan
_1&^
dengan1-~2*2|]
, yang memberi tanda sebaliknya. Jadi saya mengubah-
ke+
(yang hanya penting pada input1
dan_1
).Inilah tes-tesnya:
Seperti yang Anda lihat, domain dan rentang semua bilangan real, tetapi hanya berfungsi untuk bilangan bulat (termasuk 0).
Penjelasan:
sumber
GolfScript
ceiling(26*.9)=24
Golfscript hanya menangani bilangan bulat, jadi terapkan
Z
bonus dengan total 24 poin:Kasing khusus 0 akun untuk 8 karakter. Mengabaikan 0, kita dapat memiliki 17 poin jawaban:
Kode ini melakukan hal berikut ini ke integer
x
di atas tumpukan:x
0, tinggalkan0
di tumpukan dan tidak menerapkan aturan lagi.x
genap, negasikanx
.x
positif, tambahkan1
.x
negatif, kurangi1
.Ini secara logis menghubungkan set 4 angka dalam satu siklus, di mana
f
elemen lintas siklus, dan sudut-sudut yang berlawanan dari siklus adalah negatif satu sama lain. Setiap bilangan bulat adalah bagian tepat dari 1 siklus seperti itu, kecuali 0 yang merupakan casing khusus. Misalnya, untuk{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Satu-satunya kasus uji yang relevan yang dapat saya pikirkan adalah negatif aneh, negatif bahkan, positif aneh, bahkan positif
0
, dan kemudian saya melemparkan-1
dan1
karena kedekatannya dengan0
mungkin telah menyebabkan masalah:Saya yakin GolfScript yang sebenarnya dapat sedikit ditingkatkan. Itu tidak terasa seperti itu harus mengambil 26 karakter! Senang mendengar beberapa saran.
sumber
Jawa, hanya untuk bersenang-senang
Berikut ini adalah implementasi yang melakukan penambangan aktual antara ℤ dan ℤ², yang merupakan fungsi aneh pada saat yang sama (g (-x) == -g (x)). Ini memperlakukan elemen ℤ² yang sesuai sebagai bilangan kompleks dan mengalikannya dengan "i", lalu mengubahnya kembali menjadi ℤ.
f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x
Fungsi berjalan di O (1).
PS Selamat Tahun Baru!
sumber
Python 3 - 38
Mirip dengan jawaban @ moose, tetapi
f(n) == n
,. Berfungsi untuk semua nilai integer.sumber
Perl, 33 (non-spasi putih)
Edit:
$=.".1"
disingkat menjadi"$=.1"
(terima kasih ardnew).Matematika:
Tidak Disatukan:
Contoh:
sumber
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
ini tidak keadaan bebas, ia menggunakan sebuah negara melalui variabel$_
. Karena itu,f
tidak ada lagi fungsi (dalam arti matematika), karena nilai yang berbeda dimungkinkan untuk nilai input yang sama tergantung pada keadaan (cuaca$_
mengandungx
atau tidak). Algoritme saya tidak menggunakan status, informasi dikodekan dalam nilai output. Integer dikonversi ke bilangan real dengan menambahkan.1
. Dan bilangan real dikonversi kembali ke bilangan bulat dengan tanda diaktifkan.$=
?f
didefinisikanQ->Q
) denganx
char itu. juga$=.".1"
dapat disingkat menjadi"$=.1"
$=
hanya membutuhkan nomor integer. Hal yang sama dapat dicapai dengan menggunakan variabel biasa:$a=int$_[0]
. Tetapi biaya tiga byte tambahan karena fungsiint
.Julia, 26
Tidak super kompetitif, tetapi sangat Julian karena bergantung pada pengiriman ganda. Itu hanya membuat na Rasional jika itu sebuah Int, atau sebuah int dengan tanda minus jika itu hal lain. Orang mungkin keberatan bahwa ini adalah 2 fungsi, tetapi Julia menganggap ini sebagai satu fungsi dengan dua metode, dan itu setara dengan mendefinisikan satu fungsi dengan statemen if pada tipe
n
.sumber
3==3//1
kembalitrue
tetapif(3//1)==f(3)
kembalifalse
.Permen ,
2018 byteMenggunakan 3 -> 4 -> -3 -> -4 -> 3 trik.
Untuk memintanya gunakan tombol -i pada interpreter
Contoh invokasi ganda:
Bentuk panjang:
sumber
Dyalog APL, 9 poin
Sumbernya berukuran 9 byte dan memenuhi syarat untuk bonus (yang tidak membantu sama sekali). Ini juga menggunakan rumus dari jawaban SO atas.
sumber
Python: 32 byte (29 poin)
f: Z -> Z
Menggunakan metode Ben Reich.
sumber
(n>0)-(n<0)
dengancmp(n,0)
, untuk menyimpan beberapa byte. (Tetapi tidak dalam Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
sumber
Java, 113 byte
Pendekatannya cukup sederhana. Itu berakhir lebih banyak byte daripada yang saya perkirakan, tetapi mungkin bisa diturunkan sedikit.
Ini pada dasarnya menciptakan 4 "area" berbeda x, memanfaatkan fakta bahwa Java dengan senang hati membiarkan variabel membungkus. Saya harus melakukan beberapa konversi rumit untuk angka negatif yang merupakan alasan utama ini berakhir lebih besar dari yang diperkirakan.
Berfungsi untuk semua x selain -2147483648.
sumber
Urutan angka yang sama (3, 4, -3, -4, 3 ...) sebagai jawaban skrip golf, tetapi diimplementasikan dalam perl (42 karakter setelah spasi dilucuti)
Lebih jelas:
Atau bahkan lebih jelas:
Keluaran:
sumber
Sed, 25 byte.
Pemakaian:
sumber
Matlab, 26 karakter
sumber
C ++ -
6355.8Begini tampilannya kode:
Itu tidak bekerja pada bilangan bulat yang byte keempatnya sama dengan 0xB karena menggunakan nilai itu untuk melacak lintasan. Jika tidak bekerja pada anggota Z, termasuk nol.
sumber
f
dengan variabel statis. tapi lalu apa gunanyasqrt
?sqrt
karena dibulatkan pula dengan tipe casting. Saya akan refactor sehingga berfungsi tanpa variabel statis.55.8
, tetapi kode Anda saat ini adalah 62 byte. Sunting: Sudahlah, saya tidak membaca pertanyaan dengan benar.Diperbarui dengan fungsi yang disediakan oleh Synthetica (jelas orang yang seharusnya mendapatkan kredit untuk ini sekarang)
Bahasa: Python
Jumlah karakter: 41 termasuk spasi
sumber
f=lambda x:-float(x) if str(x)==x else`x`
cukup sedikit lebih pendek: 41 termasuk spasif
mengembalikan sebuah string; spesifikasi mengatakan itu harus mengembalikan bilangan rasional.Prolog, 36 byte
Kode:
Dijelaskan:
Contoh:
sumber
Javascript ES6,
2726 bytesumber
Mouse-2002 ,
211912 byteMendefinisikan suatu fungsi
A
; sebut seperti#A,#A,?;;
(yang akan menunggu pengguna memasukkan nomor apa pun). Atau, sebut saja seperti di#A,#A,n;;
manan
nomor apa pun.sumber
Julia, 21
Kemudian
p // q adalah notasi literal bilangan rasional dari julia.
sumber