[MUSIC SPIEL] 

ZAMYLA CHAN: Nun wollen wir angehen Greedy. Angenommen, Sie sind ein Kassierer, und Sie müssen Ihre Kunden einen geben gewisse Veränderung. Nun, wenn Sie ein gieriger Kassierer waren, Sie wollen würde, um alle zu halten die Münzen für sich. So können Sie dem Kunden die Änderung geben würde mit so wenig Münzen wie möglich. 

Ihre Aufgabe für diese p-Set ist zu implementieren Gierig, ein Programm, das berechnet die Mindestzahl von Münzen verwendet, zu einem machen gegebenen Betrag der Änderung. Vor dem Tauchen in der Programmierung Konzepte und C-Syntax für Gierig, Sprechen wir zuerst über die Greedy -Programm, und sehen, ob wir kann einen Algorithmus zu identifizieren. Denken Sie daran, dass ein Algorithmus ist nur eine Reihe von Anweisungen für die Lösung von Problemen. Ein Algorithmus zur Greedy wäre nur ein Satz von logischen Regeln und Schritte, die wir folgen können. Und sie werden immer die minimale Ausbeute Anzahl von Münzen benötigt. 

Das erste, was Sie brauchen schon wissen, ist, wie viel Veränderung wird dem Kunden gegenüber. Für dieses Beispiel, sagen wir $ 0,32. Es gibt viele Möglichkeiten, um wieder 0,32 $. Sie könnten zum Beispiel 32 Pfennige. Oder wenn Sie ein bisschen gieriger waren in Auswahl Ihrer Münzen, die Sie verwenden können fünf Münzen 32 statt, indem der Kunde drei Groschen - Jeweils $ 0,10 - und zwei Pfennige - $ 0,01 je. 

Aber können wir es besser machen als fünf Münzen? Können wir noch gieriger sein? Durchaus möglich. 

Lassen Sie uns weiter zu Fuß durch der Greedy-Programm, und zu sehen. Wenn Ihr Endziel ist es, ein paar Münzen zu verwenden wie möglich, dann würde es den meisten sein ratsam, den größten verwenden möglich Münzen. Sie würden eher geben ein Viertel Rücken - - jede 0,25 $ als fünf Nickels - $ 0,05 je. Also vielleicht unsere Regierungsregel für Gierig sein kann, um immer die größte Münze möglich. Aus Viertel, Groschen, Nickel, und Pfennige, unsere größte Münze ist das Viertel. Also werden wir versuchen, sie zum ersten Mal verwenden. 

Zurück zu unserer $ 0,32. Können wir ein Viertel zu geben, der Kunde 0,32 $? Ja. Das würde uns mit $ 0,07 nach links verlassen. 

Können wir ein weiteres Quartal? Nein, denn 25 ist größer als sieben. Wir wollen nicht, um dem Kunden zu geben mehr, als wir ihnen zu verdanken haben. 

Gut. Nun, da wir unser Quartier erschöpft, lassen Sie uns nun auf die nächste größte Münze, die Cent. Können wir einen Cent zu geben, die Kunden ihre 0,07 $ zurück? Nein, da 10 größer als sieben. 

So wird der nächste größte Münze zugänglich ist für uns die Nickel. Können wir eine Nickel? Ja. Und dann würden wir 0,02 $ übrig haben. 

Wir können nicht mit einem Nickel zu 0,02 $ zurück. So zogen wir die letzte Münze uns zur Verfügung - der Groschen. Und nach über zwei Pfennige, würden wir sein links mit null Cent, was bedeutet, dass haben wir erfolgreich zurückgezahlt der Benutzer die Änderung geschuldeten mit nur vier Münzen - ein Viertel, die Nickel, und zwei Pfennige. 

Sie können die Personal-Lösung laufen, um zu sehen, ob unsere Regierungs Regel-und Prozess gab uns die richtige Antwort. Für die meisten Problemstellungen, werden Sie in der Lage sein, Lösung, um die Mitarbeiter ausführen, um zu sehen, wie Ihr eigenes Programm sollte funktionieren. Und spezifischen Anweisungen wird sein, das Problem setzt specs. 

Sobald wir die Personal-Lösung laufen, es veranlasst uns, wie viel Veränderung geschuldet beachten Sie, dass es für das fragt betragen in Dollar. Wir Eingangs $ 0,32, 0,32. Es sagt uns, dass vier Münzen geschuldet, im Einklang mit unserer Antwort. Fantastic. 

So, jetzt zu beginnen, lassen Sie bei der Umsetzung der Greedy-Algorithmus. Wir wissen, ein paar Dinge. Eine, die wir brauchen, um die Eingabeaufforderung Benutzer für einen Betrag von Veränderung. 

