Petunjuk arah
Tulis sebuah program yang, diberi bilangan bulat input n ( n >= 0
), menghasilkan bilangan bulat positif terkecil m di mana:
n = a[1]^b[1] + a[2]^b[2] + a[3]^b[3] + ... + a[k]^b[k]
a
danb
urutan terbatas dengan panjang yang sama- semua elemen
a
kurang darim
- semua elemen
b
kurang darim
- semua elemen
a
yang berbeda dan bilangan bulata[x] >= 0
- semua elemen
b
yang berbeda dan bilangan bulatb[x] >= 0
a[x]
danb[x]
bukan keduanya 0 (karena 0 ^ 0 tidak pasti)
Ini adalah kode-golf , byte paling sedikit menang.
Contohnya
In 0 -> Out 1
Possible Sum:
In 1 -> Out 2
Possible Sum: 1^0
In 2 -> Out 3
Possible Sum: 2^1
In 3 -> Out 3
Possible Sum: 2^1 + 1^0
In 6 -> Out 4
Possible Sum: 2^2 + 3^0 + 1^1
In 16 -> Out 5
Possible Sum: 2^4
In 17 -> Out 4
Possible Sum: 3^2 + 2^3
In 23 -> Out 6
Possible Sum: 5^1 + 3^0 + 2^4 + 1^3
In 24 -> Out 5
Possible Sum: 4^2 + 2^3
In 27 -> Out 4
Possible Sum: 3^3
In 330 -> Out 7
Possible Sum: 6^1 + 4^3 + 3^5 + 2^4 + 1^0
code-golf
number
arithmetic
kukac67
sumber
sumber
m<2
kemudianm<3
kemudianm<4
dll sampai saya menemukan jumlah yang saman
. Juga, saya berpikir tentang memiliki jumlah0
tanpa syarat, tapi lalu apa hasilnya? m>?n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k]
.a
danb
adalah urutan panjang yang terbatas0
, sehingga tidak ada bilangan bulatm
yang tidak memenuhi kendala, dan karena tidak ada bilangan bulat terkecil, jawabannya tidak didefinisikan. Kemungkinan perbaikan adalah meminta bilangan alami terkecilm
(dalam hal ini Anda harus mengubah jawaban yang diharapkan di sana0
) atau untuk bilangan bulat positif terkecilm
.Jawaban:
GolfScript (59 karakter)
Demo online
Ini menggunakan rekursi untuk menyebutkan nilai-nilai yang dapat dicapai untuk diberikan
m
dan mencari yang pertamam
berhasil. Ini sedikit terinspirasi oleh jawaban xnor tetapi sangat berbeda dalam implementasinya.Pembedahan
sumber
Python, 120
Fungsi
f
merupakan fungsi tambahan yang memeriksa apakahn
dapat tidak dinyatakan sebagai jumlah dari kekuasaan dengan basis yang berbeda dariA
dan eksponen dariB
. Ini menggunakan strategi rekursif alami:n
harus bukan nol, dan kami mencoba setiap pilihan dasar dan dan eksponen yang mungkin dan mereka semua harus gagal. Kami menghapusnya dari daftar yang diizinkan dan mengurangin
jumlah yang sesuai.Fungsi
g
adalah fungsi utama. Ia mencarim
yang berfungsi.M
adalah himpunan nilai yang diizinkan hinggam-1
. Kami menghapus0
dari eksponen yang diizinkan untuk berhenti0**0
(yang Python evaluasi menjadi 1) agar tidak digunakan. Ini tidak sakit apa-apa Karena0**x
tidak berguna0
untuk semua yang lainx
.sumber
n and all()
menjadin*all()
.Python 2, 138 byte
(Terima kasih kepada @Jakube untuk semua tipsnya)
Saya belum pernah belajar banyak tentang
itertools
modul seperti yang saya miliki dari satu pertanyaan ini. Kasing terakhir memakan waktu sekitar satu menit.Kami mulai dengan mencari dari
m = 1
dan bertambah sampai kami mendapatkan solusi. Untuk memeriksa solusi, kami beralih ke:k = 0 to m-1
, di manak
jumlah istilah dalam solusi[0, 1, ... m-1]
ukurank
), lalu menjumlahkan dan memeriksa apakah kita memilikin
Perhatikan bahwa kami mengulangi
k
hinggam-1
- meskipunm
istilah teknis mungkin secara total, selalu ada solusi denganm-1
istilah sebagai0^0
yang tidak diizinkan dan0^b
tidak berkontribusi apa pun. Ini sebenarnya penting karena0^0
diperlakukan sebagai 1 oleh Python, yang tampaknya seperti masalah, tetapi ternyata tidak masalah!Inilah sebabnya.
Misalkan solusi yang ditemukan salah digunakan
0^0
sebagai 1, misalnya3^2 + 1^1 + 0^0 = 11
. Karena kita hanya menghasilkan hinggam-1
istilah, pasti ada beberapaj
yang tidak kita gunakan sebagai basis (di sinij = 2
). Kami dapat menukar basis 0 untukj
mendapatkan solusi yang valid, di sini3^2 + 1^1 + 2^0 = 11
.Jika kita mengulangi semua
m
persyaratan, maka kita mungkin mendapatkan solusi yang salah sepertim = 2
untukn = 2
, via0^0 + 1^1 = 2
.sumber
imap(pow,C,D) ... for C,D in
itertools
saat kita bicara: PI sudah memiliki tabungan lain -tee
.imap
, ketika adamap
?? -1 bytetee
sudahn=2
. Menghemat 2 byte.map
lebih dari satu iterable, dan sebenarnya pertanyaan ini menghasilkan banyak hal pertama bagi saya.GolfScript (
9084 byte)Demo online
Pembedahan
Trik paling elegan adalah penanganan case khusus untuk
0
.sumber
Haskell,
143130Contoh penggunaan:
p 23
->6
.Ini adalah pencarian brute force sederhana. Untuk setiap daftar
[0..0], [0..1], [0..2] ... [0..∞]
mengambil semua segmen awal dari permutasi (misalnya [0..2]: permutasi:[012], [102], [210], [120], [201], [021]
, segmen awal untuk permutasi 1:[0], [01], [012]
, 2:[1], [10], [102]
, dll). Untuk setiap kombinasi 2 daftar tersebut hitung jumlah daya. Berhenti ketika yang pertama sama dengan n.sumber
>>=
daripadaconcatMap
. mereka sama tetapi dengan argumen terbalik.Python: 166 karakter
Penjelasan
Fungsi
f
menciptakan semua bilangan bulat yang mungkin, yang dapat dinyatakan sebagai jumlah dari kekuatan angka dir
. Jika dimulai denganr = [0]
. Jika salah satu dari bilangan bulat itu sama dengann
, bilangan bulat mengembalikan panjangnyar
, jika tidak bilangan itu menyebut dirinya secara rekursif dengan bentang yang diperluasr
.Perhitungan semua bilangan bulat, yang dapat dinyatakan sebagai jumlah dilakukan dengan dua loop. Loop pertama adalah
for j in r
, yang memberi tahu kita panjang ekspresi (2 ^ 3 + 1 ^ 2 memiliki panjang 2). Loop dalam berulang atas semua kombinasi permutasi denganr
panjangj
. Untuk masing-masing saya menghitung jumlah kekuatan.sumber
JavaScript (ES6) 219
224Fungsi rekursif. Dimulai dengan m = 1, saya mencoba semua kombinasi integer 1..m untuk basis dan 0..m untuk eksponen (0 basis tidak berguna mengingat 0 ^ 0 == tidak terdefinisi).
Jika tidak ada solusi yang ditemukan, tambah m dan coba lagi.
Kasus khusus untuk input 0 (menurut saya itu adalah kesalahan dalam spesifikasi)
Fungsi C secara rekursif menghasilkan semua kombinasi dari array dengan panjang tertentu, sehingga
Level ketiga
every
digunakan untuk zip bersama array a basis dan b dari eksponen (tidak adazip
fungsi dalam JavaScript). Menggunakanevery
untuk berhenti lebih awal ketika ada solusi yang tidak menggunakan semua elemen dalam dua array.Uji di konsol FireFox / FireBug
Keluaran
sumber