Rantai penjumlahan adalah urutan bilangan bulat yang dimulai dengan 1, di mana setiap bilangan bulat selain 1 awal adalah jumlah dari dua bilangan bulat sebelumnya.

Misalnya, inilah rantai tambahan:

[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

Berikut ini jumlah yang menjadikannya rantai tambahan:

1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71

Dalam tantangan ini, Anda akan diberikan bilangan bulat positif n, dan Anda harus menampilkan salah satu rantai penambahan terpendek yang berakhir n.

Contoh - perhatikan bahwa ada banyak kemungkinan keluaran, yang harus Anda temukan hanyalah rantai tambahan yang sama pendeknya:

1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]

Aturan I / O standar, dll. Lubang Standar dilarang. Golf kode: Byte paling sedikit menang.

Haskell , 57 byte

c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-c,last x==n]!!0

Solusi brute force. Cobalah online!

Penjelasan

Daftar yang tak terbatas cberisi semua rantai tambahan, yang dipesan berdasarkan panjangnya. Ini didefinisikan secara induktif dalam hal dirinya sendiri, dengan mengambil daftar xdari cdan dua elemen dari x, dan menambahkan jumlah mereka ke x. Fungsi fmenemukan daftar pertama cyang diakhiri dengan nomor yang diinginkan.

c=            -- c is the list of lists
 [1]:         -- containing [1] and
 [x           -- each list x
  ++[a+b]     -- extended with a+b
 |x<-c,       -- where x is drawn from c,
  a<-x,       -- a is drawn from x and
  b<-x]       -- b is drawn from x.
f n=          -- f on input n is:
 [x           -- take list of those lists x
 |x<-c,       -- where x is drawn from c and
  last x==n]  -- x ends with n,
 !!0          -- return its first element.

Brachylog , 14 byte

∧≜;1{j⊇Ċ+}ᵃ⁽?∋

Cobalah online!

Kiriman brute-force yang membangun semua rantai tambahan yang mungkin menggunakan iterative deepening, berhenti ketika rantai berisi argumen yang tepat ditemukan. Tidak seperti kebanyakan pengiriman Brachylog, ini adalah pengiriman fungsi yang diinput melalui argumen kanannya (secara konvensional disebut Output) dan output melalui argumen kirinya (secara konvensional disebut Input); melakukan hal ini agak kontroversial, tetapi jawaban meta dengan suara tertinggi pada subjek mengatakan itu sah (dan melakukannya konsisten dengan standar I / O normal kami untuk fungsi). Jika kita menggunakan input dan output dengan cara yang lebih konvensional, ini akan menjadi 16 byte (∧≜;1{j⊇Ċ+}ᵃ⁽.∋?∧), karena sisi kanan program tidak akan dapat menggunakan kendala implisit (dengan demikian perlu dinonaktifkan, dan batasan eksplisit baru diberikan, dengan biaya 2 byte).

Penjelasan

∧≜;1{j⊇Ċ+}ᵃ⁽?∋
∧               Disable implicit constraint to read the left argument
 ≜;        ⁽    Evaluation order hint: minimize number of iterations
    {    }ᵃ     Repeatedly run the following:
   1      ᵃ       From {1 on the first iteration, results seen so far otherwise}
     j            Make {two} copies of each list element
      ⊇           Find a subset of the elements
       Ċ          which has size 2
        +         and which sums to {the new result for the next iteration}
             ∋    If the list of results seen so far contains {the right argument}
            ?     Output it via the left argument {then terminate}

Kehalusan yang menarik di sini adalah apa yang terjadi pada iterasi pertama, di mana input adalah nomor daripada daftar seperti pada iterasi lainnya; kita mulai dengan angka 1, buat dua salinan dari setiap digit (jadikan nomor 11), kemudian temukan 2 digit berikutnya (juga nomor 11). Kemudian kita ambil jumlah digitnya, yaitu 2, dan dengan demikian urutannya dimulai [1,2]seperti yang kita inginkan. Pada iterasi masa depan, kita mulai dengan daftar seperti [1,2], dua kali lipat untuk [1,2,1,2], kemudian mengambil subsequence dua elemen ( [1,1], [1,2], [2,1], atau [2,2]); jelas, jumlah masing-masing akan menjadi elemen berikutnya dari rantai penambahan.

Agak membuat frustasi di sini bahwa petunjuk urutan evaluasi diperlukan di sini, terutama ≜komponen (tampaknya yang ᵃmengambil petunjuk urutan evaluasi dari dalam bukan dari luar secara default, sehingga penggunaan yang agak kasar ≜untuk memaksa masalah).

Jelly , 17 byte

’ŒP;€µ+þ;1Fḟ@µÐḟḢ

Menghasilkan solusi leksikografis pertama dalam waktu eksponensial.

Cobalah online!

Bagaimana itu bekerja

’ŒP;€µ+þ;1Fḟ@µÐḟḢ  Main link. Argument: n (integer)

