Suatu fungsi dikatakan memiliki siklus panjang n jika ada x dalam domainnya sehingga f n (x) = x dan f m (x) ≠ x untuk 0 <m <n , di mana superscript n menunjukkan n - aplikasi lipat f . Perhatikan bahwa siklus panjang 1 adalah titik tetap f (x) = x .
Tugas Anda adalah mengimplementasikan fungsi bijective dari bilangan bulat ke diri mereka sendiri, yang memiliki tepat satu siklus dari setiap panjang positif n . Fungsi bijective adalah korespondensi satu-ke-satu, yaitu setiap bilangan bulat dipetakan tepat satu kali. Memiliki tepat satu siklus panjang n berarti bahwa ada tepat n nomor yang berbeda x yang f n (x) = x dan f m (x) ≠ x untuk 0 <m <n .
Berikut ini contoh tampilan dari fungsi tersebut di sekitar x = 0 :
x ... -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 ...
f(x) ... 2 4 6 -3 -1 1 -4 0 -2 5 7 -7 -6 3 -5 ...
Kutipan ini berisi siklus dengan panjang 1 hingga 5 :
n cycle
1 0
2 -2 1
3 -4 -3 -1
4 -5 6 3 7
5 -7 2 5 -6 4
...
Perhatikan bahwa di atas saya menggunakan "fungsi" hanya dalam arti matematika. Anda dapat menulis fungsi atau program lengkap dalam bahasa pilihan Anda, selama itu membutuhkan satu bilangan bulat (ditandatangani) sebagai input dan mengembalikan bilangan bulat tunggal (ditandatangani). Seperti biasa, Anda dapat mengambil input melalui STDIN, argumen baris perintah, argumen fungsi dll. Dan output melalui STDOUT, nilai pengembalian fungsi atau argumen fungsi (keluar), dll.
Tentu saja, banyak bahasa tidak (dengan mudah) mendukung integer presisi sewenang-wenang. Tidak apa-apa jika implementasi Anda hanya bekerja pada kisaran jenis integer asli bahasa Anda, selama itu mencakup setidaknya kisaran [-127, 127] dan itu akan bekerja untuk bilangan bulat sewenang-wenang jika jenis bilangan bahasa diganti dengan arbitrary- bilangan bulat presisi.
Aturan standar kode-golf berlaku.
sumber
Jawaban:
Pyth,
2718 bytePenjelasan (Pyth menginisialisasi
Q
ke integer input):Ini memiliki siklus
(−1)
(0, −2)
(1, −3, −4)
(2, −5, −7, −6)
(3, −9, −13, −11, −8)
(4, - 17, −25, −21, −15, −10)
(5, −33, −49, −41, −29, −19, −12)
(6, −65, −97, −81, −57, −57, −37, −23, −14)
(7, −129, −193, −161, −113, −73, −45, −27, −16)
(8, −257, −385, −321, −225 , −145, −89, −53, −31, −18)
(9, −513, −769, −641, −449, −289, −177, −105, −61, −35, −20)
⋮
Siklus panjang n diberikan oleh
( n - 2,
−2 ^ ( n - 2) ⋅1 - 1,
−2 ^ ( n - 3) ⋅3 - 1,
−2 ^ ( n - 4) ⋅5 - 1,
…,
−2 ^ 2 ⋅ (2 · n - 7) - 1,
−2 ^ 1⋅ (2 · n - 5) - 1,
−2 ^ 0⋅ (2 · n - 3) - 1).
Setiap bilangan bulat k ≥ −1 muncul sebagai elemen pertama dari siklus ( k + 2). Untuk setiap bilangan bulat k <−1, kita dapat secara unik menulis 1 - k = 2 ^ i ⋅ (2⋅ j + 1) untuk beberapa i , j ≥ 0; maka k muncul sebagai ( j + 2) th elemen dari ( i + j + 2) -siklus.
sumber
MATL , 47 byte
Cobalah online!
Penjelasan umum
Fungsi 2 di bawah ini sama dengan yang digunakan dalam jawaban @ Sp3000 untuk tantangan terkait. Terima kasih kepada @ Agawa001 karena memperhatikan.
Fungsinya adalah komposisi tiga:
Fungsi 1 dan 3 digunakan karena lebih mudah (saya pikir) untuk mencapai perilaku yang diinginkan di N daripada di Z .
Fungsi 2 adalah sebagai berikut: baris atas adalah domain, baris bawah adalah kode. Koma digunakan untuk kejelasan:
Blok pertama (dari atas
1
ke bawah1
) adalah siklus dengan panjang 1. Blok kedua (dari2 3
ke3 2
) adalah siklus dengan panjang 2, dll. Di setiap blok, bagian bawah (gambar fungsi) adalah bagian atas yang digeser secara melingkar. satu langkah ke kanan.Fungsi 1 adalah sebagai berikut:
Fungsi 3 sama dengan 1 dengan dua garis ditukar.
Contohnya
Gambar
3
adalah-5
. Pertama3
dipetakan7
oleh fungsi 1; kemudian7
dipetakan10
oleh fungsi 2; kemudian10
dipetakan ke -5` oleh fungsi 3.Siklus panjang-1 adalah
0
. Siklus panjang-2 adalah-1 1
. Siklus-3 panjang-3 2 -2
, dll.Kode dijelaskan
Fungsi 1 dan 3 sangat mudah.
Fungsi 2 berfungsi dengan menemukan titik akhir yang lebih rendah dari blok input yang sesuai. Misalnya, jika input ke fungsi ini
9
ditemukan7
(lihat blok di atas). Kemudian mengambil titik akhir atas, yang ada10
dalam contoh. Pergeseran melingkar blok dicapai berkat pengindeksan modular berbasis 1 MATL.sumber
Python 2, 55 byte
59 byte:
Menciptakan siklus
Dimodifikasi dari solusi saya pada tantangan sebelumnya , yang dimodifikasi dari konstruksi Sp3000 .
Fungsinya
membuat siklus ukuran aneh dari angka non-negatif
Untuk menemukan ukuran siklus yang benar
k
, geser inputn
turunk=1,3,5,7,...
hingga hasilnya dalam interval[0,k)
. Siklus interval ini dengan operasin->(n+1)%k
, lalu batalkan semua pengurangan yang dilakukan pada input. Ini diimplementasikan secara rekursif olehk+g(n-k,k+2)
.Sekarang, kita perlu yang negatif untuk membuat siklus genap. Perhatikan bahwa jika kita memodifikasi
g
untuk memulai dengank=2
dig
, kita akan mendapatkan siklus bahkan ukuranIni biject ke negatif melalui bit-melengkapi
~
. Jadi, ketikan
negatif, kami hanya mengevaluasig(n)
sebagai~g(~n,2)
.sumber
k
tampaknya cara lain untuk menghitungMath.floor(Math.sqrt(n))*2+1
.Python 3, 110 byte
Saya masih belum menemukan cara mendapatkan lambda di sana
jika n adalah angka segitiga [1,3,6,10,15,21,28, dll ...] maka f (n) adalah urutan dalam daftar dikalikan dengan yang negatif. jika angkanya negatif, berikan 1 + angka segitiga terkecil berikutnya. selain itu, increment.
Contoh: 5 bukan angka segitiga, jadi tambahkan 1.
Iterasi berikutnya, kita memiliki 6. 6 adalah angka segitiga, dan ini adalah ke-3 dalam daftar, jadi keluarlah -3.
Program memberikan daftar ini
panjang 1: [0]
panjang 2: [1, -1]
panjang 3: [2,3, -2]
panjang 4: [4,5,6, -3]
panjang 5: [7,8,9,10, -4]
Sunting: Terima kasih lagi kepada @TuukkaX karena telah menghapus kelebihan karakter.
sumber
0.5
ke.5
daninput('')
keinput()
.Python 3, 146 byte
Untuk setiap angka lebih besar dari 0, bahkan ada loop (len 2,4,6,8 ...), dan kurang dari 0, loop aneh (1,3,5,7). 0 peta ke 0.
(-3, -2, -1), (0), (1,2), (3,4,5,6)
peta ke
(-2, -1, -3), (0), (2,1), (6,3,4,5)
Sunting: @TuukkaX lepas landas 8 byte dari solusi sebelumnya. Dan 3 lainnya.
sumber
mi
bisa diubah menjadi sesuatu yang lebih kecil, sepertib
.f=lambda x:1+2*int(abs(x)**0.5)if x<1 else 2*int(x**0.5+0.5) x=int(input()) n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
input('')
menjadiinput()
. Kutipan tidak berguna karena kita tidak perlu mencetak apa pun ke konsol ketika kita hanya ingin mendapatkan input.f=lambda x:1+2*int(abs(x)**.5)if x<1 else 2*int(x**.5+.5) x=int(input());n=f(x) if x>0:b=n*(n-2)/4 else:b=-((n+1)/2)**2 print(b+1+(x-b-2)%n)
Matlab (423)
Non-bersaing karena itu memecahkan rekor yang bagus untuk menjadi peringkat untuk peringkat terakhir, sementara aku berjuang untuk memperpendeknya sebisa mungkin.
Beberapa bug nonesensikal mengenai akurasi dalam matlab yang saya tidak bisa menemukan jalan keluar kecuali membuat kode saya sarkastik besar, di sisi lain pemetaan yang saya pilih adalah dalam hal facor utama dan logaritma n-ary.
Eksekusi
Penjelasan
Knonwing, pertama, bahwa angka apa pun dapat ditulis sebagai produk eksponen bilangan prima
N=e1^x1*e2^x2...
dari pangkalan ini saya memilih untuk memetakan gambar siklusC
yang diekstraksi dari eksponen terbesar dari faktor terkecil (tidak harus prima) bahwa N adalah kekuatan sempurna dari .dalam kata-kata yang lebih sederhana, misalkan
N=P^x
P adalah akar sempurna terkecil,x
menunjukkan tepat dua istilah penting untuk siklus:,x=Ʃ(r*P^i)
istilahP
adalah basis siklus juga akar sempurna untuk bilangan utama N, dank
merupakan derajat siklusC=p^k
, di manai
bervariasi antara 1 dan k, koefisienr
bertambah dengan 1 dan dibatasi oleh P-1 untuk pra-gambar berikut sampai semua koefisien diatur ke r = 1, jadi kami beralih ke awal siklus itu.Untuk menghindari tabrakan antar siklus, pilihan eksponensial bilangan prima daripada produknya akurat, karena sebagai contoh dua siklus basa
3
dan2
titik temu di antaranya3*2
, jadi ini dihindari karena siklus ditentukan oleh derajatnya lebih dari derajatnya. basis, dan untuk titik temu ada siklus basis6
dan derajat 1 lainnya.Angka negatif menempatkan pengecualian, karena untuk itu, saya memesan derajat ganjil untuk angka negatif, dan bahkan derajat untuk sisanya. Bagaimana ?
untuk setiap angka N yang tertanam dalam suatu siklus
P^k
, ditulis sebagaiP^(a0*P^i0+a1*P^i1+...)
, jumlah(a0*P^i0+a1*P^i1+...)
tersebut ditransaksikan dalam basis P-ary sebagaia0,a1,....
, untuk memperjelas poin ini jika (p = 2) urutannya harus dalam basis biner. Seperti diketahui sebelumnya tanpa menetapkan kondisi derajat positif / negatif dan (+/- 1) pengecualian, angka N berada di tepi siklus derajatk
jika dan hanya jika urutanA
ditulis sebagai1111..{k+1}..10
atau111..{k}..1
untuk semua pangkalan, jika tidak tidak diperlukan rotasi, dengan demikian menetapkan kondisi negatif / positif untuk masing-masing derajat ganjil / genapk/k'
untuk keduanya membuat urutan ganjil yang ditulis dalam formulir101..{k}..100
, urutan genap ditulis dalam bentuk101..{k'}..10
untuk tepi awal dari masing-masing siklus angka negatif / positif masing-masing .Contoh:
Mengambil angka
N=2^10
,,x=10=2^1+2^3
urutan A ditulisA=1010
, jenis urutan ini menunjukkan tepi terbatas dari siklus bilangan positif, yaituC=2^3
, sehingga gambar berikutnya adalah dari ujung awalA=011
yang8
, Tapi , dengan standarisasi hasil ini menjadi (+ / -) 1 pengecualian2^10/2
peta ke8/2
dan gambar sebelumnya tidak boleh diputar.Mengambil nomor
N=-3^9
,,x=9=3^2
urutan A ditulisA=100
, jenis urutan ini gejala tepi terbatas dari siklus bilangan negatif, yaituC=3^1
, sehingga gambar berikutnya adalah dari ujung awalA=01
yang3
, Tapi, dengan mengadaptasi hasil ini ke negatif / positif-3^9
peta kondisi untuk-3
.untuk pasangan
(-/+)1
, saya membayangkan untuk mengganggunya dalam jumlah basis siklus2
, dengan kedok bahwa urutan biasa dari kelompok siklik{2,4}{8,16,32,64}..
dibuat dalam bentuk lain{1,2}{4,8,16,32}..
, ini mencegah hilangnya elemen sebelumnya, dan operasi yang dilakukan hanya bergeser dengan muncul elemen baru di.Hasil:
menjalankan lembar-kode kecil ini untuk memverifikasi rentang angka siklik pertama yang masuk akal:
Ini mengarah ke hasil ini
Yang terakhir adalah segmentasi-kesalahan tetapi cocok dengan rentang [-127.127] standar yang ditandatangani integer.
sumber
JavaScript (ES6), 73 byte
Bekerja dengan menghitung urutan (0, -1, 1, -2, 2, -3, 3, ...) hingga ditemukan
n
, menghitung siklus saat berjalan.i
berisi entri saat ini;j
berisi awal dari siklus saat ini,k
indeks dalam siklus,l
panjang siklus saat ini danm
entri berikutnya dalam urutan. Setelah kami menemukann
kami kemudian mengambilj
jika kita berada di akhir siklus ataum
jika tidak.sumber