Betrag auszahlbar?

[Nersgatt]

Moin,

ich brauch mal einen Schubbs in die richtige Richtung.
Ich muss prüfen, ob ein Betrag auszahlbar ist. Dabei ist vorgegeben, welche Banknoten/Geldstück ich habe.

Nehmen wir an, ich hab 20er, 50er und 100er in der Kasse.
Damit kann folgendes auszahlen:
10 EUR : Nein
20 EUR : Ja
30 EUR : Nein
40 EUR : Ja
50 EUR : Ja
60 EUR : Ja
70 EUR : Ja
80 EUR : Nein
usw.

Nun hab ich mir zuerst überlegt, ich nehm den Betrag und such die größte Note, die ich hab. Die Note muss aber <= Betrag sein.

Keine Note gefunden: Kann nicht ausgezahlt werden!
Note gefunden: Diese ziehe ich nun von dem Betrag ab.
Ist der Betrag nun 0, dann kann ich den Betrag auszahlen
Ist der Betrag > 0, fange ich von vorn an.

Das funktioniert in meinem Bespiel bis zur 60 EUR. Bei 60 EUR würde er im ersten Schritt 50 EUR abziehen, Rest 10. Dazu findet er keine Note mehr, also nicht auszahlbar.
Das ist aber falsch, ich könnte die 60 EUR ja mit 3x20 auszahlen.

Irgendwie hab ich da eine Denkblockade, wie ich das angehen kann

Danke!

[Stevie]

Zitat von Nersgatt:

Das funktioniert in meinem Bespiel bis zur 60 EUR. Bei 60 EUR würde er im ersten Schritt 50 EUR abziehen, Rest 10. Dazu findet er keine Note mehr, also nicht auszahlbar.
Das ist aber falsch, ich könnte die 60 EUR ja mit 3x20 auszahlen.

Führ den Test mit der nächstgrößeren Banknote nochmal durch.

[Deep-Sea]

Es könnte klappen, wenn man nicht einfach die größtmögliche Banknote nimmt, sondern erst mal die Banknote die mit dem auszuzahlenden Betrag den größten gemeinsamen Teiler hat
Reine Theorie die mir spontan so früh am morgen *gähn* einfiel

[Satty67]

Es kann auch passieren, das nur 2x 20 in der Kasse ist und somit 60 auch nicht mit 20er auszahlbar ist?

1) größten Schein aus der Kasse auswählen

2) (Rest)Betrag durch Schein teilen, bei Ergebnis:

= 1 : fertig, passt
> 1 : Schein von Betrag abziehen/aus Liste nehmen, mit Restmenge bei 1) beginnen
< 1 : Kleinerer Schein auswählbar, bei 2) weiter. Kein kleinerer Schein mehr da -> geht nicht.

[Nersgatt]

Zitat von Satty67:

Es kann auch passieren, das nur 2x 20 in der Kasse ist und somit 60 auch nicht mit 20er auszahlbar ist?

Nein, es wird angenommen, dass immer unendlich viele Scheine in der Kasse sind (leider nur eine Annahme ).

Ich hab jetzt hoffentlich eine Lösung. Das ganze hab ich rekursiv gelöst. Bei jedem Funktionsaufruf wird geprüft, ob der (Rest-) Betrag durch eine der Noten teilbar ist. Wenn ja: fertig.

Bisher hab ich kein Beispiel gefunden, wo es nicht funktioniert. Vielleicht möchte ja jemand versuchen, ein Beispiel zu finden, wo es fehlschlägt.

Delphi-Quellcode:

unit UVorschuss;

interface

uses
  Generics.Collections;

type
  TGeldstueckliste = TList<Currency>;
  TVorschuss = class(TObject)
  private
    FGeldstueckliste: TGeldstueckliste;
    Function GroessterBetrag(ABetrag : Currency) : Currency;
  protected

  public
    constructor Create;
    destructor Destroy; override;
    property Geldstueckliste : TGeldstueckliste read FGeldstueckliste;
    Function IsBetragAuszahlbar(ABetrag : Currency) : Boolean;
  end;

implementation


{ TVorschuss }

constructor TVorschuss.Create;
begin
  inherited;

  FGeldstueckliste := TGeldstueckliste.Create;
end;

destructor TVorschuss.Destroy;
begin

  FGeldstueckliste.Free;

  inherited;
end;

function TVorschuss.GroessterBetrag(ABetrag: Currency): Currency;
var
  Geldstueck : Double;
begin

  result := 0;
  for Geldstueck in FGeldstueckliste do
  begin
    if (Geldstueck <= ABetrag) and (Geldstueck > Result) then
      result := Geldstueck;
  end;

end;

function TVorschuss.IsBetragAuszahlbar(ABetrag: Currency): Boolean;
var
  sub : Double;
  NeuerBetrag : Double;
  i : integer;
  intBetrag : integer;
begin

  result := False;
  i := 0;
  intBetrag := trunc(ABetrag * 100);
  while (i <= FGeldstueckliste.Count - 1) and not result do
  begin
    result := (intBetrag mod trunc(FGeldstueckliste.Items[i] * 100)) = 0;
    inc(i);
  end;

  if not Result then
  begin
    sub := GroessterBetrag(ABetrag);
    if sub > 0 then
    begin
      NeuerBetrag := ABetrag - sub;
      if NeuerBetrag = 0 then
         result := True
      else
        result := IsBetragAuszahlbar(NeuerBetrag);
    end
    else
      result := false;
  end;
end;

end.

[joachimd]

Du kannst quasi beliebig oft verzweigen, bis Du den richtigen Weg gefunden hast, um ans Ziel zu kommen. Schau dir mal die ganzen Beispiele zu A-Path an, zB http://www.delphipraxis.net/59116-pa...ing-mit-*.html

[himitsu]

Zitat:

Nein, es wird angenommen, dass immer unendlich viele Scheine in der Kasse sind (leider nur eine Annahme ).

3 While-Schleifen.

Erstmal so viele wie mögliche 100er abziehen,
dann die 50er und dann noch die 20er.

Wenn am Ende 0 übrig bleibt, dann kann man das auszahlen.

PS: Da man 100er auch mit 50ern ausgeben kann, könnte man sich die Prüfung auf 100er auch gleich sparen.
Bleiben also noch 2 Schleifen und ein IF, bzw. als Funktion verbaut gleich das IF als Result:= .

[Nersgatt]

Das ist ja praktisch meine erste Idee gewesen. Schlägt aber bei 60 EUR fehl.

60 - 0x100 = 60
60 - 1x50 = 10
10 - ??? (kein Schein mehr gefunden).

[himitsu]

Ups, dann halt noch eine 60er-Schleife mit rein und schon geht es.
-60 -50 -20 = 0

[Deep-Sea]

Zitat von himitsu:

Ups, dann halt noch eine 60er-Schleife mit rein und schon geht es.

Und für 100 gibt er dann 1x 60 und 2x 20, also 5x 20 raus, anstatt 2x 50 (sofern wir die 100er mal beiseite lassen)?