Schreiben Sie ein Programm, das berechnet, ob ein eingegebener Geldwert als Ganzzahl durch eine eindeutige Kombination von Münzen und / oder Banknoten dargestellt werden kann. Dies bedeutet, dass dieselbe Münze / Banknote nur einmal verwendet werden kann.

Ihr Programm sollte einen Wert als Eingabe annehmen und kann eine Liste von Münz- / Notenwerten entweder über die Eingabe oder über die Entsprechung eines Arrays in Ihrer Sprache aufnehmen. Die Liste der Münzen / Banknoten sollte sich ändern können. Stellen Sie daher sicher, dass klar ist, wo dies definiert ist, wenn Sie eine Konstante verwenden.

Ihr Programm sollte jeweils einen Wahrheits- / Falschwert ausgeben.

Bitte beachten Sie, dass die Ausgabe der Liste der Münzen / Banknoten, aus denen der Wert besteht, nicht erforderlich ist.

BEISPIEL

Mit dem britischen Pfund (1,00 £ = 100 und 420,69 £ = 42069)

coins = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000]

Folgendes wird true ausgeben:

6 (1, 5)
15 (10, 5)
88 (1, 2, 5, 10, 20, 50)
512 (500, 10, 2)
7003 (5000, 2000, 2, 1)

Folgendes wird false ausgeben:

4
209
8889
4242424242
[ANYTHING ABOVE 8888]

ALTERNATIVE TESTDATEN (US-Dollar)

coins = [1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000]

Viel Glück!

Brachylog 2 (TIO Nexus), 2 Bytes

⊇+

Probieren Sie es online!

Nimmt die Liste der Münzen entweder über die Standardeingabe oder durch Voranstellen vor dem Start des Programms als Array-Literal (entweder funktioniert es, also liegt es an Ihnen, was Sie für "legitimer" halten; ersteres ist standardmäßig zulässig) PPCG-Regeln (letzteres ist in der Frage ausdrücklich erlaubt); und nimmt den zu erzeugenden Wert als Befehlszeilenargument.

Erläuterung

Dieses Programm verwendet Implementierungsdetails der Art und Weise, wie der Wrapper von TIO Nexus für Brachylog funktioniert. Insbesondere können Sie ein Befehlszeilenargument angeben, um Eingaben über die Ausgabe zu erhalten. (Dies war im ursprünglichen Design für Brachylog nicht vorgesehen. Sprachen werden jedoch durch ihre Implementierung in PPCG definiert. Wenn eine Implementierung folgt, die genau das tut, was ich brauche, kann ich sie daher nutzen.) Programm sieht so aus:

⊇+
⊇   Some subset of {standard input}
 +  sums to {the first command-line argument}

Als vollständiges Programm gibt es einen Booleschen Wert zurück. true.ob alle Behauptungen im Programm gleichzeitig erfüllt werden können oder false.nicht.

(Eine Erinnerung oder für Leute, die es noch nicht wissen: Brachylog 2 verwendet eine eigene Zeichenkodierung, die ⊇ein einziges Byte lang ist.)

05AB1E , 4 Bytes

æOså

Erläuterung:

æ      Calculate the powerset of the first input
 O     Sum each element
  s    Put the second input at the top of the stack
   å   Check whether the input is in the powerset sum.

Probieren Sie es online!

Mathematica, 25 Bytes

