Tentukan fungsi f (n) untuk bilangan bulat positif n sebagai berikut:
- n / 2 , jika n genap
- 3 * n + 1 , jika n ganjil
Jika Anda berulang kali menerapkan fungsi ini ke n lebih besar dari 0, hasilnya selalu konvergen ke 1 (meskipun belum ada yang bisa membuktikannya). Properti ini dikenal sebagai Dugaan Collatz .
Tentukan waktu berhenti integer sebagai berapa kali Anda harus melewati fungsi Collatz f sebelum mencapai 1. Berikut adalah waktu berhenti dari 15 integer pertama:
1 0
2 1
3 7
4 2
5 5
6 8
7 16
8 3
9 19
10 6
11 14
12 9
13 9
14 17
15 17
Mari kita sebut set angka dengan sepupu Collatz waktu berhenti yang sama . Misalnya, 5 dan 32 adalah sepupu Collatz, dengan waktu berhenti 5.
Tugas Anda: menulis sebuah program atau fungsi yang mengambil integer nonnegatif dan menghasilkan set sepupu Collatz yang waktu berhentinya sama dengan integer itu.
Memasukkan
Integer non negatif, diberikan melalui argumen STDIN, ARGV, atau fungsi.
Keluaran
Daftar semua angka yang waktu berhentinya adalah S, diurutkan dalam urutan menaik . Daftar tersebut dapat berupa output oleh program Anda, atau dikembalikan atau dihasilkan oleh fungsi Anda. Format output fleksibel: dipisahkan oleh spasi, dipisahkan oleh baris, atau format daftar standar bahasa Anda baik-baik saja, asalkan jumlahnya mudah dibedakan satu sama lain.
Persyaratan
Kiriman Anda harus memberikan hasil yang benar untuk setiap S ≤ 30. Itu harus selesai dalam hitungan detik atau menit, bukan jam atau hari.
Contohnya
0 -> 1
1 -> 2
5 -> 5, 32
9 -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768
Berikut adalah inti dari output untuk S = 30 .
Ini adalah kode-golf : program terpendek dalam byte yang menang. Semoga berhasil!
Jawaban:
Pyth,
262421 byteKode ini berjalan seketika untuk
S=30
. Cobalah sendiri: PeragaanTerima kasih kepada @isaacg untuk menghemat 5 byte.
Penjelasan
Kode saya mulai dengan
1
dan membatalkan fungsi Collatz. Ini peta semua nomord
dariS-1
langkah untuk2*d
dan(d-1)/3
. Yang terakhir tidak selalu valid.sumber
-F
.- ... 1
sekitar jumlah ke dalam pengurangan, Anda tidak perlu mengurangi menjadi.u
, atau-F
luar. Menghemat 2 karakter.q4%d6
setara dengan!%hhd6
, tetapi 1 karakter lebih pendek.Mathematica,
989289 byteSolusi ini
S = 30
langsung terpecahkan :Ini adalah fungsi tanpa nama yang mengambil
S
parameter dan mengembalikan daftar sepupu Collatz.Algoritma ini adalah pencarian pertama yang sederhana. Sepupu Collatz untuk diberikan
S
adalah semua bilangan bulat yang dapat dihubungi dari sepupu Collatz untukS-1
melalui2*n
atau angka ganjil yang dapat dihubungi melalui(n-1)/3
. Kita juga perlu memastikan bahwa kita hanya menghasilkan bilangan bulat yang dicapai untuk pertama kali setelahS
langkah, jadi kita melacak semua sepupu sebelumnyap
dan menghapusnya dari hasil. Karena kita tetap melakukan itu, kita dapat menyimpan beberapa byte dengan menghitung langkah-langkah dari semua sepupu sebelumnya (bukan hanya yang dariS-1
) untuk menyimpan beberapa byte (yang membuatnya sedikit lebih lambat, tetapi tidak terasa diperlukanS
).Ini adalah versi yang sedikit lebih mudah dibaca:
sumber
Python 2,
8683757371 byteSebut seperti
f(30)
.n = 30
cukup instan.(Terima kasih kepada @DLosc untuk gagasan pengulangan dengan
k
menjadi nomor daripada daftar sepupu, dan beberapa byte. Terima kasih kepada @isaacg karena telah menjatuhkan~-
.)Varian ini jauh lebih pendek, tetapi sayangnya terlalu lama karena percabangan eksponensial:
sumber
f=lambda d,n=1:d and sorted(sum((c(d-1,x)for x in[n*2]+[~-n/3][:n>4==n%6]),[]))or[n]
. Ini kurang efisien dengan pemanggilan fungsi tetapi masih dilakukann = 30
di bawah satu detik.f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,~-k/3)or[])+f(n-1,k*2))
~-
itu tidak perlu karena Anda menggunakan divisi integer.CJam,
2926 byteKredit pergi ke @isaacg untuk idenya untuk menghapus 1 setelah setiap iterasi, yang menyelamatkan saya dua byte secara langsung dan satu lagi secara tidak langsung.
Cobalah online di juru bahasa CJam (harus selesai dalam waktu kurang dari satu detik).
Bagaimana itu bekerja
sumber
CJam, 35 byte
Penjelasan segera hadir. Ini adalah versi yang jauh lebih cepat daripada pendekatan "cukup lurus ke depan" (lihat di edit history).
Cobalah online di sini untuk
N = 30
yang berjalan di detik pada versi online dan langsung di Compiler Javasumber
It should finish in seconds or minutes, not hours or days.
S=15
tidak berfungsi.Java 8, 123
Kapan
x
30, program ini memakan waktu 15 menit dan 29 detik.Diperluas
sumber
javac 1.7.0_79
di Ubuntu memberi saya banyak kesalahan sintaks.i > 1 && ++n <= x
(Anda dapat dropn++
juga) tampaknya bahkan lebih cepat untuk hanya 5 karakter ... sekitar 3 menit untuk S = 30 untuk saya. Itu akan dicukur dengan aman di bawah satu menit jika saya termasuk.parallel()
juga, tetapi karena ini adalah kode-golf ...Python 2, 118 byte
Yah, saya pikir saya tidak akan mencapai skor Python terbaik setelah melihat solusi @ Sp3000. Tapi itu tampak seperti masalah kecil yang menyenangkan, jadi saya ingin mencoba solusi independen:
Hal yang sama sebelum membuka spasi:
Ini adalah implementasi yang sangat langsung dari pencarian pertama yang luas. Di setiap langkah, kami memiliki set dengan waktu berhenti
k
, dan menurunkan set dengan waktu berhentik + 1
dengan menambahkan kemungkinan pendahulu dari setiap nilait
dalam set dari langkahk
:2 * t
selalu merupakan pendahulu yang mungkin.t
dapat ditulis sebagai3 * u + 1
, di manau
angka ganjil yang bukan1
, makau
merupakan pendahulu juga.Diperlukan waktu sekitar 0,02 detik untuk dijalankan
N = 30
di MacBook Pro saya.sumber
s.add(x)
tidak perlu bermain golf karena biasanya Anda bisa melakukannyas|={x}
. Juga, menggunakan~-x
bukannya(x+1)
menyimpan di kurung. Tetapi sebaliknya, kerja bagus :)s.add()
karena itu menjadi tugas, dan tidak bisa menjadi bagian dari ekspresi lagi. Ini berhasil untuk yang pertama. Thefor
loop berdasarkan counter selalu jenis verbose juga. Saya pikir saya bisa memperpendeknya dengan menggunakanwhile
loop, tetapi ternyata persis sama dengan panjang yang sama.for
loop, karena Anda tidak menggunakan input dengan cara lain yang mungkin bisa Anda lakukanexec"..."*input()
sebagai gantinya :)PHP 5.4+, 178 byte
Fungsinya
Uji & Keluaran
S (30) berjalan dalam 0,24 detik * , mengembalikan 732 elemen. Pasangan adalah
* Untuk menghemat byte, saya harus menambahkan
ksort
danarray_keys
di setiap langkah. Satu-satunya pilihan lain yang saya miliki adalah membuat fungsi pembungkus kecil yang memanggilc()
dan kemudian memanggilarray_keys
danksort
hasilnya sekali. Tetapi karena waktu masih cukup tajam, saya memutuskan untuk mengambil hit kinerja untuk jumlah byte yang rendah. Tanpa penyortiran & pemrosesan yang tepat, waktunya rata-rata 0,07 detik untuk S (30).Jika ada yang punya cara cerdik untuk mendapatkan pemrosesan yang tepat hanya sekali tanpa terlalu banyak byte tambahan, beri tahu saya! (Saya menyimpan nomor saya sebagai kunci array, maka penggunaan
array_keys
danksort
)sumber
Bahasa C
sumber
{}
tombol untuk memformat kode Anda, yang telah saya lakukan untuk Anda. Tapi seperti kata Alex, tolong tambahkan nama bahasa (C?) Dan coba mainkan :) Tapi selamat datang!f
tidak berlaku dengan benar. Dengans=5
, saya mendapatkan banyak hasil yang salah.if (r == s)return true;
seharusnyareturn (r==s)
, karenaf
tidak akan mengembalikan apa pun saat bermakna(r < s)
. Juga, saya pikir Anda harus menyatakani
dalamf
sepertilong
, karena akan meluap cukup cepat untuk beberapa nilai.return (r==s);