[Powered by Google Translate] [Ενότητα 3] [λιγότερο άνετα]
>> [Nate Hardison] [Πανεπιστήμιο του Χάρβαρντ]
>> [Αυτό είναι CS50.] [CS50.TV]
>> Εντάξει, ας ξεκινήσουμε.
Καλώς ήρθατε στην Εβδομάδα 4 του CS50.
Αν εσείς ανοίξει ένα πρόγραμμα περιήγησης στο Web και να ανοίξουν PSET 3,
Scramble με CS50, θα πάμε να αρχίσει να πηγαίνει
μέσα από το τμήμα των ερωτήσεων εκεί.
Ακριβώς όπως και την περασμένη εβδομάδα, θα πρέπει να εργάζονται σε χώρους CS50,
αν θα τραβήξει επίσης ότι μέχρι καθώς,
και αν πάτε μπροστά και να επισκεφτείτε αυτό το σύνδεσμο που έχω εδώ στην κορυφή.
Ήρθε η ώρα να ξεκινήσετε.
Έχουμε μικρό πρόγραμμα γεια μας εδώ. Τίποτα τρελό.
Ένα από τα πρώτα πράγματα που θέλω να κάνω μαζί σας σήμερα είναι να πάτε σε μερικές λύσεις
Πρόβλημα με Σετ 1, το είδος των λύσεων παράδειγμα,
ακριβώς έτσι μπορείτε να πάρετε μια ιδέα για το τι είδους προσωπικό κώδικα γραφής,
τι είδους κώδικα άλλους μαθητές γράφουν,
και πρέπει να ρίξετε μια ματιά σε αυτό, γιατί ξέρω ότι είναι παράξενο
όταν υποβάλλετε μια λύση σε ένα πρόβλημα σετ και να πάρει σχόλια
για τη δική σας εκδοχή, αλλά μερικές φορές είναι χρήσιμο να δούμε πώς άλλοι άνθρωποι το έκαναν,
ειδικά αυτά που είναι ωραίο αναζητούν.
Για το μεγαλύτερο μέρος, ήμουν πραγματικά εντυπωσιασμένος με τις λύσεις που εσείς παράγεται.
Δεν έχουν ακόμη αρχίσει να εξετάζουν 2s Πρόβλημα Set σας, αλλά αν είστε τίποτα όπως και το πρώτο,
αυτό δεν σημαίνει τίποτα, αλλά τα καλά πράγματα.
>> Αν κοιτάξετε τις αναθεωρήσεις μου, ας ξεκινήσουμε όλη τη διαδρομή σε Αναθεώρηση 1,
και θα πάμε να ρίξουμε μια γρήγορη ματιά σε μια λύση Mario.
Αν τραβήξετε αυτό επάνω, αυτά τα προγράμματα που πρόκειται να παρουσιάσει είναι σωστές.
Δεν υπήρχαν προβλήματα με την ορθότητα αυτών των προβλημάτων, αλλά μάλλον,
θέλουμε να μιλήσουμε λίγο για τα διάφορα θέματα σχεδιασμού
που ήταν να χρησιμοποιηθεί εδώ.
Ένα από τα πράγματα που ήταν ενδιαφέρον για τη λύση
είναι ότι χρησιμοποιείται αυτή η νέα δομή που ονομάζεται κιλό καθορίζουν,
μερικές φορές αναφέρεται επίσης ως ένα hash ορίζουν.
Επιτρέψτε μου να εστιάσετε σε αυτό εδώ.
Ένα # define σας επιτρέπει να δώσετε ονόματα σε αυτούς τους αριθμούς στο πρόγραμμά σας.
Σε αυτή την περίπτωση, το μέγιστο ύψος της πυραμίδας στο Mario
ήταν 23 και όχι 23 σε βάζοντας τον κωδικό μου-
θα αναφέρεται ότι όσο πιο σκληρά κωδικοποίηση 23 -
αντί να δίνει αυτό το όνομα MAX_HEIGHT σε αυτόν τον αριθμό,
έτσι ώστε εδώ κάτω σε do-while loop μου
μπορείτε πραγματικά να αναφέρονται σε MAX_HEIGHT
αντί να τον αριθμό 23 μέσα
[Φοιτητικό] Ποιο είναι το πλεονέκτημα του να κάνει αυτό;
Αυτό είναι ένα μεγάλο ερώτημα.
Το ένα είναι αναγνωσιμότητα.
Ένα πλεονέκτημα της χρήσης αυτής # define είναι αναγνωσιμότητα.
Όταν είμαι ανάγνωση αυτού του κώδικα, μπορώ να δω τι συμβαίνει.
>> Μπορώ να δω σε αυτή την κατάσταση εδώ που δοκιμάζουμε
για το ύψος που είναι <0, το οποίο θα μπορούσε επίσης να οριστεί
να είναι ένα ελάχιστο ύψος ή ένα ύψος min.
Το άλλο πλεονέκτημα είναι ότι μπορώ να διαβάσω τότε το υπόλοιπο της γραμμής για να δείτε
ότι είμαστε επίσης έλεγχο για να βεβαιωθείτε ότι το ύψος δεν είναι μεγαλύτερο από το ύψος max,
επειδή θα πάμε να συνεχιστεί, ενώ το ύψος είναι μεγαλύτερο από το ύψος max.
Το άλλο πλεονέκτημα είναι-αν σμίκρυνση λίγο εδώ-
αν μπορώ να εκτελέσω αυτό το πρόγραμμα και το τρέχω, ας πούμε, με 23 αυτή τη στιγμή,
θα εκτυπώσει όλες τις 23 σειρές έτσι απλά.
Αλλά να πω ότι ήθελε να αλλάξει το ύψος max,
και τώρα θέλω να περιορίσει το μέγιστο ύψος των πυραμίδων
να πω μόνο-ο άνθρωπος, που ήταν funky.
# Include , # define MAX_HEIGHT,
και ας πούμε ότι ήθελε να το θέσει ίση με το 10.
Τώρα, σε αυτό το σημείο, το μόνο που είχα να κάνω ήταν να το αλλάξετε σε αυτή τη θέση ένα.
Μπορώ να μεταγλωττίσετε τον κώδικα, και τώρα προσπαθώ, αν και πληκτρολογήστε σε 12,
θα ζητήσει και πάλι μου.
Σε αυτή την περίπτωση, χρησιμοποιούμε μόνο μία φορά MAX_HEIGHT.
Δεν είναι ότι οι μεγάλες από μια ταλαιπωρία για να πάει σε
και να αλλάξει το βρόχο, ενώ αν χρειαστεί.
Αλλά σε προγράμματα όπου και αν αναφορά τον ίδιο αριθμό μαγεία
ξανά και ξανά, αυτό ορίζουν # μηχανισμός είναι πολύ βολικό
γιατί το μόνο που αλλάζει είναι μία φορά στην κορυφή του αρχείου είναι συνήθως όπου βάζετε τους-
και η αλλαγή διαπερνά το υπόλοιπο του αρχείου.
>> Άλλα πράγματα που ήθελα να σημειωθεί σε αυτό το εργαστήριο που νόμιζα ότι φαινόταν πολύ ωραία,
ήταν η ονομασία των μεταβλητών.
Βλέπετε ότι εδώ έχουμε ακέραιες μεταβλητές που ονομάζεται γραμμή και ονομάζεται ύψος.
Χώροι, hashes, αυτό βοηθά στο να γίνει ο κώδικας είναι λίγο πιο ευανάγνωστη,
καθιστά λίγο πιο κατανοητό το τι πραγματικά συμβαίνει.
Αυτό είναι σε αντίθεση με τη χρήση, για παράδειγμα, τυχαία γράμματα
ή απλά εντελώς αλαμπουρνέζικα.
Ένα τελευταίο πράγμα που θα επισημάνω είναι ότι για βρόχους,
Συχνά αυτές οι μεταβλητές iterator, οι μετρητές που χρησιμοποιείτε σε σας για βρόχους,
είναι πρότυπο και για τους συμβατικούς ξεκινήσει είτε με i και j τότε και έπειτα k
και συνεχίζεται από εκεί, αν χρειάζεστε περισσότερες μεταβλητές,
και αυτό είναι μόνο μια σύμβαση.
Υπάρχουν πολλές συμβάσεις.
Εξαρτάται από τη γλώσσα προγραμματισμού που χρησιμοποιείτε.
Αλλά σε C, που συνήθως αρχίζουν με το i.
Δεν έχει νόημα να χρησιμοποιήσει, ας πούμε, ένα ή β
ανάλογα με την κατάσταση.
Αυτός είναι αυτό για αυτό.
Αν τώρα σηκώσει Αναθεώρηση 2, θα δείτε ένα άλλο Mario,
και αυτό είναι παρόμοιο με το άλλο που μόλις είδαμε,
αλλά κάνει κάτι το είδος της δροσερό.
Αν κοιτάξουμε αυτό το τμήμα ακριβώς εδώ μέσα στο εσωτερικό για βρόχο,
από όπου και αν χρησιμοποιούν κάποια τρελή σύνταξη που αναζητούν εδώ ακριβώς σε αυτή τη γραμμή.
Αυτό ονομάζεται χειριστής τριαδικό.
Πρόκειται για μια δήλωση αν άλλος συμπυκνώνεται σε μία γραμμή.
Η κατάσταση είναι αυτό το μέρος μέσα σε παρένθεση.
Είναι ισοδύναμο με λέγοντας ότι αν j <ύψος - i - 1.
Και τότε τι τα περιεχόμενα του ότι αν μπλοκ θα είναι ο χώρος
και στη συνέχεια, το περιεχόμενο του τι άλλο θα είναι αυτό το #.
Είναι ουσιαστικά μια εκχώρηση χώρου για αυτή τη μεταβλητή.
Είναι βάζοντας ένα χώρο στα περιεχόμενα του μπλοκ μεταβλητής,
αν πληρούται η προϋπόθεση αυτή, αν και ο όρος δεν πληρούται,
τότε η μεταβλητή παίρνει το μπλοκ #.
Και στη συνέχεια, φυσικά, αντί της οικοδόμησης ενός ολόκληρου συμβολοσειρά
εκτύπωση και πάντα στο τέλος η λύση θα εκτυπώνει ένα χαρακτήρα κάθε φορά.
Αρκετά δροσερό.
>> Ένα άλλο ζευγάρι από τα πράγματα να δούμε. Θα προχωρήσουμε σε άπληστους.
Τώρα, αν κοιτάξουμε άπληστοι, αυτή η πρώτη λύση
χρησιμοποιεί αυτά τα # καθορίζει αρκετά.
Έχουμε μία σταθερά που ορίζεται για κάθε μία από τις διαφορετικούς αριθμούς σε αυτό το πρόγραμμα.
Έχουμε ένα για σεντς ανά δολάριο, ένα για τρίμηνα, δεκάρες, πεντάρες, και πένες,
και τώρα αν μετακινηθείτε προς τα κάτω και να διαβάσετε τον κωδικό,
μπορούμε να δούμε μια τυπική κάνει-ενώ όλα εκτύπωση loop out.
Είδος την ουσία του προβλήματος αυτού ήταν να συνειδητοποιούν ότι
που απαιτούνται για τη μετατροπή του πλωτήρα που μπορείτε να διαβάσετε μέσα από τον χρήστη σε ακέραιο
να γίνει με ακρίβεια τα μαθηματικά, και αυτό οφείλεται στο γεγονός ότι
με αριθμούς κινητής υποδιαστολής, όπως μιλήσαμε για λίγο σε διάλεξη,
δεν είναι δυνατόν να αντιπροσωπεύουν με ακρίβεια την παραμικρή αξία για τον αριθμό γραμμής
επειδή υπάρχουν απείρως πολλές τιμές μεταξύ 3 και, ας πούμε, 3,1 ακόμα.
Μπορείτε να έχετε 3,01 και 3,001 και 3,0001, και μπορείτε να συνεχίσετε.
Αποδεικνύεται κάθε φορά που εργάζεστε με τα χρήματα, που συχνά θέλετε να το μετατρέψετε
σε ακέραια μορφή, έτσι ώστε δεν είστε χάσει τις πένες και τέτοιου είδους πράγματα.
Να κάνει ότι και η στρογγυλοποίηση ήταν το κλειδί.
Η λύση αυτή χρησιμοποιείται μια τέλεια απλή, μεγάλη αλγόριθμος,
η οποία μειώνεται ο αριθμός των λεπτών που απομένει, πρώτα από τρίμηνα,
έπειτα από δεκάρες, στη συνέχεια, από επινικελώνουν, στη συνέχεια, από τις πένες,
και προσθέτοντας με τον αριθμό των κερμάτων κάθε φορά.
>> Μια άλλη λύση που θα δούμε, όπως σμίκρυνση και να πάει στην αναθεώρηση 4,
είχε μια πολύ παρόμοια αρχή, αλλά αντ 'αυτού χρησιμοποιείται div και mod
δικαίωμα εδώ για να υπολογίσει τον αριθμό των λεπτών.
Αυτό, ο αριθμός των τεταρτημορίων είναι ίσος με τον αριθμό των λεπτών διαιρούμενο με 25,
και ο λόγος για αυτό είναι επειδή λειτουργεί κάνουμε διαίρεσης,
έτσι είναι απορρίπτοντας κάθε υπόλοιπο.
[Φοιτητικό] Έχουμε να σχολιάσει την έρευνα;
Εξαρτάται πραγματικά.
[Φοιτητικό] Είσαι σχολιάζοντας περισσότερο από ό, τι κώδικα εδώ.
Ναι, και έτσι υπάρχουν ένα σωρό διαφορετικές φιλοσοφίες για το θέμα αυτό.
Προσωπική φιλοσοφία μου είναι ότι ο κωδικός σας είναι πραγματικά η αλήθεια,
όπως τον κωδικό σας είναι ό, τι είναι στην πραγματικότητα εκτελείται στον υπολογιστή,
και έτσι κωδικός σας πρέπει να είναι όσο το δυνατόν περισσότερο αναγνώσιμη να μην απαιτήσει ως πολλά σχόλια.
Τούτου λεχθέντος, όταν κάνετε πράγματα που είναι δύσκολο είδος μαθηματικά
ή αλγοριθμικά, είναι καλό να σχολιάσει αυτές έτσι ώστε να μπορείτε να
προσθέσετε μια επιπλέον διάσταση, ένα επιπλέον στρώμα σε όποιον διαβάζει τον κωδικό σας.
Σε αυτές τις λύσεις, συχνά είναι πιο βαριά σχολίασε μόνο και μόνο επειδή
θέλουμε να είμαστε σε θέση να τα διανείμουν και να έχουν οι άνθρωποι να τις παραλάβετε
και να τους διαβάσει αρκετά εύκολα.
Αλλά σίγουρα, θα συμφωνήσω ότι αυτό είναι βαρύ.
[Φοιτητικό] Όμως, σε περίπτωση αμφιβολίας, να βαρύτερο;
Σε περίπτωση αμφιβολίας, να βαρύτερο.
Μερικοί άνθρωποι θα πουν μερικές φορές 0 Επιστροφή ή κάτι τέτοιο.
Νομίζω ότι είναι ένα γελοίο σχόλιο.
Είναι σαφές ότι αυτό είναι ό, τι συμβαίνει.
Δεν χρειάζεται Ελληνικά να μου πει ότι.
Μερικές φορές οι άνθρωποι θα γράψουν πράγματα όπως "kthxbai!"
Αυτό είναι το είδος του χαριτωμένο, αλλά και μη-
Αυτό δεν είναι που κάνουν τη διαφορά μεταξύ σχολιάζοντας τα σημεία ή όχι.
Αυτά τα είδη των σχολίων είναι απλά χα, χα.
Cool.
>> Σε αυτό το σημείο, ας αρχίσουν να εργάζονται για το πρόβλημα Σετ 3 τμήμα των ερωτήσεων.
Αν εσείς τραβήξει αυτό και πάλι,
όπως με την προηγούμενη εβδομάδα, εμείς δεν πρόκειται να παρακολουθήσουν τα σορτς σε αυτή την ενότητα.
Θα σας αφήσει να το κάνετε αυτό ρε παιδιά στον ελεύθερο χρόνο σας και να μιλήσουμε για τις ερωτήσεις.
Τώρα, όμως, σε αυτή την ενότητα θα πάμε να περάσετε λίγο περισσότερο χρόνο
μιλάμε για λιγότερο από τα βασικά κωδικοποίησης
όπως κάναμε και την περασμένη εβδομάδα, και αντ 'αυτού, θα πάμε να επικεντρωθεί περισσότερο στην
λίγο περισσότερο από τη θεωρία, έτσι μιλάμε για δυαδική αναζήτηση και στη συνέχεια, τη διαλογή.
Από όσους από εσάς έχουν παρακολουθήσει μαζί με τη διάλεξη,
μπορεί κάποιος να μου δώσει μια ανακεφαλαίωση του ποια είναι η διαφορά
μεταξύ δυαδική αναζήτηση και γραμμική αναζήτηση;
Τι συμβαίνει; Σίγουρα.
Γραμμική αναζήτησης, μέσα από κάθε στοιχείο στην ταξινομημένη λίστα
ένα-ένα από ένα προς ένα από μία,
και δυαδική αναζήτηση χωρίζει τη λίστα σε 2 ομάδες,
ελέγχει αν η τιμή κλειδιά που ψάχνετε για είναι μεγαλύτερη ή μικρότερη από την αξία μέσο
που μόλις βρεθεί, αν και είναι λιγότερο από ό, τι, θα πάει με το χαμηλότερο λίστα
και στη συνέχεια, κατανέμει ότι και πάλι, κάνει την ίδια λειτουργία
όλος ο τρόπος κάτω μέχρι να βρει το μέσο να είναι ίση με την ίδια αξία.
Δεξιά.
>> Γιατί μας νοιάζει;
Γιατί μιλάμε για δυαδική αναζήτηση σε σχέση με γραμμική αναζήτηση;
Ναι.
Binary είναι πολύ πιο γρήγορα, οπότε αν έχετε διπλασιάσει το μέγεθος του προβλήματος
παίρνει ένα ακόμα βήμα παρά τα διπλάσια.
Ακριβώς.
Αυτό είναι μια μεγάλη απάντηση.
Γραμμική αναζήτηση είναι πολύ επιλέγοντας ένα στοιχείο τη φορά,
και όπως είδαμε από την πρώτη κιόλας ημέρα της διάλεξης
όταν ο Δαβίδ πέρασε παράδειγμα τηλεφωνικό κατάλογο του
και άρπαξαν από μια σελίδα του τηλεφωνικού καταλόγου σε ένα χρόνο
και συνεχίσαμε να κάνουμε ότι ξανά και ξανά και ξανά,
πρόκειται να τον πάρει ένα πραγματικά μεγάλο χρονικό διάστημα για να βρει κανείς στον τηλεφωνικό κατάλογο,
εκτός αν, φυσικά, έψαχνε για κάποιον στην αρχή του αλφαβήτου.
Με την δυαδική αναζήτηση, μπορείτε να πάτε πολύ πιο γρήγορα,
και δεν είναι μόνο δύο φορές πιο γρήγορα ή 3 φορές πιο γρήγορα ή 4 φορές πιο γρήγορα.
Αλλά το πρόβλημα γίνεται ολοένα και μικρότερο και μικρότερα πολύ γρηγορότερα.
Για να φανεί αυτό, θα αρχίσουμε να μιλάμε για το τι συμβαίνει
όταν γράφουμε δυαδική αναζήτηση.
Το πρόβλημα στο χέρι είναι ότι αν έχω μια σειρά από αριθμούς,
πούμε, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
και ακολούθως 9 με έναν τόνο των 0s μετά από αυτό,
θέλουμε να είμαστε σε θέση να καταλάβω πολύ γρήγορα ό, τι είναι στην
αυτή η σειρά των αριθμών.
Ξέρω ότι αυτό φαίνεται λίγο ανόητο και λίγο σκηνοθετημένη,
γιατί τώρα είναι.
Έχουμε μια σειρά που δεν έχουν πολύ πολλά στοιχεία σε αυτό,
αν και ζητώ από εσάς να καταλάβω αν ή όχι
23 είναι στον πίνακα, μπορείτε να το κάνετε αυτό αρκετά γρήγορα
μόνο με μια ματιά αυτό και να μου λέει ναι ή όχι.
Το αναλογικό να εξετάσει το ενδεχόμενο να φανταστείτε αν αυτό ήταν, ας πούμε,
ένα υπολογιστικό φύλλο Excel με 10.000 σειρές, 20.000 σειρές.
Φυσικά, μπορείτε να κάνετε το F εντολή ή το F έλεγχο και να δούμε κάτι επάνω.
Μπορείτε επίσης να χρησιμοποιήσετε τα φίλτρα και τα πράγματα αναζήτησης,
αλλά αν έπρεπε να κοιτάξετε μέσα από αυτή τη γραμμή από το αρχείο γραμμή προς γραμμή,
θα σας πάρει πολύ χρόνο για να το βρείτε.
Είναι κάτι σαν το παράδειγμα τηλεφωνικό κατάλογο, επίσης, όπου
κανείς δεν κοιτάζει μέσα από ένα βιβλίο σελίδα ένα τηλέφωνο σε μια στιγμή.
Συνήθως, κάνουν την ανοίξετε στη μέση,
ή στην περίπτωση πολλών βιβλίων και λεξικών τηλεφώνου όπου
που πραγματικά έχουν πληκτρολογηθεί στο πρώτο γράμμα,
μπορείτε να αναστρέψετε την πρώτη επιστολή και να ανοίξει και να αρχίσει να περάσει από εκεί.
>> Υπενθυμίστε μου το όνομα σας. >> Sam πάλι.
Sam.
Όπως δήλωσε ο Σαμ, ότι γραμμική διαδικασία αναζήτησης θα είναι πολύ αργή,
και αντ 'αυτού με δυαδική αναζήτηση, ο τρόπος με τον οποίο δουλεύει αυτό είναι ότι
κάθε φορά που περνάμε από μια επανάληψη του αλγορίθμου μας αναζήτηση,
θα πάμε να διαιρέσει τη λίστα κατά το ήμισυ, κατ 'ουσίαν,
σε δύο μικρότερες λίστες.
Και στη συνέχεια, στην επόμενη επανάληψη του βρόχου, θα το διαιρέσει και πάλι
σε άλλες μικρότερες λίστες.
Όπως μπορείτε να δείτε, το πρόβλημα συνεχίζει να παίρνει όλο και μικρότερα
γιατί κρατήσουν το μισό απόρριψη της λίστας κάθε φορά.
Πώς λειτουργεί αυτό απόρριψης;
Ακριβώς όπως μια υπενθύμιση, τι θα πάμε να κάνουμε αν είχαμε έναν υπολογιστή
και εμείς, ας πούμε, η αναζήτηση για τον αριθμό 5 σε αυτήν τη λίστα
είναι ότι θα πάρει έναν αριθμό στη μέση.
Στη μέση του καταλόγου αυτού, διότι υπάρχουν 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 αριθμοί,
είχαμε πάρει τον αριθμό είτε στην 4η θέση ή στην 5η θέση,
και εμείς θα την ονόμαζα τη μέση της λίστας μας.
Διαλέξτε τον αριθμό στη μέση.
Στη συνέχεια, όπως είπε ο Σαμ, θα δοκιμάσουμε για να δούμε αν ο αριθμός αυτός είναι ίσος
με τον αριθμό που θέλετε να πάρετε ή επιθυμητό αριθμό μας.
Αν είναι ίσες, τότε έχουμε βρει. Έχουμε κερδίσει.
Αν δεν είναι ίσες, τότε υπάρχουν μια-δυο περιπτώσεις.
Οι δύο περιπτώσεις είναι είτε ο αριθμός πρέπει να είναι μεγαλύτερος από τον αριθμό που ψάχνουμε σε,
ή είναι λιγότερο από ό, τι.
Αν είναι μεγαλύτερη, προχωράμε προς τα δεξιά.
Και αν είναι λιγότερο, θα προχωρήσουμε προς τα αριστερά.
Και τότε θα επαναλάβετε την όλη διαδικασία ξανά
είτε στο δεξί ήμισυ ή το αριστερό ήμισυ του καταλόγου.
>> Το πρώτο πρόβλημα σε τμήμα του σήμερα είναι να καταλάβουμε
πώς μπορούμε πραγματικά να αρχίσει να εκφράσει αυτό σε κώδικα C.
Έχουμε την ψευδοκώδικα εδώ.
Τι θα αρχίσουν να κάνουν είναι ότι θα τραβήξει ένα ολοκαίνουργιο χώρο,
αποθηκεύσετε αυτή την αναθεώρηση, ώστε να έχουμε αυτές τις σημειώσεις για αργότερα,
θα διαγράψει όλα αυτά, και στη συνέχεια να αντιγράψετε και να επικολλήσετε από το σύνολο πρόβλημα
η πληροφορία αυτή σε χώρους μας, και ελπίζω ότι αυτό δεν σπάσει.
Τέλεια.
Αν εσείς όλοι το κάνουμε αυτό, αντιγραφή και επικόλληση του κώδικα σε νέο χώρο σας,
σε ένα κενό μία.
Ας προσπαθήσουμε Δανιήλ. Εάν μεταγλωττίσετε και να εκτελέσετε αυτό το πρόγραμμα, δεν λειτουργεί;
Όχι >> Τι να πω;
Λέει ο έλεγχος φτάσει στο τέλος του μη-κενό λειτουργίας.
Ναι, οπότε επιτρέψτε μου να προσπαθήσω τρέχει.
Έχετε παιδιά ξαναδεί αυτό; Ξέρετε τι σημαίνει αυτό;
Εντάξει, ας το αναλύσουμε αυτό λίγο.
Είναι λέει στο file.c on line 9, στήλη 1 έχουμε ένα σφάλμα, όπως ακριβώς είπατε,
και λέει ότι αυτό είναι που απορρέουν από την προειδοποίηση σφάλματος και την προειδοποίηση τύπο επιστροφής.
Μοιάζει με κάτι συμβαίνει με τον τύπο επιστροφής, η οποία έχει νόημα.
Έχουμε μια μη-κενό λειτουργία, πράγμα που σημαίνει ότι έχουμε μια συνάρτηση
που δεν επιστρέφει κενό.
Μία συνάρτηση είναι ένα κενό που μοιάζει με αυτό:
άκυρη foo (), και είναι άκυρη, διότι ο τύπος επιστροφής είναι άκυρη,
πράγμα που σημαίνει ότι αν είχαμε κάτι εδώ
όπως η επιστροφή 1, είχαμε πάρει ένα σφάλμα μεταγλωττιστή για αυτό.
Ωστόσο, έχουμε μια μη-άκυρη λειτουργία.
Μη-κενό λειτουργία μας σε αυτή την περίπτωση είναι η λειτουργία αναζήτησης μας
επειδή έχει ένα είδος επιστροφής του bool.
Όταν λέει ότι ο έλεγχος φτάσει στο τέλος του ενός μη-κενού λειτουργία,
αυτό συμβαίνει γιατί αναζήτησης δεν έχει εντολή return.
Δεν είναι τίποτα επιστροφή του τύπου bool.
>> Μπορούμε να ορίσουμε ότι, και τι σκέφτονται σας παιδιά
αναζήτηση θα πρέπει να επιστρέψει από προεπιλογή;
Ποια πρέπει να είναι η τιμή επιστροφής προεπιλογή της αναζήτησης;
Διότι αυτό είναι που μπορούμε να βάλουμε στο τέλος.
Charlotte, έχετε οποιαδήποτε-;
Σωστό ή λάθος; >> Σωστό ή λάθος.
Ποιο από τα δύο;
Λάθος. Δεν ξέρω.
Λάθος; Ας το προσπαθήσουμε.
Γιατί θα λέγατε επιστροφή ψευδείς? Αυτό είναι μεγάλη διαίσθηση.
[Charlotte] Δεν ξέρω.
Εμείς πάμε για να επιστρέψει false σε αυτή την περίπτωση, γιατί αυτή θα είναι προεπιλεγμένη μας
αν για κάποιο λόγο η λίστα είναι κενή ή η βελόνα
ότι ψάχνουμε για δεν υπάρχει.
Στη συνέχεια, στο τέλος, αν δεν επιστρέψει αλήθεια νωρίτερα σε αυτή τη λειτουργία,
πάντα ξέρουμε ότι αυτή η λειτουργία θα πει nope, δεν είναι στον πίνακα.
Δεν είναι στα άχυρα.
Τώρα, αν θα μεταγλωττίσετε και να εκτελέσετε το-επιτρέψτε μου να σώσει αυτό, ώστε να μπορούμε να το σηκώσει.
Τώρα, αν θα μεταγλώττιση και εκτέλεση του προγράμματος μας, χτίζει.
Παίρνουμε λίγο προτροπή μας.
Αν χτυπήσει 4-uh-oh.
Δεν εκτυπώνει τίποτα. Μοιάζει με ό, τι τελείωσε καλά.
Έχουμε να συμπληρώσετε αυτό μέσα
Μιλήσαμε για τον αλγόριθμο σε ψευδοκώδικα λίγο πριν.
Επιτρέψτε μου να δει, εκτός από αυτό,
και εγώ θα τραβήξει ότι ο αλγόριθμος πίσω πάλι.
Ας χτυπήσει αυτός ο τύπος. Όχι.
Εκεί είναι.
Πώς θα το κάνουμε αυτό;
Τι θα ήταν μια καλή στρατηγική για την εκκίνηση αυτού του κώδικα;
Θα πρέπει να επιλέξετε έναν αριθμό στη μέση.
Πώς να πάρει έναν αριθμό στη μέση ενός πίνακα;
Οποιεσδήποτε προτάσεις;
[Φοιτητικό] strlen διαιρούμενο δια του 2.
Strlen διαιρούμενο δια του 2. Αυτό είναι μία πολύ μεγάλη.
Strlen έργα με ειδικές είδη συστοιχίες.
Τι είδους πίνακες;
String πίνακες, πίνακες χαρακτήρων.
Είναι το ίδιο είδος της έννοιας που θέλουμε να ισχύουν,
αλλά δεν μπορούμε να χρησιμοποιήσουμε strlen επειδή δεν έχουμε μια σειρά από χαρακτήρες.
Έχουμε μια σειρά από χαρακτηριστικά της.
Αλλά τι σημαίνει strlen πάρετε για μας;
Ξέρετε τι παίρνει για μας;
[Φοιτητικό] strlen μας παίρνει το μήκος.
Ακριβώς, μας παίρνει το μήκος.
Strlen παίρνει το μήκος της συστοιχίας για εμάς.
>> Πώς θα πάρετε ότι στο πρόγραμμα δυαδική αναζήτηση μας;
Πώς θα πάρετε το μήκος ενός πίνακα;
[Φοιτητικό] strlen;
Μπορείτε να πάρετε το μήκος μιας σωστή μορφή πίνακα συμβολοσειρών με C strlen.
Το πρόβλημα, όμως, είναι ότι δεν έχουμε μια σειρά χορδών.
Αν κοιτάξουμε πίσω σε αυτόν τον κώδικα, έχουμε αυτό το ακέραιο πίνακα.
Πώς ξέρουμε πόσο καιρό είναι;
[Φοιτητικό] Υπάρχει μια ισοδύναμη για τελικό σημείο, όπως int l ή κάτι άλλο;
Αποδεικνύεται στην πραγματικότητα δεν είναι εκεί, και έτσι κατά κάποιο τρόπο, αυτό είναι
ένα από εκείνα τα πράγματα που είναι απλά καλό να γνωρίζουμε για το C,
ότι δεν υπάρχει τρόπος για να πάρετε το μήκος μιας συστοιχίας
αν όλοι σας δίνω είναι η σειρά.
Ο λόγος που λειτουργεί με χορδές, ο λόγος strlen έργα,
οφείλεται στο γεγονός ότι αν ένα string έχει την κατάλληλη μορφή,
θα έχουν αυτό το ιδιαίτερο \ 0 χαρακτήρας στο τέλος.
>> Μπορείτε επίσης να φανταστείτε, εάν έχετε μια σωστά μορφοποιημένη συμβολοσειρά
και δεν υπάρχει \ 0 χαρακτήρας εκεί, τότε το όλο πράγμα δεν λειτουργεί.
[Φοιτητικό] Μπορείτε να προσθέσετε το \ 0;
Θα μπορούσαμε στην περίπτωση αυτή.
Θα μπορούσαμε να προσθέσουμε κάποια \ 0
ή κάποιο είδος του χαρακτήρα που σηματοδοτεί και στη συνέχεια να χρησιμοποιήσετε αυτό.
Αλλά αυτό δεν είναι αρκετά πρόκειται να λειτουργήσει
επειδή το 0 \ είναι για έναν τύπο char,
και εδώ έχουμε ints.
Το άλλο πράγμα είναι εάν επρόκειτο να χρησιμοποιήσετε μια ειδική τιμή
σαν -1 έως σηματοδοτήσει το τέλος ενός πίνακα
τότε θα μπορούσαμε ποτέ να αποθηκεύσετε ένα ακέραιο -1 σε συστοιχίες μας.
Θα ήθελα να κολλήσει.
Αποδεικνύεται ότι ο μόνος τρόπος για να πάρει το μήκος
ενός πίνακα σε C είναι να θυμόμαστε ότι στην πραγματικότητα
όταν το ρυθμίσετε και στη συνέχεια να περάσει γύρω με την σειρά
έτσι ώστε κάθε φορά που έχω μια λειτουργία που πρόκειται να κάνουν κάποια εργασία
σε μια σειρά από ακέραιους αριθμούς ή πλωτήρες ή διπλασιάζεται ή ό, τι έχετε,
Επίσης, πρέπει να δώσει το μήκος λειτουργία της συστοιχίας,
και αυτό είναι ακριβώς ό, τι έχουμε κάνει εδώ στη λειτουργία αναζήτησης.
Αν κοιτάξετε, τι έχουμε κάνει όταν περνάμε σε παράταξη μας εδώ,
μπορούμε επίσης να περάσει το μήκος, το μέγεθος.
Συμβαίνει ακριβώς ότι έχουμε αυτό που ονομάζεται μεταβλητή εδώ,
αυτή η παράμετρος ή επιχείρημα.
Αυτό ονομάζεται κατάλογος των argument μια λειτουργία ή λίστα παραμέτρων,
και αυτά είναι που ονομάζεται επίσης τα επιχειρήματα ή τις παραμέτρους.
Οι άνθρωποι χρησιμοποιούν διαφορετικούς όρους σε διαφορετικούς χρόνους.
Μερικές φορές τον εαυτό μου να εναλλάσσονται.
Συμβαίνει ότι αυτή η μεταβλητή εδώ ονομάζεται ομοίως
σε αυτό το # define εδώ.
Αλλά δεν είναι το ίδιο πράγμα.
Η κεφαλαιοποίηση έχει σημασία.
>> Αν κοιτάξουμε τι συμβαίνει εδώ, δηλώνουμε
int σειρά μας, το οποίο έχουμε αριθμούς που καλέσατε.
Έχουμε δώσει το μέγεθός μας, το οποίο αντιστοιχεί σε μας # define επάνω στην κορυφή.
Είναι πρόκειται να είναι 8.
Και στη συνέχεια, όταν λέμε συνέχεια, λειτουργία αναζήτησης μας κάτω,
περνάμε στον αριθμό που θέλετε να αναζητήσετε, το οποίο έχουμε ζητηθεί,
πάρει από το χρήστη.
Περνάμε στη σειρά, αυτό αριθμούς,
και στη συνέχεια πρέπει επίσης να περάσει στο μέγεθος του πίνακα,
και στη συνέχεια η τιμή του μεγέθους 8 παίρνει αποθηκεύονται
ή να περάσει σε αυτό που ονομάζεται ακέραιο μεταβλητό μέγεθος.
Έχουμε το μέγεθος της συστοιχίας.
Τώρα αν πάμε πίσω σε ό, τι μιλούσαμε για νωρίτερα,
Νομίζω ότι Missy έφερε το σημείο ότι αυτό που χρειάζεται να κάνετε είναι να πάρετε το μήκος του πίνακα
και το διαιρούμε με το 2, και ότι θα μας δώσει το μέσον.
Ας δούμε.
Μπορώ να έχω κάποιον γράψω αυτό και να το αποθηκεύσετε στο χώρο τους;
Τι θα λέγατε για Leila;
Μπορώ να σας έχουμε γράψει αυτό μέσα;
Γράψτε την πρώτη γραμμή, όπου μπορείτε να το μήκος του πίνακα και να πάρει το μέσο
και να το αποθηκεύσετε σε μια νέα μεταβλητή.
Θα σας δώσω ένα ζευγάρι δευτερόλεπτα. Είστε έτοιμοι;
[Φοιτητών ακούγεται]
Σίγουρα, θα μπορούσα να έχετε υπολογίσει το μέσο
του πίνακα άχυρα μέσα στο λειτουργία αναζήτησης
χρησιμοποιώντας το μήκος της συστοιχίας άχυρα, το οποίο είναι η μεταβλητή μέγεθος;
Τίποτα δεν είναι δύσκολο εδώ.
[Leila] Ακριβώς το μέγεθος / 2 και μόνο-
Και να το αποθηκεύσετε και πατήστε το κουμπί Αποθήκευση εδώ στην κορυφή,
και εμείς θα το σηκώσει.
Τέλεια.
Εκεί πάμε. Awesome.
>> Όπως είναι, θα καταρτίσει αυτό;
[Leila] Όχι, δεν πρέπει να είναι υψηλότερο.
[Nate] Ναι, έτσι τι πρέπει να κάνουμε;
[Leila] Όπως int μέσο ή κάτι τέτοιο.
Awesome. Ναι, ας το κάνουμε αυτό, int = μέσο μέγεθος.
Αυτό θα συγκεντρώνουν;
Ας διαγράψετε αυτό το σχόλιο και να το πάρετε από το δρόμο.
Αυτό που δεν θα συγκεντρώσει γι 'αυτό;
Εμείς δεν κάνουμε τίποτα με ακέραιο αριθμό,
έτσι πρέπει να το εκτυπώσετε ή κάτι τέτοιο.
Ναι, ακριβώς.
Θα πάρετε μια μεταβλητή αχρησιμοποίητο.
Τι άλλο δεν πρόκειται να λειτουργήσει γι 'αυτό;
Νομίζω ότι είπατε κάτι, Σαμ. Ερωτηματικά.
Ναι, είμαι λείπουν τα ερωτηματικά.
Είναι πρόκειται να είναι ένα σταθερό πράγμα καθ 'όλη τη διάρκεια του χρόνου.
Το τελευταίο πράγμα που θα κάνω είναι θα βάλω κάποιο κενό χώρο και στις δύο πλευρές
του εν λόγω φορέα εκμετάλλευσης εδώ, αφού αυτό είναι συνήθως το πώς μπορούμε να το κάνουμε
σύμφωνα με τον οδηγό στυλ μας.
Έχουμε το μέσο του πίνακα μας.
Τώρα, αν θυμηθούμε ξανά τον αλγόριθμο μας,
ό, τι ήταν το δεύτερο βήμα που έπρεπε να κάνουμε όταν έχουμε το μέσο;
[Φοιτητικό] Αν είναι μεγαλύτερη [δεν ακούγεται].
Ναι, έτσι πρέπει να κάνουμε κάποια σύγκριση, και τι είμαστε συγκρίνοντας εδώ;
Είπατε, εάν είναι μεγαλύτερη από ό, τι. Τι είναι αυτό στο εν λόγω πρόταση αναφέρεστε;
Ο αριθμός που εμφανίζεται, αν αυτό είναι μεγαλύτερο από το μέσο, ​​τότε πηγαίνετε μέχρι τη σειρά;
Ακριβώς, έτσι ώστε ο αριθμός που εμφανίζεται όταν-
Η βελόνα, έτσι είμαστε σε σύγκριση με τη βελόνα,
και τι μπορούμε κατά τη σύγκριση της βελόνας;
Επειδή η βελόνα είναι αυτό που ψάχνουμε.
Είμαστε σε σύγκριση με το να φτάσετε στο μέσον.
>> Αλλά δεν έχει νόημα να ελέγξετε
αν βελόνα = μέσο;
Μήπως αυτό έχει νόημα;
Πιστεύει κανείς διαφωνείτε;
Ας δώσει μια δοκιμή, αν (βελόνα μέσο ==).
[Φοιτητικό] Μην printf το βρήκατε.
[Nate] printf ("βρήκαμε \ n")?
Διαφορετικά-Πάω να αρχίσουν να κάνουν κάτι διαφορετικό εδώ.
Πάω να αρχίσει η εφαρμογή τιράντες γύρω δηλώσεις αν όλη την ώρα
μόνο και μόνο επειδή αν προσθέσουμε περισσότερα πράγματα, τότε
δεν παίρνουμε τα μεταγλωττιστές.
Ναι, Σαμ. Έχεις ένα σημείο.
Το πρόβλημα είναι ότι το μεσαίο σημείο παριστά μια θέση στη συστοιχία,
αλλά μπορείτε να το πάρετε για να αντιπροσωπεύουν την αξία σε αυτή τη θέση του πίνακα.
Αυτό είναι ένα μεγάλο σημείο.
Μήπως όλοι ακούσει τι είπε ο Σαμ;
Είπε ότι είναι ως μέσο
αντιπροσωπεύει μόνο μια θέση στη συστοιχία, αλλά δεν είναι το πραγματικό στοιχείο στη συστοιχία.
Εάν σκέφτεστε για τον κώδικα όπως γράφεται τώρα,
εάν κοιτάξουμε αυτό εδώ κάτω σειρά, το οποίο έχει 8 στοιχεία σε αυτό,
ποια είναι η αξία του μέσου σημείου θα είναι σε αυτή τη λειτουργία;
[Φοιτητικό] 4.
[Nate] 4.
Αν κοιτάξουμε τον αριθμό 4 -
και μπορούμε να τρέξουμε μόνο αυτόν τον κώδικα και να θέσει ένα μικρό θλιμμένο πρόσωπο εδώ
γιατί δεν το βρείτε, αν εκτελέσετε αυτόν τον κώδικα
όπως είναι τώρα, το φόρτωμα, κτίριο, επιτρέψτε μου να μετακινηθείτε προς τα κάτω,
και αν κοιτάξουμε για τον αριθμό 4,
το βρήκαμε, αλλά δεν πήραμε αυτό να printf ναι.
Ένας λόγος είναι ότι δεν είχαμε επιστρέψει αλήθεια,
αλλά δεν έχουμε βρει πραγματικά τον αριθμό 4;
Και ο Σαμ λέει όχι.
Τι θα βρούμε;
Βρήκαμε πολύ το μέσο, ​​το οποίο, αν κοιτάξουμε την σειρά εδώ κάτω,
πρόκειται να είναι το στοιχείο στο δείκτη 4 ότι ψάχνουμε σε,
η οποία είναι 23.
>> Πώς να πάρει πραγματικά αυτό το στοιχείο στο μέσο
και όχι μόνο το ίδιο το μέσο;
[Φοιτητικό] Θα τεθεί char ή κάτι άλλο;
Τι θα που κάνουν, απλά από περιέργεια;
Μπορείτε να επεκταθείτε λίγο περισσότερο;
Θα πρέπει να μετατρέψει τη θέση στον αριθμό,
έτσι έχετε να κάνετε κάποια σχέση, νομίζω ότι είναι char, αλλά δεν θα μπορούσε να είναι.
Ναι, αυτό είναι ένα καλό σημείο.
Έχουμε ήδη κάνει πολλά αυτού μετατροπή θέσεων σε χαρακτήρες, οι χαρακτήρες,
στις πρώτες δύο σύνολα πρόβλημα.
Αποδεικνύεται ότι εδώ, αυτό είναι σχεδόν παρόμοια με
την πρόσβαση του i-χαρακτήρα μέσα σε ένα string, αν αυτό έχει νόημα.
Εδώ θέλουμε να έχουν πρόσβαση στο στοιχείο μέσο.
Πώς θα το κάνουμε αυτό;
Κέβιν, δεν έχετε προτάσεις για το πώς θα μπορούσαμε να το κάνουμε αυτό;
Θα μπορούσατε να κάνετε άχυρα, ανοιχτό βραχίονα, τα μέσα, έκλεισε βραχίονα.
Μπορείτε να γράψετε ότι για μας;
Αποθήκευση στο εδώ, και θα τραβήξει αυτό επάνω.
Ψάχνουμε σε αυτή τη γραμμή 9,
και είμαστε συνειδητοποιούν ότι δεν θέλουμε να συγκρίνουμε τη βελόνα στο μέσο,
αλλά αντίθετα, θέλουμε να συγκρίνουμε τη βελόνα
στο στοιχείο στο μέσο θέση εντός συστοιχίας άχυρα μας.
Cool.
Εκεί πάμε.
Ναι, αυτό φαίνεται αρκετά καλό, αν (βελόνα στ 'άχυρα == [μέσο]).
Το βρήκαμε.
Τώρα, αν τρέξουμε τον κώδικα-we'll back up λίγο-
να συγκεντρώνει, να τρέχει, και τώρα αν κοιτάξουμε για 4,
εμείς δεν το βρείτε, γιατί τώρα είμαστε πραγματικά να πάρει τον αριθμό 23.
Παίρνουμε την αξία 23, και αυτό είναι ό, τι είμαστε σε σύγκριση με βελόνα μας.
Αλλά αυτό είναι καλό. Αυτό είναι ένα βήμα προς τη σωστή κατεύθυνση.
>> Αυτό είναι που προσπαθούμε να κάνουμε.
Εμείς δεν προσπαθούμε να συγκρίνουμε τη βελόνα κατά θέσεις στον πίνακα
αλλά μάλλον εναντίον των πραγματικών στοιχείων της συστοιχίας.
Αν κοιτάξουμε πίσω πάλι τώρα στο επόμενο βήμα στον αλγόριθμο μας,
ποιο είναι το επόμενο βήμα;
Leila αναφέρθηκε ήδη εν συντομία.
[Φοιτητικό] Ελέγξτε για να δείτε αν είναι μεγαλύτερο ή μικρότερο από ό, τι και στη συνέχεια να αποφασίσει ποια κατεύθυνση να κινηθεί.
[Nate] Ναι, έτσι πώς θα το κάνουμε αυτό;
Μπορείτε να βάλετε σε κάποια-Θα αποθηκεύσετε αυτή την αναθεώρηση,
και στη συνέχεια, αν βάλετε σε ορισμένες γραμμές που θα το κάνει αυτό.
Ναι, Σαρλότ. >> Έχω μια ερώτηση.
Δεν θα έπρεπε να είναι κεντρικό σημείο - 1, διότι το πρώτο πράγμα είναι
αυτό είναι 0 ευρετήριο, έτσι αν βάλουμε 4, που δεν είναι στην πραγματικότητα ο χαρακτήρας που ψάχνουμε;
Ναι, και το άλλο πρόβλημα με αυτό είναι-
αυτό είναι ένα μεγάλο αλιευμάτων, γιατί ό, τι πρόκειται να καταλήξετε πιθανώς συμβαίνει
αν θέλουμε να προχωρήσουμε και εμείς ποτέ δεν ρυθμίσετε αρχικά;
Υποθέτω ότι αυτό που θα μπορούσε να καταλήξει να κάνει προσπαθεί να αποκτήσει πρόσβαση
το στοιχείο κατά την 8η θέση της συστοιχίας,
η οποία σε αυτή την περίπτωση δεν υπάρχει.
Θα θέλετε να κάνετε κάποιο είδος της λογιστικής για το γεγονός
ότι έχουμε κάποια μηδέν ευρετηρίαση.
[Charlotte] Συγνώμη, εννοούσα μέσο - 1 στις αγκύλες.
Μπορούμε να το κάνουμε αυτό.
Θα επανέλθουμε στο θέμα αυτό σε μόλις ένα κομμάτι.
Μόλις αρχίζουμε να φτάσουμε στην πραγματική looping,
ότι όταν θα δείτε πραγματικά αυτό μπαίνουν στο παιχνίδι.
Προς το παρόν, μπορούμε να το κάνουμε αυτό, αλλά είσαι εντελώς δεξιά.
Ότι η μηδενική ευρετηρίαση θα έχουν επίδραση ότι πρέπει να αντιπροσωπεύουν.
Ας δούμε.
>> Πώς είναι η μεγαλύτερη από και μικρότερη από-;
[Φοιτητικό] παίρνω το πώς να κάνει το μεγαλύτερο και μικρότερο μέρος.
Απλά δεν ήταν σίγουρος τι να εκτυπώσετε αν διαπιστώσετε ότι είναι μικρότερο από το μέσο άχυρα ή μεγαλύτερη από ό, τι.
Εδώ μπορώ να σώσει ό, τι I've-
[Nate] Ναι, αν μπορείτε να αποθηκεύσετε ό, τι έχετε, και θα το σηκώσει.
Εκεί πάμε.
[Φοιτητικό] Και έβαλα ερωτηματικά για το τι δεν ήξερα.
[Nate] Αυτό φαίνεται μεγάλη.
Εδώ έχουμε ερωτηματικά, γιατί ακόμα δεν γνωρίζουμε
τι θα πάμε να κάνουμε ακόμη αρκετά.
Τι θα θέλουμε να κάνουμε-ουπς, έχουμε κάποια στηρίγματα για όλα τα funky μας.
Θα διορθώσει αυτά τα σιδεράκια.
Εκεί πάμε.
Και έτσι αυτό που θέλουμε να κάνουμε, σύμφωνα με τον αλγόριθμο μας,
αν δεν βρούμε τη βελόνα;
Πείτε σε περίπτωση που η βελόνα είναι μικρότερη από ό, τι ψάχνουμε σε. Kevin.
Μόνο ματιά στο αριστερό μισό.
Σωστά, έτσι θα βάλουμε ένα σχόλιο εδώ που λέει "κοιτάξτε στο αριστερό μισό."
Και αν η βελόνα είναι μεγαλύτερη από ό, τι στ 'άχυρα στο μέσον, τι θέλουμε να κάνουμε;
[Φοιτητικό] Στη συνέχεια θα εξετάσουμε το δεξί μισό.
Κοιτάξτε το δεξί μισό, "ματιά στο δεξιό μισό."
Not too shabby.
Εντάξει, έτσι σε αυτό το σημείο, τα πράγματα φαίνονται αρκετά καλά.
Το πρόβλημα με τον κώδικα όπως είναι γραμμένο αυτό;
[Φοιτητικό] Δεν έχουν τελικά σημεία για τα μισά.
Σωστά, δεν έχουμε τελικά σημεία για τα μισά.
Επίσης, είναι μόνο πρόκειται να περάσει μέσα από αυτό μια φορά.
Είμαστε μόνο πρόκειται να δούμε σε ένα κεντρικό σημείο.
Είτε το στοιχείο δεν υπάρχει, ή δεν είναι.
Για να ολοκληρώσει αυτό, θα χρειαστεί να κάνετε κάποια επανάληψη.
Πρέπει να το επαναλαμβάνουμε μέχρι να βρούμε ότι
είτε το στοιχείο είναι εκεί, διότι έχουμε περιοριστεί και τελικά το βρήκε,
ή δεν είναι εκεί επειδή έχουμε εξετάσει με όλα τα πράγματα
στις κατάλληλες μισά της συστοιχίας και διαπίστωσε ότι τίποτα δεν είναι εκεί μέσα.
>> Κάθε φορά που έχουμε αυτή την επανάληψη συμβαίνει, τι πρόκειται να χρησιμοποιήσετε;
[Φοιτητικό] Ένας βρόχος.
Κάποιο είδος βρόχου. Ναι.
[Φοιτητικό] Μπορούμε να κάνουμε μια do-while loop και να το κάνουμε αυτό και στη συνέχεια, ενώ
η βελόνα δεν είναι ίσο-σίγουρα όπου πήγαινα με αυτό.
Αλλά κάτι σαν το κάνουμε αυτό όσο δεν ισούται με την αξία που η παρέμβαση του χρήστη.
Ναι, γι 'αυτό ας δούμε, πώς θα μπορούσε να γράψει αυτό το ίδιο;
Είπατε ας χρησιμοποιήσουμε ένα do-while loop.
Σε περίπτωση που δεν το κάνει εκκίνηση;
[Φοιτητικό] Αμέσως μετά από το μέγεθος / 2.
[Nate] Εντάξει, και τι θα κάνουμε;
Θα συμπληρώσετε το λίγο αργότερα.
Τι θα κάνουμε;
[Φοιτητικό] Μην θέλουμε να κάνουμε όλα τα πράγματα που έχουμε στην περίπτωση που τμήμα;
[Nate] Μήπως όλα αυτά τα πράγματα, μεγάλη.
Αντιγραφής και επικόλλησης.
Ω, ο άνθρωπος.
Ας δούμε αν αυτό λειτουργεί, αν μπορούμε να την καρτέλα πάνω.
Όμορφη.
Εντάξει, και εμείς να σώσει αυτό, έτσι ώστε να παιδιά να έχουν.
Εντάξει, και πρόκειται να το κάνουμε αυτό, ενώ-
ποια ήταν η κατάσταση, ενόσω ήσασταν μετά;
[Φοιτητικό] Ενώ η βελόνα δεν ισούται, έτσι όπως το θαυμαστικό.
Αλλά δεν είμαι σίγουρος τι ακριβώς ότι είναι ακόμη.
[Nate] Ναι, αυτός είναι ένας τρόπος για να το κάνει.
Sam, έχετε κάποιο σχόλιο;
[Sam] θυμήθηκα όταν είδα το βίντεο,
Πήρα ένα screenshot από μία από τις-όπως όταν κάναμε τον ψευδοκώδικα για αυτό,
υπήρχε κάποια σχέση μεταξύ max και min.
Νομίζω ότι ήταν κάτι σαν max αν είναι ποτέ λιγότερο από λεπτό.
Πήρε αυτό.
[Sam] Ή αν θέλετε max δεν είναι λιγότερο από λεπτό ή κάτι τέτοιο,
γιατί αυτό θα σήμαινε ότι έχετε ψάξει τα πάντα.
>> Ναι, ναι, τι σημαίνει αυτό ακούγεται σαν max και min αναφέρονταν;
[Sam] Οι τιμές που-ακέραιοι που πρόκειται να αλλάξει
σε σχέση με την οποία βάζουμε το μέσο.
Ακριβώς.
[Sam] Σε εκείνο το σημείο, πρόκειται να [δεν ακούγεται] υπολογίζει το max και min.
Μέσο είναι το max και min ιδέα.
Μήπως αυτό έχει νόημα για τους λαούς;
Αν επρόκειτο να αρχίσει να ψάχνει το πώς θα πάμε να κάνουμε αυτή την επανάληψη,
είστε απόλυτα σωστό ότι θέλουμε να χρησιμοποιήσουμε κάποιο είδος του do-while loop.
Αλλά υποθέτω ότι αν θυμηθούμε τι συμβαίνει στο σημείο αυτού του πίνακα
και τι πραγματικά συμβαίνει-Πάω να γράψω εδώ-
κατά την πρώτη επανάληψη της δυαδικής αναζήτησης, έχουμε-
Πάω να χρησιμοποιήσετε β και ε, η οποία χαρακτηρίζει την αρχή.
Και μετά το τέλος του πίνακα μας.
Γνωρίζουμε ότι η αρχή είναι 4 δεξιά πάνω από εδώ,
και γνωρίζουμε ότι το τέλος είναι στο 108.
Πείτε μας ψάχνετε για τον αριθμό 15.
Την πρώτη φορά που το κάνουμε αυτό, όπως είδαμε νωρίτερα,
το μέσο είναι είτε πρόκειται να είναι 16 ή 23
ανάλογα με το πώς υπολογίζουμε τα πράγματα.
Από τη διαίρεση ομοιόμορφα στη μέση θα μας δώσει αυτό το διάστημα
μεταξύ 16 και 23, δεν μπορούμε να το διαιρέσετε ομοιόμορφα
ή να διαιρέσει και να πάρετε σε ένα πραγματικό μέσο.
Θα εξετάσουμε σε 16.
Θα συνειδητοποιήσετε "Hey, 16> 15 ότι ψάχνουμε."
Για να δούμε στη συνέχεια, στο αριστερό μισό του πίνακα
τι θα καταλήγουν να κάνουν είναι απόρριψη
όλο αυτό το ανώτερο τμήμα
και λέει, "Εντάξει, τώρα τελικό σημείο μας θα είναι εδώ."
Η επόμενη επανάληψη του βρόχου μας, είμαστε τώρα βλέπουν αυτό το φάσμα,
ουσιαστικά έχει απορριφθεί αυτό το τμήμα, διότι τώρα
αν είμαστε λαμβάνοντας το μέσο να είναι η διαφορά μεταξύ της αρχής και του τέλους,
βρίσκουμε μέσο μας να είναι 8,
το οποίο μπορούμε να ελέγξουμε τότε 8 για να δούμε πού είναι σε σχέση με τον αριθμό που ψάχνουμε,
15, βρείτε ότι το 15 είναι μεγαλύτερο,
έτσι πρέπει να προχωρήσουμε προς τα δεξιά μέρος της λίστας,
οποίο γνωρίζουμε επειδή είμαστε άνθρωποι, και μπορούμε να το δούμε.
Γνωρίζουμε ότι το δικαίωμα τμήμα πρόκειται να είναι όπου το βρείτε,
αλλά ο υπολογιστής δεν γνωρίζει ότι, ναι, τι θα κάνουμε είναι ότι θα πραγματικότητα
έχουν αυτό ανεβαίνουν, και τώρα η αρχή και το τέλος
είναι το ίδιο σημείο, έτσι ώστε το μέσο γίνεται ο μοναδικός αριθμός στη λίστα σε αυτό το σημείο,
η οποία είναι 15, και το έχουμε βρεθεί.
Μήπως αυτό ρίξει φως σχετικά με το πού όλη αυτή η max και min σημειογραφία πρόκειται,
την παρακολούθηση των παραμέτρων του πίνακα για να καταλάβω
πώς να περιορίσετε τα πράγματα κάτω;
>> Τι θα συνέβαινε αν αυτό δεν ήταν ίση με 15 τώρα;
Τι θα συμβεί αν ψάχναμε για 15 και, αντ 'αυτού, ο αριθμός αυτός ήταν επίσης 16;
Θα ήθελα να πω, "Ω, αυτό είναι μεγαλύτερο.
Θέλουμε να πάμε πίσω προς τα αριστερά. "
Και εμείς θα προχωρήσουμε ηλεκτρονικό μας προς τα δεξιά,
Σε ποιο σημείο έχουμε ένα τελικό σημείο που θα μπορούσε να είναι αντικρουόμενες.
Δεν θα είναι σε θέση να ψάξει για κάποια περισσότερα στοιχεία
γιατί τώρα έχουμε τελικό σημείο μας και το σημείο έναρξης μας,
max και min μας μας, τώρα άλλαξαν.
Έχουμε ψάξει σε όλο το φάσμα. Εμείς δεν μπορούμε να βρούμε τίποτα.
Αυτό είναι το σημείο στο οποίο θα ήθελα να πω, «Εντάξει, θα πάμε να σταματήσει αυτόν τον αλγόριθμο.
Δεν έχουμε βρει τίποτα. Γνωρίζουμε ότι δεν είναι εδώ. "
Πώς είναι αυτή η μετάβαση;
[Φοιτητής] Πώς ακριβώς κάνει ο υπολογιστής αλλάξετε το τέλος;
Πώς το τέλος καταλήγουν πριν από την έναρξη;
Το τέλος καταλήγει πριν από την έναρξη
λόγω του ότι τα μαθηματικά θα πάμε να κάνουμε κάθε φορά που το κάνουμε αυτό.
Ο τρόπος με τον οποίο ανταλλάσσουν είναι αν δει κανείς την πρώτη κιόλας φορά που κάνουμε αυτή την ανταλλαγή
όπου έχουμε την αρχή στο 4 και το τέλος
όλος ο τρόπος κάτω σε 108 και μέσον μας, ας πούμε, στο 16 -
Πάω να επαναφέρετε την πλάτη στο 15-αν ψάχνουμε για το 15,
ξέραμε ότι αυτό που κάναμε όταν ελέγξαμε το 16 και είδε ότι ήταν μεγαλύτερη
και ήθελε να απορρίψει το σύνολο δεξιά μέρος της λίστας,
είδαμε ότι αυτό που θέλουμε να κάνουμε είναι να προχωρήσουμε αυτό το e δικαίωμα εδώ.
Ουσιαστικά, το e πήρε κινήθηκε προς ένα πριν το μέσον.
Ομοίως, όταν κάναμε αυτή την επανάληψη του αλγορίθμου
και το μέσον ήταν στο 8,
βρήκαμε ότι 8 <15, έτσι θελήσαμε να μετακινήσετε το β
ένα παρελθόν το μεσαίο σημείο.
Τώρα, η αρχή και το τέλος είναι και οι δύο μαζί σε αυτό 15.
>> Αν είχαμε συμβαίνει να ψάξουν για κάποια άλλη αξία, όχι 15,
ή αν αυτό το 15 είχε αντ 'αυτού ήταν 16,
θα έχουν διαπιστώσει ότι το e θέλουμε να προχωρήσουμε ένα πριν το μέσον.
Τώρα το e θα γυρίσει εκεί λιγότερο από ό, τι το β.
Ας δούμε πώς μπορούμε πραγματικά να καταλήξουν κωδικοποίησης αυτόν τον αλγόριθμο.
Ξέρουμε ότι θέλουμε να έχουμε τον υπολογισμό αυτό μέσο.
Γνωρίζουμε, επίσης, ότι θέλουμε να παρακολουθείτε την αρχή και το τέλος της σειράς
της τρέχουσας σειρά μας ώστε να μπορέσουμε να καταλάβουμε
όπου αυτό αριστερό μισό της λίστας είναι και όπου το δεξί μισό της λίστας είναι.
Εμείς το κάνουμε αυτό με είτε αρχίζει και να τελειώνει,
ή μπορούμε να τους αποκαλούμε min και max.
Θα χρησιμοποιήσω αρχίζει και να τελειώνει αυτή τη φορά.
Όταν ξεκινάμε, αν κοιτάξουμε πίσω στο παράδειγμά μας εδώ κάτω,
αρχή μας ιδρύθηκε στην αρχή του πίνακα, ως φυσικά.
Ποια δείκτης ήταν αυτό; Τι θα πρέπει να αρχίσει να μας;
Δανιήλ.
[Daniel] Haystack [0].
[Nate] Ναι, έτσι θα μπορούσαμε να τεθεί ίση με άχυρα [0].
Το πρόβλημα, όμως, είναι ότι αυτό δεν μας δίνει τη θέση του πρώτου στοιχείου.
Μας δίνει το δείκτη του πρώτου στοιχείου ή της πραγματικής αξίας σε αυτή την πρώτη θέση.
[Φοιτητικό] Αυτό θα μετατραπούν σε 0,20;
[Nate] Τι θα κάνουμε είναι-καλά, δεν θα κάνει καμία μετατροπή.
Αυτό που θα κάνουμε είναι ότι θα αποθηκεύουν 4 σε αρχίζουν,
και τότε θα είναι δύσκολο να γίνουν συγκρίσεις κατά αρχίσει
επειδή begin θα διοργανώσει την αξία του 4,
το οποίο είναι η αρχή της συστοιχίας μας,
αλλά θέλουμε να παρακολουθούν τους δείκτες του πίνακα
σε αντίθεση με τις τιμές.
Θα χρησιμοποιήσουμε πραγματικά ένα 0, όπως αυτό.
Για το τέλος της σειράς-Charlotte έφερε αυτό μέχρι λίγο νωρίτερα.
Αυτό είναι όπου θα ληφθεί υπόψη η μηδενική ευρετηρίαση.
>> Charlotte, ποιο είναι το τέλος της σειράς;
Τι είναι ο δείκτης στο τέλος;
[Charlotte] Μέγεθος - 1.
Ναι, και τα οποία το μέγεθος θα πρέπει να χρησιμοποιήσω;
Θα πρέπει να χρησιμοποιήσετε το μέγεθος του κεφαλαίου ή πεζά μέγεθος;
Μέγεθος κεφαλαίου.
Σε αυτή την περίπτωση, θα μπορούσαμε να χρησιμοποιήσουμε το μέγεθος του κεφαλαίου.
Αν θέλαμε αυτή η λειτουργία να είναι φορητό
και να χρησιμοποιήσετε αυτή τη λειτουργία σε άλλα προγράμματα,
μπορούμε να χρησιμοποιήσουμε πραγματικά πεζά μέγεθος.
Είναι πάρα πολύ ωραία.
Αλλά Charlotte είναι απόλυτα σωστό ότι θέλουμε να έχουμε το μέγεθος - 1.
Σε αυτό το σημείο-
[Φοιτητής] Πώς είναι ότι μπορείτε να χρησιμοποιήσετε κεφαλαία μέγεθος;
Πώς είναι ότι θα μπορούσαμε να χρησιμοποιήσουμε κεφαλαία μέγεθος;
Αποδεικνύεται ότι αυτά ορίζει # είναι πραγματικά,
κάτω από την κουκούλα, ένα κείμενο όπως η εύρεση και αντικατάσταση, αν αυτό έχει νόημα.
Όταν κάνεις compile κώδικα σας, η φάση προεπεξεργασίας
του μεταγλωττιστή περνάει από το αρχείο,
και αυτό φαίνεται παντού για να έχετε γράψει το μέγεθος του κεφαλαίου,
και αντικαθιστά το κείμενο αυτό κυριολεκτικά με ένα 8, έτσι απλά.
Υπό αυτή την έννοια, αυτό είναι πολύ διαφορετική από μια μεταβλητή.
Δεν καταλαμβάνει χώρο στη μνήμη.
Είναι ένα απλό τέχνασμα αντικατάσταση κειμένου.
Σε αυτή την περίπτωση, θα πάμε να χρησιμοποιήσετε το μέγεθος.
Από εδώ θέλουμε να κάνουμε κάποιο είδος της επανάληψης,
και είμαστε στο σωστό δρόμο με do-while loop μας.
Θέλουμε να κάνουμε κάτι μέχρι μια κατάσταση που δεν ισχύει πια,
και όπως είδαμε νωρίτερα, είδαμε ότι η κατάσταση
Ήταν πράγματι ότι δεν θέλουμε το τέλος
να είναι μικρότερο από το να αρχίσει.
>> Αυτή είναι η στάση μας κατάσταση.
Εάν συμβεί αυτό, θέλουμε να σταματήσουμε και να δηλώνει, όπως, «Hey, δεν έχουμε βρει τίποτα."
Για να εκφράσουν αυτό, θέλουμε να χρησιμοποιούν κάποιο είδος του βρόχου.
Σε αυτή την περίπτωση, θα ήταν ένα do-while loop, ένα για βρόχο, ενώ ένας βρόχος;
Έχουμε ένα do-while loop εδώ.
Do you guys, όπως αυτή την προσέγγιση;
Πιστεύετε ότι θα πρέπει να δοκιμάσετε μια διαφορετική προσέγγιση;
Κέβιν, οποιεσδήποτε σκέψεις;
Θα μπορούσαμε να έχουμε ένα βρόχο, ενώ επειδή γνωρίζουμε κατ 'ανώτατο όριο
θα ήταν μεγαλύτερο από min στην anyways έναρξης.
Ναι, έτσι δεν υπάρχει καμία προετοιμασία που πρέπει να γίνει.
Οι do-while loops είναι μεγάλη όταν έχετε κάτι να προετοιμαστεί
πριν από τη δοκιμή, στη συνέχεια, ενώ εδώ
ξέρουμε ότι δεν πρόκειται να κρατήσει τόσο reinitializing αρχίζει και να τελειώνει
κάθε γύρο του βρόχου.
Ξέρουμε ότι θέλουμε να τους προετοιμάσει, στη συνέχεια ελέγξτε μας κατάσταση.
Σε αυτήν την περίπτωση, εγώ θα πάω στην πραγματικότητα με ένα απλό βρόχο while.
Αποδεικνύεται ότι είναι do-while loops χρησιμοποιούνται αρκετά σπάνια.
Μια πολλά μέρη δεν έχουν ακόμη διδάσκουν ενώ βρόχους.
Είναι καλό για το χειρισμό είσοδο του χρήστη, έτσι έχουμε δει πολλά από αυτά μέχρι σήμερα.
Αλλά και για την κανονική, ενώ βρόχοι είναι πολύ πιο κοινή.
Αποδεικνύεται ότι η προϋπόθεση αυτή ως γραπτή
δεν θα μας κάνει πραγματικά πολύ καλή, και γιατί συμβαίνει αυτό;
Λυπάμαι, δεν ξέρω το όνομά σου.
Είμαι Τζέρι. >> Συγνώμη;
Είναι Β-Ο-Κ-Υ-Ι.
Ω, εντάξει.
Δεν βλέπετε στη λίστα μου.
Ω, αυτό συμβαίνει γιατί-OH, που κάνει αίσθηση.
Έχετε μια ιδέα για το γιατί αυτό το βρόχο, ενώ δεν θα μπορούσε να λειτουργήσει ως στόχο,
όπως είναι γραμμένο με την κατάσταση;
[Τζέρι] Εννοείς όπως θέλετε όλα τα πράγματα αφού η-σε;
Ναι, έτσι ώστε να είναι ένα.
Μπορεί να έχουμε να θέσει όλα αυτά τα πράγματα μέσα στο βρόχο while, η οποία είναι εντελώς αλήθεια.
Το άλλο πράγμα που είναι λίγο πιο προβληματική, όμως, είναι ότι αυτή η κατάσταση δεν λειτουργεί.
[Φοιτητικό] Θα πρέπει να το γυρίσετε.
Σωστά, έτσι ώστε αυτή η κατάσταση δεν θα είναι ποτέ αλήθεια αρχικά ο τρόπος που μίλησε γι 'αυτό.
Θέλουμε να κάνουμε κάτι μέχρι <τέλος ξεκινήσει,
αλλά θέλουμε να κάνουμε κάτι, ενώ
αρχίζουν ≤ τέλος.
>> Υπάρχει ότι η αντιστροφή της λογικής εκεί.
Είμαι ένοχοι αυτά τα λάθη όλη την ώρα.
[Φοιτητικό] Γιατί πρέπει να είναι μικρότερη ή ίση με?
Επειδή εσείς δεν θυμάστε την υπόθεση ότι φτάσαμε στο
όπου υπήρχε μόνο ένα στοιχείο, και ήμασταν κάτω,
και ψάχναμε ακριβώς στη 15 σε σειρά μας;
Και μας αρχή και στο τέλος μας ήταν το ίδιο στοιχείο.
Θέλουμε να είμαστε σίγουροι ότι χειριστεί την υπόθεση.
Αν κάναμε μια ευθεία λιγότερο από ό, τι,
θα είναι σε θέση να πιάσουμε μια σειρά 2-στοιχείο.
Μόλις φτάσαμε μέχρι αυτό το τελευταίο στοιχείο, αν αυτό ήταν το στοιχείο μας, ποτέ δεν θα το βρείτε.
Τώρα, εδώ, μπορούμε να κάνουμε ακριβώς όπως έλεγες.
Μπορούμε να αρχίσουμε να plopping πράγματα δεξιά στη μέση του βρόχου while μας.
Μπορούμε να γδούπο στο μέσον μας.
Μπορούμε να πάρουμε όλα αυτά, αν δηλώσεις,
τραβήξτε τους έξω από αυτό το do-while loop,
γδούπο τους,
καθαρίσετε τα πράγματα λίγο,
και θα πάω μπροστά και να σώσει αυτή την αναθεώρηση.
Και σε αυτό το σημείο, παίρνουμε πολύ κοντά.
Sam.
Νομίζω ότι θα πρέπει επίσης να έχουν int = μέσο μέγεθος - 1/2.
Got it, μέγεθος - 1/2.
Υπάρχει κάτι άλλο που πρέπει να αλλάξουμε για αυτή τη γραμμή εκεί;
Αυτό ήταν μια καλή ψαριά.
>> Τι μέγεθος κάνει; Είμαστε αλλάζουν ποτέ μέγεθος;
Για να κρατήσει τη γραμμή, όπως αυτό, θα πρέπει να αλλάξετε το μέγεθος.
Πρέπει να αλλάξετε το μέγεθος κάθε φορά που πάμε γύρω από το βρόχο for.
Αλλά να θυμάστε όταν θα πήγαιναν με το παράδειγμά μας και λίγο νωρίτερα,
και είχαμε την αρχή στους 4
και το τέλος σε όλη τη διαδρομή πάνω στο 108;
Πώς θα υπολογίσετε το μέσο;
Αν κάνουμε χρήση του μεγέθους;
Ή θα χρησιμοποιούσαν αρχίζει και να τελειώνει αντ 'αυτού;
Είναι η διαφορά μεταξύ του τέλους και της αρχής.
Ακριβώς, και πώς ακριβώς θα πρέπει να γράψω ότι, Charlotte;
Μόλις τελειώσει - να αρχίσει.
Δεν θα πρέπει να κάνει το - 1
επειδή η - 1 έχει συμπεριληφθεί στο τέλος και την ξεκινήσει ήδη.
[Nate] Μεγάλη, είσαι εντελώς δεξιά.
Δεν έχουμε να κάνουμε το - 1 επειδή αυτό - 1 έχει συμπεριληφθεί
και υπολογίζονται όταν έχουμε προετοιμαστεί το μεταβλητό τέλος.
>> Υπάρχει κάτι άλλο που πρέπει να κάνω συντακτικά να έχουν αυτό το νόημα γραμμή εκεί;
[Φοιτητικό] Plus αρχίσει. >> Plus ξεκινήσει;
[Φοιτητικό] Στο τέλος.
Επειδή είναι μόνο υπολογίζεται το μισό του μήκους.
Θα πρέπει να προσθέσετε το ξεκινήσει.
[Nate] Τι θα υπολογίσει αυτό για εμάς;
Αν σκεφτούμε τέλος σε αυτή τη πρώτη επανάληψη του βρόχου,
άκρο πρόκειται να είναι σε θέση δείκτη 7.
Αρχίστε είναι στη θέση 0.
Θυμηθείτε, ψάχνουμε είτε
θέση 3 ή στη θέση 4.
Αν κοιτάξουμε αυτό μαθηματικά, απλά για να γίνει λίγο πιο απτή,
θέσει κάποιους αριθμούς εδώ, έχουμε 7, 0,
έτσι 7 - 0, και στη συνέχεια / 2
είναι 3 στο ακέραιο τμήμα, αυτό είναι.
Τότε χρειαζόμαστε να προσθέσει στη συνέχεια πίσω μας ξεκινήσω;
Εμείς δεν κάνουμε σε αυτή την περίπτωση.
Από την πρώτη κιόλας επανάληψη, θα είναι ωραία επειδή begin είναι 0.
Όμως, καθώς προχωρούμε, κάνουμε πραγματικά όλα το μόνο που χρειάζεται
τέλος - να αρχίσει / 2.
Υπάρχει ένα άλλο τέχνασμα εδώ, και ότι είναι δηλαδή ένας από τους προτεραιότητα.
[Φοιτητικό] Χρειαζόμαστε παρενθέσεις;
[Nate] Ακριβώς, και αυτό γιατί αν δεν βάλουμε αυτά τα παρενθέσεις,
τότε αυτή η γραμμή θα πρέπει να ερμηνευθεί αντί
ως (τέλος) - (έναρξη / 2), το οποίο σίγουρα δεν θέλουν.
Προσέξτε για τους κανόνες προτεραιότητας.
[Φοιτητικό] Γιατί δεν καταλήγουν + ξεκινήσει;
Γιατί δεν είναι το τέλος + ξεκινήσει;
[Φοιτητικό] Γιατί δεν είναι αυτό;
Γιατί θα ήταν +;
Νομίζω ότι έχεις δίκιο.
[Φοιτητικό] Επειδή είναι κατά μέσο όρο;
[Nate] Τέλος + αρχίσει, είσαι εντελώς δεξιά.
Πω πω, εντελώς goofed. Έχεις δίκιο.
Αν κάναμε το μείον, θα θέλαμε να προσθέσετε το αρχίσει ξανά μέσα
Σε αυτή την περίπτωση, είστε πολύ σωστό ότι θέλουμε να πάρει το μέσο όρο των δύο,
έτσι θέλουμε να τα προσθέσετε, σε αντίθεση με τους αφαιρέσετε.
[Φοιτητικό] Θα λειτουργήσει επίσης εάν κάνατε τέλος - να αρχίσει / 2 + αρχίσει.
Θα ήταν, αν κάνουμε-έτσι πιστεύω.
>> Για παράδειγμα, αν ψάχναμε στο αρχίσουν,
και εμείς θα μετατοπιστεί εδώ
στο 15.
Τώρα αρχίζουν είναι στη θέση 2.
Τέλος είναι στη θέση 7.
Αν αφαιρέσουμε τους, έχουμε 5.
Διαιρέστε ότι με το 2, παίρνουμε 2.
Και τότε προσθέστε 2 πίσω,
και ότι μας παίρνει την 4η θέση,
το οποίο είναι ακριβώς εδώ, το οποίο είναι το μέσο.
[Φοιτητικό] Μήπως πρέπει να αναλάβει τη φροντίδα του περιτυλίγματος;
Με ποια έννοια δεν θα πρέπει να αναλάβει τη φροντίδα του περιτυλίγματος;
Αν το ποσό ή η διαφορά μεταξύ
ανάλογα με το πώς το κάνουμε δεν είναι ένας άρτιος αριθμός.
Στη συνέχεια, ο υπολογιστής μπερδεύεται αν και όταν είναι 2,5?
δεν κινείστε προς τα αριστερά ή προς τα δεξιά για να καθορίσει ποια είναι το μέσο;
Πήρε αυτό.
Αποδεικνύεται ότι με διαίρεσης,
δεν παίρνουμε ποτέ αυτές τις αριθμούς κινητής υποδιαστολής.
Ποτέ δεν πάρετε το δεκαδικό.
Είναι εντελώς απορρίπτονται.
Αν έχετε έναν υπολογιστή χωρίζουν δύο int μεταβλητών,
και το ένα είναι 7, και το άλλο είναι 2,
δεν θα πάρετε 3,5 ως αποτέλεσμα.
Θα πάρει 3.
Το υπόλοιπο θα πρέπει να απορρίπτεται, έτσι ώστε να είναι αποτελεσματικά στρογγυλοποίηση
όχι γύρο, αλλά μάλλον ένα πάτωμα, αν εσείς είστε εξοικειωμένοι με ότι στα μαθηματικά,
όπου θα απορρίψει εντελώς το δεκαδικό,
και έτσι είστε περικοπή κατ 'ουσίαν προς τα κάτω στο πλησιέστερο
ολόκληρη θέση, στον πλησιέστερο ακέραιο αριθμό.
[Φοιτητικό] Στη συνέχεια, όμως αυτό είναι προβληματικό, διότι αν έχετε μια σειρά από 7 στοιχεία
τότε αυτό παίρνει αυτόματα το 3ο στοιχείο από το μέσο, ​​αντί του 4ου.
Πώς μπορούμε να αντιμετωπίσουμε με αυτό;
Είναι προβληματική, διότι αν είχαμε μια σειρά από 7,
θα πάρει το 3ο αντί του 4ου.
Θα μπορούσατε να μας εξηγήσετε λίγο περισσότερο;
[Φοιτητικό] Γιατί αν έχετε 7 στοιχεία τότε το 4ο στοιχείο
θα είναι το κεντρικό σημείο, έτσι δεν είναι;
Θυμηθείτε το σχόλιό σας για την ύπαρξη δείκτη μηδέν, όμως.
[Φοιτητικό] Ναι, έτσι στη θέση 3. Αυτό θα είναι το κεντρικό σημείο.
Ναι.
Ω, εντάξει. Βλέπω τι εννοείς.
Είναι το είδος της παράξενο, όπως έχουμε συνηθίσει όλο αυτό έννοια της
να απαλλαγούμε από δεκαδικών ψηφίων.
Αυτό είναι ένα μεγάλο σημείο.
Ας τελειώσει αυτό επάνω.
Έχουμε υπολογίζεται μέσο μας.
>> Εμείς δοκιμάζουμε για να δούμε αν βελόνα μας είναι ίση με τη μέση τιμή.
Είμαστε εκτύπωση ότι το βρήκαμε, αλλά πραγματικά, τι θέλουμε να κάνουμε σε αυτή την κατάσταση;
Έχουμε το βρήκε, έτσι θέλουμε να αφήσουμε τον καλούντα ξέρω ότι το βρήκαμε.
Έχουμε μια λειτουργία που είναι ένα δακτυλογραφημένο boolean λειτουργία.
Ο τρόπος που σηματοδοτούν στον καλούντα της λειτουργίας μας ότι είμαστε έτοιμοι να προχωρήσουμε
είναι που λέμε, "Γεια σου, αυτό είναι αλήθεια."
Πώς θα το κάνουμε αυτό, Kevin;
Είστε κουνώντας το κεφάλι σας. >> [Kevin] Προσθήκη επιστροφή αλήθεια.
[Nate] Ακριβώς, επιστρέφουν αλήθεια.
Τώρα, αν αυτό δεν είναι ίσες, πώς θα δούμε στο αριστερό μισό;
Οποιεσδήποτε ιδέες;
Στέλλα, οποιεσδήποτε ιδέες;
Θα πρέπει να ορίσετε μια νέα θέση για το τέλος.
Ναι.
Έτσι πρέπει να κάνουμε θέση του μέσο - το τέλος.
Μεγάλη.
Πρέπει να ορίσετε μια νέα θέση για το τέλος
να εξετάσουμε το αριστερό μισό.
Αυτό ήταν ό, τι μιλήσαμε πριν, όπου
I keep going back σε αυτό το παράδειγμα.
Έχω ξεκινήσει εδώ το, και στη συνέχεια να έχω το τέλος σε όλη τη διαδρομή πάνω από εδώ.
>> Και πάλι, αν ψάχνουμε για 15, και κεντρικό σημείο μας είναι στα 16,
και συνειδητοποιούμε, «Ωχ, 16 είναι μεγαλύτερη.
Θέλουμε να προχωρήσουμε στο αριστερό μισό. "
Θα προχωρήσουμε στη συνέχεια, το τέλος του 15,
και να το κάνουμε αυτό με τη λήψη ενός μακριά από το μέσο
και τον καθορισμό ότι ως νέα καταληκτική μας.
Ομοίως, αν θέλουμε να δούμε το δεξί μισό, πώς θα το κάνουμε αυτό;
Έχετε μια ιδέα;
[Φοιτητικό] Απλά που αρχίζουν να κεντρικό σημείο + 1.
[Nate] Μεγάλη.
Και τώρα, σε περίπτωση που δεν βρουν τίποτα,
ότι δεν παίρνουν ληφθεί μέριμνα για εμάς;
Ντάνιελ, δεν παίρνουν ότι ληφθεί μέριμνα για εμάς;
[Daniel] Όχι.
[Nate] Αν το κάνουμε σε όλο το φάσμα και δεν βρίσκουν τίποτα,
όπου θα πρέπει να ληφθεί μέριμνα, ή θα πρέπει να αναλάβει τη φροντίδα του;
[Δανιήλ] Η κατάσταση, ενόσω.
[Nate] Ναι, η κατάσταση, ενώ, ακριβώς.
Θα φροντίσει να περάσει από ολόκληρο τον πίνακα, αν δεν βρούμε τίποτα.
Αυτός ο βρόχος ενώ θα τελειώσει.
Θα έχουμε ποτέ δεν αντιμετώπισε αυτή την κατάσταση,
και μπορούμε να επιστρέψουμε ψευδείς.
Μπορούμε επίσης να αφήσετε το αν σε αυτό εδώ σαν
γιατί αν αυτή η δήλωση, αν είναι αλήθεια,
και τη λειτουργία μας θα επιστρέψει,
και έτσι θα διακόψει ουσιαστικά αυτή η λειτουργία σε αυτό το σημείο
όταν θα επιστρέψουν στην αλήθεια.
Αλλά τι συμβαίνει με αυτή τη δομή εδώ;
Αυτό θα λειτουργήσει εξ ολοκλήρου, ή υπάρχει κάποια λογική σε ελάττωμα εκεί;
>> Υπάρχει κάποια λογική σε ελάττωμα εκεί, με τον τρόπο που έχει συσταθεί.
Τι θα μπορούσε να είναι;
[Φοιτητικό] Γιατί θα πρέπει να έχετε το - και + 1s;
Αυτό θέτει σειρά μας για να είναι νέο αριστερό μισό μας και το δεξί μισό.
[Φοιτητικό] Αλλά γιατί δεν θα μπορούσε να το κάνει χωρίς το - 1s + και 1s;
[Nate] Θα μπορούσε να οριστεί ίσο με το μέσο;
Τι θα μπορούσε να είναι προβληματικό γι 'αυτό;
[Φοιτητικό] Υποθέτω ότι είναι αναποτελεσματική, γιατί είστε έλεγχο μια τιμή που είναι ήδη ελεγχθεί.
[Nate] Ακριβώς, έτσι Sam είναι εντελώς σωστό.
Εάν ορίσετε το τέλος και η έναρξη ίση με το μέσο
αντί - 1 + 1 και στοχαστικά,
σε κάποιο σημείο στο μέλλον θα καταλήξουμε έλεγχο το μέσο ξανά.
[Φοιτητικό] άρχισα το PSET, και τότε είχα κάτι τέτοιο
όπου Ξέχασα το + 1, και κόλλησε σε ένα άπειρο βρόχο.
Σωστά, γιατί σε κάποιο σημείο δεν πρόκειται ποτέ να πάρει αρχίζουν και τελειώνουν
πραγματικά να επικαλύπτονται.
Cool.
Υπάρχει ένα πιο λογικό σφάλμα, και αυτό είναι ότι αυτό θα πρέπει οπωσδήποτε να
ένα άλλο, εάν.
Γιατί μπορεί να συμβαίνει αυτό;
>> Ο λόγος είναι, αν δεν είναι ένας άλλος-αν είδες αυτό, Kevin;
[Kevin] Ναι, επειδή είστε αλλάζει το τελικό σημείο.
[Nate] Ακριβώς.
Αλλάζουμε το τελικό σημείο,
και αν είναι γραμμένο σαν αυτό-we'll κάνει διαστήματα μεταξύ-
θα ελέγξει αυτή την υπόθεση.
Η υπόθεση αυτή, αν πετύχει, θα ματαιωθεί από τη λειτουργία.
Στη συνέχεια, θα ελέγξει την επόμενη περίπτωση,
και αν αυτό πετύχει, θα προσαρμόσει το τελικό σημείο,
και στη συνέχεια θα συνεχίσει και να ελέγξει αυτή την υπόθεση.
Αλλά σε αυτό το σημείο, δεν θέλουμε να συνεχιστεί ο έλεγχος.
Ευτυχώς, δεν έχουμε να επαναφέρετε το μέσο εδώ,
και γνωρίζουμε ότι αυτή η υπόθεση δεν θα πετύχει.
Αλλά σίγουρα θέλει να βάλει το άλλο αν εκεί
παρά το γεγονός ότι θα μπορούσε-σε αυτή την περίπτωση
αφού δεν είμαστε ρύθμιση το μέσο, ​​θα κάνουν ότι μια διαφορά;
Όχι, γιατί αυτές οι περιπτώσεις είναι όλα τα αποκλειστικά.
Και πάλι, η κακή μου.
Δεν νομίζω ότι χρειάζεται αυτό το else if.
Μπορούμε να δώσουμε μια δοκιμή και να τρέξει και να δούμε τι θα συμβεί.
Κτίριο, ένα σφάλμα.
Είναι πιθανώς επειδή έφυγα από αυτά και β ηλεκτρονικού εδώ.
Έχω κάποια περισσότερα από αυτά μέχρι την κορυφή;
Δεν μοιάζει με αυτό.
Εμείς σμίκρυνση, την κατασκευή,
εκεί πηγαίνει, έτσι και τώρα, αν ψάχνουμε για 15,
Ναι.
Επιτρέψτε μου να μεγεθύνετε
15, ναι. Μπορούμε να τρέξει ξανά.
Μεταφόρτωση του πηγαίου κώδικα, τη δημιουργία, λειτουργία.
Μπορούμε να ψάξει για κάτι σαν 13,
και εμείς δεν παίρνουν τίποτα εκτύπωση, έτσι δεν είναι διαπίστωση ότι για μας.
Αυτό είναι μεγάλη, επειδή δεν είναι στη λίστα μας.
>> Είμαστε τώρα από του χρόνου.
Αυτό πρόκειται να είναι αυτό για αυτήν την εβδομάδα.
Ευχαριστώ για την ένταξη, και τα λέμε αργότερα.
>> [CS50.TV]