daily pastebin goal
36%
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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top