Jumlah kekuatan untuk n

14

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]
  • adan burutan terbatas dengan panjang yang sama
  • semua elemen akurang darim
  • semua elemen bkurang darim
  • semua elemen ayang berbeda dan bilangan bulata[x] >= 0
  • semua elemen byang berbeda dan bilangan bulatb[x] >= 0
  • a[x]dan b[x]bukan keduanya 0 (karena 0 ^ 0 tidak pasti)

Ini adalah , 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
kukac67
sumber
Bagaimana kita membuat urutan bilangan bulat unik dan non-negatif yang memiliki jumlah yang tidak terbatas?
feersum
Juga, kasus pertama tidak masuk akal karena jumlah dengan 0 syarat sudah cukup.
feersum
@feersum Saya tidak begitu mengerti pertanyaan Anda. Solusi saya untuk ini adalah pencarian brute force dari semua kombinasi mana m<2kemudian m<3kemudian m<4dll sampai saya menemukan jumlah yang sama n. Juga, saya berpikir tentang memiliki jumlah 0tanpa syarat, tapi lalu apa hasilnya? m>?
kukac67
1
Untuk urutan yang terbatas, Anda biasanya akan melakukan sesuatu seperti n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k].
Volatilitas
1
Pertanyaan yang bagus Hanya satu berdalih pada kasus uji pertama: adan badalah urutan panjang yang terbatas 0, sehingga tidak ada bilangan bulat myang tidak memenuhi kendala, dan karena tidak ada bilangan bulat terkecil, jawabannya tidak didefinisikan. Kemungkinan perbaikan adalah meminta bilangan alami terkecil m(dalam hal ini Anda harus mengubah jawaban yang diharapkan di sana 0) atau untuk bilangan bulat positif terkecil m.
Peter Taylor

Jawaban:

2

GolfScript (59 karakter)

~:T),{),.0{2$0-{2${{4$2$^}2*@3$\?4$+f~}%\;~}%+\;\;}:f~T&}?)

Demo online

Ini menggunakan rekursi untuk menyebutkan nilai-nilai yang dapat dicapai untuk diberikan mdan mencari yang pertama mberhasil. Ini sedikit terinspirasi oleh jawaban xnor tetapi sangat berbeda dalam implementasinya.

Pembedahan

~:T                  # Evaluate input and store in T (for Target)
),{                  # Search [0 1 ... T] for the first m which matches a predicate
  ),.0               #   Push [0 ... m] to the stack twice and then 0
                     #   Stack holds: possibleAs possibleBs sum
  {                  #   Define the recursive function f
    2$0-{            #     Map over A in possibleAs (except 0)
      2${            #       Map over B in possibleBs (except 0)
        {4$2$^}2*    #         Duplicate respective possibles and remove selected values
        @3$\?4$+     #         Compute sum' = sum + A^B
        f            #         Recursive call gives an array [sums]
        ~            #         Push the sums to the stack individually
        }%           #       End map: this collects the sums into a combined array
      \;             #       Pop A, leaving just the combined [sums] inside the map
      ~              #       Repeat the trick: push to the stack individually
    }%               #     End map, collecting into a combined array
                     #     Stack now holds: possibleAs possibleBs sum [sums]
    +                #     Include the original sum in the array of reachable sums
    \;\;             #     Pop possibleAs and possibleBs
  }:f                #   End function definition
  ~                  #   Evaluate the function
  T&                 #   Test whether the sums contain T
}?                   # End search
)                    # Increment to get m
Peter Taylor
sumber
6

Python, 120

f=lambda n,A,B:n*all(f(n-a**b,A-{a},B-{b})for a in A for b in B)
g=lambda n,m=1,M={0}:f(n,M-{0},M)and g(n,m+1,M|{m})or m

Fungsi fmerupakan fungsi tambahan yang memeriksa apakah ndapat tidak dinyatakan sebagai jumlah dari kekuasaan dengan basis yang berbeda dari Adan eksponen dari B. Ini menggunakan strategi rekursif alami: nharus 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 mengurangi njumlah yang sesuai.

