Latar Belakang
Sebuah urutan fraktal adalah urutan bilangan bulat di mana Anda dapat menghapus kejadian pertama dari setiap bilangan bulat dan berakhir dengan urutan yang sama seperti sebelumnya.
Urutan seperti itu sangat sederhana disebut parafrase Kimberling . Anda mulai dengan bilangan asli positif:
1, 2, 3, 4, 5, 6, 7, 8, 9, ...
Kemudian Anda mengosongkan beberapa bagian:
1, _, 2, _, 3, _, 4, _, 5, _, 6, _, 7, _, 8, _, 9, ...
Dan kemudian Anda berulang kali mengisi bagian yang kosong dengan urutannya sendiri (termasuk bagian yang kosong):
1, 1, 2, _, 3, 2, 4, _, 5, 3, 6, _, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, _, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, _, 9, ...
1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 6, 2, 7, 4, 8, 1, 9, ...
Itu urutan fraktal kami! Sekarang mari kita ambil jumlah parsial:
1, 2, 4, 5, 8, 10, 14, 15, 20, 23, 29, 31, 38, 42, 50, 51, 60, ...
Tetapi bagaimana jika kita mengulangi proses ini? "Fraktalise" urutan baru (yaitu jumlah parsial yang diperoleh dari langkah-langkah di atas):
1, _, 2, _, 4, _, 5, _, 8, _, 10, _, 14, _, 15, _, 20, _, 23, ...
1, 1, 2, _, 4, 2, 5, _, 8, 4, 10, _, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, _, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, _, 20, 8, 23, ...
1, 1, 2, 1, 4, 2, 5, 1, 8, 4, 10, 2, 14, 5, 15, 1, 20, 8, 23, ...
Dan ambil jumlah parsial lagi:
1, 2, 4, 5, 9, 11, 16, 17, 25, 29, 39, 41, 55, 60, 75, 76, 96, ...
Bilas, ulangi. Ternyata proses ini menyatu. Setiap kali Anda mengulangi proses ini, awalan yang lebih besar dari urutan akan tetap diperbaiki. Setelah jumlah iterasi yang tak terbatas, Anda akan berakhir dengan OEIS A085765 .
Fakta menyenangkan: Proses ini akan menyatu ke urutan yang sama bahkan jika kita tidak memulai dari bilangan asli selama urutan awal dimulai 1
. Jika urutan asli dimulai dengan yang lain x
, kami akan mendapatkannyax*A085765
sebagai gantinya.
Tantangan
Diberikan bilangan bulat positif N
, output N
elemen th dari urutan konvergen.
Anda dapat menulis sebuah program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi dan mengeluarkan hasilnya melalui STDOUT (atau alternatif terdekat), nilai pengembalian fungsi atau parameter function (out).
Anda dapat memilih apakah indeks N
berbasis 0 atau 1.
Uji Kasus
Urutan dimulai dengan:
1, 2, 4, 5, 9, 11, 16, 17, 26, 30, 41, 43, 59, 64, 81, 82, 108, 117, 147, 151, 192, 203, 246, 248, 307, 323, 387, 392, 473, 490, 572, 573, 681, 707, 824, 833, 980, 1010, 1161, 1165, 1357, 1398, 1601, 1612, 1858, 1901, 2149, 2151, 2458, 2517
Jadi input 5
harus menghasilkan output9
.
Berikut ini adalah implementasi referensi CJam yang naif yang menghasilkan N
angka pertama (diberikan N
pada STDIN). Perhatikan bahwa kode Anda hanya mengembalikan N
elemen th, bukan keseluruhan awalan.
N
istilah th dari A085765 , benar?Jawaban:
CJam (
2322 bytes)Jumlah parsial diberikan pada indeks genap dari urutan fraktal, yaitu A086450 . Perulangan yang diberikan di sana sebagai definisi A086450 adalah dasar untuk implementasi ini.
Menggunakan "tumpukan" eksplisit (dalam kutipan menakut-nakuti karena itu bukan LIFO):
Demo online
Pembedahan
Pada 23 byte ada pendekatan yang jauh lebih efisien, dengan memoisasi:
Demo online
sumber
f(0) = 1; f(n) = f(n/2) + (n % 2 ? 0 : f(n-2)); return f(2*x)
, tetapi saya tidak dapat menemukan cara untuk mendapatkan penghematan dengan pendekatan itu di CJam.Python 2,
55 4942Saya tidak tahu apa yang sedang terjadi, tetapi tampaknya sulit untuk mengalahkan formula Maple dari halaman OEIS. Ini menggunakan pengindeksan berbasis 0.
Terima kasih kepada @PeterTaylor untuk -6 byte.
sumber
or
efektifg(n,1) = f(n/2,n%2); g(n,0) = f(n-1) + g(n,1)
; sehingga Anda dapat menarik keluar yang umumg(n,1)
untuk mendapatkanf=lambda n,t=0:n<1or f(n/2,n%2)+0**t*f(n-1)
Haskell, 65
sumber
Template Dianggap Berbahaya , 124
Ini adalah fungsi anonim. Ini kurang lebih sama dengan
jawaban Python sayarumus Maple pada halaman OEIS, kecuali bahwa saya tidak mengimplementasikan modulus, jadi saya harus menggunakan nn / 2 * 2 bukannya n% 2.Diperluas:
sumber
Mathematica,
4744 bytesumber
Matlab
108103Saya menggunakan fakta bahwa seri yang diinginkan adalah jumlah parsial dari https://oeis.org/A086450
Tetapi kompleksitas perhitungan implementasi saya masih jauh dari optimal, bahkan untuk perulangan yang sederhana ini.
sumber