daily pastebin goal
96%
SHARE
TWEET

Untitled

a guest Jan 17th, 2018 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Aufgabe 3
  2. b)
  3.  
  4. Eine optimale Lösung zeichnet sich dadurch aus, dass folgende Münzen höchstens in folgendem Verhältnis vorkommen:
  5.  
  6. 1 * (1, 5, 10, 50, 100)
  7. 2 * (2, 20)
  8. x * (200)
  9.  
  10. Wenn in jedem Fall das maximale Vorkommen eingehalten wird, ist der Algorithmus optimal.
  11.  
  12. Der Algorithmus operiert wie folgt:
  13.  
  14. n = Centbetrag, der gewechselt werden soll.
  15.  
  16. 1. Schritt:
  17. Falls n>=200, wende n=n-200 solange an, bis n<200.
  18.  
  19. wir erhalten x*200 als Wechselgeld, dies erfüllt unser Kriterium.
  20.  
  21. Falls n jetzt zweistellig ist, springe zu Schritt 2.
  22. Falls n jetzt einstellig ist, springe zu Schritt 3.
  23. Falls n jetzt nullstellig, sind wir fertig.
  24.  
  25. 2. Schritt:
  26. p = zweite Stelle von n:
  27.             p=9 => 50, 20, 20
  28.             p=8 => 50, 20, 10
  29.             p=7 => 50, 20
  30.             p=6 => 50, 10
  31.             p=5 => 50
  32.             p=4 => 20, 20
  33.             p=3 => 20, 10
  34.             p=2 => 20
  35.             p=1 => 10
  36. Daraufhin wird die zweite Stelle null.
  37. Falls n einstellig ist, springe zu Schritt 3.
  38. Falls n nullstellig ist, sind wir fertig.
  39.  
  40. 3.Schritt
  41. t = erste Stelle von n:
  42.             t=9 => 5, 2, 2
  43.             t=8 => 5, 2, 1
  44.             t=7 => 5, 2
  45.             t=6 => 5, 1
  46.             t=5 => 5
  47.             t=4 => 2, 2
  48.             t=3 => 2, 1
  49.             t=2 => 2
  50.             t=1 => 1
  51. Daraufhin sind wir fertig.
  52.  
  53. Wie wir sehen, ist egal welchen Centbetrag wir wechseln müssen, das Kriterium für die optimale Lösung erfüllt.
RAW Paste Data
Top