Fungsi gadalah fungsi utama. Ia mencari myang berfungsi. Madalah himpunan nilai yang diizinkan hingga m-1. Kami menghapus 0dari eksponen yang diizinkan untuk berhenti 0**0(yang Python evaluasi menjadi 1) agar tidak digunakan. Ini tidak sakit apa-apa Karena 0**xtidak berguna 0untuk semua yang lain x.

Tidak
sumber
Anda mungkin bisa berubah n and all()menjadi n*all().
grc
@ grc Ah, Anda sebenarnya tidak perlu korsleting karena itu keluar. Terima kasih untuk perbaikannya.
xnor
4

Python 2, 138 byte

from itertools import*
S=lambda n,m=0,R=[]:m*any(n==sum(map(pow,*C))for k in R for C in product(*tee(permutations(R,k))))or S(n,m+1,R+[m])

(Terima kasih kepada @Jakube untuk semua tipsnya)

Saya belum pernah belajar banyak tentang itertoolsmodul seperti yang saya miliki dari satu pertanyaan ini. Kasing terakhir memakan waktu sekitar satu menit.

Kami mulai dengan mencari dari m = 1dan bertambah sampai kami mendapatkan solusi. Untuk memeriksa solusi, kami beralih ke:

  • k = 0 to m-1, di mana kjumlah istilah dalam solusi
  • Semua kemungkinan kombinasi istilah (dengan menyatukan dua permutasi dari himpunan bagian dari [0, 1, ... m-1]ukurank ), lalu menjumlahkan dan memeriksa apakah kita memilikin

Perhatikan bahwa kami mengulangi khingga m-1- meskipun mistilah teknis mungkin secara total, selalu ada solusi dengan m-1istilah sebagai0^0 yang tidak diizinkan dan 0^btidak berkontribusi apa pun. Ini sebenarnya penting karena 0^0diperlakukan sebagai 1 oleh Python, yang tampaknya seperti masalah, tetapi ternyata tidak masalah!

Inilah sebabnya.

Misalkan solusi yang ditemukan salah digunakan 0^0sebagai 1, misalnya 3^2 + 1^1 + 0^0 = 11. Karena kita hanya menghasilkan hingga m-1istilah, pasti ada beberapa jyang tidak kita gunakan sebagai basis (di sini j = 2). Kami dapat menukar basis 0 untukj mendapatkan solusi yang valid, di sini 3^2 + 1^1 + 2^0 = 11.

Jika kita mengulangi semua mpersyaratan, maka kita mungkin mendapatkan solusi yang salah seperti m = 2untuk n = 2, via 0^0 + 1^1 = 2.

Sp3000
sumber
Bagus Anda dapat menyimpan 4 byte dengan menggunakan imap. imap(pow,C,D) ... for C,D in
Jakube
@ Jakube Saya benar-benar mencari melalui doc untuk itertoolssaat kita bicara: PI sudah memiliki tabungan lain - tee.
Sp3000
Saya juga. Juga, kesalahanku. Mengapa seseorang menyarankan imap, ketika ada map?? -1 byte
Jakube
Parameter default untuk teesudah n=2. Menghemat 2 byte.
Jakube
@ Jakube Ahaha terima kasih. Ini mungkin pertama kalinya saya menggunakan maplebih dari satu iterable, dan sebenarnya pertanyaan ini menghasilkan banyak hal pertama bagi saya.
Sp3000
4

GolfScript ( 90 84 byte)

[0.,.]](~:T),(+{:x;{:|2,{:c)|=x),^{c[1$x]=:A^x^:-;[|~-+@A-?+@A+@]}%}/+~}%.[]*T&}?)\;

Demo online

Pembedahan

