Satu sen yang disimpan adalah satu sen

21

...terhitung!

Anda akan lulus program Anda variabel yang mewakili jumlah uang dalam dolar dan / atau sen dan berbagai nilai koin. Tantangan Anda adalah menampilkan jumlah kombinasi yang mungkin dari array nilai koin yang diberikan yang akan menambah jumlah yang diteruskan ke kode. Jika tidak mungkin dengan koin yang dinamai, program harus kembali 0.

Catatan tentang terminologi numismatik Amerika:

  • Koin 1 sen: sen
  • Koin 5 sen: nikel
  • Koin 10 sen: uang receh
  • Koin 25 sen: seperempat (seperempat dolar)

Contoh 1:

Program disahkan:

12, [1, 5, 10]

(12 sen)

Keluaran:

4

Ada 4 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 12 sen:

  1. 12 sen
  2. 1 nikel dan 7 sen
  3. 2 sen dan 2 sen
  4. 1 sen dan 2 sen

Contoh 2:

Program disahkan:

26, [1, 5, 10, 25]

(26 sen)

Keluaran:

13

Ada 13 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 26 sen:

  1. 26 sen
  2. 21 sen dan 1 nikel
  3. 16 sen dan 2 sen
  4. 11 sen dan 3 sen
  5. 6 sen dan 4 sen
  6. 1 sen dan 5 sen
  7. 16 sen dan 1 sen
  8. 6 sen dan 2 sen
  9. 11 sen, 1 sen, dan 1 nikel
  10. 6 sen, 1 sen, dan 2 sen
  11. 1 sen, 1 sen, dan 3 sen
  12. 1 sen, 2 sen, dan 1 nikel
  13. 1 seperempat dan 1 sen

Contoh 3:

Program disahkan:

19, [2, 7, 12]

Keluaran:

2

Ada 2 cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 19 sen:

  1. 1 koin 12 sen dan 1 koin 7 sen
  2. 1 koin 7 sen dan 6 koin 2 sen

Contoh 4:

Program disahkan:

13, [2, 8, 25]

Keluaran:

0

Tidak ada cara yang memungkinkan untuk menggabungkan koin yang dinamai untuk menghasilkan 13 sen.


Ini telah melalui Sandbox. Celah standar berlaku. Ini adalah kode golf, jadi jawabannya dengan byte paling sedikit menang.

anonim2
sumber
1
s / dihitung / diperoleh
mbomb007
4
@ mbomb007 Selama empat byte: s/count/earn.
wizzwizz4
5
Bagi saya dan saya kira untuk orang lain yang tidak membayar dengan dolar, tidak jelas apa itu nikel dan sepeser pun. Tidak sulit untuk mengetahuinya, tetapi mungkin Anda bisa menulisnya sedikit lebih internasional?
Kritzefitz
2
@ Kempritzefitz. Saya telah menambahkan itu ke pertanyaan.
TRiG
2
@ jpaugh: Walaupun coin-o-philes mungkin setuju, saya harus tidak setuju. Satu sen adalah koin standar yang memiliki nilai satu sen. Lima puluh empat sen adalah jumlah uang. Lima puluh empat sen secara eksplisit adalah 54 koin. Ini juga disebut "koin satu sen", atau (secara resmi) "koin satu sen". Saya tidak dapat memikirkan pengaturan formal di mana kata "sen" akan tidak dapat diterima. Orang-orang ini , yang secara khusus tentang mengumpulkan koin, tidak memiliki masalah menyebutnya sebagai "sen".
MichaelS

Jawaban:

12

Jelly ( garpu ), 2 byte

æf

Ini bergantung pada cabang Jelly di mana saya sedang mengerjakan implementasi atom pemecahan Frobenius jadi sayangnya Anda tidak dapat mencobanya secara online.

Pemakaian

$ ./jelly eun 'æf' '12' '[1,5,10]'
4
$ ./jelly eun 'æf' '26' '[1,5,10,25]'
13
$ ./jelly eun 'æf' '19' '[2,7,12]'
2
$ ./jelly eun 'æf' '13' '[2,8,25]'
0