Zwei, dass wir folgen möchten unsere Regierungs Regel immer die größte Münze möglich. Und drei, dass wir den Überblick zu behalten wie viele Münzen die wir verwenden. Denn schließlich müssen wir drucken die Anzahl der Münzen, das wir. 

Erstens, die den Benutzer auffordert für einen Betrag von Veränderung. Wann immer Sie mit Benutzereingaben umgehen, stellen sicher, dass Sie all das denken, Anforderungen der Eingabe und nur Eingabe akzeptieren, dass diejenigen, trifft Anforderungen. In diesem Fall zu beschäftigen möchten wir ein Geldwert in Dollar. 

Die GetFloat und GetInt Funktionen sorgen dass die Eingabe numerischer. Aber der Benutzer ist in der Lage, Eingangs negativen Zahlenwerte. Also denken Sie daran, nur nicht-negative Eingänge, die alle negativ sind Zahlen und Null. 

In diesem Fall wird das Eingangs sollte ein Schwimmer sein. In anderen Worten, eine Dezimalzahl. Da das Problem Satz spec erfordert Sie für die Eingabe in Dollar zu bitten. 

Aber in C, kann Gleitkommazahlen nicht genau dargestellt werden. Da es eine endliche Anzahl von Bits, mit denen stellen unendliche Werte. Nehmen Sie die Zahl 0,1. Wenn ich Sie bitten, zu schreiben von 0,1 Hand auf den Hundertstel Dezimalstelle, Sie eine 1 schreiben würde, gefolgt von 99 Nullen. Wir würden erwarten, dass unsere Computer wäre drucken Sie die genau die gleiche Sache wenn wir sie aufgefordert. 

Also mal sehen, was es tut. Ich werde Druckwerte zu überprüfen Das Ende dieser Fuß durch. Denn jetzt, sehen hier, daß f% ist ein Platzhalter für eine Floating-Point. Aber wir geben im Voraus, dass wir wollen, 100 Dezimalstellen angezeigt wird, und dann ein neues Linie für schönere Formatierung. 

Nach der Zeichenfolge, wählen wir die 0,1 schweben, dass wir ausdrucken möchten. Und das Ergebnis, eine Eins ist, gefolgt von einigen Nullen, dann aber ein ganze Reihe von Zahlen. Sicher nicht, wie erwartet. 

Floating Point Ungenauigkeit einführen können Rundungsfehler in Ihren Berechnungen, die Sie möchte auf jeden Fall vermeiden. Wenn Sie weitere Beispiele sehen, möchten Sie imprecision.ce kann von der Download- Spaziergang durch Code, der ein einfacher ist Programm, das zu schweben, fragt und gibt es zurück zum hundertsten Nachkommastelle. Natürlich, wenn Sie zeigen wollen mehr oder weniger Dezimalstellen können Sie selbst ändern. 

Wie Sie sehen werden, auch wenn der Unterschied zwischen den beiden ist klein, wenn man Multiplizieren und Addieren Schwimmer, dass Diskrepanz kann schließlich summieren. Zurück zu gierig. Wir werden um Rundungsfehler zu vermeiden wollen durch den Umgang mit ganzen Zahlen. So, nachdem wir gültige Eingabe von der Benutzer, lassen Sie wandeln diese Dollarwert Cent. 

Psychisch, tun wir dies durch Multiplikation der Dollar-Wert um 100. Aber denken Sie daran, wegen der Floating-Point- Ungenauigkeit, damit wollen wir sicher, dass wir Sie mit dem richtigen Wert. Mit 100 multipliziert wird im Wesentlichen bewegen die Dezimalstelle um zwei Räume das Recht, Abhacken oder Abschneiden alles danach. 

Wenn Sie spielen, um mit etwas mehr Beispiele, werden Sie sehen, dass Sie nicht immer die richtige Zahl bekommen, wenn Sie Mit dieser Methode des Abschneidens. Beispielsweise 12,59 bis 100 gedruckt Dezimalstellen, die Ihnen 12,5899, et cetera. Sie würden 12,58, wenn man abgeschnitten, 12.59 nicht, wie Sie benötigen. 

Stattdessen ist es am besten zu runden die Zahl zuerst. Zum Glück kommt mit dem C Funktion aufgerufen Runde. Es ist in der Mathematik-Bibliothek. 

Wenn Sie wissen wollen, wie zu Runde zu verwenden, dann können Sie rufen Sie die manuelle oder man-Seite für diese Funktion. Sie tun dies, indem Sie man, kurz für manuell, und dann die Funktion, die Sie nachschlagen möchten. So runden Sie man in das Terminal Befehlszeile öffnet das Handbuch. 

