>> JASON HIRSCHHORN: Willkommen zu Woche drei, jeder.
Wir haben einen vollen, aber spannend Abschnitt vor uns.
Also erstens, weil wir einige gemacht haben headway mit dem Verlauf aber wir haben noch
haben eine Menge zu lernen noch zu tun, ich bin gehen, um euch einige Ressourcen zeigen
das sollte sich als unglaublich sein hilfreich, da Sie nicht nur Ihren Ansatz
Problem setzt, sondern auch verdauen alle das Material geben wir euch in
Vorträge und Shorts und Abschnitt.
>> Dann werden wir die ersten 20 ausgeben bis 25 Minuten von Abschnitt geht über
GDB, die Sie haben können oder nicht können an diesem Punkt verwendet wird, aber es ist ein
unglaublich hilfreiches Werkzeug, das wird Ihnen helfen, Ihre Programme zu debuggen.
Viele von Ihnen werden in der printf verwendet haben Mitte des Programms heraus
Sie heraus, was eine Variable erreicht.
GDB ist sogar besser als printf und nicht vermasseln, weil Sie Ihren Code
führen Sie es auf einer ausführbaren Datei.
Also werden wir über die 10 hilfreichsten gehen Befehle, die Sie für GDB benötigen, und wir sind
gehen, um auf eine Übung zusammen, so gehen Problem in Satz drei und darüber hinaus, Sie
gdb zu debuggen helfen Ihre Programme.
Und schließlich werden wir über einige gehen Sortier-und Suchalgorithmen
Sie sah in der Vorlesung, und wir sind gehen, um tatsächlich Code, nicht nur
Pseudocode, aber Code binäre Suche, Bubble-Sort und Selection Sort.
>> Also zuerst, ich will gehen über die Ressourcen.
Dies ist eine umfangreiche Liste, und es ist kleinere Schrift, denn ich hatte eine Menge zu
passen hier.
Aber das wird nicht nur helfen Ihnen, wieder mit dem Problem Sätze und
Verdauen Informationen, die Sie gelernt, aber auf jeden Fall kommen Quiz Zeit, diese werden
unglaublich hilfreich.
Also erstens, stellt der Vortrag.
Wenn Sie gehen, um cs50.net/lectures und navigieren Sie zu dem bestimmten Woche und Tag,
Sie werden sehen, dass es Noten für jede Vortrag, das ist nicht einfach nur ein
Transkript, sondern eine bearbeitete Version was im Vortrag mit Codes
Snippets und andere hilfreiche Leckerbissen.
Ich empfehle, gehen über diese.
Und dann auch, es gibt Quellcode erhältlich von jeder Vorlesung.
Und wieder werden diese Folien auch bei cs50.net/sections online
an diesem Abend.
>> So zweiten Jede Woche sind die Shorts, die Abdeckung Themen, in der Regel 5 bis 15
Minuten lang.
Und die, hoffentlich geben Ihnen einen große Primer zu verschiedenen Themen.
Drittens -
und das ist ganz neu ist, Jahre - ist study.cs50.net.
Wenn Sie es nicht überprüft haben, habe ich empfehlen, dass Sie das tun.
Sie erhalten, um ein Thema auszuwählen.
Wir haben Dutzende von Themen gibt.
So zum Beispiel, holen Sie Funktionen.
Es gibt Ihnen einige Folien und stellt fest, auf Funktionen.
Das sind eigentlich die Dias dass TFs sind aufgefordert, während nutzen Sie unser
Präsentationen im Schnitt.
Es gibt auch Tipps und Tricks für den Umgang mit Funktionen, und es gibt
Praxis Probleme, die helfen Sie arbeiten mit Funktionen.
Wir geben Ihnen auch Links zu den Kurz auf Funktionen und die Zeiten, die wirkt,
haben in der Vorlesung zu kommen.
So study.cs50.net, ganz neu ist, Jahr eine fantastische Ressource.
>> Als nächstes habe ich Menschen, die das Handbuch Befehl, den Sie bei der laufen
Befehlszeile.
Also, wenn Sie Fragen zu haben, ein Befehl, zum Beispiel, Rand, die wir
letzte Woche begegnet während Abschnitt und Sie werden wahrscheinlich in angetroffen haben
Ihr Problem eingestellt, wenn man durch die Code generieren, aber wenn man man
rand, werden Sie die Seite bekommen, dass erfahren Sie alles über rand.
Es gibt Ihnen, was es braucht, die Parameter dauert es, ebenso wie Rück
Typ und eine kurze Beschreibung dieser Funktion.
>> So überprüfen Sie rand.
Es kann ein wenig wortreich und verwirrend, so manchmal finde ich, dass
einfach googeln, was ich wissen will, ist der beste Weg, um die Antwort zu finden.
So üben mit Google.
Holen Sie sich gute bei Google.
Es wird Ihr bester Freund werden.
>> Neben Google, wenn Sie es nicht finden können auf Google, cs50.net/discuss, ist es
das Diskussionsforum.
Die Chancen stehen gut, wenn Sie eine Frage haben, ein Ihre 700 + Kollegen hat auch, dass
Frage und können aufgefordert haben es bereits in der Diskussion
Foren und haben sie beantwortet.
Also, wenn Sie eine allgemeine Frage oder Sie eine Frage haben, die Sie denken
vielleicht andere Leute vielleicht in ausgeführt haben, Besuche cs50.net/discuss.
>> Schließlich ist die letzten zwei, wenn Sie wollen sprechen Sie mit einem wirklichen Menschen, Büro-
Zeiten Montag bis Freitag.
Es gibt auch Online-Bürozeiten für die Erweiterung Studenten.
Und last but not least, mir, Ausrufezeichen.
Sie haben alle meine Kontaktdaten.
Wenn Sie etwas brauchen, wenden Sie sich bitte nie gerne an mich wenden.
Immer das Gefühl frei, dies zu tun.
Sehr wenige von Euch haben mich auf GChat aufgenommen, so dass war enttäuschend,
aber hoffentlich, dass ich zwischen ändern diesem und im nächsten Abschnitt.
Haben Sie Fragen bisher auf die Ressourcen?
Große.
>> Schließlich ist ein weiterer Stecker für Feedback sayat.me/cs50.
Sie können mich anonymes Feedback geben auf, wie ich tue.
Das war letzte Woche wirklich hilfreich.
Ich habe ein paar Kommentare von euch direkt nach dem Abschnitt, sowie von
anderen Studenten, die es beobachtet während der Woche, und es
war unglaublich hilfsbereit.
Ich werde versuchen, meine Verwendung zu beschränken das Wort "süß", aber ich werde meine
Begeisterung und Aufregung in anderer Hinsicht.
Aber es gab andere zusätzliche materiellen erteilen,
sowohl Vor-und Delta.
Also bitte, ich gebe euch Rückmeldung zu Ihrem Problem Sets.
Fühlen Sie sich frei, mir Feedback geben auf meiner Lehre.
Ich bin hier für euch.
>> Große.
Das ist alles, was ich für der erste Abschnitt.
Weiß jemand welche haben Fragen so weit?
Und ich habe eine Nachricht für die Schaltzentrale.
Erweiterung Studenten haben mich angeschrieben sagen, sie kommen nicht von der Audio-,
aber das ist aus meiner Kraft zu beheben.
So hoffnungsvoll, dass bekommt in Kürze behoben.
Wenn Sie online gerade anschauen, hallo, aber du hast mich nicht hören.
>> Also erstens, werden wir durch GDB zu gehen.
GDB, wie ich früher angedeutet, ist ein Debugging-Tool
viel besser als printf.
Also, mit GDB, Jungs begann, wenn bekommen Sie öffnen Ihr Gerät wollen
und nehmen Sie die Datei, die ich per E-Mail an Sie früher - Diese Datei wird auch
online in ein wenig -
und führen GDB. / den Namen der Datei.
Erstens, natürlich, zu kompilieren müssen Sie weil GDB-Datei funktioniert nur auf
ausführbare Dateien.
>> Aber wenn Sie schon immer einmal starten GDB, das erste, was Sie tun,
Sie GDB. / Caesar laufen.
Also das ist der Name des Programms, wir sind gehen, um mit ihm jetzt gehen.
So werde ich zu schreiben machen Caesar, die wird mir eine ausführbare Datei geben
hier in grün hervorgehoben.
Und dann werde ich GDB. / Cesar laufen.
>> Und dort gehen Sie.
Sie sehen, wir haben einen Text sagen mir, über die Version von GDB, die mir
einige Garantieinformationen, und dann werden wir haben die BIP Aufforderung, die Art sieht
der wie unsere Eingabeaufforderung, aber Sie sehen, es ist offen
paren, GDB, in der Nähe paren.
Bevor wir fortfahren und zu debuggen diese Datei dass ich an Sie alle gesendet, schauen wir uns an
einige nützliche Befehle, so dass wir ein Gefühl von dem, was werden wir abdecken.
>> Diese Befehle werden hier in der aufgeführten Reihenfolge, in der ich sie verwenden im Allgemeinen.
Also habe ich mein Programm starten, indem Sie GBD. / Name des Programms,
in diesem Fall Caesar.
Und dann das erste, was ich machen 99,9% der Zeit wird Typ Pause bedeuten.
Das setzt einen Haltepunkt am Haupt.
Wesentlichen, was du da tust wird das Programm wird sich an der Haltestelle
Haupt so können Sie mit der Prüfung es Linie Zeile, anstatt alle Lauf
Weg durch.
Sie können an verschiedenen Stellen im brechen Ihr Code, aber in der Regel eine Haupt
guter Ort, um zu starten.
>> Der nächste Befehl, den ich laufen ist Lauf.
Das beginnt das Programm läuft, und wenn Sie Befehlszeile eingeben müssen
Argumente, dass es Sie Befehl ausführen.
Führen Sie mit den Argumenten.
So, da sind wir über eine Version gehen von C, die das Programm euch ist
schrieb für pset zwei -
diese, natürlich, hat einige Bugs in, dass es hoffentlich werden wir finden -
wir werden laufen mit einigen Befehl ausführen Zeilenargumente, weil Caesar,
wie Sie wissen, Jungs pro Problems spec gesetzt, nimmt etwas
Befehlszeilenargumente.
>> Die nächsten paar Befehle, die nächste ist man eigentlich nächste aufgerufen.
Dass man führt Sie Zeile für Zeile durch das Programm.
So schlagen Sie dann die Eingabetaste n führt Sie in der nächsten Zeile, die Ausführung
die bisherige Linie.
Schritt führt Sie nicht nur auf Die nächste Zeile, aber es
bringt Sie innerhalb von Funktionen.
Also, wenn Sie eine Funktion in geschrieben haben Ihr Code oder wenn Sie erforschen möchten ein
i, zum Beispiel, können Sie s getroffen, und anstatt sich in die nächste Zeile von
die Datei, die Sie durch rechts gehst jetzt, werden Sie tatsächlich in Schritt
diese Funktion und sehen seinen Code.
>> Liste zeigt Ihnen, in sehr benutzerfreundlich Format, die 10 oder so Linien um
wo Sie derzeit in Ihrem Code so können Sie tatsächlich sehen die Datei
anstatt zu tauschen und zurück her zwischen verschiedenen Ansichten.
Print ist wie printf, wie der Name schon sagt.
Das zeigt Ihnen, was eine Variable ist gleich.
>> Info Einheimischen ist wirklich hilfreich.
Dies ist eine spezielle Version von Print.
Info Einheimischen zeigt Ihnen alle lokalen Variablen, druckt sie alle für Sie
die derzeit verfügbar sind.
Also habe ich in der Regel, anstatt drucken Sie sich die vier Variablen, die ich bin
neugierig, wenn ich in einer for-Schleife für Beispiel habe ich nur schreiben info Einheimische,
und es wird mir, was mein Gegen i zeigen entspricht, sowie die Anordnung, die ich bin
Arbeiten am Gleichen.
>> Schließlich fortsetzen.
Typing Pause hält Sie an der Bruchstelle.
Sie können durch die Leitung gehen durch Entsprechend nächsten Schritt und.
Weiter läuft das Programm auf Ihren nächsten Haltepunkt oder bis zum Abschluss, wenn
gibt es keine Bruchstellen.
Disable entfernt Bruchstellen, wenn Sie beschloss der Pause am Haupt war
unangemessen, wollen Sie legen Sie es woanders.
Und schließlich q, beenden, steigt aus der GDB.
>> Also das Programm. / Cäsar, werden wir durch jetzt aussehen, und wir
gehen, um GDB verwenden, um die Bugs in diesem Programm.
Ich lief dieses Programm zuvor mit Prüfen Sie 50, und ich habe ein Stirnrunzeln.
Alles, was es gab, es kompiliert, es bestanden viele der Tests, aber für
einen Grund, es nicht die fünfte geben Test, Drehen BARFOO, alle Kappen, in
E-D-U-I-R-R, alle Kappen, mit drei als Schlüssel.
Ich habe ziemlich nahe.
Ich habe durch einen Buchstaben.
So gibt es einige kleine Fehler hier.
Ich habe durch meinen Code aussah.
Ich konnte es nicht herausfinden.
Hoffentlich können Sie mir helfen Jungs herauszufinden, was dieser Fehler ist.
>> Also das ist der Fehler, den wir sind für die Suche.
Lassen Sie uns in GDB zu bewegen.
Auch hier habe ich GDB. / Caesar laufen, so jetzt sind wir in GDB.
Und was ist das erste , was ich tun soll?
Ich habe gerade eingegeben GDB.
Jemand gab mir einen guten Befehl eingeben.
>> STUDENT: Break Haupt.
>> JASON HIRSCHHORN: Break Haupt.
Fantastic.
Lassen Sie uns geben, dass in.
Ihr Jungs können Sie sich hier ansehen oder folgen entlang auf Ihrem Computer.
Brechen Haupt, und Sie werden sehen, ein Haltepunkt gesetzt wurde -
es gibt mir einige seltsame Speicheradresse, und es gibt mir auch die Zeilennummer.
Wenn ich wieder in dieser Datei zu suchen, Ich würde die Haupt realisieren
passiert in Zeile 21.
Was soll ich laufen weiter?
Ist mein Programm läuft?
Nein.
Also, was soll ich laufen weiter?
>> STUDENT: Führen.
>> JASON HIRSCHHORN: Führen.
Sollte ich nur laufen, oder sollte Ich einige andere Dinge in hinzufügen?
>> STUDENT: Führen Sie mit dem Argument.
>> JASON HIRSCHHORN: Führen Sie mit die Befehlsargumente.
Und da ich eine sehr spezielle Debugging Fall sollte ich das eingeben
Befehlszeilenargument.
Also werde ich laufen nicht drei, das ist wieder die Ausgangs ich von Check 50 bekam.
Startprogramm.
Wir gehen durch ein paar Zeilen.
Sie sehen nun, dass wir in Zeile 21 sind.
Wie kann ich wissen, dass wir in Zeile 21 sind?
Denn wenn man nach links zu schauen meiner Terminalfenster gibt
es sagt, Zeile 21.
Und das gibt mir eigentlich die Code, der in Zeile 21 ist.
So misspoke ich früher.
Main ist eigentlich nicht in Zeile 21.
Main ist ein paar Zeilen über 21.
Aber in Zeile 21, das ist wo wir brechen.
Diese Codezeile hat noch nicht ausgeführt.
Das ist wichtig.
Die Linie, die Sie sehen, hat nicht noch nicht ausgeführt.
Das ist die nächste Codezeile Sie sind dabei, auszuführen.
>> Also das nächste Linie, wie ihr seid wahrscheinlich kennen, ist dies
Zustand zu überprüfen, ob ich trat in eine Befehlszeilenargument.
Und a bis i, was ist der zweite Teil davon gerade?
Was ist ein i?
>> STUDENT: Ändern sie auf eine ganze Zahl.
>> JASON HIRSCHHORN: Es tut uns leid?
>> STUDENT: Sie verändert die Argument auf eine ganze Zahl.
>> JASON HIRSCHHORN: Also a bis i ändert arg v1 aus einem String in eine Ganzzahl.
Und dann, was sie prüfen?
>> TEILNEHMER: Wenn es eine zweite Befehlszeilenargument, abgesehen
von der Ausführung des Programms.
>> JASON HIRSCHHORN: Und was ist die zweite Hälfte dieses
Booleschen Ausdruck überprüfen?
Dieser Teil hier, a bis i?
>> STUDENT: Wenn es negativ.
>> JASON HIRSCHHORN: Stellt sicher, was?
>> STUDENT: Sicherstellen, dass es ist in der Tat positiv.
>> JASON HIRSCHHORN: Genau.
Dies ist zu überprüfen, ob es negativ, und wenn es negativ ist, ich
habe das Gefühl, die nächste Zeile Macht werden Sie mich anschreien den Benutzer.
Lassen Sie uns also getroffen, diese Linie zu Ende auszuführen.
Wir sehen nicht, dass die Linie, die euch vielleicht erwartet, um zu sehen, schrie der
Benutzer und dann wieder, weil Diese Zeile wurde nicht ausgeführt.
Ich betrat 3.
So habe ich in der Tat, geben Sie zwei Befehls Zeilenargumente und 3 ist
größer als Null ist.
So haben wir gesehen, dass die Linie, die wir ausgeführt, aber wir haben nicht Schritt
in der if-Bedingung.
>> So, jetzt, neben, sehe ich, ich bin die Einstellung int Schlüssel entspricht einem i arg v1.
Also das ist mir die Schaffung einer variablen Schlüssel.
Also, wenn ich drucken Schlüssel gerade jetzt, da dass können Sie sehen, die
Wert in der Variablen, Schlüssel entspricht 47.
Das ist komisch, aber natürlich, das ist, weil ich nicht
ausgeführt, dass die Linie noch.
So jetzt, wenn ich auf n, führen Sie diese Zeile, und tun, Druck-Taste, wird der Schlüssel gleich 3,
das ist, was wir erwarten, dass es gleich.
>> Also noch einmal, in GDB, die Linie, die Sie Sie sehen noch nicht ausgeführt haben.
Sie haben zu schlagen N oder S oder eine Zahl andere Befehle, um tatsächlich
führen diese Zeile.
Print-Taste.
Key bei 3.
So weit, so gut.
String ist Klartext.
Lassen Sie diese Zeile ausführen.
Ich bekomme einen String aus Benutzer.
>> Lassen Sie uns in meinem prüfen 50 sehen, ich Geben BARFOO alle Kappen, so
das ist, was ich dir geben.
Wenn ich jetzt Klartext zu drucken.
Du wirst sehen, es eine Zeichenfolge entspricht.
Es gibt mir eine andere seltsame hexadezimale Zahl, aber es macht in
Tatsache sagen, dass mein String ist BARFOO.
Wenn ich wollte sehen, was Taste erreicht dieser Punkt, wie kann ich prüfen, Schlüssel?
>> STUDENT: Print-Taste.
>> JASON HIRSCHHORN: Print-Taste, genau.
Und tatsächlich gibt es eine Abkürzung.
Wenn Sie müde von Tippdruck, du kannst direkt p.
Also p-Taste macht das gleiche genaue Sache.
Und wieder sehe ich es gleich 3 ist.
>> Wenn ich wollte herausfinden, was sowohl die Schlüssel BARFOO und erreicht in der gleichen Zeit
aber ich war müde von der Eingabe jedes ein einzeln, ich
könnte info Einheimischen geben.
Das gibt mir gleich 3 Schlüssel.
Plain Text entspricht BARFOO.
Es gibt mir auch diese zwei seltsame Dinge an der Spitze, die Variable i und
diese Variable n.
>> Diese sind tatsächlich vorhandenen in meinem Hauptprogramm.
Wir haben sie noch nicht begegnet, sondern als eine Vorschau, die
gibt es in meiner for-Schleife.
So jetzt, gleich sie einige seltsame Zahlen, weil sie nicht in der
noch initialisiert, aber es gibt sie noch nicht im Speicher, so sind sie nur eingestellt
bis zu einem gewissen Wert Müll.
Aber wir sehen, Schlüssel im Klar Text recht.
>> Also werde ich diese Zeile ausführen, Linie 34, die for-Schleife.
Wir werden in die springen for-Schleife durch Schlagen n.
Und wir sind innerhalb der for-Schleife.
Wir sind bei unserem ersten Scheck.
Und wieder, sollten diese Art von Blick bekannt vor, denn es war ein
Caesar-Programm, das geschrieben wurde, aber wieder, hat eine Art Bug.
>> Und jetzt, wenn ich Informationen Einheimischen, denn ich bin im Inneren, die for-Schleife, sehen Sie,
dass ich gleich Null ist, wie wir es erwarten.
Das ist, was wir sie auf und initialisiert es in der TO-for-Schleife.
n gleich 6.
Das macht auch Sinn, denn wir setzen es um die strlen von Klartext.
Also Ich mag an info Einheimischen oder Druck tun variable oft um sicherzustellen, dass
alles ist immer, was Ich erwarten, dass es gleich.
In diesem Fall ist alles was ich erwarten, dass es gleich.
>> Lassen Sie uns also auf Wanderschaft durch Diese for-Schleife.
Die Linie bin ich auf der Leitung 36 ist, wenn Klar Text i größer als ein und schlicht ist
text i kleiner als oder gleich z ist.
Ich weiß, mein Problem ist nicht mit meinem ersten Schreiben, ist es mit dem zweiten Buchstaben.
Wenn wir zurückblicken auf prüfen 50, geht B bis E in Ordnung.
Ich nehme das A und lasse sie als ein A, nicht auf D. Also veränderte sie
etwas ist falsch mit der zweite Buchstabe.
So werde ich zu bewegen in einer Sekunde.
>> Aber wenn ich wollte, was schlicht überprüfen Text, den ich in diesem speziellen erreicht
Fall denke ich, es sollte was sein?
Was soll ich gleich Klartext in dieser ersten Runde durch die for-Schleife?
>> STUDENT: Zero?
>> JASON HIRSCHHORN: Klartext von I?
So sollte es Kapital B. I, natürlich, gleich Null ist, sondern Klartext
Klammer Null geschlossenen Klammer gleich B Da Zeichenfolgen, wie wir letzte Woche gesehen haben,
Array sind, so dass wir immer den erste Zeichen von diesem.
Also noch einmal, wenn ich ausgedruckt Klartext Ich, ich glaube in der Tat, bekommen den Charakter
B. Und das ist ordentlich, oder?
Ich weiß nicht wirklich Klartext I. Das ist nicht eine der Variablen I
oder initialisiert, aber Sie drucken können aus einer ganzen Reihe von Dingen
wenn Sie zu möchten.
>> Aber lassen Sie uns durch zu bewegen.
Wenn Klartext ich größer als A und ist Klartext ich weniger als oder gleich ist
Z, dass klar ist wahr, weil wir eine Kapital B. Ich werde laufen
einige Befehl auf sie.
Wir sahen, dass die Mathematik in der vergangenen Woche, so dass wir es für selbstverständlich, dass es funktioniert
rechts nach 50 Prüfen.
>> Diese geschweiften Klammern, die erste zeigte, dass ich verlassen, wenn die
Zustand, zeigte die zweite dass ich dem Verlassen der for-Schleife.
Und jetzt, wenn ich auf nächstes werden wir sehen, sind wir wieder bei der for-Schleife wieder.
Wir gehen durch die for-Schleife wieder.
Lassen Sie uns tatsächlich in die zweite Schritt Iteration der for-Schleife und Art
info Einheimischen.
>> Also haben wir in der zweiten Iteration sind der for-Schleife.
Ich gleich 1 ist, was wir erwarten.
N gleich 6, was wir erwarten.
Key gleich 3 ist, was wir erwarten.
Und Klartext, werden Sie sehen, entspricht EARFOO jetzt nicht mehr, weil BARFOO
in unserem letzten Iteration, war die B auf eine Kapital E. verändert Also wir sind
um das Problem zu begegnen, so dass diese ist, wohin wir gehen, um
tauchen ein in die Debugging.
Aber hat jemand irgendwelche Fragen haben, über das, was wir bisher getan?
Fantastic.
>> Also wir sind dabei, diese auszuführen, wenn Zustand, Klartextklasse I geschlossen
Klammer größer als A und Klartext ich weniger als oder gleich Z. Aber bevor
Ich gehe in das, weil das ist, wo Ich weiß, mein Fehler ist, möchte ich darauf hinweisen
Klartext aus der I. So lassen wir Druck heraus.
Es macht gleich die Zeichen A, so dass scheint so weit, ist alles schön und gut.
>> Also erwarte ich, dass diese Zeile pro meine Logik, diese Linie sollte wahr sein.
Es ist ein Großbuchstabe.
Aber wenn ich auf n, wir erkennen, dass diese Zeile, in der Tat, wurde nicht ausgeführt.
Ich sprang auf die else if.
Warum ist das passiert?
>> STUDENT: Denn Sie haben Ihren Zustand Klartext ist größer
als A, nicht gleich oder größer als.
>> JASON HIRSCHHORN: Also meine Klartext hatte ich I größer als a ist, nicht größer ist
oder gleich.
So klar, der Hauptstadt A nicht auslösen, wenn dieser Zustand, und wir haben
nicht in sie zu treten, und wir haben die notwendige Verschiebung nicht.
Das ist es also, eigentlich.
Ich dachte mir, meine Fehler.
Ich konnte in meiner Quelldatei zurück, ändern Sie es, und aktualisieren Sie es und
Überprüfen Sie laufen 50 wieder.
>> Aber wir werden sehen, nur für die Pädagogik willen, wenn ich weitermachen.
Der sonst, wenn nicht entweder ausführen, aber statt, was gleich ist der Befehl
das nicht ändern.
Es ist also überhaupt nicht verändert, und wenn ich drucken Klartext hier werden wir sehen, gehen
durch die for-Schleife nicht in der Tat, ändern, dass die zweite Zeichen überhaupt.
Es ist immer noch eine Kapital A.
>> Also noch einmal, testet haben wir unsere Fehler.
Wir haben erkannt, dass es gewisse Logik fehlt.
Und wir testet vor der Zeit vor tatsächlich ausgeführt, dass die Linie,
aber Sie würden bemerkt haben, hatten wir nur Weiter schlagen und springen auf diesen else if,
das bedeutet, dass, dass, wenn die Bedingung war nicht wahr.
Wir wussten nicht, in der Tat, erhalten das Ergebnis, das wir erwartet.
Also dann könnten wir aufgefordert worden, hatte wir nicht so scharfsinnig gewesen, zu sehen
dass, wenn Zustand und überprüfen, ob in der Tat, unsere Lage zu beurteilen, sollte
stimmt im aktuellen Kontext.
>> Das ist alles für dieses Programm zu debuggen.
Hat jemand Fragen?
Welche Befehl könnte ich schlagen, um GDB aufhören?
Frage: Und dann werde ich aufgefordert, beenden haupt?
Ja oder nein.
Ich werde berührt ja, und ich werde GDB beendet haben.
>> So, dass war eine schnelle Grundierung auf GDB.
Eigentlich in einem realen Szenario Ich tat dies bei Bürozeiten.
Ich GDBed genau dieses Programm Bürozeiten mit einem Schüler.
Und wenn wir gehen zurück auf die Befehle, die wir sahen vor, haben wir Pause Haupt zuerst
was wir taten.
Wir verwendeten Lauf mit Kommandozeilen-Argumente, zweite, was wir getan haben.
Wir haben neben viel zu bewegen uns durch die Leitungen.
Und wieder, die kurze Version der nächsten n ist.
Das ist in den Klammern in grau auf der Folie.
>> Wir haben nicht Schritt, aber wir haben nicht notwendigerweise müssen für diesen Fall.
Aber wir haben es in einem etwas später verwenden können heute, wenn wir debuggen, für
Beispiel binäre Suche, wenn binäre Suche in einem separaten genannt
Funktion, aber es gibt einige Fehler mit sich.
Wir werden in Schritt wollen der Aufruf von binären Suche und
tatsächlich debuggen.
Liste haben wir nicht genutzt, weil wir entweder einen guten Sinn für unseren Code, aber wenn ich
wollte, um ein Gefühl von dem, was ich Code Nähe war, konnte ich nur verwenden Liste.
>> Drucken wir verwendet, Info Einheimischen wir eingesetzt.
Weiter haben wir nicht brauchen, um in dieses verwenden Fall, weder haben wir verwenden müssen,
Verwendung zu deaktivieren, aber wir haben zu beenden.
Auch diese 10 Befehle, üben Sie sie.
Wenn Sie verstehen, diese 10 Befehle, sollten Sie für die Fehlersuche jede eingestellt werden
Problem mit GDB.
>> So sind wir über zu gehen, wieder auf die Kern der Abschnitt heute, geht über
diese Sortieren und Suchen Algorithmen.
Bevor wir das tun, wieder Fragen, Kommentare, Anliegen für GDB?
So wird jeder gehen, um zu verwenden GDB statt printf?
Also alle, für die ewige Rente willen, jeder ist ihr Kopf nickend Recht
nun, so werde ich Sie bei der Bürozeiten sehen und alle TFs werden Sie und sehen
sie sagen, zeigen Sie mir, wie Sie mit GDB, und du wirst in der Lage sein,
um ihnen zu zeigen, oder?
Art?
Vielleicht hoffnungsvoll.
Kühl.
>> So werden wir, um in Bewegung Sortieren und Suchen.
Du wirst sehen, ich habe eine Liste bereits sortiert für uns, aber das wird nicht
der Fall immer sein.
Also das Problem gesetzt Spezifikation für Problem drei gesetzt, Shorts haben Sie
dass Sie sehen können, und es tatsächlich fordert Sie auf, diese Shorts zu sehen.
Auch im Vortrag letzte Woche gingen wir viele dieser Algorithmen, also bin ich
nicht gehen, um Zeit in der Klasse verbringen werde über diese Algorithmen wieder oder Zeichnung
Bilder, wie dieser Algorithmen arbeiten.
Auch die Informationen, die Sie wieder sehen können Vortrag, oder dass die Informationen
ist hervorragend auf der Hose eingefangen für diese Recherchen, die alle
die verfügbar sind bei cs50.net.
>> Anstatt also, was wir zu zu tun ist, diese Programme zu schreiben.
Wir haben eine Richtung, ein mentales Modell, wie sie arbeiten, und so was werden wir
zu tun ist, kodieren sie für real.
Wir werden diese mentale Modell drehen, dass Bild, wenn man will, in der
eigentlichen Code.
Und wenn Sie ein wenig verwirrt oder waren verschwommen auf der mentalen Modell, ich total
zu verstehen.
>> Wir sind nicht wirklich nach springen, um Code auf Anhieb.
So, während diese Aufforderung in dieser Folie fragt Sie binäre Such kodieren, und
tatsächlich eine iterative Version binäre Suche, das erste, was ich
wünschen Sie wirklich tun müssen, ist schreiben einige Pseudocode.
So können Sie diese mentale Modell haben wie binäre Suche funktioniert.
Nehmen Sie ein Blatt Papier, wenn Sie ein leicht verfügbar ist, oder öffnen Sie ein
Text-Editor, und ich möchte alle zu schreiben.
Nehmen Sie vier Minuten, um das zu schreiben Pseudocode für binäre Suche.
>> Wieder denke über diese mentale Modell.
Ich werde kommen, um, wenn Sie Fragen haben, und wir können das Bild ziehen.
Aber zuerst, bevor wir beginnen Programmierung, Ich würde gerne schreiben, die
Pseudocode für binäre Such so, wenn wir tauchen, haben wir etwas Richtung wie
, wo wir fahren sollten.
>> STUDENT: Können wir davon ausgehen das Array von Werte, die wir erhalten, ist bereits sortiert?
>> JASON HIRSCHHORN: Also für binäre Such zu arbeiten - gute Frage - Sie
müssen in einer sortierten nehmen Array von Werten.
So nehme an, es wird funktionieren.
Wir kommen wieder auf diese Folie zu wechseln.
Sie werden in lila Funktion siehe Erklärung bool int binary_search
Wert, int-Werte, int n.
Dies sollte Ihnen bekannt vorkommen, wenn Sie habe bereits angesprochen oder bekommen Ihre
Hände schmutzig mit dem Problem-Set.
>> Aber das ist Ihre Funktion Erklärung.
Auch hier sollte nicht Sorgen machen müssen dass viel zu diesem Zeitpunkt.
Was ich wirklich möchte, dass Sie tun, ist vier Minuten binären Pseudo
zu suchen, und dann gehen wir über, dass als Gruppe.
Und ich werde kommen um.
Wenn Sie Fragen haben, zögern frei, um Ihre Hand zu heben.
>> Warum gehst du nicht mehr zwei Minuten dauern zu Ende zu den Pseudocode?
Ich weiß, das mag lächerlich erscheinen, dass wir so viel Zeit auf
etwas, das in nicht sogar tatsächlich C, aber besonders für diese mehr
anspruchsvollen Algorithmen und Problem Sätze, die wir haben, um herauszufinden,
ab Pseudo keine Sorgen über die Syntax, nur Gedanken über
die Logik, ist unglaublich hilfreich.
Und so, du bist nicht die Lösung zwei unglaublich schwierige Probleme auf einmal.
Sie sind nur die sich auf die Logik und dann bewegen Sie in die Syntax.
>> OK.
Beginnen wir gehen durch der Pseudocode.
Ich habe hier binär geschrieben, Suche Pseudocode.
Wir werden dies auf der Schreib an Bord zusammen.
Oder ich werde es schreiben, und Sie geben mir die Ansagen ich brauche.
Also kann mir jemand die erste geben Zeile des Pseudo Sie
schrieb für binäre Suche?
Ja, Annie?
>> STUDENT: Während die Länge des Liste ist größer als Null.
>> JASON HIRSCHHORN: Während Länge Liste der größer als Null ist.
Und wieder sehen wir einige C-suchen syntaktische Dinge hier.
Aber die meisten davon ist in englischer Sprache.
Hat jemand eine Linie, die sie gesetzt haben bevor diese in ihren Pseudo-Code?
>> STUDENT: Holen Sie sich eine Reihe sortierter Zahlen.
>> JASON HIRSCHHORN: Sie schrieb "bekommen eine Array von sortierten Zahlen. "Per die
Funktionsdeklaration, werden wir vorbei eine Anordnung von Nummern sortiert.
>> STUDENT: [unverständlich].
>> JASON HIRSCHHORN: Also werden wir das haben.
Aber ja, wenn wir nicht haben, dass wir müssten unser Angebot an sortieren
Zahlen, weil binäre Suche funktioniert nur auf sortierten Arrays.
So, während Länge der Liste gleich Null, ich bin werde in einigen geschweiften Klammern setzen
, um es sich ein wenig mehr wie C. Doch während, scheint auf eine Karte
while-Schleife, so dass in diesem, während Schleife, was brauchen wir, um
für binäre Suche zu tun?
>> Jemand, der mich nicht gegeben hat Antwort noch nicht, aber wer das geschrieben hat?
>> STUDENT: Gehen Sie auf die Mitte der Liste.
>> JASON HIRSCHHORN: Tom.
Zur Mitte der Liste.
Und die Anschlussfrage, was tun wir, wenn wir an die sind
Mitte der Liste?
>> STUDENT: Führen Sie eine Prüfung, ob das ist, die Zahl, die Sie suchen.
>> JASON HIRSCHHORN: Excellent.
Gehen Sie in der Mitte der Liste und überprüfen wenn unser Wert ist da -
fantastisch.
Hat jemand etwas anderes haben das war anders als das?
Das ist genau richtig.
>> Das erste, was wir tun, in binäre Suche ist an der Mitte der Liste zu gehen und
überprüfen, um zu sehen, ob unser Wert ist.
Also gehe ich davon aus, wenn unser Wert ist da, was sollen wir tun?
>> STUDENT: Wir kehren Null [unverständlich].
>> JASON HIRSCHHORN: Ja, wenn unsere Wert ist, fanden wir es.
So können wir etwas zu erzählen, aber dies Funktion definiert ist, wird der Benutzer sagen, wir
wir fanden es.
Wenn er nicht da ist, obwohl, das ist wo dies wird schwierig.
Also, wenn es nicht da ist, jemand anderen, der wurde am binäre Suche oder Arbeits
hat jetzt eine Idee, was tun wir?
>> STUDENT: Frage.
>> JASON HIRSCHHORN: Ja?
>> STUDENT: Ist das Array bereits sortiert?
>> JASON HIRSCHHORN: Ja, wir gehen davon aus, das Array bereits sortiert.
>> STUDENT: So, dann müssen Sie überprüfen, ob der Wert, den Sie sehen, ist größer als
der Wert, den Sie wollen, können Sie verschieben bis zur Mitte der anderen Hälfte.
>> JASON HIRSCHHORN: Also, wenn die Mitte des die Liste ist größer als das, was wir sind
suchen, dann tun wir was?
Wir bewegen uns wo?
>> STUDENT: Sie möchten sich zu bewegen die Hälfte der Liste mit
Zahlen niedriger.
>> JASON HIRSCHHORN: Also wir werden rufen, dass die linke.
Also, wenn Mitte größer ist, können wir suchen Die linke Hälfte der Liste.
Und dann suchen, was meine ich mit Suche?
>> STUDENT: [unverständlich].
>> JASON HIRSCHHORN: Wir gehen in der Mitte.
Wir dieses Ding tatsächlich zu wiederholen.
Wir gehen zurück durch unsere while-Schleife.
Ich werde Ihnen die letzte -
sonst, wenn weniger als das, was Mittel wir, was tun wir hier?
>> STUDENT: Gehen Sie nach rechts.
>> JASON HIRSCHHORN: Suche die richtige.
Das sieht gut aus, aber hat jemand alles, was wir können fehlen oder
alles andere, was Sie setzen in der Pseudo-Code?
Also das ist, was wir bisher haben.
Während die Länge der Liste größer ist als Null ist, werden wir gehen
auf der Mitte der Liste, und überprüfen, ob unser Wert ist.
>> Wenn die Mitte größer ist, werden wir Suche nach links, sonst, wenn die Mitte ist
weniger, wir gehen, um die richtige zu suchen.
So haben wir alle eine gewisse Vertrautheit mit hatte die Begriffe, die wir in der Informatik
und die Werkzeuge, die wir haben.
Aber du wirst schon merken, wir waren Sprechen in Englisch, aber wir fanden ein
Menge Dinge, die zur Karte an schien Werkzeuge, die wir in unserem Codierung Tool-Kit zu haben.
So auf Anhieb, wir sind nicht gehen, um noch wirklich zu codieren.
>> Was sehen wir hier, dass die Karten in Englisch auf, die Dinge können wir in C zu schreiben?
>> STUDENT: Während.
>> JASON HIRSCHHORN: Während.
Also das, während hier Karten auf, was?
>> STUDENT: Eine while-Schleife.
>> JASON HIRSCHHORN: Eine while-Schleife?
Wohl oder, allgemeiner, eine Schleife.
Wir wollen etwas über und über zu tun.
So werden wir, um eine Schleife zu codieren.
Und wir wissen bereits, weil wir getan haben dies ein paar Mal und wir
haben viele Beispiele gibt, wie eigentlich zu schreiben
dieser Index für eine Schleife.
Damit sollte recht einfach.
Wir sollten in der Lage zu bekommen, dass sein begann ziemlich schnell.
>> Was wir sonst noch hier zu sehen?
Welche anderen Strukturen Syntax, Dinge dass wir in C vertraut, wir tun
bereits einen Sinn für Based weg von den Worten, die wir verwendet?
Ja, Anna?
[Unverständlich]
nur ein Scherz.
Anna, nur zu.
>> STUDENT: Wenn und anderes.
>> JASON HIRSCHHORN: Wenn und andere - genau hier.
Also, was tun die aussehen?
>> STUDENT: Eine if else-Anweisung.
>> JASON HIRSCHHORN: Ja, Bedingungen, oder?
Also werden wir wohl brauchen, um schreiben einige Bedingungen.
Und wieder, wenn auch vielleicht verwirrend Zunächst müssen wir in der Regel einen Sinn, jetzt
, wie die Bedingungen und schreiben die Syntax für Bedingungen.
Und wenn wir das nicht tun, wir schauen das Syntax für Bedingungen, Ausschneiden und Einfügen
das, weil wir wissen, dass wir brauchen eine Bedingung hier.
Alle anderen Dinge, die wir sehen, dass auf der Karte Dinge könnten wir in C tun?
Ja, Aleha?
>> STUDENT: Dies könnte klar sein, nur um zu überprüfen, ob ein
Wert gleich etwas.
>> JASON HIRSCHHORN: So, wie wir überprüfen und - so gehen Sie auf die Mitte der Liste
und prüfen, ob unser Wert ist?
Wie machen wir das in C?
Was ist die Syntax für das?
>> STUDENT: Gleich, gleich.
>> JASON HIRSCHHORN: Gleich, gleich.
Also diese Prüfung ist wahrscheinlich um ein Gleichheits sein, entspricht.
Also werden wir wissen, wir müssen, dass irgendwo.
Und tatsächlich, gerade das Schreiben ist, wir sehen die anderen Dinge.
Wir werden einige tun zu haben, Vergleichsoperatoren in da -
fantastisch.
So ist es tatsächlich aussieht, und durch groß, haben wir nicht eine schriftliche
Wort der C-Code noch.
Aber wir die mentale Modell machte sich über Vorträge und diesen Shorts.
>> Wir schrieben Pseudo-Code als Gruppe.
Und schon haben wir 80%, wenn nicht 90% von dem, was wir tun müssen.
Jetzt müssen wir nur noch codieren es ist wieder welche ein
nicht-triviales Problem zu lösen.
Aber zumindest sind wir auf der Logik fest.
Spätestens jetzt, wenn wir zu Bürozeiten, Ich kann sagen, ich weiß, was ich brauche
zu tun, aber kann Sie daran erinnern, mich an die Syntax?
Oder auch wenn der Bürozeiten sind überfüllt, die Sie kann für die Syntax Google, sondern
als auf der Logik fest.
>> Und wieder, anstatt zu versuchen, zu lösen die Logik und die Syntaxprobleme alle
gleichzeitig ist es oft viel besser, brechen diese beiden Fest Probleme ab in
zwei mehr überschaubar Einsen und tun das Pseudo-Code und dann in C-Code
Also mal sehen, was ich tat, für die Pseudo-Code vor der Zeit.
>> Während die Länge der Liste größer ist als Null ist, in der Mitte aus
auf der Liste.
Ist die Nummer gefunden wahr, anderes zurück wenn die Zahl höher, Suche links.
Else, wenn die Zahl niedriger, Suche rechts, return false.
Damit sieht fast identisch, wenn nicht nahezu identisch zu dem, was wir geschrieben haben.
Eigentlich, Tom, was Sie zuerst gesagt, Brechen der Mitte der Liste, und wenn
Nummer in zwei Erklärungen gefunden ist eigentlich das, was ich getan habe.
>> Ich kombinierte sie dort.
Ich sollte abgehörte Sie das erste Mal.
Das ist also die Pseudo-Code, den wir haben.
Wenn Sie wollen jetzt, sorry, gehen Zurück zu unserem Ausgangsproblem.
Lassen Code binary.c.
So implementieren eine iterative Version binäre Suche mit dem folgenden
Funktionsdeklaration.
>> Und Sie brauchen nicht zu kopieren es ist nur noch nach unten.
Ich bin tatsächlich zu öffnen bis hier binary.c.
So gibt es die Funktion Erklärung in der Mitte des Bildschirms.
Und Sie werden sehen, ich nahm das Pseudo-Code aus auf meinen Seiten, aber fast identisch
zu dem, was wir geschrieben, und umsetzen, die in für Sie.
So, jetzt nehmen wir mal 5 Minuten , um diese Funktion zu codieren.
>> Und wieder, wenn Sie irgendwelche Fragen haben, heben Sie Ihre Hand, lassen Sie mich wissen, ich werde
kommen um.
>> STUDENT: [unverständlich].
>> JASON HIRSCHHORN: Also nahm ich den binären Suche Definition auf die
Oben, auf der Linie 12.
Das ist, was ich für meinen Schlitten bekommen.
Und dann all diese Pseudo-Code, den ich gerade kopieren und von der Folie eingefügt,
Pseudo-Code-Folie.
Ich bin immer noch nicht hören [unverständlich].
>> Also, wenn Sie fertig sind Ihre Umsetzung, ich will es zu überprüfen.
Ich mailte Sie die Datei helpers.h früher in dieser Klasse.
Und es wird auch online verfügbar sein zum Download für Leute zu beobachten
dieser Abschnitt Zeit verzögert.
Und ich nutzte die allgemeine Verteilung Code aus pset3.
Also nahm ich find.C, meine helpers.h Datei anstatt die Datei helpers.h
das ist in der Distribution Code.
>> Und ich musste eine andere Änderung in machen find.C anstatt einfach nur telefonieren
Suche, rufen binary_search.
Also, wenn Sie Ihren Code testen möchten, wissen, dass das ist, wie es zu tun.
In der Tat, wenn wir diesen Code ausgeführt werden gerade jetzt, ich habe gerade eine Kopie gemacht
meine pset3 Verzeichnis wieder ausgelagert die Helfer Dateien und machte dann, dass
ändern in find.C zu nennen binary_search anstatt einfach nur suchen.
>> JASON HIRSCHHORN: Ja.
Sie haben eine Frage?
>> STUDENT: Nevermind.
>> JASON HIRSCHHORN: Keine Sorge.
Nun, lasst uns loslegen.
Wir werden dies als Gruppe zu codieren.
Ein weiterer Hinweis.
Auch dies ist, kann leicht ausgetauscht werden für Problem-Set Drei.
Ich habe meine helpers.h Datei, die, eher als der helpers.h wir gegeben,
erklärt binäre Suche, Blase Art und Auswahl sortieren.
Und in find.c werden Sie auf der Linie bemerken, was ist das, Zeile 68, nennen wir binäre
zu suchen, anstatt Suche.
Also noch einmal, der Code, die verfügbar ist Online oder dem Code, den Sie
jetzt Erstellung kann leicht ausgetauscht werden für p 3 bis es zu überprüfen.
>> Aber zunächst wollen wir Code binäre Suche.
Unsere Funktionsdeklaration, wir geben einen bool.
Wir nehmen eine ganze Zahl genannt Wert.
Wir nehmen eine Reihe von Zahlen genannt Werte, und wir nehmen n sein
die Größe des Arrays.
In Zeile 10, hier habe ich scharf sind stdbool.h.
Weiß jemand, warum das so ist da?
Also, was bedeutet, dass Codezeile tun?
>> STUDENT: Es ermöglicht Ihnen, verwenden Sie ein Rückgabetyp bool.
>> JASON HIRSCHHORN: Genau.
>> STUDENT: Oder es ist eine Bibliothek, die erlaubt einen bool Rückgabetyp verwenden.
>> JASON HIRSCHHORN: Also die sind scharf stdbool.h Linie gibt mir einige
Definitionen und Erklärungen für Dinge dass ich verwenden darf, in
Diese Bibliothek.
Also bei denen, sagt, dass es diese Art genannt bool, und es kann
wahr oder falsch.
Also das ist, was diese Linie nicht.
Und wenn ich nicht diese Linie, würde ich in Schwierigkeiten für das Schreiben dieses
Wort hier, bool, genau dort.
Genau richtig.
Also muss ich, dass in diesem Code.
OK.
So dass diese wiederum ist ein iterativer Version, nicht eine rekursive ein.
Also lassen Sie uns loslegen.
>> Lassen Sie uns mit diesem ersten Start Linie der Pseudo-Code.
Und hoffentlich werden wir - oder nicht hoffnungsvoll.
Wir gehen durch den Raum zu gehen.
Wir gehen durch die Linie Linie, und ich will helfen Sie herausfinden, die Linie, die wir brauchen
Zur ersten schreiben.
So, während Länge der Liste größer als Null ist.
Beginnen wir in der Front.
Welche Linie soll ich schreiben hier im Code?
>> STUDENT: Während Klammer n größer als 0 ist.
>> JASON HIRSCHHORN: Während n ist groß als 0 ist.
N so ist die Größe der Liste, und wir werden prüfen, ob -
>> [Zwischen VOICES]
>> JASON HIRSCHHORN: - sorry?
>> STUDENT: Woher wissen wir, dass n die Größe der Liste?
>> JASON HIRSCHHORN: Es tut uns leid.
Per pset der Spezifikation, die Suche und Funktionen sortieren Sie schreiben müssen,
n die Größe der Liste.
Ich habe vergessen, hier zu erklären.
Aber ja. n die Größe der die Liste, in diesem Fall.
Während also n größer als 0 ist.
OK.
Das kann ein bisschen problematisch erweisen aber, wenn es so weiter geht.
Da wir auch weiterhin wissen, dass die Größe der Liste in diesem
Funktion, sondern sagen, wir starten mit einer Reihe von 5 Zahlen.
Und wir gehen durch und wir haben Jetzt verengt sie sich
ein Array von 2 ganze Zahlen sind.
Welche zwei ganzen Zahlen ist das?
Die Größe ist 2 jetzt, dass wir wollen, betrachten, die aber 2 das ist?
Heißt das Sinn machen, diese Frage?
>> OK.
Ich werde es noch einmal fragen.
Also beginnen wir mit dieser Reihe 5 Zahlen und n gleich 5, oder?
Wir werden hier durchlaufen.
werden wir wahrscheinlich die Größe ändern, rechts, wie die Dinge weitergehen.
Welche ist das, was wir sagen, wir tun möchten.
Wir wollen nicht zu suchen die vollständige Sache wieder.
Also sagen wir es auf 2 ändern.
Wir nehmen die Hälfte der Liste, die ungerade ist.
So wählen Sie einfach 2.
So, jetzt n gleich 2 ist.
Ich entschuldige mich für die Armen Filzstifte.
Right?
Und wir sind in der Liste suchen wieder mit einer Liste der Größe 2.
Nun, das ist unser Angebot noch der Größe 5.
Wir sagen, wir wollen nur Suche 2 Spots in sie.
Also, was 2 Punkte sind das?
>> Heißt das Sinn?
Sind sie die links 2 Flecken?
Sind sie die richtigen zwei Flecken?
Sind sie die Mitte 2 Spots?
Wir haben das Problem kaputt, aber wir eigentlich nicht wissen, welcher Teil
das Problem, wir sind immer noch an, nur, indem er diese zwei Variablen.
Also brauchen wir ein wenig mehr dann, wobei n größer als 0 ist.
Wir müssen wissen, wo das n ist in unserer aktuellen Array.
>> Also hat jemand ein ändern, um dieser Linie?
Die meisten dieser Linie ist vollkommen richtig.
Gibt es einen anderen dazu?
Können wir tauschen etwas aus für n machen diese Linie ein bisschen besser?
Mm-hm?
>> STUDENT: Können Sie eine Variable initialisiert wie Länge n, die dann verwendet werden, werden
später in der Funktion?
>> JASON HIRSCHHORN: Also initialisieren eine variable Länge n,
und wir später benutzen?
Aber dann haben wir nur Länge, und wir aktualisieren noch in dieses Problem, wo wir
reduzieren die Länge unseres Problems, aber wir wissen nie, wo eigentlich
Länge, dass Karten auf.
>> STUDENT: Ist das nicht passieren wird später, wenn du sagst, Suche nach links,
Suche rechte?
Du wirst zu einem anderen gehen Bereich des -
>> JASON HIRSCHHORN: Wir gehen zu einem Bereich, aber wie wir wissen,
Welche sind zu gehen?
Wenn wir nur das Array und diese n, wie wir wissen, wo
gehen, um in der Anordnung.
In den Rücken, ja?
>> STUDENT: Sie haben, wie, eine niedrigere gebunden und eine obere Schranke Variable oder
so etwas?
>> JASON HIRSCHHORN: OK.
Also das ist eine andere Idee.
Anstatt nur die Verfolgung der Größe, verfolgen wir den unteren und
obere Grenze variabel.
Wie können wir also berechnen Sie die Größe aus eine untere Grenze und obere Grenze?
>> [Zwischen VOICES]
>> JASON HIRSCHHORN: Subtraktion.
Und auch die Verfolgung der unteren gebunden und Ober verpflichtet, uns zu informieren,
suchen wir diese beiden?
Suchen wir diese beiden hier?
Suchen wir die mittleren beiden?
Wahrscheinlich nicht, die beiden mittleren, weil dies in der Tat, ist binäre Suche.
Aber jetzt werden wir in der Lage, die Größe zu bekommen, aber auch die Grenzen des Arrays.
Im Wesentlichen, wenn wir unsere Riesen Telefonbuch, reißen wir sie in zwei Hälften.
Wir wissen jetzt, wo, dass kleinere Telefonbuch ist.
Aber wir sind nicht wirklich Ripping das Telefonbuch in der Hälfte.
Wir müssen noch wissen, wo der neue Grenzen unseres Problems ist.
Hat jemand irgendwelche Fragen haben, darüber?
Ja?
>> STUDENT: Wäre es durch die Schaffung einer Arbeits Variable, i, dass Sie nur dann verschieben
die Position der i bezogen auf ihre aktuelle Position und die Länge n?
>> JASON HIRSCHHORN: Und was ist, ich?
>> STUDENT: Wie ich zu sein wie Art -
Wie Sie initialisieren würde ich auf die sein mittlere Position des Arrays.
Und dann, wenn der Wert an der Position i in die Mitte des Arrays gefunden
kleiner sein als der Wert, den Sie benötigen, jetzt habe ich wird die Länge der Anordnung, und
der Wert von i durch 2 geteilt.
Wie, sehen, verschieben Sie i -
>> JASON HIRSCHHORN: Richtig.
>> STUDENT: - bis zu der -
>> JASON HIRSCHHORN: Also ich bin fast positiv, das wird funktionieren.
Aber der Punkt ist, müssen Sie zwei Stücke von Informationen hier.
Sie können es mit Anfang und Ende zu tun, oder Sie können es mit der Größe zu tun, und dann
einige Marker.
Aber Sie müssen zwei Stücke von Informationen hier.
Sie können nicht durch mit nur einem.
Ist das sinnvoll?
>> So werden wir zu durchlaufen, und wir tun werden [unverständlich]
und ein paar Markierungen.
So was hast du in den Code zu schreiben?
>> Student: Ich sagte nur int gebunden eine gleich 0 ist.
>> JASON HIRSCHHORN: Nennen wir int, dass, beginnend.
>> STUDENT: OK.
>> JASON HIRSCHHORN: Das macht mehr Sinn für mich.
Und?
>> STUDENT: Ich sagte, ich denke, int enden.
>> JASON HIRSCHHORN: int enden.
>> STUDENT: Ich denke, n minus 1, oder so ähnlich.
Wie, das letzte Element.
>> JASON HIRSCHHORN: Sie schrieb, int Anfang gleich 0, Semikolon, und int
Ende gleich n minus 1, Semikolon.
So im Wesentlichen, was wir tun Dabei bedeutet 0 die erste Position.
Und wie wir wissen, in Arrays, sie gehen nicht bis zu n, gehen sie bis zu n minus 1.
So haben wir einige Grenzen unser Angebot.
Und diese ersten Grenzen geschehen zu sein die ursprünglichen Grenzen der unser Problem.
OK.
Also, das klingt gut.
Dann, wenn wir wieder zu dieser Linie, während Länge der Liste ist größer als 0,
Was anstelle von n sollte wir hier setzen?
>> STUDENT: Schreiben endet minus Anfang.
>> JASON HIRSCHHORN: Während Ende minus Beginn größer als 0 ist?
OK.
Und wir könnten, wenn wir wollten machen, dass ein bisschen schöner, was
sonst könnten wir tun?
Wenn wir zu reinigen wollte dieser Code ein wenig?
Wie werde wir von der 0 zu befreien?
Dies ist nur eine Art Frage.
Es ist richtig, gerade jetzt.
>> STUDENT: Ende nicht gleich zu Beginn?
>> JASON HIRSCHHORN: Wir können tun, was?
>> [Zwischen VOICES]
>> STUDENT: Ending ist größer?
>> JASON HIRSCHHORN: Ja.
Wir können nur tun, während endet größer ist als zu Beginn.
Richtig.
Wir haben beginnend zur anderen Seite das, und wir haben von der 0 zu befreien.
Also das sieht einfach nur ein wenig sauberer.
OK.
Also, während Länge der Liste ist 0, schrieben wir dass, während die Endung ist größer
als am Anfang.
Wir werden in unserem notwendig setzen geschweiften Klammern, und dann das erste, was
wir tun wollen, ist Blick auf sie in eine kleine Liste.
Sie?
Können Sie mir das -
>> STUDENT: Wenn Klammer Wert eckige Klammer -
>> JASON HIRSCHHORN: Wenn Klammern Wert eckige Klammer.
>> STUDENT: Ending durch 2 geteilt.
>> JASON HIRSCHHORN: Ending?
>> STUDENT: Ich sehe ein Problem mit Ihrem -
>> JASON HIRSCHHORN: OK.
Nun, schauen Sie in der Mitte.
Wie können wir wissen, was die Mitte ist?
Ja.
Also lassen Sie mich diesen Code löschen.
Wie können wir wissen, was die Mitte ist?
In nichts, wenn Sie den Anfang haben und das Ende, wie finden Sie
die Mitte?
>> STUDENT: Sie durchschnittlich.
>> STUDENT: Sie fügen sie zusammen und dann -
>> JASON HIRSCHHORN: Fügen Sie sie zusammen und dann?
>> STUDENT: Und Sie durchschnittlich.
Teilen sie durch zwei.
>> JASON HIRSCHHORN: Fügen Sie sie zusammen und durch 2 teilen.
So int Mitte gleich?
Tom, können Sie es mir geben?
>> STUDENT: Ab und Ende -
>> JASON HIRSCHHORN: Beginn Plus enden.
>> STUDENT: Alle, Halter, geteilt durch zwei.
>> JASON HIRSCHHORN: Alle in Klammern durch 2 geteilt.
Also das gibt mir die Mitte nichts, richtig?
>> STUDENT: Sie müssen auch sie aufrunden.
>> JASON HIRSCHHORN: Was tun Sie meine, ich muss es aufrunden?
>> [Zwischen VOICES]
>> STUDENT: denn wenn es eine ungerade Nummer, dann ist es wie -
>> JASON HIRSCHHORN: Gut, OK.
So konnte ich es abzurunden.
Aber wenn es eine ungerade Zahl, eine 5, kann ich wobei 1 weg von der Mitte.
Oder wenn es eine gerade Zahl ist, und nicht, das ist ein Fall besser.
Wenn es 4, wir haben nur 4, kann ich nehmen die erste "Mitte", zitat, oder unquote
die zweite "Mitte" ein.
Entweder würde für eine binäre Suche funktioniert, so dass ich nicht wirklich brauchen, um es zu runden.
Aber es ist eine andere Sache, die ich müssen auf dieser Linie zu suchen.
Wir können nicht erkennen, es noch nicht, aber wir werden darauf zurückkommen.
Da diese Linie tatsächlich noch muss eine andere Sache.
>> Aber so weit, die wir geschrieben haben vier Zeilen Code.
Wir haben unsere Anfang bekam und endet Marker.
Wir haben unsere while-Schleife, die Karten direkt an unsere Pseudocode.
Wir sind in der Mitte, die Karten schauen direkt auf unsere Pseudocode.
Ich würde sagen, das geht bis in die Mitte der Liste, diese Codezeile.
Und dann, wenn wir nach der Mitte die Liste, das nächste, was wir tun müssen,
ist zu überprüfen, ob unsere Wert gibt es für der Pseudocode schrieben wir früher.
>> So, wie wir überprüfen, ob unsere Wert ist in der Mitte der Liste?
Sie.
Warum gehst du nicht dies zu tun?
>> STUDENT: Wenn unser Wert ist in der Mitte ist gleich
was wir durch die -
Ich meine, gleich gleich -
>> JASON HIRSCHHORN: Es -
OK.
>> STUDENT: Ich bin mir nicht sicher, was die Variable, die wir schauen,
für ist jedoch, weil -
>> [Zwischen VOICES]
>> STUDENT: [unverständlich].
>> JASON HIRSCHHORN: Genau.
Per Funktionsdeklaration, wir sind auf der Suche nach einem Wert.
So sind wir auf der Suche nach einem Wert in einem Array von Werten.
So sind Sie genau richtig.
Sie werden tun, wenn offene paren Wert Halterung Mitte geschlossen Halterung Gleichen
entspricht Wert, und im Inneren was wollen wir tun?
Wenn unsere Wert da, was müssen wir tun?
>> [Zwischen VOICES]
>> STUDENT: Zurück Null.
>> JASON HIRSCHHORN: Zurück wahr.
>> STUDENT: Zurück wahr.
>> JASON HIRSCHHORN: Michael, was bedeutet diese Zeile tun?
>> STUDENT: [unverständlich] das Programm laufen seinen Lauf, und das Ende ist, und
Sie haben, was Sie tun müssen?
>> JASON HIRSCHHORN: Das Programm, oder was?
In diesem Fall?
>> STUDENT: Die Funktion.
>> JASON HIRSCHHORN: Die Funktion.
Und ja, in was auch immer genannt zurückkehren es und geben ihm den Wert, wahr.
Genau richtig.
Main.
Was ist der Rückgabetyp von Haupt-, Michael?
>> STUDENT: int, integer?
>> JASON HIRSCHHORN: int, genau.
Eine ganze Zahl.
Das war nur eine Frage, um sicherzustellen, Sie Jungs haben oben drauf gewesen.
Was bedeutet es in der Regel zurück, wenn alle Dinge gut funktionieren?
>> STUDENT: Null.
>> JASON HIRSCHHORN: Null.
Genau richtig.
>> STUDENT: Wenn dies nur true zurück, es gibt keine Informationen gegeben
darüber, was die -
Oh, das wird einfach nur sagen, dass Wert ist innerhalb des Arrays.
>> JASON HIRSCHHORN: Genau.
Dieses Programm ist nicht mit Informationen von wo genau der Wert ist.
Es ist nur zu sagen, ja, wir fanden , oder nein, haben wir nicht finden.
Also, wenn Nummer gefunden, return true.
Na ja, eigentlich haben wir nur getan, dass wirklich schnell mit, dass eine Zeile Code.
Also werde ich diese Zeile von Pseudocode zu bewegen.
>> STUDENT: Brauchen wir nicht um das Array zu ändern?
Es sollte Werte, nicht Wert sein, oder?
>> JASON HIRSCHHORN: Es tut uns leid.
Danke.
>> STUDENT: Ja.
>> JASON HIRSCHHORN: Diese Zeile sollten Werte sein.
Genau richtig.
OK.
Also haben wir in der Mitte-Liste sah.
Ist die Nummer gefunden return true.
Weiter auf unserer Pseudocode, wenn Mitte größer ist, links suchen.
So hatte ich in hier, wenn die Zahl höher, links suchen.
Konstantin, kann Ihnen mir diese Codezeile?
>> STUDENT: Wenn der Wert des mittleren -
>> JASON HIRSCHHORN: Also, wenn der Wert -
wenn offen paren Werte Halterung Mitte Klammer zu -
>> STUDENT: Ist kleiner als Wert?
>> JASON HIRSCHHORN: Ist weniger als.
>> STUDENT: Weniger als Wert.
>> JASON HIRSCHHORN: Wert.
Nun, eigentlich wollen Sie überprüfen, ob die Anzahl -
Entschuldigung.
Dies ist ein wenig verwirrend.
Aber sonst, wenn die Zahl in der Mitte-Liste ist länger.
>> STUDENT: Oh, OK.
>> JASON HIRSCHHORN: Ich werde das ändern.
Else, wenn Mitte höher ist, wir wollen, suchen links, OK?
Und was machen wir innen tun wenn diese Bedingung?
>> STUDENT: Kann ich eine kleine Änderung an die Bedingung, ändern Sie sonst, wenn?
>> JASON HIRSCHHORN: Else wäre, wenn?
OK.
So wird dieser Code ausführen etwa gleich.
Aber das schöne an mit if, else if, else if oder if, else if, else
bedeutet, dass nur einer von denen ist, werde überprüft werden, nicht alle drei von ihnen,
potenziell.
Und das macht es ein bisschen schöner auf dem Computer, ist
Ihr Programm.
>> So [? Konstantin,?]
Wir sind innerhalb dieser Linie, sonst, wenn Werte, Halterung Mitte Klammer zu
ist größer als der Wert.
Was müssen wir tun?
Wir müssen die links suchen.
Wie tun wir das?
Ich werde Ihnen einen Start zu geben.
>> Wir haben diese beiden Dinge genannt beginnt und endet.
Also, was muss geschehen, zu Beginn?
Wenn Sie den links neben dem Such wollen Liste, bekommen wir unsere aktuelle Anfang.
Was brauchen wir es zu tun?
>> STUDENT: Wir setzen den Anfang bis Mitte plus 1.
>> JASON HIRSCHHORN: Also, wenn wir Suche der linken Seite?
>> STUDENT: Sorry, Mitte minus -
so das Ende wäre Mitte minus 1 und Anfang -
>> JASON HIRSCHHORN: Und was passiert den Anfang?
>> STUDENT: Es bleibt gleich.
>> JASON HIRSCHHORN: Also die Bedeutung bleibt gleich.
Wenn wir die Suche im linken, wir sind mit dem gleichen Anfang -
genau richtig.
Und das Ende?
Es tut uns leid, was macht der gleich wieder beenden?
>> STUDENT: Mittel minus 1.
>> JASON HIRSCHHORN: Mittel minus 1.
Nun, warum minus 1, nicht nur Mitte?
>> STUDENT: Die Mitte ist von der Bild bereits, denn wir hatten
überprüft, dass es aus ist?
>> JASON HIRSCHHORN: Das ist genau richtig.
Die Mitte ist aus dem Bild heraus.
Wir haben bereits in der Mitte überprüft.
So wollen wir nicht "in der Mitte", Zitat unquote, weiterhin in der sein
Array, dass wir auf der Suche.
Also das ist fantastisch.
>> Else, wenn Werte Halterung Mitte größer als Wert endet Gleichen
Mitte minus 1.
Jeff, was ist mit diesem letzten Zeile?
>> STUDENT: Else.
Werte Mitte ist kleiner als der Wert?
>> JASON HIRSCHHORN: Wir werden du mir sonst was.
Also, wenn Sie mir nicht geben -
>> STUDENT: So dann beginnen würde Mitte plus 1 sein.
>> JASON HIRSCHHORN: Anfang Gleichen Mitte plus 1 wieder für die gleiche
Grund dafür, dass Constantine hat uns früher.
Und am Ende, die nicht gegeben hat, mir eine Codezeile noch?
Return false, Aleha, was wir hier schreiben?
>> STUDENT: Zurück falsch.
>> JASON HIRSCHHORN: Zurück falsch.
Und wir müssen das tun, denn wenn wir Sie finden es nicht, zu sagen, wir brauchen wir
fand es nicht.
Und wir sagten, wir werden zurückkehren ein bool, so haben wir auf jeden Fall zurückkehren
ein bool irgendwo.
>> Also lassen Sie diesen Code ausführen.
Ich bin eigentlich los, um -
so sind wir in der Klemme.
Wir werden unsere Fenster zu löschen.
Machen wir alle.
Wir fanden, es gibt einen Fehler.
Es gibt einen Fehler in Zeile 15, zu erwarten Semikolon am Ende der
Erklärung.
So was habe ich vergessen?
>> STUDENT: Semikolon.
>> JASON HIRSCHHORN: Semikolon bis hier.
Ich denke, dass Tom der Code war.
Also Tom, [unverständlich].
Nur ein Scherz.
Lassen Sie uns wissen Machen Sie das ganze noch einmal.
>> STUDENT: Was Dropbox-Verzeichnis sollten wir dafür sein?
>> JASON HIRSCHHORN: So kann man nur zuschauen für dieses Bit.
Aber noch einmal, wenn Sie diese bewegen wollte Code in Ihre pset3 Verzeichnis zu versuchen
es ist das, was ich getan habe.
Wenn Sie hier feststellen - sorry, gute Frage.
>> [? LS?]
Ich habe hier in der find.c Code von dieser Woche Distribution Code.
Ich habe helpers.h.
Ich habe eine Make-Datei, die ich eigentlich bearbeitet ein bisschen diese neuen einschließen
Dateien wir schreiben.
All dieses Codes zur Verfügung stehen, nicht die Verteilung Code, aber die neue
Machen Datei, wird die neue Datei helpers.h zum Download online zur Verfügung.
Auch hier sind also die Zusätze die wir haben.
>> So machen alle, pro dieser Linie, macht zu finden, Binär-, Blase Auswahl - Marken
alle drei und kompiliert in Diese Programmcode.
Also in der Regel, die wir nicht wollen , um direkt zum check50.
Wir wollen einige Tests auf unseren eigenen laufen.
Aber nur so können wir diese ein wenig zu beschleunigen, check50 2013 pset3.find passieren
in helpers.c-- mein schlecht.
>> Ich habe nicht, dass gerade jetzt.
Daher freuen wir uns tatsächlich zu führen Sie den Code für echt.
Usage.find /, wissen Sie, was das bedeutet?
>> STUDENT: Sie brauchen eine zweite Befehlszeile auf sie.
>> JASON HIRSCHHORN: Ich brauche eine zweite Kommandozeile.
Und gemäß der Spezifikation, muss ich zu geben, was wir suchen.
Also schauen wir uns für 42.
Wir werden es in sortierter zu halten, weil wir habe nicht eine Sortierfunktion geschrieben noch -
42, 43, 44.
>> Und Control D nicht das finden die Nadel im Heuhaufen.
Das ist schlecht.
Es ist definitiv da.
Versuchen wir etwas anderes.
Vielleicht ist es, weil ich am Anfang.
>> Lassen Sie uns 41, 42, 43.
Dort gehen wir.
Es fand.
Sagen wir es am Ende jetzt, nur so können wir gründlich sein -
40, 41, 42.
Nicht die Nadel.
So erwähnte ich diese früher.
Leider ist dies wusste, dass ich passieren würde.
>> Aber für pädagogische Zwecke, es ist gut, sie zu erforschen.
Es funktioniert nicht.
Aus irgendeinem Grund, sie nicht finden können.
Wir wissen, was da drin ist, aber wir finden es nicht.
Also eine Sache, die wir tun können, ist zu gehen durch GDB, um es zu finden, aber weiß jemand,
ohne durch GDB, haben einen Gefühl von wo wir vermasselt?
[? Madu? ?]
>> Student: Ich denke, es könnte, wenn sein Ende ist gleich zu Beginn, und es ist
nur ein Ein-Element-Liste.
Dann ist es einfach ignoriert, statt tatsächlich die Kontrolle es.
>> JASON HIRSCHHORN: Das ist genau richtig.
Wenn Ende gleich Anfang, wir tun noch ein Element in unserer Liste?
>> STUDENT: Ja.
>> JASON HIRSCHHORN: Ja, in der Tat, wir haben ein und nur ein Element.
Und das wird wahrscheinlich passieren, wenn, nach der Code, den wir getestet, wir sind an der
vor dem Heuhaufen oder zumin das Ende der Heuhaufen.
Das ist, wo Anfang und Ende ist gleich los
ein, mit binären Suche.
So in diesen beiden Fällen hat es nicht funktioniert, da endet war gleich zu Beginn.
>> Aber wenn Ende ist gleich zu Beginn, bedeutet das while-Schleife ausführen?
Er tut es nicht.
Und wir könnten überprüft haben dass wieder durch GDB.
Wie können wir dieses Problem beheben Code, weil wenn bei der Beendigung ist gleich
beginnen, wollen wir auch dieses while-Schleife zu laufen.
>> Also, was können wir fix in die Linie 18?
>> STUDENT: [unverständlich] ist größer oder gleich.
>> JASON HIRSCHHORN: Genau richtig.
Während Ende größer ist oder gleich zu Anfang.
So, jetzt stellen wir sicher, dazu kommen Ecke Fall am Ende.
Und mal sehen.
Laufen wir diese noch einmal.
>> Lassen Sie uns alle.
Auch hier werden Sie müssen nur folgen hier.
Finden Sie 41 dieser Zeit.
Nur halten sie konsistent.
>> Finden Sie 42.
Sagen wir es am Anfang -
42, 43, 44.
Wir fanden es.
So, dass war in der Tat die Änderung wir brauchten zu machen.
>> Das war eine Menge von Codierungs wir gerade tat, binäre Suche.
Hat jemand irgendwelche Fragen haben, bevor Ich bewege mich auf in Zeilen schrieb, die wir in
binäre Suche oder wie wir dachten Sie heraus, was wir haben, herauszufinden?
Bevor wir fortfahren, möchte ich auch darauf hinweisen darauf hin, dass im Großen und Ganzen haben wir abgebildet
unsere Pseudo-Code ein, um ein auf unseren Code.
>> Wir haben haben, dass heikle Sache , mit der heraus
beginnt und endet.
Aber hatte man nicht gedacht, dass sich, Sie würde ziemlich viel geschrieben haben, die
identischen Code, außer für die beiden oberen Zeilen.
Und dann würden Sie realisiert, wenn können Sie es in Kontrollen und Fälle, dass
Sie brauchen etwas anderes.
Also selbst wenn Sie gefolgt war unsere Pseudo-Code-Zeile zu Zeile, die Sie haben möchten
bekommen alle außer zwei Zeilen Code zu schreiben benötigt.
>> Und ich wäre bereit zu wetten, dass Sie Jungs würden alle herausgefunden haben, dass sich
ziemlich schnell, die Sie benötigt zu setzen eine Art Marker in dort heraus
herauszufinden, wo Sie waren.
Das wiederum ist die Leistung zu tun Pseudo-Code vor der Zeit.
So können wir die Logik zuerst tun, und dann können wir über die Syntax zu kümmern.
>> Hätten wir über die Logik verwechselt worden bei dem Versuch, diesen Code in C zu schreiben,
wir bekommen haben, alle durcheinander.
Und dann würden wir Fragen über Logik und Syntax und Vernetzung
sie alle zusammen.
Und wir würden verlorenen bekommen haben in dem, was schnell zu einem
sehr schwieriges Problem.
Also machen wir weiter jetzt Auswahl sortieren.
>> Wir haben 20 Minuten.
So habe ich ein Gefühl, das wir nicht in der Lage zu sein, erhalten durch alle Auswahl Art
und Bubble-Sort.
Aber lassen Sie uns wenigstens versuchen Auswahl Art zu beenden.
So implementieren Auswahl Sortierung mittels der folgende Funktionsdeklaration.
>> Auch dies ist von der genommen Problem eingestellt Spezifikation.
Int-Werte Klammern ist ein Array von ganzen Zahlen.
Und int.n ist die Größe des Arrays.
Auswahl Art wird um diese Anordnung zu sortieren.
>> Also nach unserer mentalen Modells der Auswahl Art, ziehen wir das -
ersten, durch die Liste gehen wir den ersten Zeit, finden die kleinste Zahl,
legte es am Anfang, finden die zweite kleinste Zahl, steckte es in die
zweite Position, wenn wir wollen aufsteigend sortiert.
Ich sage nicht, Sie zu zwingen, zu schreiben Pseudo-Code jetzt.
>> Aber bevor wir den Code zu tun, wie eine Klasse in fünf Minuten werden wir schreiben
Pseudo-Code, so dass wir ein Gefühl wo wir gehen.
So versuchen, Pseudocode schreiben auf eigene Faust.
Und dann versuchen, dass drehen Pseudo-Code in Code.
Das werden wir als Gruppe tun in fünf Minuten.
>> Und natürlich, lassen Sie mich wissen, wenn Sie Fragen haben.
>> STUDENT: Dass es?
>> JASON HIRSCHHORN: Sehen Sie, wie weit Sie kann in zwei Minuten zu bekommen.
Ich verstehe, Sie werden nicht der Lage sein, zu beenden.
Aber wir werden über diese als Gruppe zu gehen.
>> Sie sind alle so Codierung [unverständlich], also bin ich Entschuldigung anzuhalten, was du tust.
Aber lassen Sie uns durch diese gehen als Gruppe.
Und wieder, binäre Suche, geben Sie alle mir eine, wenn nicht mehr Codezeilen.
Vielen Dank dafür.
Wir werden das gleiche tun hier, Code als Gruppe zusammen.
>> Also Auswahl sortieren - schreiben wir einige schnelle Pseudo-Code.
Per mentales Modell, kann mir jemand die erste Zeile der Pseudo-Code, bitte?
Was will ich tun?
>> STUDENT: Während die Liste nicht in Ordnung ist.
>> JASON HIRSCHHORN: OK, während die Liste ist nicht in Ordnung.
Und was meinen Sie mit "in Ordnung?"
>> STUDENT: Während [unverständlich]
wurde nicht sortiert.
>> JASON HIRSCHHORN: Während die Liste nicht in Ordnung ist, was tun wir?
Gib mir die zweite Linie, Bitte Marcus.
>> STUDENT: So finden Sie den nächsten kleinste Zahl.
Dieser wird eingerückt.
>> JASON HIRSCHHORN: So finden Sie die nächste kleinste Zahl.
Und dann hat jemand anderes?
Einmal finden wir die nächste kleinste Nummer, was tun wir?
Ich werde sagen, finden die kleinste Zahl.
Das ist, was wir tun wollen.
>> So finden Sie die kleinste Zahl.
Und was tun wir?
>> STUDENT: [unverständlich], um Anfang.
>> JASON HIRSCHHORN: Es tut uns leid?
>> STUDENT: Legen Sie es in die Anfang der Liste.
>> JASON HIRSCHHORN: Also legen Sie sie in der Anfang der Liste.
Und was tun wir, um die Sache das war am Anfang
der Liste, oder?
Wir sind etwas zu überschreiben.
Also, wo setzen wir das?
Ja, Anna?
>> STUDENT: Wo der kleinste Zahl war?
>> JASON Hirshhorn: So setzen Sie den Anfang der Liste, in der
kleinste Zahl war.
Während also die Liste nicht in Ordnung ist, finden die kleinste Zahl, legen Sie sie in
der Anfang der Liste, legte der Anfang der Liste, wo die
kleinste Zahl war.
Marcus, können Sie diese Zeile anders formulieren während die Liste nicht in Ordnung ist?
>> STUDENT: Während die Zahl wurden nicht sortiert?
>> JASON Hirshhorn: OK, also um , dass die Zahlen nicht
sortiert, was müssen wir tun?
Wie viel brauchen wir, um gehen durch diese Liste?
>> STUDENT: Also ich denke, eine for-Schleife, oder während weniger ist, während Zahlen geprüft
als die Länge der Liste?
>> JASON Hirshhorn: OK, das ist gut.
Ich glaube, ich misphrased meine Frage schlecht.
Ich habe nur versucht, zu erhalten wir gehen zu müssen, gehen
durch die ganze Liste.
So, während die Liste ist nicht in Ordnung, ist für mich schwer zu Karte auf.
Aber im Grunde ist das, wie Ich denke darüber nach.
Gehen Sie durch die gesamte Liste, finden die kleinste Zahl, legen Sie sie in die
Anfang - eigentlich, du hast Recht.
Sagen wir sie beide.
>> So, während die Liste ist nicht in Ordnung, wir brauchen, um durch die gesamte Liste gehen
einmal die kleinste Zahl, Ort finden es am Anfang der Liste setzen
der Anfang der Liste, in der kleinste Zahl war, und dann, wenn der
Liste ist immer noch nicht in Ordnung, wir haben bekam durch diese gehen
Prozess wieder, oder?
Das ist, warum Auswahl Art, Big-O-Laufzeit Auswahl von Art, anyone?
>> STUDENT: n quadriert.
>> JASON Hirshhorn: n quadriert.
Denn wie Marcus und ich erkannte, hier, wir gehen zu müssen
gehen Sie durch die Liste Liste Mal.
So gehen durch etwas Länge n n-mal
ist in der Tat n quadriert.
>> Das ist also unsere Pseudocode.
Das sieht sehr gut aus.
Hat jemand irgendwelche Fragen haben, über den Pseudocode?
Denn eigentlich sollte Auswahl sortieren wahrscheinlich kommen eins zu eins, Code aus
Pseudocode.
Also Fragen über die Logik des Pseudo?
Bitte fragen Sie es jetzt.
>> Auswahl Art - während die Liste ist aus der Ordnung, werden wir durch sie gehen
und finden Sie die jeweils kleinste und legen Sie sie in der Front.
Während also die Liste nicht in Ordnung ist, kann jemand, dass die Codezeile, die mir
hat mich nicht eine Linie gegeben Code noch, bitte?
Es klingt wie ein was?
>> STUDENT: Das ist eine for-Schleife.
>> JASON Hirshhorn: Es klingt wie eine for-Schleife.
OK, kannst du mir die for-Schleife geben?
Für -
>> STUDENT: i gleich 0 ist.
>> JASON Hirshhorn: i oder -
was fehlt uns?
Was geht hier?
>> STUDENT: Int.
>> JASON Hirshhorn: Genau.
(Int i = 0; -
>> STUDENT: i <n; i + +).
>> JASON Hirshhorn: Nailed es, Jeff.
Wir sind durch die Liste gehen, oder?
Wir haben diesen Code zuvor gesehen.
Perfect.
Also lassen wir unsere geschweiften Klammern hier.
Ich werde einige setzen geschweiften Klammern hier.
>> So, während es ist 0, wir müssen gehen durch die gesamte Liste.
So ist jedes Mal, wenn wir durch die Liste, was wollen wir den Überblick zu behalten?
>> STUDENT: Wenn irgendwelche Swaps vorgenommen werden.
>> JASON Hirshhorn: Suche die kleinste Zahl.
Also sollten wir wohl im Auge behalten die kleinste Zahl, jeder Zeit.
So Linie kann ich tun, um Kurs zu halten der kleinste Zahl?
Aleha, wie kann ich halten Spur von etwas?
>> STUDENT: Starten Sie eine neue Variable.
>> JASON Hirshhorn: Starten Sie eine neue Variable.
Lassen Sie uns also eine Variable zu erstellen.
Welche Art?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
Nennen wir es das kleinste.
Und was bedeutet es, wenn gleich wir gerade erst anfangen?
Wir haben noch nicht durch die Liste noch weg.
Wir sind am ersten Teil der Liste das erste Mal durch.
Was bedeutet es gleich, die kleinste Zahl?
>> STUDENT: Werte i.
>> JASON Hirshhorn: Werte i.
Das klingt genau richtig, oder?
Die kleinste Zahl am Anfang ist, wo wir sind.
So, jetzt haben wir unsere kleinste, und wir brauchen , um durch die gesamte Liste zu gehen und
Vergleichen Sie diese kleinsten um alles andere.
So haben wir durch die Liste wieder zu gehen?
Michael?
>> STUDENT: Sie müssen sicherstellen, ein anderer for-Schleife.
>> JASON Hirshhorn: Eine weitere for-Schleife.
Lass es uns tun.
Geben Sie mir einige Code.
>> STUDENT: For-Schleife -
für den kleinsten -
nur int j, könnte man sagen?
= 0, so daß -
>> JASON Hirshhorn: Nun, wenn wir wollen, , um durch die gesamte Liste zu gehen -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Wir werden durchlaufen die for-Schleife wieder.
Und wie finden wir die kleinste Zahl?
Tom?
Wir haben die aktuellen kleinste Zahl, so wie finden wir die neue kleinste?
>> STUDENT: Wir können prüfen, ob der kleinste Zahl, die wir haben, ist größer als
Werte Halterung j.
>> JASON Hirshhorn: Also, wenn kleinste ist Werte größer als Halterung j.
Also, wenn unsere aktuellen kleinste größer als -
Ich werde diese beiden Zeilen verschieben Code gibt, für eine Sekunde.
Denn bevor wir keinerlei Swapping, wir brauchen, um durch die gesamte Liste zu gehen.
Also das sollte eigentlich Pseudo sein, außerhalb dieses inneren for-Schleife.
So durch die gesamte Liste zu gehen.
Wenn kleinsten größer ist Werte j was dann?
>> STUDENT: Dann kleinste Werte gleich j.
>> JASON Hirshhorn: Fantastic.
Eine kurze Frage -
das erste Mal, dass wir durch diese Schleife zu gehen, i geht um gleich 0, ist j gehen
bis gleich null, wenn wir in hier.
So werden wir den Vergleich werden eine Anzahl an sich.
Ist das effizient?
Nein, es ist nicht wirklich effizient.
So sieht unsere j müssen gehen von 0 bis n jeweils?
Brauchen wir immer zu prüfen, durch die gesamte Liste?
[Unverständlich]?
>> STUDENT: Starten Sie mit i statt.
>> JASON Hirshhorn: j Dose beginnen mit was?
>> Student: Ich.
>> JASON Hirshhorn: j mit i beginnen.
So, jetzt vergleichen wir ab mit dem einen sind wir auf.
Aber selbst dann, ist, dass, effizient wie möglich?
>> STUDENT: i + 1.
>> JASON Hirshhorn: i + 1 zu sein scheint die effizienteste, weil wir
bereits i.
Wir sind die besagt, dass die kleinste in Zeile 15.
Wir werden mit dem Start nächste automatisch.
So gehen wir durch die for-Schleife.
Wir werden durch jede Zeit zu gehen.
Wir werden durch eine Reihe von mal zu gehen.
Jetzt haben wir durch bekommen haben diese innere for-Schleife.
Wir haben das kleinste Wert spart.
Wir müssen es an der Stelle, Anfang der Liste.
So, wie ich sie auch in die Anfang der Liste?
Was ist die Variable, bezieht an den Anfang der Liste?
Wir sind in dieser Außen for-Schleife so was bezieht sich auf die
Anfang der Liste?
>> STUDENT: Werte i.
>> JASON Hirshhorn: Genau richtig.
Werte i ist der Beginn des -
oder sorry, nicht der Anfang.
Das war verwirrend.
Es ist, wo wir am Anfang sind die unsortierten Teil der Liste.
Also i-Werte.
Und was tut das gleich?
>> STUDENT: Kleinste.
>> JASON Hirshhorn: Werte i gleich was?
>> STUDENT: Kleinste.
>> JASON Hirshhorn: Kleinste.
Genau richtig.
Daher freuen wir uns, sie in den Anfang der Liste, und jetzt müssen wir setzen
der Anfang der Liste, wo die kleinste Zahl war.
So, wie ich schreibe, wo die kleinste Zahl war?
Werte von was?
>> STUDENT: 0.
>> JASON Hirshhorn: Das kleine Nummer ist bei 0?
>> STUDENT: Ja.
>> JASON Hirshhorn: Was, wenn die kleinste Zahl betrug am Ende
diese unsortierten Liste?
>> STUDENT: Sorry, was war die Frage?
>> JASON Hirshhorn: Wo ist die kleinste Zahl?
Wir haben die kleinste und legte es auf die beginnen, mit dieser Linie hier richtig.
>> STUDENT: Es sollte wurde in einigen gespeichert -
>> STUDENT: Werte j.
>> JASON Hirshhorn: Nun, es ist nicht unbedingt Werte j.
Es ist nicht einmal an dieser Stelle existieren.
>> STUDENT: Sie müssen erklären, eine variable früher und
ordnen sie dann -
wenn Sie finden, die kleinste Zahl, weisen Sie den Index dieses Nummer
einige Variablen oder so ähnlich.
>> JASON Hirshhorn: So kann Sie sagen, dass wieder?
>> STUDENT: Also, wo Sie int deklariert kleinste, sollten Sie auch erklären int
kleinsten Index = i, oder so ähnlich.
>> JASON Hirshhorn: Also, wo ich int kleinste, ich sollte nicht nur Kurs zu halten
der Wert, sondern die Lage.
int = smallest_location in diesem Fall werden wir nur tun, ich.
Wir müssen wissen, wo es ist.
Wir haben das Ende des Codes, und wir erkannten wir hatten keine Ahnung, wo es war.
Und so wieder, Mapping sind wir Diese eins zu eins.
Ihr Jungs Codierung diese auf Ihrem eigenen Willen wahrscheinlich auf das gleiche Problem.
Wie zum Teufel kann ich ihn finden?
Und dann merkt man, warte, ich brauchen, um zu verfolgen, dass zu halten.
>> Also, wenn kleinste Wert größer ist als die Werte j.
Wir setzen kleinste gleich auf Werte j.
Was wir sonst noch zu ändern?
Constantin, was anderes zu tun müssen wir ändern?
>> STUDENT: Die Lage.
>> JASON Hirshhorn: Genau.
Also geben Sie mir diese Zeile im Code.
>> STUDENT: smallest_location = j.
>> JASON Hirshhorn: Genau.
Und dann unten am Ende, wenn wir wollen stellen den Anfang der Liste, wo
die kleinste Zahl war, wie wir verweisen, wo die
kleinste Zahl war?
Marcus?
>> STUDENT: Die kleinste Zahl war bei kleinsten Lage.
>> JASON Hirshhorn: Also bei Werten smallest_location.
Und was machen wir dort setzen?
Der Beginn der Liste, was ist das?
>> STUDENT: Nun, wir wissen nicht wirklich, mehr, weil wir überschrieb.
Es ist also ein ausgelagert Standorten dieser beiden Linien?
Wenn Sie diese beiden Linien wechseln sich um.
>> JASON Hirshhorn: OK, so dass wir nicht mehr, weil wir die Linie zurückgesetzt haben
bevor ich zum kleinsten Werte.
So verloren wir, dass Ausgangswert.
So sagte man Swap diese beiden Linien.
So, jetzt setzen Sie den Anfang der Liste wobei die kleinste Zahl war.
So smallest_location gleich Werte i.
Das bewegt sich der Beginn dieser unsortierten Teil der Liste, um die
kleinsten Lage.
Und dann in Werte i wir bewegen dass kleinste Zahl.
>> Macht das Sinn, warum wir musste diese Swap zu machen?
Wir würden diesen Wert überschrieben - eine andere Sache, haben Sie wahrscheinlich würde
herausgefunden und in BIP gefunden.
Also haben wir gesorgt all der Pseudocode.
Gibt es etwas, was wir brauchen, um hier zu schreiben?
Kann jemand an nichts denken?
>> STUDENT: Woher wissen Sie, wenn Sie fertig sind?
>> JASON Hirshhorn: Wie wollen wir wissen, wenn wir fertig sind?
Gute Frage.
So, wie wir wissen, wann wir fertig sind.
>> STUDENT: Erstellen Sie eine Variable, um Zahl halten der, wenn es eine Swap gemacht oder nicht
und durch einen Pass zu gehen.
>> JASON Hirshhorn: OK.
Das wäre in der Blase Art zu arbeiten.
Aber für die Auswahl zu sortieren, wenn wir nicht einen Swap, das könnte nur sein,
denn der kleinste Wert ist es in seiner rechten Lage.
Vielleicht haben wir eine Liste mit 1, 2, 4, 3.
Beim zweiten Durch wir werde keine Swaps.
Wir werden uns auf die Nummer 2 sein, aber wir werden noch brauchen, um weiterzumachen.
Also brauchen wir, um zu verfolgen, wenn zu halten wir fertig sind, oder wollen wir nur gehen
, bis dieser fertig ist?
>> STUDENT: Wir können einfach gehen bis es fertig ist.
>> JASON Hirshhorn: Wir können nur gehen, bis dieser fertig ist.
In Bubble-Sort, sind Sie genau richtig, Jeff und Aleha, mit Ihrer Lösung -
es ist großartig, um zu verfolgen, wie viele Swaps Sie gemacht, denn in der Luftblase
Art, wenn Sie in der Tat machen keine Swaps, Sie sind fertig, und Sie können vielleicht schneiden Sie Ihre
Problem ein wenig nach unten.
Aber für die Auswahl zu sortieren, haben Sie wirklich bekam bis zum Ende der go
Liste jedes Mal um.
>> Das ist also, dass.
Wir haben zwei Minuten.
Lassen Sie uns alle.
Lassen Sie mich nur offen Suche hier und machen sicher, ich bin in der Tat Aufruf -
Ich bin nicht fordern Bubble-Sort.
Lassen Sie uns, um die Auswahl zu ändern sind diese Art.
machen alle. / zu finden.
Lassen Sie uns 42.
Dieses Mal werden wir ein geben unsortierte Liste, denn es sollte zu sortieren
zuerst, pro Fund Code - sollte sortieren erste Verwendung unserer Sortierfunktion und dann
suchen Sie nach etwas.
Daumen drücken alle.
>> Ach du meine Güte.
Whoa, mein Herz schlug.
So, dass ist richtig.
In der Tat, wenn wir diese lief mehr ausgiebig, der Code, so weit wie ich kann
sagen, das ist vollkommen richtig.
Es gibt einige Vorschläge, Ich würde für Sie haben.
Zum Beispiel 15 und 16 scheinen ein wenig redundant.
Es scheint, wie Sie nicht unbedingt tun müssen sowohl solche zu speichern.
Wenn Sie den kleinsten Lage, haben Sie können ganz einfach die kleinsten Wert von
nur die Eingabe Werte von i.
>> Also wenn ich den Code Einstufung werden, welche ich in der Tat, ich würde
wahrscheinlich ausziehen, wenn Sie einen Punkt enthalten diese beiden, weil Sie
brauchen nicht beides.
Wenn Sie den Speicherort haben, können Sie sehr leicht den Wert.
Und es scheint ein wenig seltsam um beide zu speichern.
Vielleicht nicht einmal einen Punkt, aber sicherlich Kommentar, dass dies vielleicht
nicht eine stilistische Wahl Sie machen müssen.
Natürlich ist der Code noch läuft sehr gut.
>> Also leider haben wir nicht erhalten, Bubble-Sort.
Ich bin mir leid.
Wir haben Finish Auswahl sortieren.
Hat jemand irgendwelche Fragen haben, endgültig Auswahl zu sortieren?
>> OK, bevor wir den Kopf aus, ich will dich zu öffnen, Ihre Chrome-Browser.
Es tut uns leid, das war nur eine eklatante Stecker für eine Art von Internet-Browser.
Sie öffnen sich jegliche Art von Browser, aber es wird wahrscheinlich Chrome sein.
Und zu dieser folgenden Website -
sayat.me/cs50.
Wenn Sie nicht in Ihren Computer eingeben gerade jetzt, sind Sie deutlich
tun es nicht, Tom.
>> Und tun Sie es bitte entweder mit der rechten jetzt oder in der nächsten Stunde -
gib mir ein Feedback.
Dies ist nur Abschnitt zwei.
Wir haben viel mehr zusammen, so dass ich haben eine Menge Raum zu verbessern.
Ich hoffentlich auch haben einige Dinge gut.
So können Sie mich alles schlecht, aber wenn Sie wollen, dass ich einen Smiley zu geben
Gesicht, ich würde das auch zu schätzen wissen.
Füllen Sie, dass in.
>> Und noch eine Minute, Das war drei Wochen.
Ich werde für ein bisschen außerhalb stehen wenn Sie Fragen haben.
Ich werde euch in sehen Vortrag morgen.