Pertimbangkan ekspresi 2^2^...^2
dengan n
operator ^
. Operator ^
berarti eksponensial ("dengan kekuatan"). Asumsikan bahwa ia tidak memiliki asosiatif default, sehingga ekspresi perlu dikurung sepenuhnya untuk menjadi tidak ambigu. Jumlah cara untuk mengurung ekspresi diberikan oleh angka Catalan C_n=(2n)!/(n+1)!/n!
.
Kadang-kadang tanda kurung yang berbeda memberikan hasil numerik yang sama, misalnya (2^2)^(2^2)=((2^2)^2)^2
, sehingga jumlah kemungkinan hasil numerik yang berbeda untuk yang diberikan n
lebih sedikit daripada C_n
untuk semua n>1
. Urutan dimulai 1, 1, 2, 4, 8, ...
sebagai kebalikan dari angka Catalan1, 2, 5, 14, 42, ...
Masalahnya adalah untuk menulis program (atau fungsi) tercepat yang menerima n
sebagai input dan mengembalikan jumlah hasil numerik yang berbeda dari ekspresi 2^2^...^2
dengan n
operator ^
. Kinerja tidak boleh memburuk secara signifikan seiring n
pertumbuhan, jadi perhitungan langsung menara daya tinggi mungkin merupakan ide yang buruk.
sumber
2^n
, dan karena itu tidak perlu untuk melacak apa pun kecualin
. Yaitu, hanya menggunakan aturan eksponensial tampaknya bijaksana. Namun, pasti ada cara yang lebih cerdas dan sepenuhnya aljabar untuk melakukan ini.n
ini masih terlalu besar untuk menghitung. Masih, dicatat dengan baik. Mungkin representasi rekursif dalam bentuk "1 atau 2 ^ (...) atau (...) + (...)"; tetapi Anda masih memiliki masalah tentang cara menormalkan representasi nomor tersebut (atau membandingkan dua representasi untuk kesetaraan nilai).n
dua pasangan danC_n=(2n)!/(n+1)!/n!
harus menjadi jumlah tanda kurung, maka untuk n = 3 itu harus 5, benar? Saya melihat(2^2)^2
dan2^(2^2)
, tetapi apakah tiga kombinasi lainnya? Saya pikir C_n memberi Anda jumlah tanda kurung untuk n + 1 dua.Jawaban:
Python 2.7
Pendekatan ini mengambil keuntungan dari pertimbangan berikut:
Setiap bilangan bulat dapat direpresentasikan sebagai jumlah dari kekuatan dua. Eksponen dalam kekuatan dua juga dapat direpresentasikan sebagai kekuatan dua. Sebagai contoh:
Ekspresi ini yang kita hasilkan dapat direpresentasikan sebagai set set (dengan Python, saya menggunakan built-in
frozenset
):0
menjadi set kosong{}
.2^a
menjadi himpunan yang berisi himpunan yang mewakilia
. Misalnya:1 = 2^0 -> {{}}
dan2 = 2^(2^0) -> {{{}}}
.a+b
menjadi gabungan dari set yang mewakilia
danb
. Misalnya,3 = 2^(2^0) + 2^0 -> {{{}},{}}
Ternyata ekspresi formulir
2^2^...^2
dapat dengan mudah diubah menjadi representasi himpunan unik mereka, bahkan ketika nilai numeriknya terlalu besar untuk disimpan sebagai integer.Sebab
n=20
, ini berjalan dalam 8.7s pada CPython 2.7.5 di komputer saya (sedikit lebih lambat di Python 3 dan jauh lebih lambat di PyPy):(Konsep dekorator memoisasi disalin dari http://code.activestate.com/recipes/578231-probably-the-fastest-memoization-decorator-in-the-/ .)
Keluaran:
Pengaturan waktu untuk berbeda
n
:Setiap
n
21 di atas menghasilkan kesalahan memori pada mesin saya.Saya tertarik jika ada yang bisa membuat ini lebih cepat dengan menerjemahkannya ke bahasa yang berbeda.
Sunting: Mengoptimalkan
get_results
fungsi. Juga, menggunakan Python 2.7.5 bukannya 2.7.2 membuatnya berjalan sedikit lebih cepat.sumber
(a^b)^c = (a^c)^b
, dan itu masih jauh lebih lambat daripada implementasi Python ini.C #
Ini adalah terjemahan kode Python flornquake ke C # menggunakan rutin tambahan tingkat rendah yang memberikan peningkatan kecepatan melalui terjemahan langsung. Ini bukan versi paling optimal yang saya miliki, tapi itu agak lebih lama karena harus menyimpan struktur pohon dan juga nilainya.
sumber