Es könnte ein wenig schwer zu entziffern sein, aber irgendwann werde bekommen den Dreh raus. Man-Seiten zeigen Ihnen, was die Funktion tut, und dann einige Einsatzmöglichkeiten es. Ich werde dich verlassen, um zu erkunden der Mann Seite für Runde. Aber wissen, dass Sie es verwenden, um runden der Wert während der Umwandlung von Dollar auf Cent. 

Runde wird Ihnen wieder eine Reihe vom Datentyp double. Und Sie können zu konvertieren oder gegossen es in einen int danach. Große. Inzwischen haben wir die Benutzer aufgefordert, für ein Geldbetrag, und wandelte sie in Cent. Jetzt können wir einen Algorithmus zu implementieren dass immer verwendet der größten Münzen zur Verfügung. 

Denken Sie daran, dass es mehrere Wege zur Umsetzung Gierig, wie es gibt mehrere Möglichkeiten sich zu nähern jeder Computer Science Problem. Das Finden der eleganteste Weg, das ist der spaßige Teil. In diesen p-Sets, wenn Ihr Programm nicht exakt meine Erklärung in den Komplettlösungen, das ist OK. Aber so stellen Sie sicher, dass es geht Check 50, erfüllt alle Anforderungen bilden die Vorgaben, und dass Sie prüfen, ob Ihre Ansatz hat gutes Design. 

In anderen Worten, wie effizient es? Zum Beispiel, wussten Sie geben sich wiederholende Codelinien, anstelle der Verwendung einer Schleife? Schreiben von Code mit besseren Design wird kommen Erfahrung, wie Sie Fortschritte durch den Kurs. 

Für diese durch zu gehen, werde ich gehen über Zwei Methoden, die verwendet werden können, Greedy vervollständigen. Das erste Verfahren ist ein Verfahren, das Schleifen und Subtraktion. Früher, als wir durch die gesprochen Greedy Verfahren, die wir kontinuierlich überprüft, ob wir ein Viertel nutzen könnten, und verwendet ein Viertel bis die Restwert betrug weniger als 0,25 $. 

Dies führt auch zu einer while-Schleife-Struktur. Während wir immer noch verwenden können ein Viertel, verwenden Sie eine. Das while-Schleife sollte so lange ausführen als der verbleibende Wert ist größer als oder gleich Cent Wert eines Quartals. Das heißt, Sie wollen auch verfolgen die restliche Geld Wert und aktualisieren Sie es jeden Zeit, dass Sie eine Münze zu verwenden. 

Denken Sie auch daran, dass am Ende, Ihre Ausgang ist die Anzahl der Münzen verwendet. Also eine andere Sache im Auge zu behalten ist die Anzahl der Münzen, die Sie verwenden. Sie können verfolgen, diese mit zu halten gut benannten Variablen. Und innerhalb des Körpers der Schleife würde sein, ein Update auf diese Variablen. Sobald die Schleife für das Quartal beendet, können Sie kann eine ähnliche für Groschen zu verwenden, und so weiter und so fort, bis Sie haben zurück alle Bargeld. 

Ich habe einige Pseudo-Code hier geschrieben Sie visualisieren, wie die Prozess, den wir diskutiert vielleicht übersetzen C. Wie Sie hier sehen, ich bin immer noch mit Englisch Wörter. Es ist noch nicht C. Aber ich habe den Gedankenstrich Dinge gestartet. Ich habe Bedingungen innen setzen meine Klammern. Es beginnt ein wenig aussehen bisschen wie Programmiercode. 

Pseudo-Code ist ein guter Weg um sich selbst zu beginnen. Visualisieren Sie Ihre Code vor Sie nach oben schauen Syntax. Da oft der schwierigste Teil über eine Problem wirklich zu verstehen, was genau Sie tun müssen. Wenn Sie das aufschreiben, dann ist es eine viel einfacher zu schauen die Funktionen Syntax und speziell auf Ihre Linie der Pseudo-Code 

Beachten Sie, dass dies nicht sein identisch mit der Art von Skelett Ihr Code, den Sie schreiben. Es gibt immer Optimierungen vorgenommen werden. Und vor allem in meinem Pseudo-Code hier finden Sie, wenn Sie es erkennen. 

Aber im Grunde der Prozess und die Art des Denkens ist nur, wie wir diskutiert. Die erste Zeile sagt uns, zu erhalten ein bestimmter Betrag in Dollar. Und der zweite sagt uns, wandelt es in Cent. 

Und dann, während Quartalen verwendet werden, haben wir wollen, um die Münze Zahl erhöhen und verringern Sie den Geldbetrag. Das Gleiche gilt für Groschen, Nickel, und Pfennige. Und schließlich, die Benutzer sagen, dass wir wir, wie viele Münzen verwendet. 