Penjelasan

æf  Input: total T, denominations D
æf  Frobenius count, determines the number of solutions
    of nonnegative X such that X dot-product D = T
mil
sumber
10
... itu bahkan tidak adil.
ETHproduksi
... dan saya yakin itu jauh lebih cepat!
Jonathan Allan
18

Haskell, 37 34 byte

s#l@(c:d)|s>=c=(s-c)#l+s#d
s#_=0^s

Contoh penggunaan: 26 # [1,5,10,25]-> 13.

Pendekatan rekursif sederhana: coba kedua nomor berikutnya dalam daftar (asalkan jumlahnya kurang atau sama dengan jumlahnya) dan lewati saja. Jika mengurangi angka mengarah ke jumlah nol, ambil yang 1lain (atau jika daftar elemen habis) ambil a 0. Jumlahkan 1dan 0s.

Sunting: @Damien: disimpan 3 byte dengan menunjuk ke casing dasar yang lebih pendek untuk rekursi (yang juga dapat ditemukan dalam jawaban @xnors ).

nimi
sumber
s # l @ (c: d) | s> = c = (sc) # l + s # d; s # _ = 0 ^ s
Damien
dan apa yang akan menjadi hasil dari 1209 [1,5,10,33,48] dan 6000 [1,5,10,33] sehingga saya dapat mengkalibrasi kode saya
RosLuP
@RosLuP: 1209 # [1,5,10,33,48]-> 1314050.
nimi
@nimi ok untuk 1314050 Saya memiliki hasil yang sama di sini ... Terima kasih ...
RosLuP
@RosLuP: ... 537menit kemudian: 6000 # [1,5,10,33]-> 22086484.
nimi
15

Mathematica, 35 22 byte

Terima kasih kepada miles untuk menyarankan FrobeniusSolvedan menghemat 13 byte.

Length@*FrobeniusSolve

Mengevaluasi fungsi yang tidak disebutkan namanya, yang menjadikan daftar koin sebagai argumen pertama dan nilai target sebagai yang kedua. FrobeniusSolveadalah singkatan untuk menyelesaikan persamaan Diophantine dari formulir

a1x1 + a2x2 + ... + anxn = b

untuk bilangan bulat non-negatif dan memberi kami semua solusi.xi

Martin Ender
sumber
@RosLuP Anda akan memerlukan akses ke Mathematica untuk menjalankan ini. Juga ini adalah fungsi anonim sehingga untuk menyebutnya, baik merangkumnya dalam tanda kurung atau menyimpannya ke variabel. Misalnya,(Length@*FrobeniusSolve)[{1, 7, 9}, 18]
mil
dan apa yang akan menjadi hasil dari 1209 [1,5,10,33,48] dan 6000 [1,5,10,33] sehingga saya dapat mengkalibrasi kode saya
RosLuP
@RosLuP 1314050 dan 22086484, masing-masing.
Martin Ender
Ok di sini hasilnya sama, terima kasih ...
RosLuP
16 suara untuk ini dibenarkan hanya jika programmer yang menulis Panjang @ * FrobeniusSolve apakah Anda ...
RosLuP
12

Pyth, 8 byte