!FreeQ[Tr/@Subsets@#,#2]&

Reine Funktion, die ein Array von Münzwerten als erstes Argument und die Ziel-Ganzzahl als zweites Argument verwendet und Trueoder zurückgibt False.

Gelee, 6 Bytes

ŒPS€e@

Probieren Sie es online!

-2 Bytes dank Leaky Nun
-13 Bytes dank Leaky Nun (lange Geschichte)

Retina , 52 31 Bytes

\d+
$*
^((1+) |1+ )+(?<-2>\2)+$

Probieren Sie es online! Übernimmt die Eingabe als durch Leerzeichen getrennte Liste von Münzen und Banknoten, gefolgt vom gewünschten Wert. Bearbeiten: Dank @Kobi, der meinen Code getestet hat, wurden 18 Bytes gespeichert. Erläuterung: Die ersten beiden Zeilen werden einfach von dezimal in unär umgewandelt. Die dritte Zeile erfasst dann die Liste der Münzen und Banknoten. Die Abwechslung ermöglicht es dem Motor, zurückzuverfolgen und bestimmte Münzen / Banknoten nicht zu erfassen. Die Bilanzgruppe vergleicht dann den Wert mit allen Suffixen der Erfassungsliste (unnötig, aber golferischer).

Brachylog , 7 Bytes

tT&h⊇+T

Probieren Sie es online!

Wie es funktioniert

tT&h⊇+T
tT      the second input is T
  &     and
   h    the first input
    ⊇   is a superset of a set
     +  that sums up to
      T T

Einschließlich der Kombination, 9 Bytes

tT&h⊇.+T∧

Probieren Sie es online!

Java (OpenJDK 8) , 125 Byte

boolean f(int[]c,int n){int l=c.length;if(l<1)return n==0;int[]a=java.util.Arrays.copyOf(c,l-1);return f(a,n-c[l-1])|f(a,n);}

Probieren Sie es online!

Prolog (SWI) , 46 Bytes

a([],0).
a([H|T],X):-Y is X-H,(a(T,Y);a(T,X)).

Probieren Sie es online!

Gabel meiner Python Antwort .

JavaScript (ES6), 81 69 67 64 Byte

Nimmt die Liste der Münzen cund den Zielbetrag ain Curry-Syntax auf (c)(a). Rückgabe 0oder true.

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

Testfälle

let f =

c=>g=(a,m=1)=>c.map((c,i)=>x-=c*(m>>i&1),x=a)&&!x||x-a&&g(a,m+1)

const pound = [1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000];

console.log(f(pound)(6))
console.log(f(pound)(15))
console.log(f(pound)(88))
console.log(f(pound)(512))
console.log(f(pound)(7003))

console.log(f(pound)(4))
console.log(f(pound)(209))
console.log(f(pound)(8889))
console.log(f(pound)(4242424242))

Haskell , 28 Bytes

Die Operatorfunktion (#)nimmt eine Ganzzahl und eine Liste von Ganzzahlen (oder allgemeiner einen beliebigen TraversableContainer mit Zahlen) und gibt a zurück Bool.

Verwenden Sie als 6#[1, 2, 5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000].

c#l=elem c$sum<$>mapM(:[0])l

Probieren Sie es online!

Wie es funktioniert

• cist der gewünschte Wert und ldie Liste der Münzwerte.
• mapM(:[0])lordnet (:[0])über l, paart jeden Wert mit 0 und konstruiert dann das kartesische Produkt, wobei Listen angegeben werden, in denen jedes Element entweder den entsprechenden Wert in loder 0 hat.
• sum<$>summiert jede Kombination und elem c$prüft, ob sie cin der Ergebnisliste enthalten ist.

R 88 83 Bytes

-5 Bytes dank @Jarko Dubbeldam

Gibt eine anonyme Funktion zurück. Es generiert alle möglichen Kombinationen von Münzen (mit Hilfe expand.gridvon Paaren von T,F) und prüft, ob die Werte vorhanden sind. kist eine Münze, da ces sich bei R um ein reserviertes Wort handelt. Kann mehrere Werte gleichzeitig prüfen.

function(k,v)v%in%apply(expand.grid(Map(function(x)!0:1,k)),1,function(x)sum(k[x]))

Probieren Sie es online!

Japt , 7 Bytes

à mx èN

Probieren Sie es online! Ausgaben 0für Falsy, eine positive Ganzzahl für Truthy.

Erläuterung

à mx èN
          // Implicit: U = input array, V = input integer, N = array of all inputs
à         // Take all combinations of U.
  mx      // Map each combination to its sum.
     è    // Count the number of items in the result which also exist in
      N   //   the array of inputs.
          // This returns 0 if no combination sums to V, a positive integer otherwise.
          // Implicit: output result of last expression

Python 3 , 52 Bytes

5 Bytes dank ovs.

f=lambda c,n:c and f(c[1:],n-c[0])|f(c[1:],n)or n==0

Probieren Sie es online!

Ruby , 39 Bytes

Gibt nilden falschen Wert und den kleinsten Münzwert in der Liste zurück, der die Zahl als wahr darstellt (alle Zahlen sind in Ruby wahr).

f=->c,n{n!=0?c.find{|i|f[c-[i],n-i]}:1}

Aber Sie passen, dass dieser Algorithmus irrsinnig langsam ist, mit O(C!)Zeitkomplexität, wo Cdie Länge der Münze Liste. Es endet schließlich, aber die meisten Testfälle laufen bei den meisten Online-Dolmetschern sogar aus f(UK_POUND, 5).

Hier ist eine 41-Byte-Version, die durch Hinzufügen einer zusätzlichen Endebedingung viel schneller beendet wird und eine Zeitüberschreitung erheblich erschwert

f=->c,n{n>0?c.find{|i|f[c-[i],n-i]}:n==0}

Probieren Sie es online!

Bash + GNU-Dienstprogramme, 56 39

printf %$2s|egrep "^ {${1//,/\}? {}}?$"

Eingabebezeichnungsliste (unsortiert) wird als durch Kommas getrennte Liste angegeben. Eingabeliste und Wert werden als Befehlszeilenparameter angegeben.

Ausgabe in Form des Shell-Returncodes. Überprüfen Sie mit, echo $?nachdem Sie das Skript ausgeführt haben. 0bedeutet wahr, 1bedeutet falsch.

Probieren Sie es online aus .

• printf %$2sgibt eine Folge von valueLeerzeichen aus
• "^ {${1//,/\}? {}}?$"ist eine Shell-Erweiterung, die die Nennwertliste zu einem regulären Ausdruck erweitert ^ {1}? {2}? {5}? {10}? ... $. Es stellt sich heraus, dass die egrepRegex-Engine intelligent genug ist, um mit dieser übereinzustimmen, unabhängig davon, in welcher Reihenfolge sich die Nennwerte befinden
• egrep prüft, ob die Zeichenkette mit dem regulären Ausdruck übereinstimmt

C 66 Bytes

m;v;f(n){for(m=1e5;m/=10;)for(v=5;n-=n<v*m?0:v*m,v/=2;);return!n;}

Sehen Sie es hier arbeiten .

C 53 Bytes

g(c,w,n)int*c;{for(;n-=n<c[--w]?0:c[w],w;);return!n;}

Diese Variante verwendet das Coin-Array, das den Zweck dieses Problems zunichte macht, da es sich um eine einfache Subtraktion handelt.

Das erste Argument ist das Münzfeld, das zweite die Münzzahl und das dritte der Wert.

C 48 Bytes

g(c,n)int*c;{for(;n-=n<*c?0:*c,*++c;);return!n;}

Eine Alternative zur vorherigen Variante. Es wird davon ausgegangen, dass das Münzarray umgekehrt und nullterminiert werden kann.

Pyth , 6 Bytes

/sMtyE

Testsuite.

CJam , 18 17 Bytes

q~_,2\m*\f.*::+#)

Probieren Sie es online!

Erläuterung

q~                  e# Read and eval input.
  _,                e# Duplicate the money list and take its length.
    2\m*            e# Take the (length)th Cartesian power of [0 1].
        \f.*        e# Element-wise multiplication of each set of 0's and 1's with the money
                    e#   list. This is essentially the powerset, but with 0s instead of 
                    e#   missing elements.
            ::+     e# Sum each set.
               #    e# Find the index of the desired amount in the list. (-1 if not found)
                )   e# Increment. -1 => 0 (falsy), anything else => nonzero (truthy)

C (gcc) 91 Bytes

i,j,c[]={1,2,5};f(n){for(i=1000;i;i/=10)for(j=2;j>=0;j--)n-=n<i*c[j]?0:i*c[j];return n==0;}

Probieren Sie es online!

PHP, 70 Bytes

Gibt 1 für wahr und nichts für falsch aus

<?foreach($_GET[1]as$v)$i-=$v*$r[]=($i=&$_GET[0])/$v^0;echo max($r)<2;

Probieren Sie es online!

Oktave, 39 Bytes

 @(L,n)any(cellfun(@sum,powerset(L))==n)

Eine anonyme Funktion, die ein Array von Münzwerten als erstes Argument und die Ziel-Ganzzahl als zweites Argument verwendet und true oder false zurückgibt.

Probieren Sie es online!

Mathematica, 42 Bytes

ListQ@NumberDecompose[#,Sort[#2,Greater]]&

Eingang

[15, {10,5}]