ROB BOWDEN: Γεια σας, είμαι ο Rob Bowden, και ας μιλήσουμε για quiz0.
>> Έτσι, το πρώτο ερώτημα.
Αυτό είναι το ερώτημα στο οποίο που έπρεπε να δίνεται ο αριθμός
127 στο δυαδικό βολβούς.
Αν ήθελε, θα μπορούσε να κάνει την τακτική μετατροπής
από bi-- ή, από το δεκαδικό στο δυαδικό.
Αλλά αυτό είναι κατά πάσα πιθανότητα θα να πάρει πολύ χρόνο.
Εννοώ, θα μπορούσα να καταλάβω ότι, Εντάξει, 1 είναι εκεί, 2 είναι εκεί,
4 είναι εκεί, 8 είναι εκεί.
Ευκολότερη τρόπο, 127 είναι 128 μείον ένα.
Αυτή η λάμπα αριστερότερο είναι ο 128-bit.
Έτσι 127 είναι πραγματικά ακριβώς όλα των άλλων λαμπτήρων,
δεδομένου ότι είναι η αριστερότερη λάμπα μείον 1.
Αυτό είναι για το συγκεκριμένο ζήτημα.
>> Ερώτηση ένα.
Έτσι, με 3 κομμάτια μπορείτε αντιπροσωπεύουν 8 διακριτές τιμές.
Γιατί, λοιπόν, είναι η 7 η μεγαλύτερη μη-αρνητικό ακέραιος αριθμός που μπορεί να αντιπροσωπεύει;
Λοιπόν, αν μπορούμε μόνο αντιπροσωπεύουν 8 διακριτές τιμές,
τότε τι θα πάμε να είναι που εκπροσωπούν είναι από 0 έως 7.
0 καταλαμβάνει μία από τις αξίες.
>> Ερώτηση δύο.
Με Ν bits, πόσες διακριτές τιμές μπορεί να σας εκπροσωπήσει;
Έτσι, με n bits, έχετε 2 πιθανές τιμές για κάθε bit.
Έτσι έχουμε 2 πιθανές τιμές για Το πρώτο bit, 2 πιθανές τιμές
για το δεύτερο, 2 είναι δυνατόν για το τρίτο.
Και έτσι αυτό είναι 2 φορές 2 φορές 2, και τελικά, η απάντηση είναι 2 στο Ν.
>> Ερώτηση τρία.
Τι είναι 0x50 σε δυαδικό;
Έτσι, να θυμάστε ότι δεκαεξαδικό έχει ένα πολύ απλή μετατροπή σε δυαδικό.
Μέχρι εδώ, εμείς απλά πρέπει να δούμε το 5 και το 0 ανεξάρτητα.
Έτσι τι είναι 5 στο δυαδικό;
0101, αυτό είναι το bit 1 και το 4 bit.
Τι είναι 0 σε δυαδικό;
Δεν είναι δύσκολο.
0000.
Έτσι τα βάλει μόνο μαζί, και ότι είναι ο πλήρης αριθμός σε δυαδικό.
01010000.
Και αν ήθελε θα μπορούσε να απογείωση που αριστερότερο μηδέν.
Είναι άσχετο.
>> Έτσι, στη συνέχεια, εναλλακτικά, τι είναι 0x50 σε δεκαδικό;
Αν ήθελε, θα could-- αν είστε πιο άνετα με το δυαδικό,
θα μπορούσατε να πάρετε αυτό το δυαδικό απάντηση και να μετατρέψετε ότι σε δεκαδικό.
Ή θα μπορούσαμε απλά να θυμάστε ότι δεκαεξαδικό.
Έτσι ώστε 0 είναι στο 0-ου τόπος, και το 5 είναι το 16 στην πρώτη θέση.
Μέχρι εδώ, έχουμε 5 φορές 16 με το πρώτα, συν 0 φορές 16 στο μηδέν,
είναι 80.
Και αν κοίταξε το τίτλος στο ερώτημα,
ήταν CS 80, το οποίο ήταν το είδος της ένα υπαινιγμός για την απάντηση σε αυτό το πρόβλημα.
>> Ερώτηση πέντε.
Έχουμε αυτό το σενάριο Scratch, η οποία είναι επαναλαμβάνοντας 4 φορές φυστικοβούτυρο ζελέ.
Έτσι, πώς εμείς τώρα τον κωδικό που σε C;
Λοιπόν, έχουμε here-- έχουν το μέρος με έντονους είναι το μόνο μέρος που έπρεπε να εφαρμόσουν.
Έτσι έχουμε ένα 4 βρόχο που είναι looping 4 φορές, printf-σης φυστικοβούτυρο ζελέ,
με τη νέα γραμμή, όπως το πρόβλημα ζητά.
>> Ερώτηση έξι, ένα άλλο πρόβλημα Ξυστό.
Βλέπουμε ότι είμαστε σε ένα βρόχο για πάντα.
Εμείς λέμε την μεταβλητή i και στη συνέχεια προσαύξηση i από 1.
Τώρα θέλουμε να το κάνουμε αυτό σε C. Υπάρχουν πολλαπλούς τρόπους με τους οποίους θα μπορούσαν να το έχουν κάνει αυτό.
Εδώ έτυχε να κωδικοποιήσει το πάντα βρόχο ως μια στιγμή (αλήθεια).
Έτσι, δηλώνουμε την μεταβλητή i, απλά όπως είχαμε μεταβλητή i στο Ξυστό.
Δηλώστε τη μεταβλητή i, και για πάντα ενώ η (πραγματική), λέμε τη μεταβλητή i.
Έτσι printf% i-- ή θα μπορούσατε να έχετε χρησιμοποιήσει% d.
Λέμε ότι η μεταβλητή, και στη συνέχεια να την αυξήσετε, i ++.
>> Ερώτηση επτά.
Τώρα θέλουμε να κάνουμε κάτι πολύ παρόμοιο στο Mario dot C από το πρόβλημα που μία.
Θέλουμε να εκτυπώσετε αυτά τα hashtags, θέλουμε να εκτυπώσετε πέντε
από τρεις ορθογώνιο αυτών των hashes.
Λοιπόν, πώς θα πάμε να το κάνουμε αυτό;
Λοιπόν, θα σας δώσω μια ολόκληρη μάτσο κώδικα, και απλά
πρέπει να συμπληρώσετε τη λειτουργία του δικτύου εκτύπωσης.
>> Έτσι τι PrintGrid μοιάζει;
Καλά είστε παρελθόν, η το πλάτος και το ύψος.
Έτσι έχουμε ένα εξωτερικό 4 βρόχου, που είναι looping
πάνω από όλες τις σειρές αυτό πλέγμα που θέλετε να εκτυπώσετε.
Στη συνέχεια έχουμε την ενδο-ένθετα 4 βρόχο, ότι είναι η εκτύπωση πάνω από κάθε στήλη.
Έτσι, για κάθε σειρά, θα εκτυπώσετε για κάθε στήλη, ένα ενιαίο χασίς.
Στη συνέχεια, στο τέλος της σειράς θα εκτυπώσετε μια νέα ενιαία γραμμή για να μεταβείτε στην επόμενη σειρά.
Και αυτό είναι για το σύνολο του δικτύου.
>> Ερώτηση οκτώ.
Μια συνάρτηση, όπως PrintGrid λέγεται έχει μια παρενέργεια, αλλά όχι μια επιστροφή
αξία.
Εξηγήστε τη διάκριση.
Έτσι, αυτό εξαρτάται από εσάς να θυμόμαστε τι μια παρενέργεια είναι.
Λοιπόν, μια επιστροφή value-- γνωρίζουμε PrintGrid δεν
έχει τιμή επιστροφής, δεδομένου εδώ λέει άκυρη.
Έτσι, κάτι που επιστρέφει κενό δεν επιστρέφει τίποτα.
Έτσι ποια είναι η παρενέργεια;
Λοιπόν, μια παρενέργεια είναι οτιδήποτε είδους επιμένει
μετά το τέλος της λειτουργίας ότι δεν ήταν μόλις επέστρεψε,
και δεν ήταν μόνο από τις εισόδους.
>> Έτσι, για παράδειγμα, θα μπορούσαμε αλλάξετε μια καθολική μεταβλητή.
Αυτό θα μπορούσε να είναι μια παρενέργεια.
Σε αυτή τη συγκεκριμένη περίπτωση, μια πολύ σημαντική παρενέργεια
εκτυπώνει στην οθόνη.
Έτσι ώστε να είναι μια παρενέργεια ότι PrintGrid έχει.
Εμείς να εκτυπώσετε αυτά τα πράγματα στην οθόνη.
Και μπορείτε να σκεφτείτε ότι, ως παρενέργεια,
δεδομένου ότι αυτό είναι κάτι που επιμένει μετά τελειώνει αυτή η λειτουργία.
Αυτό είναι κάτι έξω από το πεδίο εφαρμογής αυτής της λειτουργίας που τελικά
είναι να αλλάξει, η περιεχόμενα της οθόνης.
>> Ερώτηση εννέα.
Εξετάστε το πρόγραμμα παρακάτω, στην οποία οι αριθμοί γραμμή
έχουν προστεθεί για η χάρη της συζήτησης.
Έτσι, σε αυτό το πρόγραμμα είμαστε μόνο καλώντας GetString, την αποθήκευσή
Σε αυτήν την μεταβλητή s, και στη συνέχεια, την εκτύπωση της μεταβλητής s.
ΟΚ.
Έτσι εξηγήσει γιατί μία γραμμή είναι παρούσα.
#include CS50 dot h.
Γιατί πρέπει να #include CS50 dot h;
Καλά είμαστε καλώντας το GetString λειτουργία,
και GetString ορίζεται στη βιβλιοθήκη CS50.
Έτσι, αν δεν είχαμε #include CS50 dot h,
θα πάρει ότι σιωπηρή δήλωση του σφάλματος λειτουργίας GetString
από τον compiler.
Γι 'αυτό και πρέπει να περιλαμβάνει το library-- θα πρέπει να συμπεριλάβετε το αρχείο κεφαλίδας,
ή αλλιώς ο compiler δεν θα αναγνωρίζουν ότι υπάρχει GetString.
>> Εξηγήστε γιατί γραμμή δύο είναι παρούσα.
Έτσι πρότυπο io dot h.
Είναι ακριβώς η ίδια όπως και το προηγούμενο πρόβλημα,
εκτός αντί αντιμετώπιση GetString, μιλάμε για printf.
Έτσι, αν εμείς δεν είπαμε χρειαζόμαστε να περιλαμβάνει τις τυποποιημένες io dot h,
τότε δεν θα είμαστε σε θέση να χρησιμοποιήσετε τη λειτουργία printf,
γιατί τον compiler δεν θα γνωρίζουν.
>> Why-- ποια είναι η σημασία του κενού στη γραμμή τέσσερα;
Έτσι, εδώ έχουμε int main (void).
Αυτό ακριβώς λέμε ότι δεν παίρνουν καμία γραμμή εντολών
επιχειρήματα στο κύριο.
Να θυμάστε ότι θα μπορούσαμε να πούμε int κύρια int argc παρένθεση εγχόρδων argv.
Έτσι, εδώ απλά λέμε κενό για να πούμε εμείς Οι αγνοώντας τα επιχειρήματα της γραμμής εντολών.
>> Εξηγούν, σε σχέση με τη μνήμη, ακριβώς τι GetString στη γραμμή έξι αποδόσεις.
GetString επιστρέφει ένα μπλοκ του μνήμη, μια σειρά χαρακτήρων.
Είναι πραγματικά μια επιστροφή Pointer στον πρώτο χαρακτήρα.
Να θυμάστε ότι ένα string είναι ένα αστέρι ΧΑΡ.
Έτσι s είναι ένας δείκτης για την πρώτη χαρακτήρα σε ό, τι το string είναι
ότι ο χρήστης εγγράφεται στο πληκτρολόγιο.
Και ότι η μνήμη που συμβαίνει να malloced, έτσι ώστε η μνήμη είναι στο σωρό.
>> Ερώτηση 13.
Εξετάστε το παρακάτω πρόγραμμα.
Έτσι όλο αυτό το πρόγραμμα κάνει είναι printf-ing 1 διαιρείται με το 10.
Έτσι, όταν καταρτίζονται και εκτελείται, αυτό το πρόγραμμα
εξόδους 0,0, μολονότι 1 διαιρούμενο με 10 είναι 0,1.
Γιατί λοιπόν είναι 0.0;
Λοιπόν, αυτό είναι επειδή της ακέραιος διαίρεσης.
Έτσι, 1 είναι ένας ακέραιος, 10 είναι ένας ακέραιος.
Έτσι, 1 διαιρούμενο με 10, όλα αντιμετωπίζεται ως ακέραιοι,
και C, όταν κάνουμε διαίρεση ακέραιο, έχουμε περικόψει οποιαδήποτε δεκαδικού ψηφίου.
Έτσι, 1 διαιρούμενο με 10 0, και στη συνέχεια προσπαθούμε
να εκτυπώσετε ότι ως ένα πλωτήρα, έτσι μηδέν εκτυπώνονται ως πλωτήρας είναι 0,0.
Και γι 'αυτό παίρνουμε 0.0.
>> Εξετάστε το παρακάτω πρόγραμμα.
Τώρα είμαστε εκτύπωση 0.1.
Έτσι, δεν υπάρχει διαίρεση ακέραιο, είμαστε απλά εκτυπώνετε 0.1,
αλλά είμαστε αυτό εκτύπωση με 28 δεκαδικά ψηφία.
Και παίρνουμε αυτό το 0,1000, ένα σωρό από μηδενικά, 5 5 5, μπλα μπλα μπλα.
Έτσι, το ερώτημα εδώ είναι γιατί το κάνει εκτυπώστε ότι, αντί ακριβώς 0.1;
>> Έτσι, ο λόγος εδώ είναι τώρα κινητής υποδιαστολής ανακρίβεια.
Θυμηθείτε ότι ένας πλωτήρας είναι μόνο 32 bits.
Έτσι μπορούμε να αντιπροσωπεύουν μόνο ένα πεπερασμένο αριθμό των τιμών κινητής υποδιαστολής με αυτά τα 32
bits.
Καλά υπάρχει τελικά απείρως πολλές τιμές κινητής υποδιαστολής,
και υπάρχουν απείρως πολλά πλωτά τιμές σημείο μεταξύ 0 και 1,
και είμαστε προφανώς σε θέση να αντιπροσωπεύουν ακόμη περισσότερες τιμές από αυτό.
Έτσι πρέπει να κάνουμε θυσίες για να να είναι σε θέση να αντιπροσωπεύουν το μεγαλύτερο μέρος αξίες.
>> Έτσι μια τιμή, όπως 0,1, προφανώς δεν μπορούμε να εκπροσωπεί ότι ακριβώς.
Έτσι, αντί να εκπροσωπούν 0.1 κάνουμε το καλύτερο μπορούμε να αναπαραστήσουμε αυτό 0.100000 5 5
5.
Και αυτό είναι πολύ κοντά, αλλά για πολλές εφαρμογές
έχετε να ανησυχείτε για κινητής υποδιαστολής ανακρίβεια,
γιατί απλά δεν μπορεί να αντιπροσωπεύει όλα τα πλωτά σημεία ακριβώς.
>> Ερώτηση 15.
Θεωρήστε τον παρακάτω κώδικα.
Είμαστε μόνο εκτύπωση 1 συν 1.
Έτσι δεν υπάρχει κανένα τέχνασμα εδώ.
1 συν 1 αποτιμάται σε 2, και τότε είμαστε εκτύπωση αυτό.
Αυτό απλά τυπώνει 2.
>> Ερώτηση 16.
Τώρα είμαστε εκτύπωση του χαρακτήρα 1 συν το χαρακτήρα 1.
Γιατί λοιπόν να κάνει αυτό που δεν εκτυπώστε το ίδιο πράγμα;
Λοιπόν ο χαρακτήρας 1 συν το χαρακτήρα 1, ο χαρακτήρας 1 έχει τιμή ASCII 49.
Έτσι, αυτό είναι πραγματικά λέγοντας 49 συν 49, και τελικά αυτό πρόκειται να εκτυπώσετε 98.
Έτσι, αυτό δεν εκτυπώνει 2.
>> Ερώτηση 17.
Ολοκλήρωση της εφαρμογής περίεργο παρακάτω με τέτοιο τρόπο
ότι η συνάρτηση επιστρέφει true αν n είναι περιττός και ψευδής αν το n είναι άρτιος.
Αυτό είναι ένα μεγάλο σκοπό για το mod χειριστή.
Έτσι παίρνουμε το επιχείρημα μας ν, αν n mod 2 ισούται με 1, και
αυτό σημαίνει ότι n διαιρείται με 2 είχε ένα υπόλοιπο.
Εάν n διαιρείται με 2 είχε ένα υπόλοιπο, ότι σημαίνει ότι ο n είναι περιττός, οπότε επιστρέφουμε αλήθεια.
Αλλιώς θα επιστρέψει false.
Μπορείτε, επίσης, θα μπορούσε να γίνει n mod 2 ίσων μηδέν, επιστρέφει False, αλλιώς επιστρέφει αλήθεια.
>> Εξετάστε την αναδρομική συνάρτηση παρακάτω.
Έτσι, αν η είναι μικρότερο ή ίσο με 1, επιστροφή 1,
άλλο αντάλλαγμα n φορές στ του ν μείον 1.
Έτσι τι είναι αυτή η λειτουργία;
Λοιπόν, αυτό είναι ακριβώς το παραγοντικό λειτουργία.
Αυτό είναι όμορφα εκπροσωπείται καθώς το n παραγοντικό.
>> Έτσι ερώτηση 19 τώρα, θέλουμε να λαμβάνουν αυτό αναδρομική συνάρτηση.
Θέλουμε να γίνει επαναληπτική.
Λοιπόν, πώς θα το κάνουμε αυτό;
Καλά για το προσωπικό λύση, και πάλι δεν υπάρχει
πολλαπλούς τρόπους που θα μπορούσαν να έχουν γίνει ότι, ξεκινάμε με αυτό το προϊόν int
ισούται με 1.
Και όλη αυτή η για βρόχο, θα πάμε
να πολλαπλασιάζοντας το προϊόν σε τελικά καταλήγουν με την πλήρη παραγοντικό.
Έτσι, για int i ισούται με 2, i είναι μικρότερη ή ίση με n, i ++.
>> Ίσως να αναρωτιέστε γιατί i ισούται με 2.
Λοιπόν, να θυμάστε ότι εδώ έχουμε να βεβαιωθείτε ότι βασική μας υπόθεση είναι σωστή.
Έτσι, αν η είναι μικρότερη ή ίση σε 1, είμαστε μόλις είχαν επιστρέψει 1.
Έτσι, εδώ, έχουμε ξεκινήσει σε i ισούται με 2.
Λοιπόν αν μου ήταν 1, τότε the-- ή αν n ήταν 1, τότε ο βρόχος for
δεν θα εκτελέσει καθόλου.
Και γι 'αυτό θα ήταν απλά προϊόν επιστροφή, η οποία είναι 1.
Ομοίως, εάν το η ήταν τίποτα λιγότερο από 1--
αν ήταν μηδέν, αρνητικές 1, whatever-- θα ήθελα ακόμα να επιστρέφει 1,
το οποίο είναι ακριβώς ό, τι το αναδρομική έκδοση κάνει.
>> Τώρα, εάν το η είναι μεγαλύτερο από 1, τότε θα πάμε
να κάνουμε τουλάχιστον ένα επανάληψη αυτού του βρόχου.
Ας πούμε ότι το π είναι 5, τότε είμαστε πρόκειται να κάνει χρόνους προϊόν ισούται με 2.
Έτσι τώρα το προϊόν είναι 2.
Τώρα θα πάμε να κάνουμε φορές προϊόντος ισούται με 3.
Τώρα είναι 6.
Χρόνοι προϊόν ισούται με 4, τώρα είναι 24.
Χρόνοι προϊόν ισούται με 5, τώρα είναι 120.
Μέχρι τότε, τελικά, γυρίζουμε 120, το οποίο είναι σωστά 5 παραγοντικό.
>> Ερώτηση 20.
Αυτό είναι το ένα, όπου θα πρέπει να συμπληρώσετε σε αυτόν τον πίνακα με οποιοδήποτε δεδομένο αλγόριθμο,
κάτι που έχουμε δει, ότι ταιριάζει με αυτά αλγοριθμική τρέξιμο
φορές αυτές οι ασυμπτωτικές χρόνους λειτουργίας.
Έτσι τι είναι ένας αλγόριθμος που είναι το ωμέγα 1, αλλά μεγάλο O Ν;
Έτσι, θα μπορούσε να υπάρξει απείρως πολλές απαντήσεις εδώ.
Το μόνο που έχουμε δει πιθανώς πιο συχνά είναι ακριβώς γραμμική αναζήτηση.
>> Έτσι, στην καλύτερη περίπτωση, σενάριο, το στοιχείο είμαστε
ψάχνει για είναι σε το αρχή της λίστας
και έτσι σε ωμέγα 1 βήματα, το πρώτο πράγμα που ελέγχει,
εμείς απλά επιστρέψει αμέσως ότι βρήκαμε το στοιχείο.
Στη χειρότερη περίπτωση, το στοιχείο είναι στο τέλος,
ή το στοιχείο δεν είναι στη λίστα καθόλου.
Έτσι, πρέπει να ψάξουμε ολόκληρη τη λίστα, όλα τα n
στοιχεία, και γι 'αυτό είναι ο Ν.
>> Έτσι, τώρα είναι κάτι που είναι τόσο ω του n log n, και μεγάλη O Ν log n.
Καλά το πιο σχετικό πράγμα έχουμε δει εδώ είναι η συγχώνευση του είδους.
Έτσι Ταξινόμηση με συγχώνευση, θυμηθείτε, είναι τελικά θήτα
του n log n, όπου θήτα ορίζεται αν τα δύο ωμέγα και μεγάλη O είναι το ίδιο.
Τόσο n log n.
>> Αυτό είναι κάτι που είναι ωμέγα Ν, και Ο του Ν τετράγωνο;
Λοιπόν, και πάλι δεν υπάρχει πολλαπλές πιθανές απαντήσεις.
Εδώ τυχαίνει να πούμε bubble sort.
Ταξινόμηση με εισαγωγή θα μπορούσε επίσης να λειτουργήσει εδώ.
Να θυμάστε ότι το bubble sort έχει ότι η βελτιστοποίηση όπου,
αν είστε σε θέση να πάρετε καθ 'όλη τη λίστα
χωρίς να χρειάζεται να κάνετε τυχόν ανταλλαγές, τότε, επίσης,
μπορούμε να επιστρέψουμε αμέσως ότι ο κατάλογος ήταν ταξινομημένο για να αρχίσει με.
Έτσι, στην καλύτερη περίπτωση, είναι ακριβώς ωμέγα της Ν.
Αν αυτό δεν είναι απλά μια ωραία ταξινομημένη λίστα για να αρχίσει με,
τότε έχουμε O Ν τετράγωνο swaps.
Και τέλος, έχουμε το είδος επιλογής για ν τετράγωνο, τόσο ωμέγα και μεγάλα O.
>> Ερώτηση 21.
Τι είναι ακέραιος υπερχείλιση;
Καλά πάλι, παρόμοια με τις προηγούμενες, έχουμε μόνο πεπερασμένο πλήθος bits
να αντιπροσωπεύει έναν ακέραιο, οπότε ίσως 32 bits.
Ας πούμε ότι έχουμε ένα υπογεγραμμένο ακέραιο.
Στη συνέχεια, τελικά, το υψηλότερο θετικός αριθμός που μπορεί να αντιπροσωπεύει
είναι 2 έως το 31 μείον 1.
Λοιπόν, τι θα συμβεί αν προσπαθήσουμε να στη συνέχεια, αύξηση που ακέραιος;
Λοιπόν, θα πάμε για να πάει από το 2 έως το 31 μείον 1, σε όλη τη διαδρομή προς τα κάτω σε αρνητικές 2
στο 31.
Έτσι, αυτό είναι ακέραιος υπερχείλισης όταν κρατάτε προσαύξηση,
και, τελικά, δεν μπορείτε πάρετε οποιαδήποτε υψηλότερη και αυτό ακριβώς
αναδιπλώνεται όλος ο τρόπος πίσω γύρω σε μια αρνητική τιμή.
>> Τι γίνεται με υπερχείλιση;
Έτσι, ένα ρυθμιστικό overflow-- θυμηθείτε τι ένα ρυθμιστικό είναι.
Είναι απλά ένα κομμάτι της μνήμης.
Κάτι σαν μια συστοιχία είναι ένα ρυθμιστικό.
Έτσι, η υπερχείλιση του buffer είναι όταν μπορείτε να προσπαθήσετε να αποκτήσετε πρόσβαση μνήμης
πέρα από το τέλος της εν λόγω διάταξης.
Έτσι, εάν έχετε ένα σειρά μεγέθους 5 και
προσπαθήσετε να αποκτήσετε πρόσβαση βραχίονα σειρά 5 ή 6 ή στήριγμα βραχίονα 7,
ή οτιδήποτε άλλο πέρα ​​από το τέλος, ή ακόμα και τίποτα
below-- βραχίονα σειρά αρνητικών 1-- όλα αυτά είναι υπερχειλίσεις μνήμης.
Είσαι αγγίζοντας μνήμης σε κακή τρόπους.
>> Ερώτηση 23.
Έτσι, σε αυτό που χρειάζεστε για την εφαρμογή της strlen.
Και θα σας πω ότι μπορείτε να υποθέσουμε s δεν θα είναι μηδενική,
έτσι ώστε να μην χρειάζεται να κάνει οποιοδήποτε έλεγχο για μηδενική.
Και υπάρχουν πολλοί τρόποι θα μπορούσατε να είχατε κάνει αυτό.
Εδώ έχουμε λάβει μόνο την απλή.
Ξεκινάμε με ένα μετρητή, Ν. η είναι μετρώντας πόσοι χαρακτήρες υπάρχουν.
Ξεκινάμε λοιπόν σε 0, και στη συνέχεια εμείς επαναλάβετε σε ολόκληρη τη λίστα.
>> Είναι s βραχίονα 0 ίση με το null χαρακτήρα τερματισμού;
Θυμηθείτε ψάχνουμε για η μηδενική χαρακτήρας τερματισμού
για να καθορίσει πόσο μακριά σειρά μας είναι.
Αυτό πρόκειται να τερματίσει κάθε σχετική κορδόνι.
Έτσι είναι s βραχίονα 0 ίση με τη μηδενική τερματισμού;
Αν δεν είναι, τότε θα πάμε να εξετάσουμε s βραχίονα 1, s βραχίονα 2.
Συνεχίζουμε μέχρι να βρείτε τη μηδενική τερματισμού.
Μόλις έχουμε βρει, τότε η περιέχει το συνολικό μήκος του κορδονιού,
και μπορούμε απλά να επιστρέψει αυτό.
>> Ερώτηση 24.
Έτσι, αυτό είναι το ένα, όπου μπορείτε πρέπει να κάνουν το εμπόριο off.
Έτσι, ένα πράγμα είναι καλό σε ένα τρόπο, αλλά με ποιο τρόπο είναι αυτό κακό;
Μέχρι εδώ, συγχώνευση είδος τείνει να είναι ταχύτερη από ό, τι bubble sort.
Τούτου λεχθέντος that-- καλά, εκεί είναι πολλαπλές απαντήσεις εδώ.
Αλλά το κυριότερο είναι ότι το bubble sort είναι ω ν για μια ταξινομημένη λίστα.
>> Θυμηθείτε αυτόν τον πίνακα μόλις είδαμε νωρίτερα.
Έτσι φούσκα ταξινομεί ωμέγα της n, το καλύτερο σενάριο
είναι ότι είναι σε θέση να πήγαινε πάνω ο κατάλογος φορά, καθορίζουν
hey αυτό το πράγμα είναι ήδη διαλογή, και την επιστροφή.
Ταξινόμηση με συγχώνευση, δεν έχει σημασία τι κάνετε, είναι ωμέγα της n log n.
Έτσι, για την ταξινομημένη λίστα, φούσκα Ταξινόμηση πρόκειται να είναι ταχύτερη.
>> Τώρα τι γίνεται με συνδεδεμένες λίστες;
Έτσι, μια συνδεδεμένη λίστα μπορεί να αναπτυχθεί και να συρρικνωθεί για να χωρέσει όσο πολλά στοιχεία, όπως απαιτείται.
Αφού είπε that-- έτσι συνήθως η άμεση σύγκριση
πρόκειται να είναι ένα συνδεδεμένο λίστα με μια σειρά.
Έτσι, ακόμα κι αν συστοιχίες μπορούν εύκολα να αναπτυχθούν και να συρρικνωθεί
για να χωρέσει τόσες στοιχεία όπως απαιτείται, μια λίστα που συνδέεται
σε σύγκριση με ένα array-- σειρά έχει τυχαίας προσπέλασης.
Μπορούμε δείκτη σε οποιαδήποτε συγκεκριμένο στοιχείο της συστοιχίας.
>> Έτσι, για μια συνδεδεμένη λίστα, δεν μπορούμε απλά πηγαίνετε στο πέμπτο στοιχείο,
πρέπει να διασχίσει από την αρχή μέχρι να φτάσουμε στο πέμπτο στοιχείο.
Και αυτό πρόκειται να μας αποτρέψει από να κάνει κάτι σαν δυαδική αναζήτηση.
Μιλώντας δυαδική αναζήτηση, δυαδική αναζήτηση τείνει να είναι ταχύτερη από ό, τι με τη γραμμική αναζήτηση.
Αφού είπε that-- έτσι, ένα δυνατό πράγμα
είναι ότι δεν μπορείτε να κάνετε δυαδικό αναζήτηση σε συνδεδεμένες λίστες,
μπορείτε να το κάνετε μόνο σε συστοιχίες.
Αλλά ίσως το πιο σημαντικό, δεν μπορείτε να κάνετε δυαδική αναζήτηση
σε μια σειρά που δεν είναι ταξινομημένο.
Εξ αρχής μπορεί να χρειαστεί να ταξινομήσετε η συστοιχία, και μόνο τότε μπορεί να
κάνετε δυαδική αναζήτηση.
Έτσι, αν το πράγμα σας δεν είναι διαλεγμένα για να αρχίσει με,
Στη συνέχεια γραμμική αναζήτηση μπορεί να είναι γρηγορότερη.
>> Ερώτηση 27.
Έτσι, θεωρούν το πρόγραμμα παρακάτω, η οποία θα είναι στην επόμενη διαφάνεια.
Και αυτό είναι το ένα, όπου είμαστε Θα ήθελα να δηλώσω ρητά
Οι τιμές για διάφορες μεταβλητές.
Έτσι, ας ρίξουμε μια ματιά σε αυτό.
>> Έτσι, μία γραμμή.
Έχουμε int x ισούται με 1.
Αυτό είναι το μόνο πράγμα που συνέβη.
Έτσι, σε μία γραμμή, βλέπουμε σε μας τραπέζι, η Υ, Α, Β, και tmp είναι όλα
σκοτεινόχρωμα.
Έτσι τι είναι x;
Λοιπόν αυτό που ακριβώς ίσο με 1.
Και τότε η Γραμμή δύο, και, βλέπουμε ότι η ομάδα έχει οριστεί σε 2,
και ο πίνακας είναι ήδη συμπληρώνεται για εμάς.
Έτσι, το χ είναι 1 και το γ είναι 2.
>> Τώρα, γραμμή τρεις, είμαστε τώρα μέσα στη συνάρτηση swap.
Τι περνάμε να ανταλλάξουν;
Περάσαμε συμπλεκτικό σύμβολο x για Α, και εμπορικό και y για β.
Όταν το πρόβλημα νωρίτερα δήλωσε ότι η διεύθυνση του x
είναι 0x10, και η διεύθυνση του y είναι 0x14.
Έτσι, α και b είναι ίσες με 0x10 και 0x14, αντίστοιχα.
>> Τώρα στη γραμμή τρία, ποια είναι τα x και y;
Λοιπόν, τίποτα δεν έχει αλλάξει για x και y σε αυτό το σημείο.
Ακόμα κι αν είστε μέσα σε ένα κύριο πλαίσιο στοίβας,
που εξακολουθούν να έχουν το ίδιο αξίες που έκαναν πριν.
Δεν έχουμε τροποποιήσει οποιαδήποτε μνήμη.
Έτσι, το χ είναι 1, το γ είναι 2.
Εντάξει.
Μέχρι τώρα είπαμε int tmp ίσο να πρωταγωνιστήσει ένα.
Έτσι, στη γραμμή τέσσερα, τα πάντα είναι η ίδια εκτός από tmp.
Δεν έχουν αλλάξει οποιεσδήποτε τιμές τίποτα εκτός από tmp.
Θέτουμε tmp ίσα να πρωταγωνιστήσει ένα.
Τι είναι ένα αστέρι;
Λοιπόν, ένα σημεία x, λοιπόν πρωταγωνιστήσει ένα πρόκειται για ίση x, η οποία είναι 1.
Έτσι, τα πάντα είναι αντιγραφή προς τα κάτω, και TMP έχει οριστεί σε 1.
>> Τώρα, η επόμενη γραμμή.
Αστέρι το α ισούται με αστέρι β.
Έτσι, από τη γραμμή five-- και πάλι καλά, τα πάντα είναι η ίδια, εκτός από ό, τι ένα αστέρι είναι.
Τι είναι ένα αστέρι;
Λοιπόν, εμείς απλά είπε ένα αστέρι είναι x.
Έτσι αλλάζουμε x για ίση αστέρι β.
Τι είναι το αστέρι β; Υ. σημεία β έως y.
Έτσι αστέρων b είναι y.
Έτσι είμαστε ρύθμιση x ίσο με το y, και όλα τα άλλα είναι το ίδιο.
Έτσι βλέπουμε στην επόμενη σειρά ότι το x είναι τώρα 2, και τα υπόλοιπα είναι απλώς αντιγράψει.
>> Τώρα στην επόμενη γραμμή, αστέρι β ισούται tmp.
Λοιπόν, εμείς απλά είπε αστέρων b είναι y, έτσι είμαστε ρύθμιση y ίσο με tmp.
Όλα τα άλλα είναι η ίδια, έτσι όλα παίρνουν αντιγράψει.
Είμαστε ρύθμιση y ίσο με ΠΔΤ, η οποία είναι ένα, και όλα τα άλλα είναι το ίδιο.
>> Τώρα, τέλος, σειρά επτά.
Είμαστε πίσω στην κύρια λειτουργία.
Είμαστε μετά τη συμφωνία ανταλλαγής έχει τελειώσει.
Έχουμε χάσει ένα, b, και tmp, αλλά τελικά εμείς
δεν αλλάζουν οποιεσδήποτε τιμές τίποτα σε αυτό το σημείο,
εμείς απλά να αντιγράψετε x και y προς τα κάτω.
Και βλέπουμε ότι τα x και y είναι τώρα 2 και 1, αντί του 1 και 2.
Η συμφωνία ανταλλαγής έχει εκτελεστεί με επιτυχία.
>> Ερώτηση 28.
Ας υποθέσουμε ότι έχετε να αντιμετωπίσετε τα μηνύματα λάθους
κάτω κατά τη διάρκεια των ωρών γραφείου το επόμενο έτος, όπως μια ΑΠ ή TF.
Συμβουλές πώς να διορθώσετε το καθένα από αυτά τα λάθη.
Έτσι αόριστη αναφορά σε GetString.
Γιατί μπορεί να βλέπετε αυτό;
Λοιπόν, αν ένας μαθητής χρησιμοποιεί GetString στον κώδικά τους,
έχουν σωστά hash περιλαμβάνονται CS50 dot h για να συμπεριλάβει τη βιβλιοθήκη CS50.
>> Λοιπόν, τι κάνουν αυτοί Πρέπει να διορθώσετε αυτό το σφάλμα;
Θα πρέπει να κάνετε μια εξόρμηση σε lcs50 η γραμμή εντολών όταν είναι κατάρτιση.
Έτσι, αν δεν περάσει κλαγγή παύλα lcs50, είναι
δεν πρόκειται να έχουν την πραγματική κώδικα που υλοποιεί GetString.
>> Ερώτηση 29.
Εμμέσως δηλώνοντας λειτουργία βιβλιοθήκης strlen.
Καλά αυτό τώρα, δεν έχουν κάνει τη σωστή hash περιλαμβάνουν.
Στη συγκεκριμένη περίπτωση, το αρχείο header θα πρέπει να συμπεριλάβετε είναι εγχόρδων dot h,
και συμπεριλαμβανομένων των εγχόρδων dot ώρα, τώρα η student-- τώρα ο compiler
έχει πρόσβαση ο δηλώσεις του strlen,
και γνωρίζει ότι ο κωδικός σας χρησιμοποιεί σωστά strlen.
>> Ερώτηση 30.
Περισσότερες μετατροπές τοις εκατό από τα επιχειρήματα των δεδομένων.
Λοιπόν, τι είναι αυτό;
Καλά να θυμάστε ότι αυτά τοις εκατό signs-- πώς είναι σχετικές με τις printf.
Έτσι, στην printf θα μπορούσαμε να percent-- θα μπορούσαμε να εκτυπώσετε κάτι
όπως τοις εκατό i backslash n.
Ή θα μπορούσαμε να εκτυπώσετε σαν ποσοστό θ, χώρου, επί τοις εκατό Ι, το διάστημα, επί τοις εκατό Ι.
Έτσι, για κάθε ένα από αυτά σημάδια τοις εκατό, χρειαζόμαστε
να περάσει μια μεταβλητή στο τέλος της printf.
>> Έτσι, αν λέμε παρένθεσης printf τοις εκατό i backslash n κλείσιμο παρένθεσης,
καλά, μπορούμε να πούμε ότι είμαστε πρόκειται να εκτυπώσετε έναν ακέραιο,
αλλά τότε δεν περνούν printf ένας ακέραιος για να εκτυπώσετε πραγματικά.
Έτσι, εδώ περισσότερα τοις εκατό μετατροπές από τα επιχειρήματα των δεδομένων;
Αυτό λέει ότι έχουμε ένα σωρό ποσοστά,
και δεν έχουμε αρκετές μεταβλητές να συμπληρώσετε πραγματικά σε αυτές ποσοστά.
>> Και τότε σίγουρα, για την ερώτηση 31, σίγουρα έχασε 40 bytes σε ένα μπλοκ.
Έτσι, αυτό είναι ένα λάθος Valgrind.
Αυτό λέει ότι κάπου στον κώδικά σας,
έχετε μια κατανομή που είναι 40 bytes μεγάλα ώστε να malloced 40 bytes,
και ποτέ δεν θα απελευθερωθεί.
Το πιο πιθανό είναι το μόνο που χρειάζεται να βρείτε κάποια διαρροή μνήμης,
και βρείτε πού θα πρέπει να ελευθερώσετε αυτό το μπλοκ της μνήμης.
>> Και ερώτηση 32, άκυρη εγγραφής του μεγέθους 4.
Και πάλι αυτό είναι ένα λάθος Valgrind.
Αυτό δεν έχει να κάνει με διαρροές μνήμης τώρα.
Αυτό είναι, οι περισσότεροι likely-- εννοώ, είναι κάποιο είδος άκυρα δικαιώματα μνήμης.
Και το πιο πιθανό είναι κάποια το είδος της υπερχείλισης buffer.
Όταν έχετε μια σειρά, ίσως μια σειρά ακέραιος, και ας
λένε ότι είναι του μεγέθους 5, και σας προσπαθήστε να αγγίξετε βραχίονα πίνακα 5.
Έτσι, αν προσπαθήσετε να γράψετε ότι αξία, αυτό δεν είναι ένα κομμάτι της μνήμης
ότι έχετε πράγματι πρόσβαση σε αυτά, και έτσι θα πάμε για να πάρει αυτό το σφάλμα,
λέγοντας άκυρο εγγραφής του μεγέθους 4.
Valgrind πρόκειται να αναγνωρίσετε ότι είστε προσπαθώντας να αγγίξει τη μνήμη ανάρμοστα.
>> Και αυτό είναι για quiz0.
Είμαι Rob Bowden, και αυτό είναι CS50.