Große. Damit schließt die Schleife Methode. Jetzt reden wir über die modulare Methode zu sprechen, die mehr wie Division ist. 

Wir sind alle vertraut mit dem Plus, Minus, multiplizieren und dividieren Betreiber uns zur Verfügung. C hat alle vier Personen, aber auch die Modulo-Operator, dargestellt durch ein Prozent-Zeichen. Modulo ist wirklich ordentlich. Es gibt Ihnen den Rest aus Dividieren von zwei Zahlen. 

Denken Sie an die lange Teilung Meldung, wenn Sie teilen, sagen wir, 74 von drei? Beginnend mit der Zehnerstelle, würden Sie wissen, dass 3 geht in sieben zweimal, um eine sechs mit machen Rest ein. Sie würden zwei an der Spitze schreiben, und dann subtrahieren 6 aus sieben, die Durchführung über der Rest von 14 bis wiederholen Sie den Vorgang. 

Drei geht in 14 viermal 12 machen, mit Rest zwei. Und zwei nicht über mehr tragen. So würden zwei auf der linken Seite werden Boden als Rest besteht. 

Und das ist, was Modulo gibt, sie die Anzahl an der Unterseite. So 74 Modulo drei würden Sie zwei. Und 10 modulo zwei, gut, dass würde Ihnen Null. Da es keine restlichen wenn Sie durch zwei zu teilen 10. 

Sechs Modulo fünf, gut fünf geht in sechs mal. Und dann hat es ein übrig. Also sechs Modulo fünf ist eins. 

Dann, wenn Sie sieben Modulo haben neun, sieben Sie bekommen würde. Da neun ist größer als sieben. So ist es nicht teilen sie alle in sieben, Verlassen sieben als deine Antwort. 

Wenn Sie sich über ein wenig mehr Modulo denken, daran erinnern, dass es Ihnen die Rest nach der Sie etwas zu teilen. Überlegen Sie, wie Sie sein könnte Lage, es in Greedy verwenden. Nehmen wir an, der Benutzer fragt nach $ 400,11. Was ist ein Weg, um herauszufinden, wie viele Quartalen Sie, ohne zu müssen, zählen jeweils ein? 

Wenn Sie herausfinden, wie viele Viertel Sie verwenden, um 400,11 $ zu machen, wie viel Überreste ändern? Vielleicht eine Kombination hier zwischen Modulo und Division kommen würde, in praktisch, um Ihnen einen cool, elegant nähern, um das gierige Problem. Aber denken Sie daran, dass der EZB Regel immer noch gilt. Verwenden Sie immer die größte Münze möglich. 

Sobald Sie die Berechnung, wie getan viele Münzen zu bedienen, den letzten Schritt ist, drucken Sie die Anzahl der Münzen, die Sie berechnet. So weit, wir habe mit dem printf funktionieren ausschließlich für Streicher. Aber wenn Sie zum Ausdrucken eines In, oder wollen nur jede Art von Daten, die gespeichert ist in einer Variablen, haben Sie, um anzuzeigen, dass mit einem Platzhalter. 

Hier habe ich nur ein paar Tipps enthalten auf, wie man ausdrucken Werte. Wenn Sie eine ganze Zahl haben, würden Sie schreiben Sie Ihre String mit% d als Platzhalter. Nach dem Schlusskurs Marke, geben Sie ein Komma. Und dann in der Integer-setzen, dass Will an die Stelle von% d, wenn ausgedruckt. 

So nach dem Anzeigen der Anzahl von Münzen verwendet, sind Sie mit Greedy beendet. Stellen Sie sicher, dass alle Grenzfälle zu überprüfen, Aufräumen Stil ein wenig, und du bist ganz eingestellt, um zu speichern. Am Ende dieses Problems Satz, werden Sie mehr vertraut mit dem CS50 Gerät, das Terminal und Schleife Strukturen und Variablen in C. 

Sie sind gut auf dem Weg. Die Lernkurve kann scheinen hart. Also nehmen Sie es Schritt für Schritt. Stellen Sie sicher, dass Sie schreiben aus Pseudo-Code vor dem Tauchen zu tief in unbekannte Syntax. 

Machen Sie eine Liste zu tun, und brechen die Zuordnung in kleinere, überschaubare Aufgaben. Entdecken Sie alle CS50 Ressourcen. Neben Vortrag rewatch diese durch zu gehen. 

Achten Sie genau auf Abschnitt. Schauen Sie sich die Shorts. Lesen Sie Ihre Fragen Mitschüler Diskutieren auf, und posten Sie Ihre eigenen. 

Viel Glück mit dem p-Set. Und Dank für das Aufpassen. Dies war gierig. 

[MUSIC SPIEL]