>> [Παίζει μουσική]
>> ANDI PENG: Καλώς ήρθατε στην εβδομάδα 3 του τμήματος.
Ευχαριστώ, παιδιά, για τα οποία προέρχονται όλα σε αυτή την πρώτη ώρα έναρξης σήμερα.
Έχουμε ένα ωραίο, μικρό οικεία ομάδα σήμερα.
Έτσι, ελπίζουμε ότι θα φτάσουμε φινίρισμα, ίσως, από νωρίς,
λίγο νωρίς σήμερα.
Έτσι γρήγορα, μόλις μερικά Ανακοινώσεις για τη σημερινή ημερήσια διάταξη.
Πριν αρχίσουμε, είμαστε Θα πήγαινε πάνω
μερικές σύντομες οργανωτικών ζητημάτων, το chipset ερωτήσεις, debrief, τέτοια πράγματα.
Και τότε θα μπείτε στα βαθιά.
Θα χρησιμοποιήσουμε ένα πρόγραμμα εντοπισμού σφαλμάτων που ονομάζεται GDB να ξεκινήστε την απομυθοποίηση μας κώδικα, ο οποίος David
εξήγησε σε ομιλία την άλλη μέρα.
Θα πάω πάνω από τα τέσσερα είδη του είδους.
Θα πάμε πάνω τους αρκετά γρήγορα δεδομένου ότι είναι αρκετά εντατική.
Αλλά ξέρετε ότι όλες οι διαφάνειες και πηγαίος κώδικας είναι πάντα σε απευθείας σύνδεση.
Έτσι αισθάνονται ελεύθεροι, στο διάβασμα σας, για να πάει πίσω και να ρίξετε μια ματιά σε αυτό.
>> Θα περάσει ασυμπτωτική σημειογραφία, η οποία
είναι μόνο ένα φανταχτερό τρόπο του λέγοντας «runtimes,"
όπου έχουμε τη μεγάλη O, η οποία David εξήγησε στην ομιλία.
Και έχουμε επίσης Omega, η οποία είναι το κατώτερο όριο χρόνου εκτέλεσης.
Και θα μιλήσουμε λίγο περισσότερο σε βάθος σχετικά με το πώς αυτές οι εργασίες.
Και τέλος, θα πάμε πάνω από δυαδική αναζήτηση, επειδή πολλοί από εσάς που έχετε ήδη
Κοίταξα psets σας ίσως γνωρίζετε ότι ότι είναι μια ερώτηση που είναι στο PSET σας.
Έτσι όλοι θα είναι ευχαριστημένοι ότι έχουμε καλύψει αυτό σήμερα.
>> Και τέλος, ανά σας τμήμα σχολίων, εγώ πραγματικά
αριστερά περίπου 15 λεπτά σε το τέλος να φύγουμε πάνω
logistics της pset3, οποιεσδήποτε ερωτήσεις, ίσως ένα κομμάτι της καθοδήγησης, αν θέλετε,
πριν αρχίσουμε τον προγραμματισμό.
Οπότε ας προσπαθήσουμε να ξεπεράσουμε το υλικό αρκετά γρήγορα.
Και τότε μπορούμε να περάσουν λίγο χρόνο λαμβάνοντας περισσότερες ερωτήσεις για τον PSET.
ΕΝΤΆΞΕΙ.
>> Γρήγορα, έτσι ώστε μόλις λίγα ανακοινώσεις πριν αρχίσουμε σήμερα.
Πρώτον, καλώς να κάνει μέσω δύο psets σας.
Έριξα μια ματιά ναι, ας your-- πάρετε ένα χειροκρότημα για εκείνο το ένα.
Στην πραγματικότητα, ήμουν πραγματικά, πραγματικά εντυπωσιασμένος.
Θα βαθμολογούνται την πρώτη το chipset για σας παιδιά την περασμένη εβδομάδα και εσείς έκανε απίστευτο.
>> Στυλ ήταν στο σημείο εκτός από ορισμένες παρατηρήσεις.
Βεβαιωθείτε ότι είστε πάντα σχολιάζοντας τον κωδικό σας.
Αλλά psets σας ήταν στο σημείο.
Και να τον διατηρήσουμε.
Και αυτό είναι καλό για το γκρέιντερ να δείτε ότι εσείς βάζετε
σε τόση προσπάθεια στο στυλ σας και το σχεδιασμό σας τον κωδικό σας
ότι θα θέλαμε να δούμε.
Έτσι είμαι περνώντας κατά μήκος ευγνωμοσύνη μου για το υπόλοιπο της ΤΒ.
>> Ωστόσο, υπάρχουν μερικές ερωτήσεις debrief
Θέλω μόνο να πάει πέρα ​​από αυτό θα κάνουν τη ζωή μου τόσο
και πολλά από τα άλλα ΕΥ «ζει λίγο πιο εύκολη.
Πρώτον, έχω παρατηρήσει αυτό παρελθόν week-- πόσοι από εσάς
έχουν τρέξει σε check50 κωδικό σας, πριν να υποβάλετε;
ΕΝΤΆΞΕΙ.
Έτσι, ο καθένας θα πρέπει να κάνει check50, because-- μια secret-- στην πραγματικότητα
check50 τρέξει ως μέρος της ορθότητας μας σενάρια για δοκιμή τον κωδικό σας.
Έτσι, αν κωδικό σας αποτυγχάνει check50, κατά πάσα πιθανότητα,
πρόκειται πιθανώς να αποτυγχάνουν έλεγχο μας.
Μερικές φορές εσείς έχει τις σωστές απαντήσεις.
Όπως, στην άπληστοι, κάποια από έχετε το δικαίωμα αριθμούς,
μπορείτε απλά να εκτυπώσετε κάποια επιπλέον πράγματα.
Και ότι επιπλέον πράγματα αποτυγχάνει στην πραγματικότητα τον έλεγχο,
επειδή ο υπολογιστής δεν πραγματικά γνωρίζουν τι ψάχνει.
Και γι 'αυτό θα τρέξει μόνο μέσα, δείτε ότι η παραγωγή σας δεν
ταιριάζει με αυτό που περιμένουμε την απάντηση να είναι και το σήμα αυτό είναι λάθος.
>> Και ξέρω ότι συνέβη στο ορισμένες από τις υποθέσεις σας αυτή την εβδομάδα.
Έτσι πήγα πίσω και με το χέρι υποβαθμισμένα κωδικό του καθενός.
Στο μέλλον όμως, παρακαλώ, βεβαιωθείτε
ότι τρέχετε ελέγχει 50 σχετικά με τον κωδικό σας.
Επειδή είναι το είδος του πόνου για το ΕΠ να πρέπει να πάει πίσω και με το χέρι υποβαθμίσεως
κάθε PSET για κάθε ενιαία, λίγο έχασε παράδειγμα.
Γι 'αυτό και δεν είχε απογειωθεί πόντους.
Νομίζω ότι ίσως απογειώθηκε μία ή δύο για το σχεδιασμό.
Στο μέλλον όμως, αν είστε παραλείποντας check50,
Θα ληφθούν σημεία off για την ορθότητά τους.
>> Επιπλέον, είναι psets λόγω Παρασκευή το μεσημέρι.
Νομίζω ότι υπάρχει μια επτά λεπτά όψιμη περίοδο χάριτος που σας δίνουμε.
Ανά ώρα του Χάρβαρντ, από όπου και αν επιτρέπεται να είναι επτά λεπτά καθυστέρηση για τα πάντα.
Έτσι, εδώ στο Yale, θα τηρούν και αυτό.
Αλλά λίγο πολύ, στις 12:07, αν το chipset σας δεν είναι,
πρόκειται να σημανθεί ως αργά.
Και έτσι ενώ σημειώνεται τόσο αργά, η TA-- είμαι
ακόμα πρόκειται να ταξινόμησης psets σας.
Έτσι θα δείτε ακόμα ένα βαθμό φαίνεται.
Ωστόσο, γνωρίζουμε ότι σε το τέλος του εξαμήνου,
Όλα τα τέλη psets θα είναι ακριβώς μηδενίζεται αυτόματα από τον υπολογιστή.
>> Το κάνουμε αυτό για δύο λόγους.
Μία, μερικές φορές παίρνουμε συγγνώμη, σαν δικαιολογίες του κοσμήτορα,
αργότερα ότι δεν ξέρω ακόμα.
Έτσι θέλουμε να διασφαλίσουμε ότι είμαστε ταξινόμησης ό, τι ακριβώς σε περίπτωση, όπως, είμαι
Λείπει δικαιολογία ενός κοσμήτορα.
Και δεύτερον, να έχετε κατά μυαλό, μπορείτε ακόμα
Ρίξτε ένα PSET ότι έχει πλήρη σημεία πεδίο.
Και έτσι μας αρέσει να Βαθμός όλα psets σας μόνο
για να βεβαιωθείτε ότι το πεδίο εφαρμογής σας εκεί και εσείς που προσπαθούν.
Έτσι, ακόμα κι αν είναι αργά, θα εξακολουθούν να πάρει πίστωση για τα σημεία πεδίο, νομίζω.
>> Έτσι ηθικό δίδαγμα της ιστορίας είναι, να κάνει βεβαιωθείτε ότι psets σας είναι στο χρόνο.
Και αν δεν είναι μέσα σε χρόνο, Γνωρίζουμε ότι δεν είναι μεγάλη.
Ναι, πριν προχωρήσω, όμως κάποιοι έχουν οποιεσδήποτε ερωτήσεις σχετικά με το chipset ανατροφοδότηση;
Ναι.
>> Κοινό: Μήπως λέμε μπορεί να πέσει ένας από τους psets;
>> ANDI PENG: Ναι.
Έτσι υπάρχει psets εννέα συνολικά κατά τη διάρκεια του εξαμήνου.
Και αν έχετε πεδίου points-- έτσι το πεδίο εφαρμογής είναι απλά,
λίγο πολύ, είναι εσείς που προσπαθούν το πρόβλημα, βάζετε στο χρόνο,
σας δείχνουν ότι έχετε αποδεικνύεται έχετε διαβάσει το spec.
Αυτό είναι λίγο πολύ το πεδίο εφαρμογής.
Και αν πληρούν σημεία πεδίο, εμείς
μπορεί να μειωθεί το χαμηλότερο ένα από τα πλήρη έκταση.
Έτσι ώστε να είναι σε σας πλεονέκτημα να να συμπληρώσουν και να δοκιμάσετε κάθε PSET.
>> Ακόμη upload-- αν κανένα από τους εργασία, να φορτώσετε όλα αυτά.
Και τότε θα ελπίζω να είναι σε θέση να να σας δώσω μερικά από αυτά τα σημεία πίσω.
Cool.
Οποιεσδήποτε άλλες ερωτήσεις;
Εξαιρετική.
>> Δεύτερον, γραφείο hours-- μερικά γρήγορες σημειώσεις σχετικά με τις ώρες γραφείου.
Έτσι, πρώτα, να έρθει στις αρχές της εβδομάδας.
Κανείς δεν είναι ποτέ σε ώρες γραφείου Δευτέρα.
Christabel ήρθε για να ώρες γραφείου χθες το βράδυ.
Ναι, Christabel.
Και τι έχουμε στο γραφείο ώρες χθες το βράδυ, Christabel;
>> Κοινό: Είχαμε παγωτό.
>> ANDI PENG: Έτσι, αυτό είναι σωστό, είχαμε παγωτό σε ώρες γραφείου χθες το βράδυ.
Αν και δεν μπορώ να σας υποσχεθώ ότι θα έχουμε το παγωτό σε ώρες γραφείου
κάθε εβδομάδα, αυτό που μπορώ να σας υποσχεθώ είναι ότι θα υπάρξει μια σημαντική
την καλύτερη αναλογία μαθητών ΤΑ.
Όπως legit, είναι σαν τρία προς ένα.
Ότι, σε αντίθεση με ότι Πέμπτη, έχετε περίπου 150
τόνισε πραγματικά τα παιδιά και δεν το παγωτό.
Και δεν είναι μόνο παραγωγικοί για κανέναν.
Έτσι ηθικό δίδαγμα της ιστορίας είναι, να έρθει νωρίς σε ώρες γραφείου και καλά πράγματα
θα συμβεί.
>> Επίσης, έρχονται προετοιμασμένοι να κάνουν ερωτήσεις.
Ξέρεις?
Ανεξάρτητα από το τι βοηθούς, που νομίζω, έχουν πει,
έχουμε πάρει ένα ζευγάρι φοιτητών που έρχονται σε την Πέμπτη στις, όπως, 10:50
που δεν έχουν διαβάσει το spec είναι σαν να με βοηθήσει, να με βοηθήσει.
Δυστυχώς σε αυτό το σημείο, υπάρχει Δεν μπορούμε να κάνουμε πολλά για να σας βοηθήσουμε.
Επομένως, σας παρακαλώ να έρθει στις αρχές της εβδομάδας.
Ελάτε νωρίς για ώρες γραφείου.
Ελάτε προετοιμασμένοι να κάνετε ερωτήσεις.
Βεβαιωθείτε ότι εσείς, ως ένας φοιτητής, είναι όπου
θα πρέπει να είναι έτσι ώστε η ΤΒ μπορεί να σας καθοδηγήσει κατά μήκος,
η οποία είναι ό, τι ώρες γραφείου θα πρέπει να παραχωρηθεί για.
>> Δεύτερον, οπότε ξέρω καθηγητές ήθελα να μας εκπλήσσει με τις δοκιμές.
Είχα ένα καθηγητή εκείνες όπως, yo, από τον τρόπο,
να θυμάστε ότι η ενδιάμεση έχετε την ερχόμενη Δευτέρα.
Ναι, δεν ήξερα γι 'αυτό ενδιάμεση.
Έτσι, Πάω να είναι ότι το ΤΑ ώστε να υπενθυμίζει σε όλους ότι κουίζ
0-- γιατί, ξέρετε, είμαστε CS.
Τώρα που έχουμε κάνει συστοιχίες, μπορείτε να πάρετε Γι 'αυτό είναι κουίζ 0, δεν κουίζ 1, ε;
ΕΝΤΆΞΕΙ.
Ω, πήρα μερικά γέλια σε αυτό.
ΕΝΤΆΞΕΙ.
>> Έτσι κουίζ 0 θα είναι 14 Οκτωβρίου, αν και είστε στο τμήμα από Δευτέρα έως Τετάρτη
και της 15ης Οκτωβρίου, αν είστε σε το τμήμα Τρίτη έως Πέμπτη.
Αυτό δεν ισχύει για Όσοι από εσάς στο Χάρβαρντ
who-- Νομίζω ότι θα είναι όλοι τη λήψη κουίζ σας στην 14η.
>> Οπότε ναι, την επόμενη εβδομάδα, εάν Ο David, σε διάλεξη, πηγαίνει,
ναι, έτσι γι 'αυτό κουίζ την επόμενη εβδομάδα, όλοι σας
Δεν θα είναι σοκαρισμένος, διότι ήρθες στο τμήμα
και ξέρετε ότι σας κουίζ 0 είναι σε δύο εβδομάδες.
Και θα έχουμε κριτική συνεδρίες και τα πάντα.
Έτσι, υπάρχουν ανησυχίες σχετικά με να φοβάται για αυτό.
Οποιεσδήποτε ερωτήσεις before-- απορίες σε όλα τα θέματα σχετικά με την υλικοτεχνική,
ταξινόμησης, ώρες γραφείου, τμήματα;
Ναι.
>> Κοινό: Έτσι το κουίζ είναι θα είναι κατά τη διάρκεια της διάλεξης;
>> ANDI PENG: Ναι.
Έτσι το κουίζ, νομίζω, είναι 60 λεπτά που διαθέτω σε αυτό το χρονοθυρίδα
ότι θα πάρει μόνο στην αίθουσα διαλέξεων.
Έτσι, δεν χρειάζεται να έρθουν σε σχετικά, όπως, ένα τυχαίο 19:00.
Είναι όλα καλά.
Ναι.
Cool.
>> Εντάξει.
Έτσι θα πάμε να παρουσιάσω μια ιδέα για να σας
αυτή την εβδομάδα ότι ο David έχει ήδη το είδος των έθιξε στην ομιλία την περασμένη εβδομάδα.
Αυτό λέγεται GDB.
Και πόσοι από εσάς, ενώ σε η πορεία της γραφής psets σας,
έχουν παρατηρήσει ένα μεγάλο κουμπί που λέει "Debug" στην κορυφή του IDE σας;
ΕΝΤΆΞΕΙ.
Έτσι τώρα θα πάρει πραγματικά να ξεθάψει το μυστήριο του τι πραγματικά αυτό το κουμπί
κάνει.
Και σας εγγυώμαι, είναι ένα όμορφο, όμορφο πράγμα.
>> Έτσι, μέχρι τώρα, νομίζω έχει υπάρξει δύο πράγματα
οι μαθητές έχουν συνήθως κάνει όταν τον εντοπισμό σφαλμάτων psets.
Ένα, είτε να προσθέσετε στο printf () - έτσι ώστε κάθε λίγες γραμμές,
προσθέτουν στην printf () - Ω, τι είναι αυτή η μεταβλητή;
Ω, τι είναι αυτή η μεταβλητή now-- και κατά κάποιο τρόπο δείτε την εξέλιξη
του κωδικού σας, καθώς τρέχει.
Ή η δεύτερη μέθοδος είναι να κάνει παιδιά ότι το μόνο που γράφουν το όλο θέμα
και στη συνέχεια να πάμε σαν αυτό στο τέλος.
Ας ελπίσουμε ότι αυτό λειτουργεί.
Σας εγγυώμαι, GDB είναι καλύτερη τόσο από τις μεθόδους αυτές.
Ναι.
Έτσι, αυτό θα είναι ο καλύτερός σας φίλος.
Επειδή είναι ένα όμορφο πράγμα ότι οπτικά εμφανίζει δύο
τι κωδικός σας κάνει σε ένα συγκεκριμένο σημείο
καθώς και αυτό που όλοι σας Οι μεταβλητές που μεταφέρουν,
όπως ποιες είναι οι αξίες τους, σε εκείνο το συγκεκριμένο σημείο.
Και με αυτόν τον τρόπο, μπορείτε πραγματικά ορίσετε σημεία διακοπής στον κώδικά σας.
Μπορείτε να τρέχει μέσα από γραμμή προς γραμμή.
Και GDB θα πρέπει απλώς για σας, εμφανίζεται για εσάς,
ό, τι το σύνολο των μεταβλητών σας Οι, τι κάνουν,
τι συμβαίνει στον κώδικα.
Και με τέτοιο τρόπο, είναι τόσο πολύ ευκολότερο να δείτε
τι συμβαίνει αντί της printf-σης ή να γράψει κάτω τις δηλώσεις σας.
>> Έτσι θα κάνουμε ένα παράδειγμα για αυτό αργότερα.
Έτσι, αυτό φαίνεται λίγο αφηρημένη.
Μην ανησυχείτε, θα κάνουμε παραδείγματα.
Και έτσι, κατ 'ουσίαν, τα τρία μεγαλύτερα, πλέον χρησιμοποιούμενες λειτουργίες που θα χρειαστείτε στο GDB
είναι το επόμενο, βήμα πάνω, Βήμα και σε κουμπιά.
Πάω να το κεφάλι πάνω εκεί, στην πραγματικότητα, αυτή τη στιγμή.
>> Έτσι, μπορείτε να δείτε όλα τα παιδιά που ή θα πρέπει να κάνετε ζουμ σε ένα κομμάτι;
Στο πίσω μέρος, μπορείτε να δείτε αυτό;
Θα πρέπει να μεγεθύνετε;
Λιγάκι μόνο?
ΟΚ κομπλε.
Εκεί πάμε.
ΕΝΤΆΞΕΙ.
>> Έτσι έχω εδώ, μου εφαρμογή για άπληστοι.
Και ενώ πολλοί από εσάς παιδιά έγραψαν άπληστοι σε βρόχο, ενώ form-- ότι
είναι ένας απόλυτα αποδεκτός τρόπος για να κάνουμε it-- έναν άλλο τρόπο για να γίνει αυτό είναι να απλά
χωρίζουν το modulo.
Επειδή τότε μπορείτε να έχετε σας αξία και στη συνέχεια να έχουν υπόλοιπο σας.
Και τότε μπορείτε απλά προσθέστε όλα μαζί.
Μήπως η λογική του τι κάνω εδώ έχουν νόημα για όλους,
πριν ξεκινήσουμε;
Περίπου?
Cool.
Εξαιρετική.
Είναι μια αρκετά σέξι κομμάτι του κώδικα, θα έλεγα.
Όπως είπα, ο David, σε διάλεξη, μετά από λίγο,
θα αρχίσετε να βλέπετε όλες κωδικός ως κάτι που είναι όμορφο.
Και μερικές φορές όταν βλέπεις όμορφη κώδικα, είναι ένα τέτοιο θαυμάσιο συναίσθημα.
>> Έτσι όμως, ενώ αυτός ο κώδικας είναι πολύ όμορφη, δεν λειτουργεί σωστά.
Οπότε ας τρέξει check50 σε αυτό.
Ελέγξτε 20-- 50 oop.
2;
Είναι ότι pset2;
Ναι.
Ω, pset1.
ΕΝΤΆΞΕΙ.
Γι 'αυτό και τρέχει check50.
>> Και όπως εσείς μπορείτε να δείτε εδώ, είναι αδυναμία μερικές περιπτώσεις.
Και για κάποιους από εσάς, στην Φυσικά για να γίνει το πρόβλημα σετ,
είστε όπως, αχ, γιατί δεν είναι αυτό που εργάζονται.
Γιατί είναι αυτό που εργάζονται για ορισμένους τιμές, αλλά όχι για τους άλλους;
Λοιπόν, GDB θα βοηθήσει το σχήμα σας γιατί αυτές οι είσοδοι δεν εργάζονταν.
>> ΕΝΤΆΞΕΙ.
Ας δούμε λοιπόν, ένα από τα ελέγχους που απέτυχε σε check50
ήταν η τιμή εισόδου των 0,41.
Έτσι, η σωστή απάντηση που θα πρέπει να πάρει είναι 4.
Αλλά αντ 'αυτού τι είμαι εκτύπωση είναι η 3-Ν, η οποία είναι εσφαλμένη.
Έτσι, ας τρέξει αυτό με το χέρι, απλά βεβαιωθείτε ότι check50 λειτουργεί.
Ας κάνουμε ./greedy.
Ωχ, έχω να κάνω άπληστοι.
Εκεί πάμε.
Τώρα ./greedy.
>> Πόσο οφείλεται;
Ας κάνουμε 0,41.
Και Ναι, βλέπουμε εδώ ότι έχει την έξοδο 3
όταν η σωστή απάντηση, Στην πραγματικότητα, θα πρέπει να είναι 4.
Ας εισάγετε GDB και να δούμε πώς μπορούμε μπορούν να πάνε για τον καθορισμό αυτό το πρόβλημα.
>> Έτσι, το πρώτο βήμα debugging πάντα τον κωδικό σας
είναι να ορίσετε ένα σημείο διακοπής, ή ένα σημείο στο οποίο θα
θέλουν τον υπολογιστή ή το εντοπισμού σφαλμάτων για να αρχίσει κανείς να κοιτάζει.
Έτσι, αν δεν το κάνετε πραγματικά ξέρετε τι είναι το πρόβλημά σας,
Συνήθως, η τυπική πράγμα που θέλουμε να κάνετε είναι να ορίσετε breakpoint μας στο κεντρικό.
Έτσι, αν εσείς μπορείτε να δείτε αυτό το κόκκινο κουμπί εκεί,
Ναι, αυτό ήταν με μια ρύθμιση σημείου τύπου για την κύρια λειτουργία.
Κάνω κλικ αυτό.
>> Και τότε μπορώ να πάω μέχρι το κουμπί Debug μου.
Χτύπησα αυτό το κουμπί.
Επιτρέψτε μου να μεγεθύνετε αν μπορώ.
Εκεί πάμε.
Έτσι έχουμε, εδώ, ένα πάνελ στα δεξιά.
Λυπάμαι, παιδιά στο πίσω μέρος, που Δεν μπορεί πραγματικά να δει πολύ καλά.
Αλλά ουσιαστικά, όλα Αυτό το δικαίωμα πάνελ κάνει
παρακολουθεί με ιδιαίτερη προσοχή τόσο την επισημαίνονται γραμμή, η οποία είναι η γραμμή του κώδικα
ότι ο υπολογιστής λειτουργεί αυτή τη στιγμή, καθώς και το σύνολο των μεταβλητών σας
εδώ κάτω.
>> Έτσι έχετε σεντ, κέρματα, n, το σύνολο των δηλωθέντων με διαφορετικά πράγματα
σε αυτό το σημείο.
Μην ανησυχείτε, γιατί δεν έχουμε πραγματικότητα τους προετοιμαστεί για τυχόν μεταβλητές ακόμα.
Έτσι, στον υπολογιστή σας, σας υπολογιστή απλά να δει,
OH, 32767 ήταν η τελευταία φορά που χρησιμοποιήθηκε λειτουργία του εν λόγω χώρου μνήμης στον υπολογιστή μου.
Και έτσι αυτό είναι όπου είναι σήμερα σεντ.
Αλλά όχι ότι μόλις την εκτέλεση του κώδικα, θα πρέπει να γίνει προετοιμαστεί.
>> Ας πάμε μέσα, σύμφωνα με την γραμμή, τι συμβαίνει εδώ.
ΕΝΤΆΞΕΙ.
Έτσι, εδώ είναι οι τρεις κουμπιά που μόλις εξήγησα.
Έχετε το παιχνίδι, ή τη λειτουργία Run, κουμπί, έχετε το βήμα πάνω από το κουμπί,
και έχετε επίσης το βήμα σε κουμπί.
Και ουσιαστικά, και οι τρεις τους μόλις περάσουν τον κωδικό σας
και να κάνει διαφορετικά πράγματα.
>> Έτσι, συνήθως, όταν τον εντοπισμό σφαλμάτων, δεν θέλουμε να χτυπήσει απλά παίζουν,
Καθώς το παιχνίδι θα τρέξει μόνο κωδικό σας προς το τέλος της.
Και τότε δεν θα είναι πράγματι ξέρετε τι το πρόβλημά σας
είναι, εκτός εάν ορίσετε πολλαπλά σημεία διακοπής.
Εάν ορίσετε πολλαπλά σημεία διακοπής, Θα μόνο αυτόματα
τρέχει από το ένα σημείο διακοπής, στο επόμενο, στο επόμενο.
Αλλά σε αυτή την περίπτωση έχουμε ακριβώς αυτό, διότι εμείς
Θέλετε να εργαστείτε με τον τρόπο μας από πάνω προς τα κάτω προς τα κάτω.
Έτσι θα πάμε να αγνοήσει αυτό το κουμπί τώρα για τους σκοπούς του παρόντος προγράμματος.
>> Έτσι το βήμα πάνω από τη λειτουργία μόνο βήματα πάνω από κάθε γραμμή
και σας λέει τι ο υπολογιστής κάνει.
Το Βήμα σε λειτουργία πηγαίνει στην πραγματική λειτουργία
αυτό είναι για σας γραμμή κώδικα.
Έτσι, για παράδειγμα, όπως printf (), ότι είναι μια λειτουργία, σωστά;
Αν ήθελα να σωματικά βήμα σε με την printf (),
Θα ήθελα πραγματικά να πάμε στο κομμάτι της κώδικας όπου printf () γράφτηκε και δείτε
τι συμβαίνει εκεί.
>> Αλλά συνήθως, υποθέτουμε ότι ο κωδικός που σας δίνουμε λειτουργεί.
Έχουμε αναλάβει την printf () λειτουργεί.
Υποθέτουμε ότι GetInt () λειτουργεί.
Έτσι δεν υπάρχει καμία ανάγκη να βήμα σε αυτές τις λειτουργίες.
Αλλά αν υπάρχει λειτουργίες ότι εσείς οι ίδιοι γράφουν
ότι θέλετε να ελέγξετε τι συμβαίνει,
θα θέλατε να εντείνουν σε αυτή τη συνάρτηση.
>> Έτσι τώρα είμαστε ακριβώς πρόκειται στο βήμα πάνω από αυτό το κομμάτι του κώδικα.
Ας δούμε λοιπόν.
Ω, εκτύπωση, "Αχ hai, πώς πολλές αλλαγές οφείλεται; "
Εμείς δεν με νοιάζει.
Γνωρίζουμε ότι λειτουργεί, γι 'αυτό το βήμα πάνω του.
>> Έτσι, n, η οποία είναι float μας ότι έχουμε initialized-- ή declared--
στην κορυφή, είμαστε τώρα ισούται ότι για να GetFloat ().
Ας βήμα πέρα ​​από αυτό.
Και βλέπουμε κατά τη κάτω εδώ, το πρόγραμμα
είναι να μου ζητά να εισάγετε μια τιμή.
Ας είσοδο την τιμή που θέλουμε να δοκιμάσει εδώ, η οποία είναι 0,41.
Εξαιρετική.
>> Έτσι τώρα n-- κάνετε εσείς δείτε εδώ, στο bottom-- είναι
stored-- γιατί Δεν έχουν στρογγυλεμένες ακόμα, είναι
αποθηκεύονται σε αυτό σαν γίγαντας float που είναι 0,4099999996,
η οποία είναι αρκετά κοντά για να μας σκοπούς, αυτή τη στιγμή, στο 0,41.
Και τότε θα δούμε αργότερα, όπως να συνεχίσει την ενίσχυση πάνω από το πρόγραμμα,
μετά εδώ, n έχει γίνει στρογγυλεμένες και σεντς έχει γίνει 41.
Εξαιρετική.
Έτσι, γνωρίζουμε ότι στρογγυλοποίηση εργασίας μας.
Γνωρίζουμε ότι έχουμε το σωστό αριθμό των λεπτών,
έτσι ξέρουμε ότι αυτό είναι δεν είναι πραγματικά το πρόβλημα.
>> Έτσι, συνεχίζουμε την ενίσχυση σχετικά σε αυτό το πρόγραμμα.
Εμείς πάμε εδώ.
Και έτσι μετά από αυτή τη γραμμή του κώδικα, που Πρέπει να ξέρετε πόσα τρίμηνα έχουμε.
Εμείς βήμα πάνω.
Και βλέπετε το κάνουμε, στην πραγματικότητα, έχουν ένα τρίμηνο επειδή έχουμε αφαιρούνται 25
από την αρχική μας τιμή των 41.
Και έχουμε 16 σεντ το αριστερό για μας.
>> Μήπως όλοι καταλαβαίνουν πώς Το πρόγραμμα ενισχύει μέσω
και γιατί σεντ έχει γίνει πλέον 16 και γιατί, τώρα, έχει γίνει κέρματα 1;
Είναι όλοι μετά από αυτή τη λογική;
Cool.
Έτσι, από το σημείο αυτό, η εργασίας προγράμματος, έτσι δεν είναι;
Γνωρίζουμε ότι κάνει ακριβώς ό, τι θέλουμε να.
Και δεν το κάναμε πραγματικότητα πρέπει να εκτυπώσετε, ω, τι
Είναι σεντ σε αυτό το σημείο, τι είναι κέρματα σε αυτό το σημείο.
>> Συνεχίζουμε να περάσει από το πρόγραμμα.
Βήμα πάνω.
Cool.
Εμείς πάμε πάνω δεκάρες.
Εξαιρετική.
Βλέπουμε ότι έχει ληφθεί μακριά $ 0.10 για μια δεκάρα.
Και τώρα έχουμε δύο νομίσματα.
Αυτό είναι σωστό.
>> Εμείς πάμε πάνω από τις πένες και βλέπουμε ότι έχουμε απομείνει σεντ.
Χμμ, αυτό είναι περίεργο.
Μέχρι εδώ στο πρόγραμμα, θα έπρεπε να αφαιρείται πένες μου.
Ίσως εγώ απλά δεν ήταν κάνει αυτό το δικαίωμα γραμμή.
Και δυστυχώς, μπορείτε να δείτε εδώ, γιατί γνωρίζουμε
ότι πατάμε μέσω των γραμμών 32 και 33,
αυτό είναι όπου το πρόγραμμά μας εσφαλμένα είχε τρέξει μεταβλητές.
Έτσι, μπορούμε να εξετάσουμε και να δούμε, OH, Είμαι εδώ για την αφαίρεση σεντ,
αλλά δεν είμαι στην πραγματικότητα προσθέτοντας αξία νομίσματος μου.
Είμαι προσθέτοντας σεντ.
Και δεν θέλω να προσθέσετε σεντ, θέλω να προσθέσω τα κέρματα.
Έτσι, αν θέλουμε να αλλάξει αυτό με τα κέρματα, έχουμε ένα πρόγραμμα εργασίας.
Μπορώ να τρέξω check50.
Μπορείτε απλά να βγείτε έξω από GDB δικαιώματος εδώ και στη συνέχεια εκτελέστε ξανά check50.
Θα μπορούσα να κάνω ακριβώς αυτό.
Πρέπει να κάνω άπληστοι.
0.41.
Και εδώ, είναι εκτύπωση έξω η σωστή απάντηση.
>> Έτσι, όπως μπορείτε να δείτε παιδιά, GDB είναι ένα πραγματικά ισχυρό εργαλείο
όταν έχουμε τόσο πολύ κώδικα συμβαίνει και τόσες πολλές μεταβλητές
ότι είναι δύσκολο για εμάς, ως έναν άνθρωπο, για να παρακολουθείτε.
Ο υπολογιστής, στον GDB εντοπισμού σφαλμάτων, έχει τη δυνατότητα
για να παρακολουθείτε τα πάντα.
Ξέρω, σε Visionaire, εσείς πιθανώς μπορεί να χτυπήσει μερικά ελαττώματα τμηματοποίησης
γιατί έτρεχαν έξω από τα όρια του πίνακα σας.
Στο παράδειγμα του Καίσαρα, που είναι ακριβώς ό, τι έχω εφαρμοστεί εδώ.
>> Γι 'αυτό και ξέχασε να ελέγξει για τι θα συμβεί αν
δεν είχε δύο επιχειρήματα της γραμμής εντολών.
Απλά δεν έθεσε στην εν λόγω ελέγχου.
Και έτσι αν τρέχω Debug-- έθεσα breakpoint μου εκεί.
Τρέχω εντοπισμού σφαλμάτων.
>> ΕΝΤΆΞΕΙ.
Ναι.
Έτσι, στην πραγματικότητα, GDB υποτίθεται Μου είπαν εκεί
Ήταν ένα σφάλμα κατάτμησης εκεί.
Δεν ξέρω τι συνέβαινε εκεί, αλλά όταν έτρεξε,
δούλευε.
Όταν εκτελείτε γραμμές κώδικα μέσα και GDB θα μπορούσε να εγκαταλείψει ξαφνικά πάνω σου,
ανεβαίνουν και να δούμε ποιο είναι το κόκκινο είναι λάθος.
Θα σας πω, hey, είχε ένα σφάλμα κατάτμησης,
πράγμα που σημαίνει ότι επιχείρησε να αποκτήσει πρόσβαση χώρου σε έναν πίνακα που δεν υπήρχε.
Ναι.
>> Έτσι, στο επόμενο πρόβλημα που αυτή την εβδομάδα, εσείς
θα έχουν κατά πάσα πιθανότητα πολύ μεταβλητές που επιπλέουν γύρω.
Δεν πρόκειται να είναι σίγουροι για το τι σημαίνουν όλα αυτά σε ένα ορισμένο σημείο.
Έτσι, GDB θα σας βοηθήσει πραγματικά στον υπολογισμό τι είναι όλα ισούται
και να είναι σε θέση να δουν ότι οπτικά.
Είναι κανείς σύγχυση σχετικά με το πώς κάποια από τα οποία δούλευε;
Cool.
Εντάξει.
Έτσι, μετά από αυτό, είμαστε πρόκειται να βουτήξει δεξιά
σε τέσσερα διαφορετικά είναι τύπους των ειδών για αυτή την εβδομάδα.
Πόσοι από εσάς, πρώτο απ 'όλα, πριν αρχίσουμε,
έχουν διαβάσει ολόκληρο το spec για pset3;
ΕΝΤΆΞΕΙ.
Είμαι περήφανος για σας παιδιά.
Αυτό είναι σαν το ήμισυ της κατηγορίας, το οποίο είναι πολύ περισσότερο από ό, τι την τελευταία φορά.
>> Έτσι, αυτό είναι σπουδαίο, γιατί όταν μιλάμε για το περιεχόμενο
σε lecture-- ή συγγνώμη, σε section-- Μου αρέσει
να αφορούν πολλά γι 'αυτό πίσω σε αυτό το chipset είναι η
και πώς θέλετε να εφαρμόσουν ότι το chipset σας.
Έτσι, αν έρθει με διαβάστε το spec, αυτό θα
είναι πολύ πιο εύκολο για σας να καταλάβετε τι πράγμα μιλάω όταν λέω,
oh hey, αυτό θα μπορούσε να είναι μια πραγματικά καλό μέρος για να εφαρμόσει αυτό το είδος.
Έτσι, όσοι από εσάς έχουν διαβάσει το spec γνωρίζουμε ότι, ως μέρος της PSET σας,
θα πάμε να πρέπει να Αποστολή τύπο του είδους.
Έτσι, αυτό μπορεί να είναι πολύ χρήσιμη για πολλούς από εσάς σήμερα.
>> Έτσι θα ξεκινήσετε με, κατ 'ουσίαν, το πιο απλό τύπο
του είδους, το είδος επιλογής.
Το τυπικό αλγόριθμος για πώς είχαμε πάει για αυτό
is-- David πέρασε από όλα αυτά σε διάλεξη, γι 'αυτό θα προχωρήσουμε γρήγορα κατά μήκος
here-- είναι κατ 'ουσίαν, μπορείτε έχουν έναν πίνακα τιμών.
Και τότε θα βρείτε το μικρότερη τιμή χωρίς διαλογή
και μπορείτε να ανταλλάσσετε με αυτή την τιμή η πρώτη αδιαχώριστα αξία.
Και τότε απλά να το επαναλαμβάνω, με το υπόλοιπο της λίστας σας.
>> Και εδώ είναι μια οπτική εξήγηση πώς αυτό θα μπορούσε να λειτουργήσει.
Έτσι, για παράδειγμα, εάν επρόκειτο να ξεκινήσει με μια σειρά από πέντε στοιχεία, ο δείκτης
0 έως 4, με 3, 5, 2, 6, και 4 αξίες τοποθετείται στο array-- έτσι τώρα,
είμαστε ακριβώς πρόκειται να υποθέσουμε ότι είναι όλοι αδιαχώριστα
γιατί δεν έχουμε δοκιμαστεί διαφορετικά.
>> Πώς, λοιπόν, ένα είδος επιλογής θα το έργο είναι ότι ήθελα πρώτα
τρέχει μέσα από το σύνολο της συστοιχίας χωρίς διαλογή.
Θα ξεχωρίσω τη μικρότερη τιμή.
Στην περίπτωση αυτή, 3, δεξιά τώρα, είναι το μικρότερο.
Παίρνει έως 5.
Όχι, 5 δεν είναι μεγαλύτερη than-- ή συγγνώμη, δεν είναι μικρότερη than-- 3.
Έτσι, η ελάχιστη τιμή είναι ακόμα 3.
Και τότε θα έχετε να 2.
Ο υπολογιστής βλέπει, ω, 2 είναι λιγότερο από 3.
2 θα πρέπει τώρα να είναι η ελάχιστη τιμή.
Και έτσι 2 swaps με την εν λόγω πρώτη τιμή.
>> Έτσι, μετά από ένα πέρασμα, θα δούμε πράγματι ότι η 2 και το 3 είναι αντίστροφα.
Και είμαστε ακριβώς πρόκειται να συνεχίσει να κάνει αυτό πάλι με το υπόλοιπο της διάταξης.
Έτσι θα πάμε απλά να τρέχει μέσα τα τελευταία τέσσερα ευρετήρια της συστοιχίας.
Θα δούμε ότι είναι 3 η επόμενη ελάχιστη τιμή.
Έτσι θα πάμε να ανταλλάξουν ότι με 4.
Και τότε είμαστε ακριβώς πρόκειται να κρατήσει διατρέχει μέχρι, τελικά, θα
φτάσουμε σε ένα ταξινομημένο πίνακα στον οποίο 2, 3, 4, 5, 6 και είναι όλα ταξινομημένο.
Μήπως όλοι κατανοούν τη λογική για το πώς λειτουργεί ένα είδος επιλογής;
>> Απλά έχουν κάποιο είδος από μια ελάχιστη τιμή.
Είσαι παρακολούθηση του τι είναι αυτό.
Και κάθε φορά που θα το βρείτε, μπορείτε να το ανταλλάξετε με την πρώτη τιμή στην array--
ή, δεν είναι η πρώτη value-- η επόμενη τιμή στη συστοιχία.
Cool.
>> Έτσι όπως εσείς το είδος της είδε από μια σύντομη ματιά,
θα πάμε να ψευδοκώδικα αυτό.
Έτσι, αν έχετε παιδιά στο πίσω θέλετε να σχηματίζουν μια ομάδα, ο καθένας σε ένα τραπέζι
μπορεί να σχηματίσει ένα μικρό εταίρο, Πάω για να σας δώσει τύπους σαν τρία λεπτά
να μιλάμε μόνο μέσω η λογική, στην αγγλική γλώσσα,
για το πώς θα μπορέσουμε να εφαρμόσουν ψευδοκώδικας για να γράψει ένα είδος επιλογής.
Και υπάρχει καραμέλα.
Παρακαλούμε έρθει και να πάρει την καραμέλα.
Αν είστε στην πλάτη και θέλετε καραμέλα, μπορώ να ρίξει καραμέλα σε σας.
Στην πραγματικότητα, κάνει you-- δροσερό.
Ω συγνώμη.
ΕΝΤΆΞΕΙ.
>> Έτσι, αν θα θέλαμε να, όπως μια κατηγορία, ο ψευδοκώδικας εγγραφής
για το πώς θα μπορούσε κανείς να προσεγγίσει Αυτό το πρόβλημα, απλά αισθανθείτε ελεύθερος.
Θα πήγαινε γύρω και, προκειμένου, να ζητήσει από τις ομάδες
για την επόμενη γραμμή του τι πρέπει να κάνουμε.
Έτσι, αν εσείς θέλετε να ξεκινήσετε μακριά, ποιο είναι το πρώτο πράγμα που
πρέπει να κάνετε όταν προσπαθείτε να εφαρμόσει έναν τρόπο για να λύσει αυτό το πρόγραμμα
να ταξινομήσετε επιλεκτικά μια λίστα;
Ας υποθέσουμε ότι Έχουν μια σειρά, εντάξει;
>> Κοινό: Θέλετε να δημιουργήσετε κάποια είδος [δεν ακούγεται] ότι είστε
που διατρέχει ολόκληρη σειρά σας.
>> ANDI PENG: Δεξιά.
Έτσι θα πάμε να θέλουν να επαναλάβει μέσα από κάθε χώρο, έτσι δεν είναι;
Τόσο μεγάλη.
Αν εσείς θέλετε να μου δώσει το επόμενη line-- ναι, στο πίσω μέρος.
>> Κοινό: Ελέγξτε τους όλα για το μικρότερο.
>> ANDI PENG: Εκεί πάμε.
Θέλουμε, λοιπόν, να περάσει και να ελέγξετε δείτε ποια είναι η ελάχιστη τιμή είναι, σωστά;
Πάω να συντομεύσει ότι για να «min».
Τι εσείς θέλετε να κάνετε μετά έχετε βρει την ελάχιστη τιμή;
>> Κοινό: [δεν ακούγεται]
ANDI PENG: Έτσι θα πάμε να θέλουν να εναλλαγή με το πρώτο του εν λόγω πίνακα,
έτσι δεν είναι;
Αυτή είναι η αρχή, Πάω να πω.
Εντάξει.
Έτσι τώρα που έχετε ανταλλάξει την πρώτη μία, τι θέλεις να κάνω μετά από αυτό;
Μέχρι τώρα γνωρίζουμε πως αυτό εδώ πρέπει να είναι η μικρότερη τιμή, σωστά;
Στη συνέχεια, έχετε ένα επιπλέον υπόλοιπο του πίνακα που είναι αδιαχώριστα.
Έτσι, αυτό που θέλουμε να κάνουμε εδώ, αν παιδιά θέλουν να μου δώσει την επόμενη γραμμή;
Κοινό: Άρα λοιπόν θέλετε να μετακινηθείτε για το υπόλοιπο της διάταξης.
ANDI PENG: Ναι.
Και έτσι τι κάνει επανάληψη μέσω είδος σημαίνει ότι θα πρέπει πιθανώς;
Τι είδους of--
>> Κοινό: Ω, μια επιπλέον μεταβλητή;
ANDI PENG: Πιθανώς ένα άλλο για το βρόχο, έτσι δεν είναι;
Γι 'αυτό και πρόκειται πιθανώς να θέλουν να επαναλάβει through-- μεγάλη.
Και μετά θα πάμε για να πάει πίσω και να πιθανώς να ελέγξει την ελάχιστη και πάλι,
έτσι δεν είναι;
Και θα πάμε να το επαναλαμβάνουμε αυτό, επειδή οι θηλιές ακριβώς πρόκειται
να συνεχίσει να τρέχει, έτσι δεν είναι;
>> Έτσι, όπως μπορείτε να δείτε τα παιδιά, εμείς μόνο να έχουν μια γενική ψευδοκώδικα
για το πώς θέλουμε αυτό το πρόγραμμα για να δούμε.
Αυτό το επαναλάβει εδώ, τι κάνουμε εμείς συνήθως πρέπει να γράψετε σε κώδικα μας
αν θέλουμε να μετακινηθείτε μέσα από μια ποικιλία, το είδος της κατασκευής;
Νομίζω Christabel ήδη πει αυτό πριν.
>> Κοινό: Ένας βρόχος for.
>> ANDI PENG: Α για βρόχο;
Ακριβώς.
Έτσι, αυτό είναι πιθανώς πρόκειται να είναι ένα για το βρόχο.
Τι είναι ένας έλεγχος εδώ θα σημαίνει;
Συνήθως, αν θέλετε να ελέγξετε αν κάτι είναι κάτι else--
>> Κοινό: Αν.
>> ANDI PENG: Μια περίπτωση, σωστά;
Και τότε η ανταλλαγή εδώ, θα πάει πάνω αργότερα, γιατί ο David
πέρασε από ότι σε διάλεξη καθώς και.
Και τότε το δεύτερο επαναλάβει implies--
>> Κοινό: Άλλη για το βρόχο.
>> ANDI PENG: --another για το βρόχο, ακριβώς.
Έτσι, αν ψάχνουμε σε αυτό σωστά, θα
μπορεί να δει ότι είμαστε κατά πάσα πιθανότητα Θα χρειαστείτε μια ένθετη βρόχο για
με την προϋπόθεση δήλωση εκεί και, στη συνέχεια, ένα πραγματικό κομμάτι του κώδικα που είναι
πρόκειται να ανταλλάξουν τις αξίες.
Έτσι έχω μόνο γενικά γραπτή ένας κώδικας ψευδοκώδικας εδώ.
Και τότε είμαστε στην πραγματικότητα θα σε φυσικά, ως τάξη,
προσπαθούν να εφαρμόσουν αυτή σήμερα.
Ας πάμε πίσω σε αυτό το IDE.
>> Ωχ.
Γιατί είναι ότι not-- εκεί είναι.
ΕΝΤΆΞΕΙ.
Λυπούμαστε, επιτρέψτε μου να προσπαθήσω να μεγεθύνετε σε λίγο περισσότερο.
Εκεί πάμε.
Όλα τα κάνω εδώ είναι που έχω δημιουργήσει ένα πρόγραμμα που ονομάζεται "επιλογή / sort.c."
Έχω δημιουργήσει μια σειρά από εννέα αξίες, 4, 8, 2, 1, 6, 9, 7, 5, 3.
Επί του παρόντος, όπως μπορείτε Βλέπετε, αυτοί είναι μη ταξινομημένες.
n πρόκειται να είναι ο αριθμός ότι σας λέει το ποσό των αξιών
έχετε στη σειρά σας.
Σε αυτή την περίπτωση, έχουμε εννέα τιμές.
Και έχω απλά ένα βρόχο for εδώ ότι εκτυπώνει το αδιαχώριστα πίνακα.
>> Και στο τέλος, έχω επίσης πήρε για βρόχο που εκτυπώνει μόνο φορά.
Έτσι, θεωρητικά, εάν αυτό το πρόγραμμα λειτουργεί σωστά, στο τέλος,
θα πρέπει να δείτε ένα έντυπο για το βρόχο στην οποία 1, 2, 3, 4, 5, 6, 7, 8,
9 είναι όλα σωστά στην τάξη.
>> Έτσι έχουμε ψευδοκώδικας μας εδώ.
Υπάρχει κάποιος που θέλει to-- Είμαι απλά πρόκειται να πάει να ζητήσει volunteers--
πες μου ακριβώς τι πρέπει να πληκτρολογήσετε αν θέλουμε, πρώτα, απλά επαναλήψεις
μέσα από την αρχή αυτής της διάταξης;
Ποια είναι η γραμμή κώδικα είμαι κατά πάσα πιθανότητα θα χρειαστεί εδώ;
>> Κοινό: [δεν ακούγεται]
>> ANDI PENG: Ναι, αισθάνομαι δωρεάν to-- συγγνώμη, σας
Δεν χρειάζεται να σταθεί αίσθηση up-- ελεύθερο να υψώσετε τη φωνή σας λίγο.
>> Κοινό: Για int i ισούται με 0--
>> ANDI PENG: Ναι, καλά.
>> Κοινό: i είναι μικρότερο από το μήκος του πίνακα.
>> ANDI PENG: Έτσι λάβετε πειράζει εδώ, γιατί είμαστε
δεν έχουν μια λειτουργία που μας λέει το μήκος μιας συστοιχίας,
Έχουμε ήδη ένα αξία που αποθηκεύει αυτό.
Σωστά;
Ένα άλλο πράγμα που πρέπει να σε mind-- σε μια σειρά
εννέα αξίες, ποιες είναι οι δείκτες;
Ας πούμε απλά ο πίνακας αυτός ήταν 0-3.
Θα δείτε ότι το τελευταίο δείκτης είναι στην πραγματικότητα 3.
Δεν είναι 4, ακόμα κι αν υπάρχει τέσσερις τιμές στη συστοιχία.
>> Έτσι, εδώ, πρέπει να είμαστε πολύ προσεκτικοί του πώς είναι η κατάστασή μας για το μήκος
θα είναι.
>> Κοινό: Δεν θα ήταν ν μείον 1;
ANDI PENG: Δεν πρόκειται n μείον 1, ακριβώς.
Μήπως αυτό έχει νόημα, γιατί n είναι μείον 1, ο καθένας;
Είναι επειδή συστοιχίες είναι μηδέν-index.
Αρχίζουν από το 0 και να τρέξει μέχρι ν μείον 1.
Ναι, είναι λίγο δύσκολο.
ΕΝΤΆΞΕΙ.
Και μετά--
Κοινό: Isnt'1 ότι που έχουν ήδη ληφθεί μέριμνα όμως,
από απλά δεν λέει "μικρότερη ή ίσο με το "και απλά λέγοντας« λιγότερο από ό, τι; "
>> ANDI PENG: Αυτό είναι ένα πολύ καλή ερώτηση.
Έτσι, ναι.
Αλλά, επίσης, τον τρόπο με τον οποίο είμαστε την εφαρμογή του δικαιώματος ελέγχου,
θα πρέπει να συγκρίνετε δύο τιμές.
Έτσι θέλετε πραγματικά να αφήστε το "στο" άδειο.
Γιατί αν συγκρίνουμε αυτό, εσείς δεν πρόκειται
έχει τίποτα μετά να συγκρίνουν με, έτσι δεν είναι;
Ναι.
Έτσι i ++.
Ας προσθέσουμε σε παρένθεση μας.
Ωχ.
Εξαιρετική.
Έτσι έχουμε την αρχή του εξωτερικού βρόχου μας.
Έτσι, τώρα πιθανόν να θέλετε να δημιουργήσετε μια μεταβλητή για τη διατήρηση
παρακολουθείτε τη μικρότερη τιμή, σωστά;
Θέλει κανείς να μου δώσει το γραμμή του κώδικα που θα το κάνει αυτό;
Τι χρειαζόμαστε αν θέλουμε να θέλετε να αποθηκεύσετε κάτι;
>> Δεξιά.
Ίσως ένα καλύτερο όνομα γι 'αυτό θα be-- "temp" εντελώς works--
ίσως μια πιο εύστοχα ονομάστηκε θα είναι, αν θέλουμε το μικρότερο value--
>> Κοινό: Min.
ANDI PENG: λεπτά, εκεί θα πάμε.
min θα ήταν καλό.
Και έτσι εδώ, τι κάνουμε εμείς Θέλετε να γίνει η προετοιμασία για;
Αυτό είναι λίγο δύσκολο.
Επειδή αυτή τη στιγμή κατά τη αρχή αυτής της διάταξης,
δεν έχετε κοίταξε τίποτα, σωστά;
Έτσι, αυτό που, αυτόματα, εάν είμαστε ακριβώς στο i ισούται με 0,
τι θέλουμε να προετοιμαστεί πρώτη ελάχιστη τιμή για μας;
Κοινό: i.
ANDI PENG: i, ακριβώς.
Christabel, γιατί θέλουμε να γίνει η προετοιμασία για i;
>> Κοινό: Επειδή, επίσης, ξεκινάμε με 0.
Έτσι, γιατί δεν έχουμε τίποτα να συγκρίνετε να, η ελάχιστη θα καταλήξει να είναι 0.
>> ANDI PENG: Ακριβώς.
Έτσι, αυτή είναι ακριβώς σωστό.
Επειδή δεν έχουμε στην πραγματικότητα κοίταξε τίποτα ακόμα,
δεν ξέρουμε τι ελάχιστη τιμή μας είναι.
Θέλουμε να γίνει η προετοιμασία μόνο για να i, η οποία, επί του παρόντος, είναι ακριβώς εδώ.
Και καθώς συνεχίζουμε να κινούνται προς αυτή την σειρά,
θα δούμε ότι, με κάθε επιπλέον άδεια, θ αυξάνει.
Και έτσι σε εκείνο το σημείο, i είναι κατά πάσα πιθανότητα θα
να θέλουν να είναι το ελάχιστο, επειδή πρόκειται να είναι ό, τι
είναι η αρχή της αδιαχώριστα πίνακα.
Cool.
>> Έτσι, τώρα θέλουμε να προσθέσουμε ένα για το βρόχο εδώ που είναι
πρόκειται να επαναλάβει μέσω της αδιαχώριστα, ή το υπόλοιπο αυτής της διάταξης.
Θέλει κανείς να μου δώσει ένα γραμμή του κώδικα που θα το κάνει αυτό;
Hint-- τι χρειαζόμαστε εδώ κάτω;
Τι πρόκειται να πάει σε αυτό για βρόχο;
Ναι.
Κοινό: Έτσι θα θέλατε να έχουν διαφορετική ακέραιος,
επειδή είμαστε τρέχει μέσα από το υπόλοιπο του πίνακα αντί του i, οπότε ίσως
j.
>> ANDI PENG: Ναι, ι ακούγεται καλό για μένα.
Ίσο;
>> Κοινό: Έτσι θα πρέπει να είναι i + 1, επειδή ξεκινάτε την επόμενη τιμή.
Και στη συνέχεια στο end-- έτσι και πάλι, το j είναι λιγότερο από n μείον 1, και στη συνέχεια, j ++.
ANDI PENG: Μεγάλη.
>> Και στη συνέχεια εδώ, θα πάμε να θέλουν για να ελέγξετε για να δείτε αν η κατάσταση μας έχει τηρηθεί,
έτσι δεν είναι;
Επειδή θέλετε να αλλάξετε την ελάχιστη τιμή
αν είναι στην πραγματικότητα μικρότερη από ό, τι είστε το συγκρίνει με, έτσι δεν είναι;
Λοιπόν, τι θα πάμε να θέλουν εδώ;
Ελέγξτε για να δείτε.
Τι είδους δήλωση είμαστε κατά πάσα πιθανότητα θα
ti θέλετε να χρησιμοποιήσετε, εάν θέλετε να ελέγξετε κάτι;
>> ΚΟΙΝΟ: Η εντολή if.
>> ANDI PENG: Μια εντολή if.
Έτσι if-- και τι πρόκειται να είναι η κατάσταση που θέλουμε μέσα
της εντολής if μας;
>> Κοινό: Εάν η τιμή του j είναι μικρότερη από την τιμή των i--
>> ANDI PENG: Ακριβώς.
Έτσι if-- οπότε ο συγκεκριμένος πίνακας ονομάζεται "συστοιχία".
Εξαιρετική.
Έτσι, αν array-- τι ήταν αυτό;
Αυτο ξαναπεστο.
>> Κοινό: Εάν το όρισμα array-j είναι μικρότερη από σειρά-i, τότε θα αλλάξει το λεπτό.
Έτσι, το λεπτό θα είναι ι.
>> ANDI PENG: Μήπως αυτό έχει νόημα;
ΕΝΤΆΞΕΙ.
Και τώρα εδώ κάτω, στην πραγματικότητα θέλουν να εφαρμόσουν τη συμφωνία ανταλλαγής, έτσι δεν είναι;
Έτσι, υπενθυμίζουν, στη διάλεξη, ότι ο Δαβίδ, όταν προσπαθούσε να ανταλλάξουν the-- ό, τι ήταν
it-- χυμό πορτοκαλιού και milk--
>> Κοινό: Αυτό ήταν ακαθάριστο.
>> ANDI PENG: Ναι, αυτό ήταν το είδος του ακαθάριστου.
Αλλά ήταν μια αρκετά καλή η έννοια του χρόνου επίδειξη.
Έτσι σκεφτείτε τις αξίες σας εδώ.
Έχετε μια σειρά από λεπτό, μια σειρά από i,
ή ό, τι προσπαθούμε να ανταλλάξουν εδώ.
Και ίσως να μην μπορεί να τα ρίχνουμε σε κάθε άλλο κατά την ίδια στιγμή, έτσι;
Λοιπόν, τι θα πάμε να χρειαστεί να δημιουργήσετε εδώ
προκειμένου να ανταλλάξουν τις αξίες σωστά;
>> Κοινό: Μια προσωρινή μεταβλητή.
>> ANDI PENG: Μια προσωρινή μεταβλητή.
Έτσι, ας κάνουμε int temp.
Βλέπε, αυτό θα είναι μια καλύτερη to-- χρόνο Πω πω, τι ήταν αυτό;
ΕΝΤΆΞΕΙ.
Έτσι, αυτό θα ήταν μια καλύτερη χρόνο για να αναφέρουμε τη μεταβλητή "temp".
Έτσι, ας κάνουμε int temp.
Τι θα πάμε να Set Temp ίσο με εδώ;
Κοινό: Ελάχιστη;
ANDI PENG: Είναι λίγο δύσκολο.
Είναι πραγματικά δεν έχει σημασία στο τέλος.
Δεν έχει σημασία τι Για να επιλέξετε να ανταλλάξουν σε
εφ 'όσον έχετε κάνει ότι είστε την παρακολούθηση του τι είστε εναλλαγή.
>> Κοινό: Θα μπορούσε να είναι σειρά-i.
>> ANDI PENG: Ναι, ας κάνουμε σειρά-i.
Και τότε ποια είναι η επόμενη γραμμή του κώδικα θέλουμε να έχουμε εδώ;
Κοινό: array-i ισούται με διάταξη-j.
ANDI PENG: Και τέλος;
Κοινό: array-j ισούται με σειρά-i.
Κοινό: Ή διάταξη-j ισούται array-temp-- ή, temp.
>> ANDI PENG: OK.
Ας τρέξει αυτή και να δούμε αν πρόκειται να λειτουργήσει.
Πού είναι αυτό που συμβαίνει;
Ω, αυτό είναι ένα πρόβλημα.
Δείτε, επί της γραμμής 40, είμαστε προσπαθείτε να χρησιμοποιήσετε συστοιχία-ι;
Αλλά από πού ι υπάρχουν μόνο μέσα;
>> ΚΟΙΝΟ: Στο βρόχο for.
ANDI PENG: Δεξιά.
Λοιπόν, τι θα πάμε να πρέπει να κάνουμε;
>> Κοινό: Ορίστε το εξωτερικό the--
Κοινό: Ναι, υποθέτω ότι έχετε να χρησιμοποιήσει άλλη μία εντολή if, έτσι δεν είναι;
Έτσι, όπως, αν ο minimum-- Εντάξει, επιτρέψτε μου να πιστεύω.
>> ANDI PENG: Παιδιά, δοκιμάστε να ρίξετε μια ματιά Ας
Βλέπετε, αυτό είναι κάτι που μπορούμε να κάνουμε εδώ;
>> Κοινό: OK.
Έτσι, αν η ελάχιστη δεν ισούται j-- οπότε αν το ελάχιστο είναι ακόμα i--
τότε δεν θα πρέπει να ανταλλάξουν.
>> ANDI PENG: Θεωρεί ότι η ίση εγώ;
Τι θέλω να πω εδώ;
>> Κοινό: Ή ναι, αν η ελάχιστο δεν είναι ίσο με i, ναι.
ANDI PENG: OK.
Λοιπόν ότι λύνει, το είδος του, τα προβλήματά μας.
Αλλά αυτό ακόμα δεν λύνει το το πρόβλημα του τι θα συμβεί αν j-- από το j
δεν υπάρχει έξω από αυτό, τι δεν θα θέλουμε να κάνουμε με αυτό;
Κηρύξει έξω;
Ας προσπαθήσουμε τρέχει αυτό.
Ωχ.
Είδος μας δεν λειτουργεί.
>> Όπως μπορείτε να δείτε, η αρχική μας σειρά είχε αυτές τις αξίες.
Και μετά θα πρέπει να έχει ήταν σε 1, 2, 3, 4, 5, 6, 7, 8, 9.
Δεν λειτουργεί.
Ααα.
Τι κάνουμε?
Κοινό: Debug.
ANDI PENG: Εντάξει, μπορούμε να προσπαθήσουμε αυτό.
Μπορούμε να debug.
Σμίκρυνση λίγο.
Ας ορίσετε breakpoint μας.
Ας πάμε like-- ΟΚ.
>> Έτσι, επειδή γνωρίζουμε ήδη ότι Αυτές οι γραμμές, 15 έως 22,
Οι working-- γιατί όλα τα κάνω είναι απλά επανάληψη και μέσω printing--
Μπορώ να προχωρήσει και να παραλείψετε αυτό.
Ας ξεκινήσουμε από τη γραμμή 25.
Oop, επιτρέψτε μου να απαλλαγούμε από αυτό.
>> Κοινό: Έτσι, το σημείο διακοπής του όπου η αποσφαλμάτωση ξεκινά;
ANDI PENG: ή σταματά.
Κοινό: Ή στάσεις.
ANDI PENG: Ναι.
Μπορείτε να ορίσετε πολλαπλά σημεία διακοπής και μπορεί απλά να πηδούν από το ένα στο άλλο.
Αλλά σε αυτή την περίπτωση δεν γνωρίζουμε όπου συμβαίνει το σφάλμα.
Γι 'αυτό ακριβώς θέλουμε να ξεκινούν από την κορυφή προς τα κάτω.
Ναι.
ΕΝΤΆΞΕΙ.
>> Έτσι, η γραμμή αυτή εδώ, μπορούμε να παρέμβει.
Μπορείτε να δείτε εδώ κάτω, έχουμε μια σειρά.
Αυτοί είναι οι αξίες που είναι στη συστοιχία.
Βλέπετε ότι, πώς δείκτη 0, το αντιστοιχεί στο value-- OH,
Πάω να προσπαθήσω να μεγεθύνετε.
Συγγνώμη, αυτό είναι πραγματικά δύσκολο να see-- στο ευρετήριο πίνακα 0,
έχουμε μια τιμή 4 και τότε ούτω καθεξής και ούτω καθεξής.
Έχουμε τοπικές μεταβλητές μας.
Αυτή τη στιγμή i είναι ίσο με 0, η οποία θέλουμε να είναι.
>> Και έτσι ας κρατήσουμε την ενίσχυση μέσα.
Ελάχιστο μας είναι ίση με 0, το οποίο θέλουμε επίσης να είναι.
Και τότε μπαίνουμε δεύτερη μας βρόχο, αν array-j είναι μικρότερη από array-i,
η οποία δεν ήταν.
Έτσι, είδες πώς ότι παρακάμπτονται αυτό;
>> Κοινό: Έτσι, αν θα πρέπει να το ελάχιστο, όλα that-- δεν θα πρέπει να
είναι μέσα στο πρώτο για το βρόχο;
ANDI PENG: Όχι, γιατί Εξακολουθείτε να θέλετε να δοκιμάσετε.
Θέλετε να κάνετε μια σύγκριση κάθε χρόνο, ακόμα και μετά την εκτέλεση μέσα από αυτό.
Δεν θέλουν απλά να το κάνω στο πρώτο πέρασμα-μέσω.
Θέλετε να το κάνετε με κάθε επιπλέον πέρασμα και πάλι.
Έτσι θέλετε να ελέγξετε για κατάστασή σας μέσα.
Έτσι, είμαστε ακριβώς πρόκειται να συνεχίσει να τρέχει από εδώ.
Θα σας δώσω μια υπόδειξη παιδιά.
Έχει να κάνει με το γεγονός ότι, όταν έχετε τον έλεγχο υπό όρους σας,
δεν είστε έλεγχο για τη σωστή δείκτη.
Έτσι τώρα έχετε τον έλεγχο για ευρετήριο πίνακα του j είναι μικρότερη από σειρά
δείκτη i.
Αλλά τι κάνεις επάνω στο Η αρχή του για βρόχο;
Δεν είσαι ρύθμιση j ισούται με i;
>> Ναι, έτσι μπορούμε πραγματικά βγείτε από το πρόγραμμα εντοπισμού σφαλμάτων εδώ.
Έτσι, ας ρίξουμε μια ματιά σε ψευδοκώδικα μας.
For-- θα πάμε να ξεκινούν από i ισούται με 0.
Εμείς πάμε για να πάει μέχρι ν μείον 1.
Ας δούμε, δεν έχουμε αυτό το δικαίωμα;
Ναι, αυτό ήταν σωστό.
>> Άρα λοιπόν εδώ μέσα, είμαστε πρόκειται να δημιουργήσουμε μια ελάχιστη τιμή
και να ορίσετε ότι ισούται με i.
Μήπως να το κάνουμε αυτό;
Ναι, το έκανε αυτό.
Τώρα στον εσωτερικό βρόχο για μας, είμαστε πρόκειται να κάνει ι θ ισούται με n μείον 1.
Μήπως να το κάνουμε αυτό;
Πράγματι, το κάναμε.
>> Έτσι όμως, αυτό που είμαστε συγκρίνοντας εδώ;
>> Κοινό: ι συν 1.
ANDI PENG: Ακριβώς.
Και μετά θα πάμε να θέλουν να ορίσετε ελάχιστη σας ίσο με j + 1, καθώς και.
Έτσι πήγα μέσα από αυτό πολύ γρήγορα.
Έχετε παιδιά να κατανοήσουν Γι 'αυτό είναι j + 1;
ΕΝΤΆΞΕΙ.
>> Έτσι, σε σειρά σας, σε η πρώτη σας περάσει,
για βρόχο σας, για int i ισούται με 0, ας
υποθέσετε ότι αυτό δεν έχει αλλάξει ακόμη.
Έχουμε μια σειρά από εντελώς, μόλις τέσσερις αδιαχώριστα στοιχεία, σωστά;
Έτσι θέλουμε να προετοιμάσει i ισούται με 0.
Και εγώ πρόκειται απλά τρέχει μέσα από αυτό το βρόχο.
Και έτσι στο πρώτο πέρασμα, θα πάμε να προετοιμάσει μια μεταβλητή που ονομάζεται "λεπτό"
ότι είναι επίσης ίσο με i, επειδή δεν έχουμε μια ελάχιστη τιμή.
Έτσι ώστε να είναι σήμερα ίση με 0, καθώς και.
Και μετά θα πάμε για να περάσει.
Και θέλουμε να επαναλάβει και πάλι.
Τώρα που έχουμε βρει ό, τι ελάχιστο μας είναι, θέλουμε να μετακινηθείτε μέσα
ξανά για να δείτε αν είναι σύγκριση, σωστά;
Έτσι, ι, εδώ, πρόκειται στην ισότητα i, η οποία είναι 0.
Και στη συνέχεια, αν συστοιχία ι συν θ, η οποία είναι αυτός που είναι δίπλα πάνω, ως λιγότερο
από ό, τι οι τρέχοντες κατώτατοι σας αξίας είναι, θέλετε να ανταλλάξετε.
>> Έτσι, ας πούμε έχουμε πήρε, όπως, 2, 5, 1, 8.
Αυτή τη στιγμή, i είναι ίσο με 0 και j είναι ίσο με 0.
Και αυτό είναι ελάχιστη αξία μας.
Αν σειρά-ι συν i-- οπότε αν το ένα αυτό είναι το ένα μετά ψάχνουμε
είναι μεγαλύτερο από το προηγούμενο αυτό, πρόκειται να γίνει η ελάχιστη.
>> Έτσι, εδώ βλέπουμε ότι 5 δεν είναι μικρότερη από εκείνη.
Γι 'αυτό πρόκειται να μην είναι 5.
Βλέπουμε ότι το 1 είναι μικρότερη από 2, σωστά;
Μέχρι τώρα γνωρίζουμε ότι οι ελάχιστες μας είναι πρόκειται να είναι η τιμή του δείκτη κατά 0, 1, 2.
Ναι;
Και στη συνέχεια, όταν μπορείτε να πάρετε εδώ κάτω, μπορείτε να ανταλλάξετε τις σωστές τιμές.
>> Έτσι, όταν παιδιά ήταν έχοντας μόλις το j πριν, δεν ήσασταν κοιτάζοντας το ένα
μετά από αυτό.
Μπορείτε κοιτούσαν η ίδια αξία, η οποία
Γι 'αυτό ακριβώς δεν είχε κάνει τίποτα.
Μήπως αυτό έχει νόημα για όλους, Γι 'αυτό απαιτείται η συν 1 εκεί;
ΕΝΤΆΞΕΙ.
Τώρα ας τρέχει μέσα από αυτό να κάνει ότι το υπόλοιπο του κώδικα είναι η σωστή.
Γιατί συμβαίνει;
Αχ, αυτό είναι το λεπτό εδώ.
Ήμασταν συγκρίνοντας την λάθος τιμή.
Ωχ όχι.
>> Ω ναι, εδώ κάτω είμαστε εναλλαγή λάθος τιμές, καθώς και.
Επειδή ψάχναμε στο i και j.
Αυτοί είναι εκείνοι που είχαν τον έλεγχο.
Είμαστε πραγματικά θέλουν να ανταλλάξουν το ελάχιστο, το τρέχον ελάχιστο,
με ό, τι αυτό που είναι έξω.
Και όπως εσείς μπορείτε να δείτε κάτω Εδώ, έχουμε ένα ταξινομημένο πίνακα.
Απλά είχε να κάνει με το γεγονός ότι, όταν
είχαμε τον έλεγχο της αξίες μας σύγκρισης,
Εμείς δεν έψαχναν τις σωστές τιμές.
Ψάχναμε στο ίδιο αυτό εδώ, στην πραγματικότητα δεν το αλλάζουν.
Θα πρέπει να εξετάσουμε το ένα δίπλα σε αυτό και, στη συνέχεια, μπορείτε να ανταλλάξετε.
Έτσι, αυτό είναι ό, τι ήταν το είδος του υποκλοπών κωδικό μας πριν.
Και τι έκανα εδώ είναι το παν το πρόγραμμα εντοπισμού σφαλμάτων θα μπορούσε να κάνει για σας
Έκανα μόνο για το του σκάφους, γιατί είναι πιο εύκολο
για να δούμε, αντί να προσπαθούν για να μεγεθύνετε το πρόγραμμα εντοπισμού σφαλμάτων.
Μήπως αυτό έχει νόημα για όλους;
Cool.
>> Εντάξει.
Μπορούμε να προχωρήσουμε σε μιλάμε για ασυμπτωτική σημειογραφία, η οποία
είναι ακριβώς ένα φανταχτερό τρόπο λέγοντας ότι η runtimes όλων αυτών των ειδών.
Έτσι ξέρω Δαβίδ, στη διάλεξη, έθιξε χρόνους εκτέλεσης.
Και πήγε όλο το τύπο για τον υπολογισμό των χρόνων εκτέλεσης.
Μην ανησυχείτε γι 'αυτό.
Εάν είστε πραγματικά περίεργος σχετικά με τον τρόπο που λειτουργεί,
διστάσετε να μου μιλήσει μετά το τμήμα.
Μπορούμε να περπατήσετε μέσα Οι τύποι μαζί.
Αλλά όλοι εσείς έχετε πραγματικά γνωρίζουμε είναι ότι n τετράγωνο πάνω από 2
είναι το ίδιο πράγμα όπως n τετράγωνο.
Επειδή το μεγαλύτερο αριθμό, ο εκθέτης, μεγαλώνει περισσότερο.
Και έτσι για τους σκοπούς μας, μας νοιάζει
είναι ότι η γιγαντιαία αριθμός που μεγαλώνει.
>> Έτσι ποια είναι η καλύτερη περίπτωση Διάρκεια της επιλογής του είδους;
Εάν πρόκειται να έχουμε για να μετακινηθείτε σε μια λίστα
και, στη συνέχεια, διέτρεξε το υπόλοιπο του εν λόγω καταλόγου,
πόσες φορές είναι Σκοπεύετε να πιθανώς,
στη χειρότερη case-- στο καλύτερη περίπτωση, sorry-- τρέχει μέσα;
Ίσως η καλύτερη ερώτηση είναι να ρωτήσω, ποια είναι η χειρότερη περίπτωση
εκτέλεσης του είδους επιλογής.
Κοινό: n τετράγωνο.
ANDI PENG: Είναι n τετράγωνο, δεξιά.
Έτσι, ένας εύκολος τρόπος για να σκεφτώ αυτό είναι σαν, κάθε φορά που θα έχετε δύο ένθετα για βρόχους,
πρόκειται να n τετράγωνο.
Διότι όχι μόνο είστε διατρέχει και πάλι,
θα πρέπει να πάμε πίσω γύρω και διασχίζουν
και πάλι μέσα για κάθε τιμή.
Έτσι, σε αυτή την περίπτωση, τρέχετε n n φορές τετράγωνο, το οποίο is-- συγγνώμη,
n n φορές, το οποίο ισούται με το Ν τετράγωνο.
>> Και είδος είναι επίσης ένα κομμάτι μοναδικό υπό την έννοια
ότι δεν έχει σημασία, εφόσον αυτά οι τιμές είναι ήδη σε τάξη.
Είναι ακόμα πρόκειται να τρέχει μέσα ούτως ή άλλως.
Ας πούμε απλά αυτό ήταν 1, 2, 3, 4.
Ανεξάρτητα από το αν ήταν ή όχι σε τάξη, ακόμα θα διέτρεχε
και εξακολουθεί να ελέγξει την ελάχιστη τιμή.
Θα έχουν κάνει το ίδιο αριθμό των ελέγχων
κάθε φορά, ακόμα και αν δεν αγγίζει τίποτα.
>> Έτσι, σε μια τέτοια περίπτωση, το καλύτερο και το χειρότερο runtimes είναι πραγματικά ισοδύναμες.
Έτσι, η αναμενόμενη αυτονομία του είδους επιλογής,
το οποίο έχουμε ορίσει με το σύμβολο του θήτα, θήτα, στην περίπτωση αυτή,
επίσης θα n τετράγωνο.
Και τα τρία αυτά θα n τετράγωνο.
Είναι σαφές σε όλους σχετικά με το γιατί ο χρόνος εκτέλεσης είναι ν τετράγωνο;
>> Εντάξει.
Έτσι, είμαι απλώς πρόκειται να τρέξει γρήγορα μέσα από το υπόλοιπο του είδους.
Ο αλγόριθμος για φούσκα sort-- θυμάστε,
Αυτό ήταν η πρώτη David πήγε πάνω στη διάλεξη.
Ουσιαστικά, θα μπείτε καθ 'όλη τη λίστα
και εσείς απλά swap-- συγκρίνουν δύο σε έναν χρόνο.
Και αν κάποιος είναι μεγαλύτερη, από ό, τι ακριβώς τους swap.
Έτσι, εφόσον αυτά είναι μεγαλύτερα, θα ανταλλάξουν.
Έχω επίσημες εδώ.
>> Έτσι, ας υποθέσουμε ότι είχατε 8, 6, 4, 2.
Θα ήθελα να συγκρίνουν το 8 και 6.
Μπορείτε Θα πρέπει να τα ανταλλάξουν.
Θα συγκρίνετε τις 8 και 4.
Μπορείτε Θα πρέπει να τα ανταλλάξουν.
Αν πρέπει να ανταλλάξουν τα 8 και το 2, να αλλάξει αυτούς.
Έτσι, σε μια τέτοια αίσθηση, μπορείτε να δείτε, παίζεται επί μακρά χρονική περίοδο,
πώς το είδος των αξιών φούσκα τα άκρα, η οποία είναι ο λόγος που το ονομάζουμε
bubble sort.
>> Θα τρέξει μόνο μέσω και πάλι σε δεύτερο πέρασμα μας, και τρίτο πέρασμα μας,
και το τέταρτο πέρασμα μας.
Ουσιαστικά, φούσκα τρέχει μόνο είδος μέχρι να μην κάνει πλέον καμία swaps.
Έτσι, με αυτή την έννοια, αυτό είναι μόνο η γενική ψευδοκώδικα για αυτό.
Μην ανησυχείτε, όλα αυτά θα είναι σε απευθείας σύνδεση.
Δεν έχουμε πραγματικά να πάει πάνω από αυτό.
>> Εμείς απλά προετοιμάσει ένα μετρητή μεταβλητή που ξεκινά από το 0.
Και έχουμε επαναλάβει όλη την παράταξη.
Και αν μία τιμή is-- εάν αυτό η τιμή είναι μεγαλύτερη από την τιμή,
θα πάμε να τους swap.
Και τότε είστε απλά πρόκειται να συνεχίσω.
Και θα πάμε να μετρήσει.
Και είστε ακριβώς πρόκειται να συνεχίσει να κάνει αυτό, ενώ ο μετρητής είναι μεγαλύτερος
από 0, που σημαίνει ότι κάθε φορά που θα χρειαστεί να ανταλλάξουν,
ξέρετε ότι θέλετε να πάτε πίσω και ελέγξτε και πάλι.
Θέλετε να κρατήσει τον έλεγχο μέχρι να γνωρίζετε ότι δεν έχετε να ανταλλάξουν πια.
>> Λοιπόν, τι είναι το καλύτερο και το χειρότερο περίπτωση runtimes για bubble sort;
Και hint-- αυτό είναι πραγματικά διαφορετικό από την ταξινόμηση με επιλογή, με την έννοια
ότι οι δύο αυτές απαντήσεις δεν είναι το ίδιο.
Σκεφτείτε τι θα συνέβαινε σε μια περίπτωση κατά την οποία είχε ήδη διευθετηθεί.
Και σκεφτείτε τι θα συνέβαινε αν ήταν
στην περίπτωση κατά την οποία δεν ήταν ταξινομημένο.
Και μπορείτε να εκτελέσετε το είδος του μέσω της γιατί αυτό συμβαίνει.
Θα σας δώσω ρε παιδιά, όπως, 30 δευτερόλεπτα για να σκεφτούμε γι 'αυτό.
>> ΕΝΤΆΞΕΙ.
Υπάρχει κάποιος που έχει μια εικασία σε αυτό που η χειρότερη περίπτωση εκτέλεσης του bubble sort είναι;
Ναι.
>> Κοινό: Θα ήταν, όπως, n φορές n μείον 1 ή κάτι τέτοιο;
Όπως, κάθε φορά που τρέχει, είναι ακριβώς, όπως, ένα λιγότερο ανταλλαγής
πως ό, τι ήταν.
>> ANDI PENG: Ναι, έτσι είσαι εντελώς δεξιά.
Και αυτό είναι μια περίπτωση κατά την οποία σας απάντηση ήταν στην πραγματικότητα πιο περίπλοκο
από αυτό που πρέπει να δώσουμε.
Έτσι, πρόκειται να είμαι run-- πρόκειται να διαγράψετε όλα αυτά εδώ.
Είναι όλοι καλά;
Μπορώ να σβήσω αυτό;
ΕΝΤΆΞΕΙ.
Θα πάμε να τρέχει μέσα από n φορές την πρώτη φορά, έτσι δεν είναι;
Και θα πάμε να τρέχει μέσα n μείον 1 δεύτερη φορά, σωστά;
Και μετά θα πάμε να κρατήσει πρόκειται, Ν ορυχείο 2, κλπ.
Ο David έκανε αυτό σε μια διάλεξη, όπου, αν αθροιστούν όλες αυτές τις αξίες,
μπορείτε να πάρετε κάτι που είναι like-- yeah-- πάνω από 2, το οποίο ουσιαστικά μειώνει μόνο
μέχρι ν τετράγωνο.
Θα πάμε για να πάρετε μια Περίεργο κλάσμα εκεί.
Και έτσι απλά να ξέρετε ότι το ν τετράγωνο πάντα
υπερισχύει το κλάσμα.
Και στην προκειμένη περίπτωση, το χειρότερο runtime θα n τετράγωνο.
Αν ήταν σε φθίνουσα Προκειμένου, νομίζω, θα
πρέπει να κάνει μια συμφωνία ανταλλαγής κάθε φορά.
>> Ποια θα ήταν, ενδεχομένως, η καλύτερη περίπτωση εκτέλεσης;
Ας πούμε, αν η λίστα ήταν ήδη προκειμένου, ποια θα είναι και ο χρόνος είναι;
>> Κοινό: n.
ANDI PENG: Είναι n, ακριβώς.
Και γιατί είναι ν?
Κοινό: Επειδή απλά πρέπει να ελέγξετε σε κάθε φορά.
ANDI PENG: Ακριβώς.
Έτσι, με τον καλύτερο δυνατό χρόνο εκτέλεσης, αν ο κατάλογος αυτός ήταν ήδη
sorted-- ας πούμε 1, 2, 3, 4-- σας θα πήγαινε μέσα, θα ελέγχει,
θα δείτε, ω, όλοι τηγάνι έξω.
Δεν είχα να ανταλλάξουν.
Τελείωσα.
Έτσι, στην περίπτωση αυτή, είναι ακριβώς n ή ο αριθμός των βημάτων που μόλις
Έπρεπε να κάνουν check-in στον πρώτο κατάλογο.
>> Και μετά, τώρα χτύπησε ταξινόμηση με εισαγωγή, όπου
ο αλγόριθμος είναι ουσιαστικά να χάσμα ότι σε μια διαλογή και χωρίς διαλογή τμήμα.
Και τότε ένα προς ένα, οι τιμές είναι χωρίς διαλογή
εισάγονται σε κατάλληλα τους θέσεις στην αρχή της λίστας.
>> Έτσι, για παράδειγμα, έχουμε ένα κατάλογο των 3, 5, 2, 6, 4 και πάλι.
Γνωρίζουμε ότι είναι επί του παρόντος αδιαχώριστα, γιατί έχουμε μόνο
άρχισε να ψάχνει σε αυτό.
Θα ρίξουμε μια ματιά και να γνωρίζουμε ότι η πρώτη τιμή είναι ταξινομημένο, έτσι δεν είναι;
Αν ψάχνετε απλά σε μια σειρά από Size One, ξέρετε ότι είναι ταξινομημένο.
>> Έτσι, τότε γνωρίζουμε ότι η άλλα τέσσερα είναι αδιαχώριστα.
Έχουμε περάσει και να βλέπουμε αυτή την τιμή.
Ας πάμε πίσω.
Δείτε αυτή την τιμή 5;
Θα ρίξουμε μια ματιά σε αυτό.
Θα το συγκρίνουμε με 3.
Γνωρίζουμε ότι είναι μεγαλύτερη από ό, τι 3, έτσι ξέρουμε ότι αυτό είναι ταξινομημένο.
Έτσι τώρα ξέρουμε ότι οι δύο πρώτες κατατάσσονται και τα τρία τελευταία δεν είναι.
>> Θα ρίξουμε μια ματιά στο 2.
Εμείς πρώτα να το ελέγξετε με 5.
Είναι λιγότερο από 5;
Δεν είναι.
Έτσι πρέπει να συνεχίσουμε κοιτάζοντας προς τα κάτω.
Στη συνέχεια, μπορείτε να ελέγξετε 2 εκτός 3.
Είναι λιγότερο από ό, τι;
Κανένα.
Έτσι, ξέρετε το 2 πρέπει να εισαχθεί στην μπροστινή και 3 και 5
και οι δύο πρέπει να ωθείται προς τα έξω.
Κάνετε αυτό και πάλι με 6 και 4.
Και εμείς απλά να διατηρήσουν τον έλεγχο, κατ 'ουσίαν, όπου απλά δείτε, έλεγχος, έλεγχος.
Και μέχρι να είναι προς τη σωστή τη θέση, το είδος ακριβώς
τοποθετήστε το στη σωστή θέση, η οποία είναι όπου το όνομα προήλθε.
>> Έτσι, αυτό είναι ακριβώς ο αλγόριθμος, pseudocode per se, το είδος,
σχετικά με το πώς θα εφαρμόσουν ένα είδος εισαγωγής.
Ψευδοκώδικας είναι εδώ.
Είναι όλα σε απευθείας σύνδεση.
Μην ανησυχείτε αν σας παιδιά προσπαθεί να αντιγράψει αυτό κάτω.
Έτσι, για άλλη μια φορά, το ίδιο ποιες question-- θα ήταν το καλύτερο και το χειρότερο runtimes
για την ταξινόμηση με εισαγωγή;
Είναι πολύ παρόμοια με την τελευταία ερώτηση.
Θα σας δώσω ρε παιδιά, όπως, 30 δευτερόλεπτα για να σκεφτούμε γι 'αυτό, καθώς και.
>> ΟΚ Υπάρχει κάποιος που θέλει να δώσε μου το χειρότερο χρόνου εκτέλεσης;
Ναι.
>> Κοινό: n τετράγωνο.
>> ANDI PENG: Είναι n τετράγωνο.
Και γιατί ν τετράγωνο;
>> Κοινό: Επειδή σε αντίστροφη σειρά, έχετε
να περάσουν από n n φορές, πράγμα που is--
ANDI PENG: Ναι, ακριβώς.
Έτσι ίδιο πράγμα όπως και το είδος φούσκα.
Εάν αυτή η λίστα είναι σε φθίνουσα σειρά, είστε
Θα πρέπει να ελέγξετε πρώτα μία φορά.
Και στη συνέχεια, με κάθε πρόσθετη αξία, είστε
θα πρέπει να το ελέγξετε κατά κάθε τιμή, σωστά;
Και έτσι συνολικά, θα πάμε για να κάνει ένα n φορές πάσα άλλη ν Pass,
n είναι τετράγωνο.
Τι γίνεται στην καλύτερη περίπτωση;
Ναι.
>> Κοινό: n μείον 1, επειδή η πρώτο είναι ήδη στο τετράγωνο.
>> ANDI PENG: Λοιπόν, κοντά.
Η απάντηση είναι στην πραγματικότητα n.
Διότι, ενώ το πρώτο είναι ταξινομημένο, δεν μπορεί να actually--
εμείς απλά lucked έξω, σε το παράδειγμα αυτό, ότι 2
έτυχε να είναι ο μικρότερος αριθμός.
Αλλά αυτό δεν θα είναι πάντα η περίπτωση.
Εάν 2 είναι ήδη ταξινομημένο στην αρχή αλλά θα δούμε και υπάρχει εδώ 1,
το 1 πρόκειται να το χτύπημα.
Και αυτό πρόκειται να καταλήξει μέχρι να ανεβαίνει ούτως ή άλλως.
>> Έτσι, στην καλύτερη περίπτωση, στην πραγματικότητα είναι ακριβώς πρόκειται να είναι n.
Εάν έχετε 1, 2, 3, 4, 5, 6, 7, 8, είστε
πρόκειται να τρέξει μέσα ότι ολόκληρη η λίστα φορά
για να ελέγξετε για να δείτε αν όλα είναι μια χαρά.
Είναι σαφές σε όλους σε λειτουργία φορές από την επιλογή, καθώς;
Ξέρω ότι περνάω Αυτά είναι πραγματικά γρήγορα.
Αλλά απλά να ξέρετε ότι αν γνωρίζετε το γενικές έννοιες, θα πρέπει να είναι καλό.
ΕΝΤΆΞΕΙ.
Γι 'αυτό θα σας δώσω τα παιδιά ίσως, όπως, ένα λεπτό για να μιλήσουμε με τους γείτονές σας
σχετικά με το τι είναι μερικά μόνο από τις βασικές διαφορές
μεταξύ αυτών των τύπων των ειδών.
Θα πάμε πάνω ότι σύντομα.
Κοινό: Ω, εντάξει.
ANDI PENG: Ναι.
ΕΝΤΆΞΕΙ.
Cool, ας συνέλθει εκ νέου σε μια τάξη.
ΕΝΤΆΞΕΙ.
Έτσι, αυτό ήταν το είδος του ένα ανοιχτή ερώτηση, με την έννοια
ότι υπάρχουν πολλά απαντήσεις σε αυτά.
Και θα πάμε πάνω από κάποια από αυτά για λίγο.
Ήθελα απλώς να σας πάρει τα παιδιά σκεφτόμαστε τι διαφοροποιούνται
και οι τρεις τύποι των ειδών.
Και άκουσα, επίσης, μια μεγάλη question-- τι κάνει ταξινόμηση με συγχώνευση κάνω;
Μεγάλη ερώτηση, γιατί αυτό είναι τι είμαστε καλύπτει την επόμενη.
>> Έτσι, ταξινόμηση με συγχώνευση είναι η ένα είδος που να λειτουργεί
πολύ διαφορετικό από τα άλλα είδη.
Όπως εσείς να see-- έκανε ο David κάνει αυτό το demo
όπου είχε όλα τα δροσερά θορύβους του βλέποντας πώς να συγχωνεύσει
Ταξινόμηση έτρεξε, όπως, απείρως ταχύτερα από τους άλλους δύο τύπους;
ΕΝΤΆΞΕΙ.
Έτσι, αυτό είναι επειδή συγχώνευσης Ταξινόμηση υλοποιεί αυτό το χάσμα
και να κατακτήσει την έννοια που έχουμε μίλησε για πολλά στη διάλεξη.
Υπό αυτή την έννοια που ήθελαν να εργαστούν εξυπνότερα, όχι σκληρότερα, όταν διαιρείτε
και να κατακτήσουν τα προβλήματα, και να σπάσει τους προς τα κάτω, και στη συνέχεια να τα βάλει μαζί,
καλά πράγματα συμβαίνουν πάντα.
>> Έτσι, με τον τρόπο που συγχωνεύονται Ταξινόμηση λειτουργεί ουσιαστικά
είναι ότι χωρίζει μια αδιαχώριστα σειρά κατά το ήμισυ.
Και τότε πήρε δύο ημίχρονα των συστοιχιών.
Και ταξινομεί ακριβώς αυτά τα δύο μισά.
Κρατά μόνο τη διαίρεση κατά το ήμισυ, σε ήμισυ, κατά το ήμισυ, έως ότου όλα ταξινομημένο
και, στη συνέχεια, αναδρομικά βάζει όλα μαζί.
>> Έτσι, αυτό είναι πραγματικά αφηρημένη.
Έτσι, αυτό είναι απλά ένα κομμάτι του ψευδοκώδικα.
Μήπως αυτό έχει νόημα σε ο τρόπος που τρέχει;
Έτσι, ας πούμε ότι έχετε ένα σειρά από n στοιχεία, σωστά;
Εάν n είναι μικρότερη από 2, μπορείτε να επιστρέψετε.
Επειδή ξέρετε ότι αν υπάρχει μόνο ένα πράγμα, πρέπει να ταξινομηθούν.
Αλλιώς, μπορείτε να ταξινομήσετε το αριστερό μισό, και, στη συνέχεια, μπορείτε να ταξινομήσετε το δεξί μισό,
και στη συνέχεια θα συγχωνευθούν.
>> Έτσι, ενώ φαίνεται ότι πραγματικά εύκολη, στην πραγματικότητα, να σκεφτόμαστε ότι είναι
είδος δύσκολο. Επειδή είστε όπως, Λοιπόν, αυτό είναι το είδος του τρεξίματος στον εαυτό της.
Σωστά;
Είναι τρέχει στον εαυτό της.
Έτσι, με αυτή την έννοια, ο Δαβίδ άγγιξε κατά την αναδρομή στην τάξη.
Και αυτή είναι μια έννοια θα μιλήσουμε για περισσότερα.
Είναι ότι αυτό, αυτές οι δύο γραμμές εδώ, στην πραγματικότητα είναι μόνο το πρόγραμμα
λέγοντάς του να τρέξει η ίδια με διαφορετική είσοδο.
Έτσι, αντί να τρέξει μόνο με το σύνολο των n στοιχεία,
μπορείτε να το σπάσει σε η αριστερό μισό και το δεξιό ήμισυ
και στη συνέχεια να εκτελέσετε ξανά.
>> Και τότε θα δούμε οπτικά, επειδή είμαι ένας οπτικός τύπος.
Λειτουργεί καλύτερα για μένα.
Έτσι θα δούμε σε ένα οπτικό παράδειγμα εδώ.
>> Ας πούμε ότι έχουμε μια σειρά, έξι στοιχεία, 3, 5, 2, 6, 4, 1, δεν ταξινομούνται.
Εντάξει, υπάρχουν πολλά σε αυτή τη σελίδα.
Έτσι, αν εσείς μπορείτε να δείτε το το πρώτο βήμα εδώ, 3, 5, 2, 6, 4, 1,
μπορείτε να τεμαχιστεί σε δύο ημιμόρια.
Έχετε 3, 5, 2, 6, 4, 1.
Γνωρίζετε ότι αυτά σας aren't-- Δεν ξέρω αν είναι ταξινομημένο ή μη,
έτσι ώστε να κρατήσει το σπάσιμο τους κάτω, στη μέση, σε ένα δεύτερο, κατά το ήμισυ, μέχρι τελικά,
έχετε μόνο ένα στοιχείο.
Και ένα στοιχείο ταξινομείται πάντα, σωστά;
>> Γνωρίζουμε, λοιπόν, ότι το 3, 5, 2, 4, 6, 1, από μόνες τους, ταξινομούνται.
Και τώρα μπορούμε να τα βάλει μαζί πίσω.
Γνωρίζουμε, λοιπόν, το 3, 5.
Έχουμε βάλει μαζί εκείνους.
Γνωρίζουμε ότι είναι ταξινομημένο.
Τα 2 είναι ακόμα εκεί.
Μπορούμε να βάλουμε το 4 και το 6 μαζί.
Γνωρίζουμε ότι αυτό είναι ταξινομημένο, έτσι βάλαμε ότι μαζί.
Και το 1 είναι εκεί.
>> Και τότε θα εξετάσουμε μόνο Αυτά τα δύο μισά ακριβώς εδώ.
Έχετε το 3, 5, 2, 2, 3, 5.
Μπορείτε να συγκρίνετε μόνο η αρχή των πάντων.
Επειδή ξέρετε ότι αυτό είναι ταξινομημένο και ξέρετε ότι αυτό είναι ταξινομημένο.
Μέχρι τότε δεν χρειάζεται καν να συγκρίνετε το 5, που μόλις συγκρίνετε τις 3.
Και το 2 είναι μικρότερη από 3, έτσι Ξέρετε 2 πρέπει να πάτε στο τέλος.
>> Το ίδιο πράγμα εκεί.
Το 1 πρέπει να πάτε εδώ.
Και στη συνέχεια, όταν θα πάτε να βάλετε αυτές οι δύο τιμές μαζί,
ξέρετε ότι αυτό διαλέγεται και ξέρετε ότι αυτό είναι ταξινομημένο.
Έτσι, τότε το 1 και το 2, το 1 είναι μικρότερη από 2.
Αυτό σας λέει ότι το 1 θα πρέπει να πάτε στο τέλος αυτής της
χωρίς καν να κοιτάζει 3 ή 5.
Και τότε το 4, μπορείτε απλά ελέγξτε, πηγαίνει δεξιά εδώ.
Δεν χρειάζεται να εξετάσουμε το 5.
Το ίδιο πράγμα με το 6.
Γνωρίζετε ότι το 6-- ακριβώς δεν πρέπει να εξεταστούν.
>> Και έτσι με αυτό τον τρόπο, είστε μόνο εξοικονόμηση εαυτό σας
πολλά βήματα όταν είστε σύγκριση.
Δεν πρέπει να συγκρίνουμε κάθε στοιχείο έναντι άλλων στοιχείων.
Απλά συγκρίνετε με αυτά ότι θα πρέπει να το συγκρίνετε με.
Έτσι, αυτό είναι το είδος της μια αφηρημένη έννοια.
Μην ανησυχείτε αν δεν είναι αρκετά χτύπημα σας αμέσως ακόμα.
Αλλά γενικά, αυτό είναι πώς ένα είδος συγχώνευσης λειτουργεί.
Ερωτήσεις, γρήγορες ερωτήσεις, πριν προχωρήσω;
Ναι.
>> Κοινό: Έτσι σας είπε ότι έχετε λάβει η 1, και στη συνέχεια το 4, και το 6
και να τους θέσει σε.
Έτσι δεν είναι those-- δεν κοιτάτε τους
ως χωριστά στοιχεία, όχι ως το σύνολο;
ANDI PENG: Ναι.
Έτσι τι συμβαίνει είναι ότι βασικά
δημιουργούν ένα ολοκαίνουργιο σειρά.
Έτσι, ξέρετε ότι, εδώ, έχω δύο σειρές μεγέθους 3, σωστά;
Έτσι ξέρετε ότι ταξινομημένο πίνακα μου πρέπει να έχει έξι στοιχεία.
Έτσι, μπορείτε απλά να δημιουργήσετε ένα νέα ποσότητα μνήμης.
Έτσι είστε κάτι σαν είναι σπάταλη της μνήμης,
αλλά αυτό δεν έχει σημασία επειδή είναι τόσο μικρό.
Έτσι θα δούμε την 1 και κοιτάς το 2.
Και ξέρετε ότι το 1 είναι μικρότερη από 2.
Έτσι ξέρετε ότι 1 θα πρέπει να πάει στο η αρχή όλων εκείνων.
>> Δεν χρειάζεται καν να εξετάσουμε το 3 και το 5.
Έτσι, ξέρετε 1 πηγαίνει εκεί.
Στη συνέχεια, μπορείτε βασικά μπριζόλα από το 1.
Είναι, όπως, νεκρός για εμάς.
Στη συνέχεια, έχουμε μόνο 2, 3, 5, και στη συνέχεια 4 και 6.
Και τότε ξέρετε ότι μπορείτε συγκρίνουν το 4 και το 2,
Ω, η 2 θα πρέπει να πάει εκεί.
Έτσι θα γδούπο το 2 κάτω, να το κόψουν.
Έτσι, τότε θα πρέπει το 3 και το 5 στο 4 και στο 6.
Και απλά να κρατήσει μακριά κοπής μέχρι να τους βάλει στην σειρά.
>> Κοινό: Έτσι είστε πάντα απλά συγκρίνοντας την [δεν ακούγεται];
>> ANDI PENG: Ακριβώς.
Έτσι, με αυτή την έννοια, είστε ακριβώς συγκρίνοντας, κατ 'ουσίαν,
έναν αριθμό έναντι του άλλου αριθμού.
Και επειδή ξέρετε ότι είναι ταξινομημένο, μπορείτε
Δεν χρειάζεται να κοιτάξετε μέσα όλους τους αριθμούς.
Απλά πρέπει να εξετάσουμε την πρώτη.
Και τότε μπορείτε να γδούπο μόνο τα κάτω, επειδή ξέρετε
ανήκουν και οι οποίοι πρέπει να ανήκουν.
Ναι.
Καλή ερώτηση.
>> Και τότε, αν κάποιος από εσάς είναι λίγο φιλόδοξο,
διστάσετε να δούμε αυτόν τον κώδικα.
Αυτό είναι στην πραγματικότητα ο φυσική εφαρμογή
για το πώς θα γράφαμε ταξινόμηση με συγχώνευση.
Και μπορείτε να δείτε, είναι πολύ μικρή.
Αλλά οι ιδέες πίσω αυτό είναι αρκετά περίπλοκη.
Έτσι, εάν αισθάνεστε σαν σχέδιο αυτό έξω στο σπίτι σας απόψε, μην διστάσετε να.
>> ΕΝΤΆΞΕΙ.
Έτσι ο Δαβίδ και πήγε πάνω από αυτό στη διάλεξη.
Ποια είναι η καλύτερη περίπτωση runtimes, χειρότερη περίπτωση χρόνων εκτέλεσης,
και τα αναμενόμενα χρόνους εκτέλεσης της συγχώνευσης του είδους;
Ένα ζευγάρι δευτερόλεπτα για να σκεφτούμε.
Αυτό είναι αρκετά δύσκολο, αλλά το είδος του διαισθητική αν το σκεφτείς.
Εντάξει.
>> Κοινό: Είναι η χειρότερη περίπτωση n log n;
ANDI PENG: Ακριβώς.
Και γιατί είναι n log n.
>> Κοινό: Δεν είναι επειδή γίνεται εκθετικά πιο γρήγορα,
έτσι είναι σαν συνάρτηση του ότι αντί απλώς να είναι απλώς ν
τετράγωνο ή κάτι τέτοιο;
ANDI PENG: Ακριβώς.
Έτσι, ο λόγος για τον οποίο η Runtime σε αυτό είναι n log
n είναι because-- τι είσαι κάνει σε όλα αυτά τα βήματα;
Είσαι απλά κόψιμο στο μισό, σωστά;
Και έτσι, όταν κάνουμε το συνδεθείτε, το μόνο που θα κάνει
μοιράζει ένα πρόβλημα στη μέση, σε ένα δεύτερο, κατά το ήμισυ, σε περισσότερα μέρη.
Και με αυτή την έννοια, μπορείτε να το είδος από την εξάλειψη του γραμμικού μοντέλου
ότι έχουμε χρησιμοποιήσει.
Γιατί όταν εσείς μπριζόλα τα πράγματα στη μέση, αυτό είναι ένα αρχείο καταγραφής.
Αυτό είναι μόνο η μαθηματική τρόπος εκπροσωπούν.
>> Και στη συνέχεια, τέλος, στο τέλος, είστε απλά κάνοντας ένα τελευταίο πέρασμα από
να θέσει όλα αυτά με τη σειρά, έτσι δεν είναι;
Και έτσι, αν απλά πρέπει να ελέγχει ένα πράγμα, αυτό είναι ν.
Και έτσι είστε το είδος του πολλαπλασιάζοντας τα δύο μαζί.
Έτσι είναι σαν να έχεις αυτόν τον τελικό ελέγξτε για Ν εδώ κάτω με ένα αρχείο καταγραφής των n
μέχρι εδώ.
Και αν πολλαπλασιάσετε τους, ότι είναι n log n.
>> Και έτσι η καλύτερη περίπτωση και το χειρότερο υπόθεσης και αναμένεται όλοι n log n.
Είναι, επίσης, όπως και ένα άλλο είδος.
Είναι σαν είδος επιλογής με την έννοια ότι το
Δεν έχει σημασία τι σας κατάλογος είναι, είναι ακριβώς πρόκειται
να κάνουν το ίδιο πράγμα κάθε φορά.
ΕΝΤΆΞΕΙ.
Έτσι, όπως μπορείτε να δείτε τα παιδιά, ακόμη και αν τα είδη που έχουμε πάει through-- n
τετράγωνο, δεν είναι πολύ αποτελεσματική.
Και ακόμα και αυτή η log η είναι δεν είναι η πιο αποτελεσματική.
Αν εσείς είστε περίεργοι, υπάρχει μηχανισμοί ταξινόμησης
που είναι τόσο αποτελεσματική ώστε να είναι σχεδόν ουσιαστικά επίπεδη στο χρόνο εκτέλεσης.
>> Έχετε κάποιο ημερολόγιο του n.
Έχετε κάποιο log n του αρχείου καταγραφής.
Εμείς δεν αγγίζουν τους σε αυτή την κατηγορία αυτή τη στιγμή.
Αλλά αν εσείς είστε περίεργοι, διστάσετε να google, τι είναι
Τα πιο αποτελεσματικούς μηχανισμούς διαλογής.
Δεν ξέρω, υπάρχουν μερικά πραγματικά αστεία αυτά,
like-- υπάρχει κάποια πραγματικά αστεία αυτά που κάνουν οι άνθρωποι.
Και αναρωτιέστε πώς Σκέφτηκες ποτέ ότι.
Έτσι google, αν έχετε κάποια ανταλλακτικά ώρα, για, ποια είναι μερικά αστεία τρόπους
ότι people-- καθώς αποτελεσματική ways-- άνθρωποι
ήταν σε θέση να εφαρμόσουν τα είδη.
ΕΝΤΆΞΕΙ.
Και εδώ είναι απλά ένα πρακτικό μικρό διάγραμμα.
Ξέρω ότι όλοι σας, πριν από την κουίζ 0, θα είναι στο δωμάτιό σας, προσπαθώντας πιθανώς
να απομνημονεύσετε αυτό.
Έτσι, αυτό είναι ωραίο εκεί για σας παιδιά.
Απλά μην ξεχάσετε τη λογική που made-- γιατί αυτοί οι αριθμοί συνέβαιναν.
Εάν είστε πάντα χαθεί, απλά κάνει βεβαιωθείτε ότι γνωρίζετε ποια είναι τα είδη.
Και μπορείτε να εκτελέσετε μέσα τους στο μυαλό σας
να καταλάβω γιατί εκείνοι απαντήσεις είναι οι απαντήσεις.
>> Εντάξει.
Έτσι θα πάμε να προχωρήσουμε σε, τελικά, να αναζήτηση.
Διότι όπως εκείνους από εσάς που έχουν διαβάσει το PSET,
αναζήτηση είναι επίσης μέρος του το πρόβλημα αυτής της εβδομάδας θέτει.
Θα σας ζητηθεί να εφαρμόσουν δύο τύποι των αναζητήσεων.
Το ένα είναι ένα γραμμικό αναζήτησης και το ένα είναι ένα δυαδική αναζήτηση.
>> Έτσι, η γραμμική αναζήτηση είναι αρκετά εύκολο.
Απλά θέλετε να αναζητήσετε στοιχείου από μια λίστα για να δείτε αν μπορείτε να το πάρετε.
Απλά πρέπει να επαναλαμβάνεται σε.
Και αν αυτό ισοδυναμεί με κάτι, μπορείτε να το επιστρέψετε απλά, σωστά;
Αλλά αυτό που είμαστε πιο ενδιαφέρονται να μιλάμε για
είναι δυαδική αναζήτηση, δεξιά, η οποία είναι η διαίρει και βασίλευε μηχανισμό ο οποίος
Ο David έκανε επίδειξη στη διάλεξη.
>> Θυμηθείτε το παράδειγμα τηλεφωνικό κατάλογο ότι κρατά ανατροφή,
αυτός που έχει το είδος της πάλευε ένα κομμάτι σε αυτό το παρελθόν έτος,
όπου μπορείτε να διαιρέσετε το πρόβλημα στη μέση, κατά το ήμισυ, κατά το ήμισυ, ξανά και ξανά,
μέχρι να βρείτε αυτό που ψάχνετε;
Και έχετε το εκτέλεσης του και αυτό.
Και μπορείτε να δείτε, είναι σημαντικά πιο αποτελεσματική
από κάθε άλλο είδος της αναζήτησης.
>> Έτσι ο τρόπος που θα πάει για εφαρμογή μιας δυαδικής αναζήτησης
είναι, αν είχαμε μια σειρά, 0 δείκτης να 6, επτά στοιχεία,
μπορούμε να δούμε στη μέση, right-- Συγγνώμη, αν η ερώτησή μας first--
αν θέλουμε να θέσουμε το ερώτημα του, το κάνει η συστοιχία περιλαμβάνει το στοιχείο του 7,
προφανώς, όντας ανθρώπους, και έχουν όπως μια μικρή συστοιχία, είναι εύκολο για μας
να πω ναι.
Αλλά ο τρόπος για να εφαρμόσει ένα δυαδικό Η αναζήτηση θα ήταν να δούμε στη μέση.
>> Γνωρίζουμε ότι ο δείκτης είναι 3 η μέση, γιατί εμείς
Γνωρίζω ότι υπάρχουν επτά στοιχεία.
Ποιες 7 διαιρείται δια 2;
Μπορείτε να κόβεις ότι επιπλέον 1.
Έχετε 3 στη μέση.
Έτσι, είναι σειρά 3 ισούται με το 7;
Δεν ειναι σωστο?
Αλλά μπορούμε να κάνουμε ένα ζευγάρι των ελέγχων.
Είναι συστοιχία 3 λιγότερο από 7 ή Είναι σειρά από 3 μεγαλύτερο από 7?
>> Και ξέρουμε ότι είναι λιγότερο από το 7.
Γνωρίζουμε, λοιπόν, ότι, ω, θα πρέπει να δεν είναι στο αριστερό μισό.
Γνωρίζουμε ότι πρέπει να είναι στο δεξιό μισό, σωστά;
Οπότε μπορούμε απλά να κόψουν το ήμισυ του πίνακα.
Δεν χρειάζεται καν να κοιτάξουμε πια.
Επειδή γνωρίζουμε ότι εξάμηνο του problem-- μας
γνωρίζουμε ότι η απάντηση είναι το δεξί μισό του προβλήματός μας.
Γι 'αυτό και μόλις δούμε ότι τώρα.
>> Έτσι τώρα κοιτάμε το μέσα του ό, τι έχει απομείνει.
Ότι ο δείκτης 5.
Εμείς κάνουμε πάλι το ίδιο επιταγή και βλέπουμε ότι είναι μικρότερα.
Έτσι, βλέπουμε στα αριστερά του ότι.
Και τότε θα δούμε ότι η επιταγή.
Είναι η τιμή σε σειρά Δείκτης 4 ίσο με 7;
Είναι.
Έτσι, μπορούμε να επιστρέψουμε αλήθεια, επειδή βρήκαμε την τιμή στην λίστα μας.
Μήπως ο τρόπος που πέρασε που έχουν νόημα για όλους;
ΕΝΤΆΞΕΙ.
Θα σας δώσω τα παιδιά ίσως, όπως, τρία, τέσσερα λεπτά για να καταλάβω
πώς να pseudocode αυτό.
>> Φανταστείτε λοιπόν Σου ζήτησα να γράψει ένα λειτουργία που ονομάζεται αναζήτησης () που επέστρεψε
μια τιμή, μια τιμή Boolean, αυτό ήταν αλήθεια ή false-- όπως,
αλήθεια αν βρεθεί η τιμή, ψευδή αν δεν το έκανε.
Και τότε θα ήταν πέρασε στην αξία σας
έψαχναν σε αξίες, οι οποίες είναι η array-- OH, εγώ σίγουρα θέσει
ότι σε λάθος μέρος.
ΕΝΤΆΞΕΙ.
Anyways, ότι θα πρέπει να έχουν ήταν στα δεξιά της αξίες.
Και τότε int n είναι ο αριθμός των στοιχείων του εν λόγω πίνακα.
Πώς θα πάτε για την προσπάθεια να pseudocode αυτό το πρόβλημα μέσα;
Θα σας δώσω παιδιά, όπως τρία λεπτά για να το κάνουμε αυτό.
Όχι, νομίζω ότι υπάρχει only-- Ναι, υπάρχει ένα δικαίωμα εδώ.
Κοινό: Μπορώ;
ANDI PENG: Ναι, έχεις.
Είναι αυτό εργασίας;
ΟΚ κομπλε.
>> ΕΝΤΆΞΕΙ.
Όλα τα παιδιά σωστά, είμαστε πρόκειται να χαλιναγωγήσει.
ΕΝΤΆΞΕΙ.
Έτσι υποθέσουμε ότι έχουμε αυτό το υπέροχο λίγο συστοιχία με τιμές n σε αυτό.
Δεν είχα τη χάραξη των γραμμών.
Αλλά πώς θα πάει για προσπαθώντας να γράψω αυτό;
Υπάρχει κάποιος που θέλει να να μου δώσει την πρώτη γραμμή;
Αν θέλετε να μου δώσετε το πρώτη γραμμή αυτού του ψευδοκώδικα.
>> Κοινό: [δεν ακούγεται]
Κοινό: Θα θέλατε να επαναλάβει through--
Κοινό: Ακριβώς ένα άλλο για βρόχο;
Κοινό: --για.
>> ANDI PENG: Έτσι, αυτό και μόνο είναι λίγο δύσκολο.
Σκεφτείτε about-- θέλετε να συνεχίσει να τρέχει αυτό το βρόχο
ξανά και ξανά μέχρι πότε;
>> Κοινό: Μέχρι την [δεν ακούγεται] τιμή είναι ίση με αυτή την τιμή.
ANDI PENG: Ακριβώς.
Έτσι μπορείτε πραγματικά ακριβώς write-- μπορούμε να απλοποιήσει ακόμη περισσότερο.
Μπορούμε να κάνουμε μόνο ένα βρόχο, ενώ, σωστά;
Έτσι, μπορείτε να έχετε μόνο loop-- ξέρουμε ότι είναι μια στιγμή.
Αλλά για τώρα, θα πάω να πει "θηλιά" - μέσα από αυτό;
Loop until-- ό, τι είναι που λήγει την κατάσταση μας;
Νομίζω ότι άκουσα.
Άκουσα κάποιον να το πω.
>> Κοινό: Οι τιμές ισούται μέση.
ANDI PENG: το πω και πάλι.
Κοινό: Ή, έως ότου η αξία ψάχνετε
είναι ίσο με την μέση τιμή.
>> ANDI PENG: Τι θα συμβεί αν δεν είναι εκεί;
Τι θα συμβεί αν η αξία ψάχνετε για να μην είναι στην πραγματικότητα σε αυτήν την σειρά;
Κοινό: Μπορείτε να επιστρέψετε 1.
>> ANDI PENG: Αλλά αυτό που θέλουμε να βρόχο μέχρι αν έχουμε μια κατάσταση;
Ναι.
>> Κοινό: Μέχρι υπάρχει μόνο μία τιμή;
ANDI PENG: Μπορείτε βρόχο until-- ώστε να γνωρίζετε ότι είστε
πρόκειται να έχουν μια μέγιστη τιμή, σωστά;
Και ξέρετε ότι θα πάμε να έχουν μια ελάχιστη τιμή, σωστά;
Επειδή, επίσης, ότι αυτό είναι κάτι Ξέχασα να πω πριν,
ότι κάτι που είναι κρίσιμη για την δυαδική αναζήτηση
είναι ότι η σειρά σας είναι ήδη ταξινομημένο.
Επειδή δεν υπάρχει τρόπος να γίνει Αυτό κι αν είναι απλά τυχαίες τιμές.
Δεν ξέρω αν κάποιος είναι μεγαλύτερο από το άλλο, έτσι δεν είναι;
>> Έτσι ξέρετε ότι max σας και λεπτά σας εδώ, έτσι δεν είναι;
Αν πρόκειται να την προσαρμογή max σας σε λεπτά και τα mid--
ας υποθέσουμε σας μέσα τιμή είναι σωστή here--
θα πάμε να βασικά βρόχο μέχρι το ελάχιστο ποσό σας είναι
περίπου το ίδιο με το μέγιστο σας, δεξιά, ή αν max σας δεν είναι το ίδιο με το λεπτό σου.
Σωστά;
Γιατί όταν συμβεί αυτό, ξέρετε ότι έχετε χτυπήσει τελικά την ίδια αξία.
Έτσι θέλετε να βρόχο μέχρι λεπτά σας είναι μικρότερη ή ίση to-- ουπς,
όχι λιγότερο από ή ίσο με, ο άλλος τρόπος around-- max είναι.
>> Μήπως αυτό έχει νόημα;
Πήρα μερικές προσπάθειες για να πάρει αυτό το δικαίωμα.
Αλλά βρόχο μέχρι Μέγιστη τιμή σας είναι ουσιαστικά σχεδόν λιγότερο
από ή ίσο με το ελάχιστο σου, σωστά;
Αυτό είναι όταν ξέρεις ότι έχετε συγκλίνει.
Κοινό: Πότε θα το μέγιστο αξία είναι μικρότερη από την ελάχιστη;
ANDI PENG: Εάν έχετε κρατήσει προσαρμόζοντάς τον, η οποία
είναι αυτό που πρόκειται πρέπει να κάνουμε σε αυτό.
Βγάζει νόημα αυτό?
Ελάχιστη και μέγιστη είναι μόνο ακέραιοι που είναι πιθανόν
πρόκειται να θέλουν να δημιουργήσουν για να κρατήσει παρακολουθείτε όπου ψάχνουμε.
Επειδή υπάρχει η συστοιχία ανεξάρτητα από το τι κάνουμε.
Όπως, δεν είμαστε πραγματικά σωματικά κόβοντας τη σειρά, έτσι δεν είναι;
Είμαστε ακριβώς προσαρμογή όπου ψάχνουμε.
Βγάζει νόημα αυτό?
>> Κοινό: Ναι.
>> ANDI PENG: OK.
Έτσι, αν αυτή είναι η προϋπόθεση για την θηλιά μας, Τι θέλουμε μέσα από αυτό το βρόχο;
Τι πρόκειται να θέλουν να κάνουν;
Έτσι τώρα, έχουμε ένα μέγιστο και ένα λεπτό, δεξιά,
πιθανότατα δημιουργήθηκε εδώ κάπου.
Εμείς πάμε για να θελήσει πιθανώς να βρούμε μια μέση, έτσι δεν είναι;
Πώς θα πάμε να είναι είναι σε θέση να βρει τη μέση;
Ποια είναι η mathematical--
Κοινό: Max συν min διαιρείται δια 2.
ANDI PENG: Ακριβώς.
Βγάζει νόημα αυτό?
Και εσείς δεν βλέπω το λόγο γιατί Δεν έκανε ακριβώς use-- γιατί το κάναμε αυτό
αντί να κάνει ακριβώς n διαιρείται με 2;
Είναι επειδή η είναι η αξία ότι πρόκειται να παραμείνει το ίδιο.
Σωστά;
Αλλά όπως έχουμε προσαρμόσει τις ελάχιστες μας και μέγιστες τιμές, πρόκειται να αλλάξει.
Και ως αποτέλεσμα, το μεσαίο μας πρόκειται να αλλάξει πάρα πολύ.
Έτσι, γι 'αυτό θέλουμε για να κάνουμε αυτό το δικαίωμα εδώ.
ΕΝΤΆΞΕΙ.
>> Και τότε, τώρα που έχουμε βρει our-- ναι.
>> Κοινό: Απλά μια γρήγορη question-- όταν λέτε min και max,
μήπως έχουμε υποθέσει ότι είναι ήδη ταξινομημένο;
>> ANDI PENG: Ναι, αυτό είναι πραγματικά ένα Προϋπόθεση για μια δυαδική αναζήτηση,
ότι θα πρέπει να ξέρετε ότι είναι ταξινομημένο.
Αυτός είναι ο λόγος ταξινόμησης, γράφετε στο σας πρόβλημα που πριν δυαδική αναζήτηση σας.
ΕΝΤΆΞΕΙ.
Έτσι τώρα που ξέρουμε πού μέσο μας είναι, τι θέλετε να κάνετε εδώ;
>> Κοινό: Θέλουμε να συγκρίνετε ότι στο άλλο.
ANDI PENG: Ακριβώς.
Έτσι θα πάμε να συγκρίνετε μέσα στην τιμή, έτσι δεν είναι;
Και τι σημαίνει αυτό πείτε μας όταν συγκρίνουμε;
Τι θέλουμε να κάνουμε μετά;
>> Κοινό: Αν η τιμή είναι μεγαλύτερη από τα μέσα της δεκαετίας, θέλουμε να το κόψει.
ANDI PENG: Ακριβώς.
Έτσι, αν η τιμή είναι μεγαλύτερη από τα μέσα της δεκαετίας, είμαστε
Πρόκειται να θελήσετε να αλλάξετε αυτές ελάχιστο και Maxes, σωστά;
Τι θέλουμε να αλλάξουμε;
Έτσι, αν γνωρίζουμε ότι η τιμή είναι κάπου εδώ, τι κάνουμε εμείς για να αλλάξουμε;
Θέλουμε να αλλάξουμε μας ελάχιστο να είναι μέσα, σωστά;
Και τότε τι άλλο, αν είναι σε αυτό το ήμισυ, τι θέλουμε να αλλάξουμε;
>> Κοινό: κατ 'ανώτατο όριο σας.
ANDI PENG: Ναι.
Και τότε είστε ακριβώς πρόκειται να κρατήσει looping, σωστά;
Γιατί τώρα, μετά από μία επανάληψη μέσα, έχεις ένα μέγιστο εδώ.
Και στη συνέχεια, μπορείτε να υπολογίσετε εκ νέου ένα μέσα.
Και τότε μπορείτε να συγκρίνετε.
Και θα πάμε να συνεχίσω μέχρι τα λεπτά και τα Maxes
έχουν ουσιαστικά συγκλίνει.
Και αυτό είναι όταν ξέρεις ότι έχετε χτυπήσει το τέλος της.
Και είτε το έχεις βρει ή δεν έχετε σε αυτό το σημείο.
>> Μήπως αυτό έχει νόημα για όλους;
ΕΝΤΆΞΕΙ.
Αυτό είναι πολύ σημαντικό, επειδή θα έχετε
να γράψω αυτό τον κωδικό σας απόψε.
Αλλά εσείς έχετε μια αρκετά καλή αίσθηση του τι θα έπρεπε να κάνετε,
το οποίο είναι καλό.
ΕΝΤΆΞΕΙ.
Έτσι έχουμε περίπου επτά λεπτά αριστερό μέρος.
Έτσι θα πάμε να μιλήσουμε για αυτό το chipset που θα κάνουμε.
Έτσι, η PSET διαιρείται σε δύο ίσα μέρη.
Το πρώτο εξάμηνο περιλαμβάνει εφαρμογή εύρεσης
στην οποία μπορείτε να γράψετε μια γραμμική αναζήτηση, μια δυαδική αναζήτηση, και ένας αλγόριθμος ταξινόμησης.
>> Έτσι, αυτό είναι το πρώτο φορά σε PSET όπου
θα δίνουμε εσείς αυτό που ονομάζεται Κώδικα Διαχείρισης του Δικτύου, η οποία είναι ο κωδικός
ότι έχουμε προ-γραπτά, αλλά μόλις έφυγε μερικά κομμάτια off
για να ολοκληρώσετε το γράψιμο.
Έτσι ρε παιδιά, όταν κοιτάς αυτό κωδικό, μπορείτε να πάρετε πραγματικά φοβισμένη.
Αν θέλετε, Ααα, εγώ απλά Δεν ξέρω τι κάνει,
Δεν ξέρω, όπως, φαίνεται ότι τόσο περίπλοκη, Ααα, να χαλαρώσετε.
Είναι εντάξει.
Διαβάστε το spec.
Το spec θα σας εξηγήσει ακριβώς τι κάνουν όλα αυτά τα προγράμματα.
>> Για παράδειγμα, generate.c είναι ένα πρόγραμμα ότι θα έρθει με το chipset σας.
Δεν χρειάζεται πραγματικά να το αγγίξει, αλλά θα πρέπει να καταλάβουν τι κάνει.
Και generate.c, το μόνο που κάνουν είναι είναι είτε τη δημιουργία τυχαίων αριθμών
ή μπορείτε να του δώσετε ένα σπόρο, σαν ένα προσχεδιασμένο αριθμό που παίρνει,
και παράγει περισσότερους αριθμούς.
Έτσι, υπάρχει ένας συγκεκριμένος τρόπος για να εφαρμογή generate.c στην οποία
μπορείτε να κάνετε απλά μια δέσμη των αριθμών για να μπορείτε να δοκιμάσετε άλλες μεθόδους σας.
>> Έτσι, αν θέλετε, για παράδειγμα, ελέγξτε εύρημα σας,
που θα ήθελαν να τρέχουν generate.c, παράγουν μια δέσμη των αριθμών,
και στη συνέχεια να εκτελέσετε τη λειτουργία βοηθοί σας.
Λειτουργία σας είναι βοηθοί όπου είστε στην πραγματικότητα φυσικά να γράφετε κώδικα.
Και σκεφτείτε βοηθοί ως αρχείο βιβλιοθήκης είστε γραπτώς ότι εύρημα καλεί.
Και έτσι μέσα helpers.c, θα κάνει την αναζήτηση και τη διαλογή.
>> Και τότε θα πάμε σε ουσιαστικά απλά να τους βάλω όλους μαζί.
Το spec θα σας πει πώς να θέσουμε ότι στη γραμμή εντολών.
Και θα είστε σε θέση να εξετάσουμε αν Δεν το είδος και την αναζήτηση εργασίας σας.
Cool.
Έχει κανείς ήδη ξεκινήσει και αντιμετώπισαν προβλήματα ή ερωτήσεις
έχουν τώρα με αυτό;
ΕΝΤΆΞΕΙ.
>> Κοινό: Περιμένετε.
Έχω μία ερώτηση.
>> ANDI PENG: Ναι.
>> Κοινό: Έτσι άρχισα να κάνω η γραμμική αναζήτηση σε helpers.c
και δεν ήταν πραγματικά λειτουργεί.
Στη συνέχεια, όμως αργότερα, έμαθα απλά πρέπει να το διαγράψετε και να κάνει δυαδική αναζήτηση.
Έτσι, έχει σημασία αν δεν λειτουργεί;
>> ANDI PENG: Σύντομη απάντηση είναι όχι.
Αλλά δεδομένου ότι είμαστε not--
Κοινό: Αλλά κανείς δεν είναι στην πραγματικότητα τον έλεγχο.
ANDI PENG: Είμαστε ποτέ Θα δείτε ότι.
Αλλά ίσως θέλετε να κάνετε βέβαιος αναζήτησή σας λειτουργεί.
Διότι, αν γραμμική σας Η αναζήτηση δεν λειτουργεί,
τότε οι πιθανότητες είναι δυαδική σας Η αναζήτηση δεν πρόκειται να λειτουργεί τόσο καλά.
Επειδή έχετε παρόμοια λογική και στις δύο από αυτές.
Και όχι, δεν έχει τόση σημασία.
Έτσι, οι μόνοι που θα στραφούν σε είδος και είναι δυαδική αναζήτηση.
Ναι.
>> Και, επίσης, πολλά παιδιά ήταν προσπαθεί να συγκεντρώσει helpers.c.
Δεν είστε πραγματικά επιτρέπονται για να το κάνουμε αυτό, γιατί helpers.c
δεν έχει μια κύρια λειτουργία.
Και έτσι θα πρέπει μόνο είναι στην πραγματικότητα κατάρτιση
να δημιουργήσει και να βρει, επειδή βρίσκουν κλήσεις helpers.c και οι λειτουργίες μέσα σε αυτό.
Έτσι ώστε να κάνει debugging ένας πόνος στην άκρη.
Αλλά αυτό είναι ό, τι πρέπει να κάνουμε.
Κοινό: Απλά κάνει όλα, έτσι δεν είναι;
ANDI PENG: Μπορείτε μόνο κάνει όλους καθώς, ναι.
ΕΝΤΆΞΕΙ.
Έτσι ώστε να είναι σε σχέση με το τι η PSET ζητά από όλους σας να κάνετε.
Εάν έχετε οποιεσδήποτε ερωτήσεις, αισθάνονται ελεύθερη να με ρωτήσει αφού το τμήμα.
Θα είμαι εδώ για, όπως, 20 λεπτά.
>> Και ναι, οι PSET του Πραγματικά δεν είναι τόσο άσχημα.
Εσείς θα πρέπει να είναι εντάξει.
Αυτά, απλώς ακολουθήστε τις κατευθυντήριες γραμμές.
Είδος έχουν μια αίσθηση της, λογικά, τι θα πρέπει να συμβαίνει και θα είστε μια χαρά.
Να μην είστε πάρα πολύ φοβισμένοι.
Υπάρχει μια πολύ κώδικα ήδη γραμμένο εκεί.
Μην να είναι πάρα πολύ φοβισμένος αν δεν το κάνετε καταλαβαίνουν τι όλα αυτά μέσα.
Αν είναι πολλά, είναι εντελώς καλά.
Και να έρθουν σε ώρες γραφείου.
Θα σας βοηθήσουμε να ρίξετε μια ματιά.
>> Κοινό: Με το επιπλέον λειτουργίες, δεν βλέπουμε εκείνους επάνω;
>> ANDI PENG: Ναι, αυτά είναι στον κώδικα.
Στο παιχνίδι του 15, ένα δεύτερο του είναι ήδη γραμμένο για εσάς.
Έτσι, οι λειτουργίες αυτές είναι ήδη στον κώδικα.
Ναι.
Εντάξει.
Λοιπόν, καλή τύχη.
Είναι ένα αηδιαστικό ημέρα.
Έτσι, ελπίζουμε ότι εσείς δεν αισθάνεστε πάρα πολύ άσχημα για την διαμονή τους στο εσωτερικό και κωδικοποίησης.