’                  Decrement; n-1.
 ŒP                Powerset; generate all subarrays of [1, ..., n-1], sorted first
                   by length, then lexicographically.
   ;€              Append n to all generate subarrays.
     µ       µÐḟ   Filterfalse; keep only subarrays for which the chain between the
                   two chain separators (µ) returns a falsy value.
     µ             Monadic chain. Argument: A (array of integers)
      +þ               Add table; compute the sums of all pairs of elements in x,
                       grouping the results by the right addend.
        ;1             Append 1 to the resulting 2D array.
          F            Flatten the result.
           ḟ@          Filterfalse swapped; remove all elements of A that appear in
                       the result. This yields an empty list for addition chains.
                Ḣ  Head; select the first result.

JavaScript (ES6), 83 86 byte

Sunting: diperbaiki untuk menampilkan daftar dalam urutan yang tidak terbalik

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

Demo

let f =

n=>(g=(s,a=[1])=>s-n?s>n||a.map(v=>g(v+=s,a.concat(v))):r=1/r|r[a.length]?a:r)(r=1)&&r

for(n = 1; n <= 15; n++) {
  console.log(n, '-->', JSON.stringify(f(n)));
}

PHP, 195 Bytes

function p($a){global$argn,$r;if(!$r||$a<$r)if(end($a)==$argn)$r=$a;else foreach($a as$x)foreach($a as$y)in_array($w=$x+$y,$a)||$w>$argn||$w<=max($a)?:p(array_merge($a,[$w]));}p([1]);print_r($r);

Cobalah online!

Mathematica, 140 byte

t={};s={1};(Do[While[Last@s!=#,s={1};While[Last@s<#,AppendTo[s,RandomChoice@s+Last@s]]];t~AppendTo~s;s={1},10^4];First@SortBy[t,Length@#&])&

.

menghasilkan rantai tambahan terpendek yang berbeda setiap kali Anda menjalankannya

Cobalah online
paste kode dengan ctrl + v, masukkan input yaitu [71] di akhir kode dan tekan shift + enter

Pyth, 13 byte

h-DsM^N2/#QyS

Suite uji

Memberikan rantai terpendek leksikografis pertama. Ini cukup lambat, tapi tidak terlalu buruk - 19selesai dalam waktu sekitar 30 detik menggunakan pypy.

Beberapa ide dari solusi @ Dennis.

Saya sangat suka yang ini - ada banyak trik rapi yang terlibat.

Penjelasan:

h-DsM^N2/#QyS
h-DsM^N2/#QySQ    Implicit variable introduction
            SQ    Inclusive range, 1 to input.
           y      Subsets - all subsets of the input, sorted by length then lexicographically
                  Only sorted subsets will be generated.
                  Our addition chain will be one of these.
        /#Q       Filter for presence of the input.
  D               Order by
 -                What's left after we remove
     ^N2          All pairs of numbers in the input
   sM             Summed
h                 Output the list that got sorted to the front.

Ini masih agak sulit untuk dipahami, tetapi izinkan saya mencoba menjelaskan dengan lebih detail.

Kita mulai dengan ySQ, yang memberikan semua himpunan bagian yang mungkin dipesan [1, 2, ... Q], dalam urutan ukuran yang meningkat. Rantai penambahan terpendek jelas merupakan salah satunya, tetapi kita perlu menemukannya.

Hal pertama yang akan kita lakukan adalah memfilter daftar hanya menyimpan daftar yang mengandung a Q. Kami melakukan ini dengan /#Q.

Selanjutnya, kami memesan daftar berdasarkan apa yang tersisa setelah kami menghapus hasil fungsi tertentu. -Dpesanan oleh sisanya setelah menghapus sesuatu.

Hal yang kami hapus adalah sM^N2, di mana Ndaftar barang yang kami hapus. ^N2memberikan produk kartesius Ndengan dirinya sendiri, semua pasangan yang memungkinkan dari dua elemen di N. sMlalu jumlahkan masing-masing pasangan.

Apa hasil sekecil mungkin, setelah kami melakukan penghapusan ini? Nah, elemen terkecil dalam daftar input pasti akan tetap ada, karena semua angka positif, jadi jumlah dari dua angka akan lebih besar dari angka terkecil. Dan akan ada setidaknya satu nomor, karena kami memeriksa bahwa input ada dalam daftar. Oleh karena itu, hasil terkecil yang mungkin terjadi adalah ketika setiap angka kecuali angka terkecil adalah jumlah dari dua angka lain dalam daftar, dan angka terkecil dalam daftar adalah 1. Dalam hal ini, kunci pengurutannya adalah [1]. Persyaratan ini berarti bahwa daftar tersebut harus merupakan rantai tambahan.

Jadi, kami mengurutkan rantai tambahan ke depan. Ingatlah bahwa ymemberikan himpunan bagiannya dalam urutan ukuran yang meningkat, sehingga daftar yang disortir ke depan harus menjadi salah satu rantai penambahan terpendek. hmemilih daftar itu.