[0.,.]             # Base case: [sum As Bs] is [0 [] []]
](~:T              # Collect it in an array of cases; fetch parameter, eval, store in T.
),(+               # Create array [1 2 ... T 0]. Putting 0 at the end means that it won't
                   # be reached except when T is 0, and nicely handles that special case.
{                  # Loop over the values from that array...
  :x;              #   ...assigning each in turn to x (and popping it from the stack)
  {                #   Stack holds array of [sum As Bs] cases; map them...

    :|             #     Store [sum As Bs] in |
    2,{:c          #     For c in [0 1]...
      )|=x),^      #       Get [0 1 ... x]^ either As or Bs, depending on c
      {            #       Map these legal new As or Bs respectively...
        c[1$x]=:A  #         Work out which of that value or x is the new A
        ^x^:-;     #         And the other one is the new B
        [          #         Begin gathering in an array
          |~       #           Push sum As Bs to the stack
          -+       #           Add - to Bs to get Bs'
          @A-?+    #           Rotate sum to top and add A^- to get sum'
          @A+      #           Rotate As to top and add A to get As'
          @        #           Final rotation to put elements in the right order
        ]          #         Gather in array [sum' As' Bs']
      }%           #       End map
    }/             #     End for
    +~             #     Push all the elements corresponding to x^B and A^x on to the stack
  }%               #   End map, collecting the untouched [sum As Bs] and all the new
                   #   [sum' As' Bs'] arrays into a new array of reached cases.
  .[]*T&           #   Flatten a copy of that array and filter to values equal to T.
                   #   This gives a truthy value iff we've found a way to make T.
}?                 # Loop until we get a truthy value, and push the corresponding x
)\;                # Increment to get the value of m and discard the array of cases

Trik paling elegan adalah penanganan case khusus untuk 0.

Peter Taylor
sumber
Saya sangat senang bahwa CJam kali ini tidak jauh lebih pendek dari standar python = P
flawr
@ flawr, ini GolfScript, bukan CJam. CJam mungkin bisa sedikit lebih pendek karena memiliki built-in untuk produk Cartesian. Dan mungkin gagasan xnor tentang fungsi rekursif juga memberikan GolfScript lebih pendek.
Peter Taylor
Oh maaf, membingungkan mereka =)
flawr
4

Haskell, 143 130

import Data.List
p n=head$[1..]>>=(\m->[m|let x=permutations[0..m-1]>>=inits,a<-x,b<-x,sum(zipWith(\x y->x^y*signum(x+y))a b)==n])

Contoh 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.

nimi
sumber
Anda harus menggunakan >>=daripada concatMap. mereka sama tetapi dengan argumen terbalik.
haskeller bangga
@proudhaskeller: Ya, terima kasih!
nimi
2

Python: 166 karakter

from itertools import*;p=permutations
f=lambda n,r=[0]:any(n==sum(map(lambda x,y:(x+y>0)*x**y,a,b))for j in r for a,b in product(p(r,j),p(r,j)))*1or 1+f(n,r+[len(r)])

Penjelasan

Fungsi fmenciptakan semua bilangan bulat yang mungkin, yang dapat dinyatakan sebagai jumlah dari kekuatan angka di r. Jika dimulai dengan r = [0]. Jika salah satu dari bilangan bulat itu sama dengan n, bilangan bulat mengembalikan panjangnya r, 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 dengan rpanjang j. Untuk masing-masing saya menghitung jumlah kekuatan.

Jakube
sumber
2

JavaScript (ES6) 219 224

Fungsi 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

C(3, [1,2,3]) --> [[3,2,1], [3,1,2], [2,3,1], [2,1,3], [1,3,2], [1,2,3]]

Level ketiga everydigunakan untuk zip bersama array a basis dan b dari eksponen (tidak ada zipfungsi dalam JavaScript). Menggunakan everyuntuk berhenti lebih awal ketika ada solusi yang tidak menggunakan semua elemen dalam dua array.

F=(n,j=1,k=[],
  C=(l,a,o=[],P=(l,a,i=l)=>{
    for(l||o.push(a);i--;)
      e=[...a],P(l-1,e.concat(e.splice(i,1)))
  })=>P(l,a)||o
)=>n&&C(k.push(j++),k)[E='every'](a=>C(j,[0,...k])[E](b=>a[E](x=>t-=Math.pow(x,b.pop()),t=n)))
?F(n,j,k):j

Uji di konsol FireFox / FireBug

;[0,1,2,3,6,16,17,23,24,27,330].map(x=>[x,F(x)])

Keluaran

[[0, 1], [1, 2], [2, 3], [3, 3], [6, 4], [16, 5], [17, 4], [23, 6], [ 24, 5], [27, 4], [330, 7]]

edc65
sumber