/sM{yS*E

Mentah kasar, terlalu intensif memori untuk pengujian yang sebenarnya. Ini adalah O (2 mn ), di mana n adalah jumlah koin dan m adalah jumlah target. Mengambil input sebagai target\n[c,o,i,n,s].

/sM{yS*EQQ      (implicit Q's)
      *EQ       multiply coin list by target
     S          sort
    y           powerset (all subsequences)
   {            remove duplicates
 sM             sum all results
/        Q      count correct sums
PurkkaKoodari
sumber
9

Haskell, 37 byte

s%(h:t)=sum$map(%t)[s,s-h..0]
s%_=0^s

Menggunakan beberapa kelipatan dari koin pertama hmengurangi jumlah yang diperlukan ske nilai non-negatif dalam perkembangan yang menurun [s,s-h..0], yang kemudian harus dilakukan dengan koin yang tersisa. Setelah tidak ada koin yang tersisa, periksa apakah jumlahnya adalah nol secara hitung 0^s.

Tidak
sumber
Sungguh menakjubkan bagaimana Anda menekan jumlah byte yang sama persis dengan @nimi menggunakan pendekatan yang berbeda.
Kritzefitz
9

JavaScript (ES6), 51 48 byte

f=(n,a,[c,...b]=a)=>n?n>0&&c?f(n-c,a)+f(n,b):0:1

Terima koin dalam urutan apa pun. Mencoba menggunakan dan tidak menggunakan koin pertama, secara rekursif menghitung jumlah kombinasi dengan cara apa pun. n==0berarti kombinasi yang cocok, n<0berarti bahwa koin melebihi jumlah sementara c==undefinedberarti tidak ada koin yang tersisa. Perhatikan bahwa fungsi ini sangat lambat dan jika Anda memiliki koin sen maka fungsi berikut ini lebih cepat (jangan melewati koin sen dalam array koin):

f=(n,a,[c,...b]=a)=>c?(c<=n&&f(n-c,a))+f(n,b):1
Neil
sumber
... dangit. Ide yang sangat bagus.
ETHproduk
dan apa yang akan menjadi hasil dari 1209 [1,5,10,33,48] dan 6000 [1,5,10,33] sehingga saya dapat mengkalibrasi kode saya
RosLuP
@RosLuP Kode yang diberikan akhirnya mengembalikan 1314050 untuk contoh pertama Anda. Penerjemah saya tidak dapat menangani rekursi yang diperlukan untuk mengevaluasi contoh kedua.
Neil
@RosLuP Saya memodifikasi fungsi untuk mengasumsikan koin sen tambahan ada dan mengembalikan 22086484 untuk 6000 [5,10,33].
Neil
@Neil ok 22086484 untuk 6000 [1,5,10,33] ... Alih-alih akan menjadi 11239 di sini untuk 6000 [5,10,33] (array yang Anda tulis)
RosLuP
7

Perl, 45 byte

Hitungan byte mencakup 44 byte kode dan -pbendera.

s%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{

Mengambil nilai koin pada baris pertama, dan jumlah yang ditargetkan pada baris kedua:

$ perl -pE 's%\S+%(1{$&})*%g,(1x<>)=~/^$_$(?{$\++})^/x}{' <<< "1 5 10 25
26"
13

Penjelasan singkat:

-p                        # Set $_ to the value of the input, 
                          # and adds a print at the end of the code.
s%\S+%(1{$&})*%g,         # Converts each number n to (1{$&})* (to prepare the regex)
                          # This pattern does half the job.
(1x<>)                    # Converts the target to unary representation.
  =~                      # Match against.. (regex)
    /^ $_ $               # $_ contains the pattern we prepared with the first line.
     (?{$\++})            # Count the number of successful matches
     ^                    # Forces a fail in the regex since the begining can't be matched here.
    /x                    # Ignore white-spaces in the regex 
                          # (needed since the available coins are space-separated)
 }{                       # End the code block to avoid the input being printed (because of -p flag) 
                          # The print will still be executed, but $_ will be empty, 
                          # and only $\ will be printed (this variable is added after every print)
Dada
sumber
6

Jelly , 10 9 byte

œċЀS€€Fċ

Cobalah online!

Bagaimana?

œċЀS€€Fċ - Main link: coins, target
  Ѐ      - map over right argument, or for each n in [1,2,...,target]
œċ        - combinations with replacement, possible choices of each of n coins
    S€€   - sum for each for each (values of those selections)
       F  - flatten into one list
        ċ - count occurrences of right argument
Jonathan Allan
sumber
2
+1 untuk menggunakan simbol Euro sebanyak itu dalam pertanyaan terkait uang.
steenbergh
6

JavaScript (ES6), 59 byte

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),0):1

Koin adalah input dari tertinggi ke terendah, mis f(26,[100,25,10,5,1]). Jika Anda memiliki satu sen, hapus dan gunakan versi yang jauh lebih cepat ini sebagai gantinya:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

Ini menggunakan rumus rekursif seperti @ nimi. Saya awalnya menulis ini beberapa hari yang lalu ketika tantangan masih di kotak pasir; terlihat seperti ini:

f=(n,c=[100,25,10,5])=>n?c.reduce((x,y,i)=>y>n?x:x+f(n-y,c.slice(i)),1):1

Satu-satunya perbedaan menjadi nilai default c(itu memiliki nilai yang ditetapkan dalam tantangan asli), dan mengubah 0dalam .reducefungsi 1(ini adalah dua byte lebih pendek dan bazillion kali lebih cepat dari c=[100,25,10,5,1]).


Berikut adalah versi yang dimodifikasi yang menampilkan semua kombinasi, bukan jumlah kombinasi:

f=(n,c)=>n?c.reduce((x,y,i)=>y>n?x:[...x,...f(n-y,c.slice(i)).map(c=>[...c,y])],[]):[[]]
Produksi ETH
sumber
dan apa yang akan menjadi hasil 1209 [1,5,10,33,48] dan 6000 [1,5,10,33] sehingga saya dapat mengkalibrasi kode saya
RosLuP
@ RosLuP Saya mendapatkan 1314050 (setelah 5 menit) dan stack overflow (setelah satu jam), masing-masing. Dengan versi yang lebih cepat saya baru saja menambahkan, saya mendapatkan 1314050 dan 22086484 dalam beberapa detik.
ETHproduksi
Dengan komputer 2.8Gh Pentium lama saya 6 detik untuk hasil pertama, untuk 5 menit kedua + atau -
RosLuP
5

PHP, 327 Bytes

function c($f,$z=0){global$p,$d;if($z){foreach($p as$m){for($j=0;$j<=$f/$d[$z];){$n=$m;$n[$d[$z]]=$j++;$p[]=$n;}}}else for($p=[],$j=0;$j<=$f/$d[$z];$j++)$p[]=[$d[$z]=>$j];if($d[++$z])c($f,$z);}$d=$_GET[a];c($e=$_GET[b]);foreach($p as$u){$s=0;foreach($u as$k=>$v)$s+=$v*$k;if($s==$e&count($u)==count($d))$t[]=$u;}echo count($t);

Cobalah

Jörg Hülsermann
sumber
5

Aksioma, 63 62 byte

1 byte disimpan oleh @JonathanAllan

f(n,l)==coefficient(series(reduce(*,[1/(1-x^i)for i in l])),n)

Pendekatan ini menggunakan fungsi pembangkit. Mungkin itu tidak membantu menurunkan ukuran kode. Saya pikir ini adalah pertama kalinya dalam bermain saya dengan Aksioma saya pergi sejauh mendefinisikan fungsi saya sendiri.

Pertama kali fungsi ini disebut memberikan peringatan yang menghebohkan, tetapi tetap menghasilkan hasil yang benar. Setelah itu, semuanya baik-baik saja asalkan daftarnya tidak kosong.

Sievers Kristen
sumber
1
Saya tidak tahu Aksioma - apakah mungkin untuk menghapus ruang sebelumnya for?
Jonathan Allan
1
@ Jonathan Allan Ya, benar! Naluri bermain golf yang bagus, terima kasih!
Christian Sievers
5

R, 81 76 63 byte

Terima kasih kepada @rturnbull untuk bermain golf 13 byte!

function(u,v)sum(t(t(expand.grid(lapply(u/v,seq,f=0))))%*%v==u)

Contoh (perhatikan bahwa c(...)Anda memberi vektor nilai ke R):

f(12,c(1,5,10))
[1] 4

Penjelasan:

uadalah nilai yang diinginkan, vadalah vektor nilai koin.

expand.grid(lapply(u/v,seq,from=0))

menciptakan bingkai data dengan setiap kemungkinan kombinasi 0 hingga k koin (k tergantung pada denominasi), di mana k adalah yang terendah sehingga k kali nilai koin itu setidaknya u (nilai untuk mencapai).

Biasanya kami akan menggunakan as.matrix untuk mengubah itu menjadi matriks, tetapi itu banyak karakter. Alih-alih, kami mengambil transpose dari transpose (!) Yang secara otomatis memaksanya, tetapi mengambil lebih sedikit karakter.

%*% vkemudian menghitung nilai moneter dari setiap baris. Langkah terakhir adalah menghitung berapa dari nilai-nilai itu sama dengan nilai yang diinginkanu .

Perhatikan bahwa kompleksitas komputasi dan persyaratan memori ini mengerikan, tetapi hei, ini kode golf.

JDL
sumber
1
Penggunaan yang bagus expand.grid! Dan saya suka t(t())triknya. Karena fungsi Anda hanya melibatkan satu baris kode, Anda dapat menghapus kurung kurawal, menghemat 2 byte. Anda juga dapat beralih do.call(expand.grid,lapply(u/v,seq,from=0))hanya expand.grid(lapply(u/v,seq,f=0)), menghemat 11 byte.
rturnbull
Terima kasih untuk itu! Saya tidak pernah menyadari expand.gridakan mengambil daftar sebagai masukan. Ini sedikit memalukan yang ":"tidak bekerja dengan baik dengan non-integer kalau tidak lapply(u/v,":",0)akan menyelamatkan pasangan lagi.
JDL
do.call(x,y)sama dengan x(y), jadi ini bukan tentang jenis input apa yang diterima. Jika Anda benar-benar ingin menggunakan :, saya kira Anda bisa menggunakan lapply(u%/%v,`:`,0), tetapi itu adalah jumlah byte yang sama.
rturnbull
1
" do.call(x,y)sama dengan x(y)" --- hanya jika ybukan daftar, yang ada dalam kasus ini. Setuju dengan poin kedua Anda.
JDL
3

J, 27 byte

1#.[=](+/ .*~]#:,@i.)1+<.@%

Pemakaian

   f =: 1#.[=](+/ .*~]#:,@i.)1+<.@%
   12 f 1 5 10
4
   26 f 1 5 10 25
13
   19 f 2 7 12
2
   13 f 2 8 25
0

Penjelasan

1#.[=](+/ .*~]#:,@i.)1+<.@%  Input: target T (LHS), denominations D (RHS)
                          %  Divide T by each in D
                       <.@   Floor each
                             These are the maximum number of each denomination
                     1+      Add 1 to each, call these B
                ,@i.         Forms the range 0 the the product of B
             ]               Get B
              #:             Convert each in the range to mixed radix B
     ]                       Get D
       +/ .*~                Dot product between D and each mixed radix number
                             These are all combinations of denominations up to T
   [                         Get T
    =                        Test if each sum is equal to T
1#.                          Convert as base 1 digits to decimal (takes the sum)
                             This is the number of times each sum was true
mil
sumber
J sangat mengagumkan, namun juga, sangat gila
CommaToast
2

TSQL, 105 byte

Ini hanya dapat menangani hingga satu dolar dengan 4 jenis koin ini. Versi ungolfed dapat menangani hingga sekitar 4 dolar, tetapi sangat lambat - pada kotak saya ini membutuhkan waktu 27 detik. Hasilnya adalah 10045 kombinasi btw

Golf:

DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)
;WITH c as(SELECT 0l,0s UNION ALL SELECT z,s+z FROM c,@t WHERE l<=z and s<@)SELECT SUM(1)FROM c WHERE s=@

Tidak Disatukan:

-- input variables
DECLARE @ INT = 100
DECLARE @t table(z int)
INSERT @t values(1),(5),(10),(25)

-- query
;WITH c as
(
  SELECT 0l,0s
  UNION ALL
  SELECT z,s+z
  FROM c,@t
  WHERE l<=z and s<@
)
SELECT SUM(1)
FROM c
WHERE s=@
-- to allow more than 100 recursions(amounts higher than 1 dollar in this example)
OPTION(MAXRECURSION 0)

Biola

t-clausen.dk
sumber
2

penggantian tinylisp , 66 byte

(d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1

Solusi rekursif: mencoba menggunakan koin pertama dan tidak menggunakan koin pertama, lalu menambahkan hasilnya dari masing-masing. Kompleksitas waktu eksponensial dan tidak ada rekursi ekor, tetapi menghitung kasus uji dengan baik.

Tidak digabungkan (kunci untuk builtin: d= define, q= quote, i= if, l= less-than, s= kurangi, h= head, t= tail):

(d combos
 (q
  ((amount coin-values)
   (i amount
    (i (l amount 0)
     0
     (i coin-values
      (s
       (combos
        (s amount (h coin-values))
        coin-values)
       (s
        0
        (combos
         amount
         (t coin-values))))
      0))
    1))))

Contoh penggunaan:

tl> (d C(q((Q V)(i Q(i(l Q 0)0(i V(s(C(s Q(h V))V)(s 0(C Q(t V))))0))1
C
tl> (C 12 (q (1 5 10)))
4
tl> (C 26 (q (1 5 10 25)))
13
tl> (C 19 (q (2 7 12)))
2
tl> (C 13 (q (2 8 25)))
0
tl> (C 400 (q (1 5 10 25)))
Error: recursion depth exceeded. How could you forget to use tail calls?!
DLosc
sumber
1

PHP, 130 byte

function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));

Fungsi rekursif 99 byte (dan 31 byte menyebutnya) yang berulang kali menghilangkan nilai koin saat ini dari target dan menyebut dirinya dengan nilai baru dan koin lainnya. Menghitung berapa kali target tepat mencapai 0. Jalankan seperti:

 php -r "function r($n,$a){if($c=$a[0])for(;0<$n;$n-=$c)$o+=r($n,array_slice($a,1));return$o?:$n==0;}echo r($argv[1],array_slice($argv,2));" 12 1 5 10
pengguna59178
sumber
Jika dipanggil dengan lebih dari 97 jenis koin yang berbeda, koin itu akan mati secara rekursi tanpa mengembalikan apa pun, tetapi karena itu jauh lebih banyak jenis koin, maka kita harus mendukungnya.
user59178
1

Racket 275 byte

(set! l(flatten(for/list((i l))(for/list((j(floor(/ s i))))i))))(define oll'())(for((i(range 1(add1(floor(/ s(apply min l)))))))
(define ol(combinations l i))(for((j ol))(set! j(sort j >))(when(and(= s(apply + j))(not(ormap(λ(x)(equal? x j))oll)))(set! oll(cons j oll)))))oll

Tidak Disatukan:

(define(f s l)
  (set! l              ; have list contain all possible coins that can be used
        (flatten
         (for/list ((i l))
           (for/list ((j              
                       (floor
                        (/ s i))))
             i))))
  (define oll '())                    ; final list of all solutions initialized
  (for ((i (range 1  
                  (add1
                   (floor             ; for different sizes of coin-set
                    (/ s
                       (apply min l)))))))
    (define ol (combinations l i))          ; get a list of all combinations
    (for ((j ol))                           ; test each combination
      (set! j (sort j >))
      (when (and
             (= s (apply + j))              ; sum is correct
             (not(ormap                     ; solution is not already in list
                  (lambda(x)
                    (equal? x j))
                  oll)))
        (set! oll (cons j oll))             ; add found solution to final list
        )))
  (reverse oll))

Pengujian:

(f 4 '[1 2])
(println "-------------")
(f 12 '[1 5 10])
(println "-------------")
(f 19 '[2 7 12])
(println "-------------")
(f 8 '(1 2 3))

Keluaran:

'((2 2) (2 1 1) (1 1 1 1))
"-------------"
'((10 1 1) (5 5 1 1) (5 1 1 1 1 1 1 1) (1 1 1 1 1 1 1 1 1 1 1 1))
"-------------"
'((12 7) (7 2 2 2 2 2 2))
"-------------"
'((3 3 2) (2 2 2 2) (3 2 2 1) (3 3 1 1) (2 2 2 1 1) (3 2 1 1 1) (2 2 1 1 1 1) (3 1 1 1 1 1) (2 1 1 1 1 1 1) (1 1 1 1 1 1 1 1))

Solusi rekursif berikut memiliki beberapa kesalahan:

(define (f s l)                      ; s is sum needed; l is list of coin-types
  (set! l (sort l >))
  (define oll '())                   ; list of all solution lists
  (let loop ((l l)   
             (ol '()))               ; a solution list initialized
    (when (not (null? l))
        (set! ol (cons (first l) ol)))
    (define ols (apply + ol))        ; current sum in solution list
    (cond
      [(null? l) (remove-duplicates oll)]
      [(= ols s) (set! oll (cons ol oll))
                 (loop (rest l) '()) 
                 ]
      [(> ols s) (loop (rest l) (rest ol))
                 (loop (rest l) '())   
                 ]
      [(< ols s) (loop l ol) 
                 (loop (rest l) ol)
                 ])))

Tidak berfungsi dengan baik untuk:

(f 8 '[1 2 3])

Keluaran:

'((1 1 1 2 3) (1 2 2 3) (1 1 1 1 1 1 1 1) (2 3 3) (1 1 1 1 1 1 2) (1 1 1 1 2 2) (1 1 2 2 2) (2 2 2 2))

(1 1 3 3) dimungkinkan tetapi tidak ada dalam daftar solusi.

juga
sumber
Saya tidak terbiasa dengan Racket, tetapi saya menulis solusi di Clojure untuk masalah yang sama dengan ini beberapa tahun yang lalu yang menggunakanreduce
miles
'perkecil' bukan bagian dari bahasa Racket dasar, meskipun 'lipatan' tersedia. Saya telah menambahkan solusi yang dimodifikasi di atas karena solusi sebelumnya memiliki beberapa kesalahan.
rnso
Sepertinya sekelompok penggemar Lisp berkumpul ... dan membuat keributan
Joe
1
Beberapa penggemar Lisp pertama kali membuat Scheme( groups.csail.mit.edu/mac/projects/scheme ) yang akhirnya menghasilkan full-blown Racket( racket-lang.org , stackoverflow.com/questions/3345397/… )!
rnso
1

Jelly , 15 byte

s+\Fṁḷ
2*BW;ç/Ṫ

Cobalah online! atau Verifikasi semua kasus uji.

Ini lebih merupakan latihan menulis versi efisien dalam Jelly tanpa menggunakan builtin. Ini didasarkan pada pendekatan pemrograman dinamis tipikal yang digunakan untuk menghitung jumlah cara untuk membuat perubahan

Penjelasan

s+\Fṁḷ  Helper link. Input: solutions S, coin C
s       Slice the solutions into non-overlapping sublists of length C
 +\     Cumulative sum
   F    Flatten
     ḷ  Left, get S
    ṁ   Mold the sums to the shape of S

2*BW;ç/Ṫ  Main link. Input: target T, denominations D
2*        Compute 2^T
  B       Convert to binary, creates a list with 1 followed by T-1 0's
          These are the number of solutions for each value from 0 to T
          starting with no coins used
   W      Wrap it inside another array
    ;     Concatenate with D
     ç/   Reduce using the helper link
       Ṫ  Tail, return the last value which is the solution
mil
sumber
1

Sebenarnya , 15 byte

Saran golf diterima. Cobalah online!

╗;R`╜∙♂S╔♂Σi`Mc

Tidak melakukanolf

         Implicit input n, then the list of coins a.
╗        Save a to register 0.
;R       Duplicate n and create a range [1..n] from that duplicate.
`...`M   Map the following function over that range. Variable i.
  ╜        Push a from register 0.
  ∙        Push the i-th Cartesian power of a.
  ♂S       Sort each member of car_pow.
  ╔        Uniquify car_pow so we don't count too any duplicate coin arrangements.
  ♂Σ       Take the sum of each coin arrangement.
  i        Flatten the list.
c        Using the result of the map and the remaining n, push map.count(n).
         Implicit return.
Sherlock9
sumber
0

Python, 120 byte

from itertools import*
lambda t,L:[sum(map(lambda x,y:x*y,C,L))-t for C in product(range(t+1),repeat=len(L))].count(0)

Bruteforce melalui semua kombinasi koin hingga nilai target (bahkan jika yang terkecil bukan 1).

Karl Napf
sumber