1
00:00:00,000 --> 00:00:10,216
>> [Παίζει μουσική]

2
00:00:10,216 --> 00:00:12,060
>> ZAMYLA CHAN: Τώρα ας αντιμετωπίσουμε άπληστοι.

3
00:00:12,060 --> 00:00:14,390
Ας πούμε ότι είστε ένας ταμίας, και εσείς
πρέπει να δώσει τον πελάτη σας μια

4
00:00:14,390 --> 00:00:16,309
ορισμένο ποσό της αλλαγής.

5
00:00:16,309 --> 00:00:18,820
Λοιπόν, αν ήταν ένας άπληστος ταμείο,
θα θέλατε να κρατήσει όλους

6
00:00:18,820 --> 00:00:20,040
τα νομίσματα για τον εαυτό σας.

7
00:00:20,040 --> 00:00:24,310
Έτσι, θα δώσει στον πελάτη την αλλαγή τους
χρησιμοποιώντας ως λίγα κέρματα δυνατό.

8
00:00:24,310 --> 00:00:27,640
>> Ο στόχος σας για αυτό το p-που είναι η εφαρμογή
Greedy, ένα πρόγραμμα που

9
00:00:27,640 --> 00:00:30,530
υπολογίζει τον ελάχιστο αριθμό
των νομισμάτων που χρησιμοποιούνται για να κάνουν οποιαδήποτε

10
00:00:30,530 --> 00:00:31,940
δεδομένη ποσότητα της αλλαγής.

11
00:00:31,940 --> 00:00:35,660
Πριν από την κατάδυση στον προγραμματισμό
έννοιες και σύνταξη C για Greedy,

12
00:00:35,660 --> 00:00:38,410
ας μιλήσουμε πρώτα μέσω της Greedy
προγράμματος, και να δούμε αν μπορούμε

13
00:00:38,410 --> 00:00:40,570
μπορεί να εντοπίσει έναν αλγόριθμο.

14
00:00:40,570 --> 00:00:42,560
Θυμηθείτε ότι ένας αλγόριθμος
είναι απλά ένα σύνολο από

15
00:00:42,560 --> 00:00:44,680
οδηγίες για την επίλυση των προβλημάτων.

16
00:00:44,680 --> 00:00:48,060
Ένας αλγόριθμος για Greedy θα είναι απλώς μια
ορίζεται από λογικούς κανόνες και τα μέτρα που

17
00:00:48,060 --> 00:00:49,000
μπορούμε να ακολουθήσουμε.

18
00:00:49,000 --> 00:00:52,510
Και θα παράγουν πάντοτε το ελάχιστο
αριθμός των κερμάτων που χρειάζονται.

19
00:00:52,510 --> 00:00:54,340
>> Το πρώτο πράγμα που θα πρέπει να
γνωρίζουμε είναι πόσο μεγάλη αλλαγή

20
00:00:54,340 --> 00:00:55,710
οφείλεται στον πελάτη.

21
00:00:55,710 --> 00:00:58,560
Για αυτό το παράδειγμα, ας πούμε 0,32 δολάρια.

22
00:00:58,560 --> 00:01:00,880
Υπάρχουν πολλοί τρόποι για να πάρει πίσω $ 0,32.

23
00:01:00,880 --> 00:01:03,950
Θα μπορούσατε να χρησιμοποιήσετε, για παράδειγμα,
32 πένες.

24
00:01:03,950 --> 00:01:07,560
Ή αν ήσουν λίγο πιο άπληστοι σε
επιλέγοντας τα νομίσματά σας, μπορείτε να χρησιμοποιήσετε

25
00:01:07,560 --> 00:01:11,730
πέντε κέρματα αντί των 32 δίνοντας
ο πελάτης τρεις δεκάρες -

26
00:01:11,730 --> 00:01:14,690
Κάθε 0,10 δολάρια - και δύο πένες -
$ 0,01 η κάθε μία.

27
00:01:14,690 --> 00:01:16,830
>> Αλλά μπορούμε να κάνουμε κάτι καλύτερο από πέντε νομίσματα;

28
00:01:16,830 --> 00:01:18,990
Μπορούμε να είμαστε ακόμη πιο άπληστοι;

29
00:01:18,990 --> 00:01:20,410
Πολύ πιθανόν.

30
00:01:20,410 --> 00:01:23,360
>> Ας συνεχίσουμε με τα πόδια μέσα
το Greedy πρόγραμμα, και να δούμε.

31
00:01:23,360 --> 00:01:27,090
Αν ο τελικός στόχος σας είναι να χρησιμοποιήσετε μερικά κέρματα
όσο το δυνατόν, τότε θα ήταν πιο

32
00:01:27,090 --> 00:01:29,680
φρόνιμο να χρησιμοποιήσει το μεγαλύτερο
δυνατόν νομίσματα.

33
00:01:29,680 --> 00:01:32,410
Θα προτιμούσα να δώσω ένα τέταρτο
πίσω - 0,25 δολάρια κάθε -

34
00:01:32,410 --> 00:01:33,640
από πέντε σεντς -

35
00:01:33,640 --> 00:01:34,940
0,05 €.

36
00:01:34,940 --> 00:01:38,260
Έτσι, ίσως διέπουν κανόνας μας για
Greedy μπορεί να είναι να χρησιμοποιείτε πάντα το

37
00:01:38,260 --> 00:01:40,590
Η μεγαλύτερη δυνατή κέρμα.

38
00:01:40,590 --> 00:01:43,640
Από τρίμηνα, δεκάρες, πεντάρες,
και πένες, μας

39
00:01:43,640 --> 00:01:44,830
μεγαλύτερο κέρμα είναι το τρίμηνο.

40
00:01:44,830 --> 00:01:47,690
Γι 'αυτό και θα προσπαθήσουμε να τα χρησιμοποιήσετε για πρώτη φορά.

41
00:01:47,690 --> 00:01:49,270
>> Back to our $ 0.32.

42
00:01:49,270 --> 00:01:52,455
Μπορούμε να χρησιμοποιήσουμε ένα τέταρτο για να δώσει
ο πελάτης 0,32 δολάρια;

43
00:01:52,455 --> 00:01:52,930
Ναι.

44
00:01:52,930 --> 00:01:55,530
Αυτό θα μας αφήσει με 0,07 δολάρια αριστερά.

45
00:01:55,530 --> 00:01:57,440
>> Μπορούμε να χρησιμοποιήσουμε άλλο ένα τέταρτο;

46
00:01:57,440 --> 00:02:00,100
Όχι, επειδή 25 είναι μεγαλύτερο από επτά.

47
00:02:00,100 --> 00:02:03,470
Δεν θέλουμε να δώσουμε στον πελάτη
περισσότερο από ότι τους χρωστάμε.

48
00:02:03,470 --> 00:02:04,190
>> Εντάξει.

49
00:02:04,190 --> 00:02:07,370
Τώρα που έχουμε εξαντλήσει τέταρτα μας,
ας προχωρήσουμε στο επόμενο μεγαλύτερο

50
00:02:07,370 --> 00:02:09,090
νόμισμα, η δεκάρα.

51
00:02:09,090 --> 00:02:12,400
Μπορούμε να χρησιμοποιήσουμε μια δεκάρα για να δώσει την
πελάτη 0,07 δολάρια πίσω τους;

52
00:02:12,400 --> 00:02:15,100
Όχι, δεδομένου ότι 10 είναι μεγαλύτερο από επτά.

53
00:02:15,100 --> 00:02:18,400
>> Έτσι, τότε το επόμενο μεγαλύτερο κέρμα προσβάσιμο
για εμάς είναι το νικέλιο.

54
00:02:18,400 --> 00:02:19,590
Μπορούμε να χρησιμοποιήσουμε ένα νικέλιο;

55
00:02:19,590 --> 00:02:20,250
Ναι.

56
00:02:20,250 --> 00:02:22,940
Και τότε θα είχαμε 0,02 δολάρια απομείνει.

57
00:02:22,940 --> 00:02:24,910
>> Δεν μπορούμε να χρησιμοποιήσουμε ένα νικέλιο για να επιστρέψει $ 0,02.

58
00:02:24,910 --> 00:02:29,510
Γι 'αυτό και μετακόμισε το τελευταίο νόμισμα σε
διάθεσή μας - την πένα.

59
00:02:29,510 --> 00:02:33,090
Και μετά τη χρήση δύο πένες, θα ήθελα να
μένει με μηδενικό σεντς, πράγμα που σημαίνει ότι

60
00:02:33,090 --> 00:02:36,350
έχουμε επιτυχία επιστραφεί
ο χρήστης αλλαγή τους οφείλονται

61
00:02:36,350 --> 00:02:37,830
χρησιμοποιώντας μόνο τέσσερα νομίσματα -

62
00:02:37,830 --> 00:02:40,410
ένα τέταρτο, ένα νικέλιο,
και δύο πένες.

63
00:02:40,410 --> 00:02:43,880
>> Μπορείτε να εκτελέσετε τη λύση του προσωπικού για να δείτε αν
διέπουν τον κανόνα και η διαδικασία μας έδωσε

64
00:02:43,880 --> 00:02:44,770
μας η σωστή απάντηση.

65
00:02:44,770 --> 00:02:47,820
Για τους περισσότερους το πρόβλημα σύνολα, θα είστε σε θέση
εκτελέσετε την επίλυση του προσωπικού για να δείτε πώς

66
00:02:47,820 --> 00:02:49,900
το δικό σας πρόγραμμα θα πρέπει να εργαστεί.

67
00:02:49,900 --> 00:02:53,390
Και ειδικές οδηγίες θα
είναι το πρόβλημα θέτει specs.

68
00:02:53,390 --> 00:02:57,180
>> Μόλις εκτελέσετε την επίλυση του προσωπικού, το
μας ωθεί για πόση αλλαγή οφείλεται

69
00:02:57,180 --> 00:02:59,790
Επισημαίνεται ότι ζητά η
ανέρχονται σε δολάρια.

70
00:02:59,790 --> 00:03:03,580
Εμείς εισαγωγής $ 0,32, 0,32.

71
00:03:03,580 --> 00:03:06,830
Μας λέει ότι οι τέσσερις νομίσματα που οφείλονται,
συνάδει με την απάντησή μας.

72
00:03:06,830 --> 00:03:08,160
Fantastic.

73
00:03:08,160 --> 00:03:10,210
>> Έτσι, τώρα ας αρχίσει να ψάχνει
κατά την υλοποίηση

74
00:03:10,210 --> 00:03:11,780
του αλγορίθμου Greedy.

75
00:03:11,780 --> 00:03:13,410
Γνωρίζουμε ένα ζευγάρι πράγματα.

76
00:03:13,410 --> 00:03:17,280
Ένα, που θα πρέπει να ζητήσει από το
χρήστη για το ποσό της αλλαγής.

77
00:03:17,280 --> 00:03:20,830
>> Δύο, ότι θα θελήσετε να ακολουθήσετε μας
διέπουν κανόνα να χρησιμοποιείτε πάντα το

78
00:03:20,830 --> 00:03:22,990
Η μεγαλύτερη δυνατή κέρμα.

79
00:03:22,990 --> 00:03:26,370
Και τρεις, ότι πρέπει να παρακολουθείτε
πόσα κέρματα που χρησιμοποιούμε.

80
00:03:26,370 --> 00:03:30,040
Επειδή, τέλος, θα πρέπει να εκτυπώσετε
ο αριθμός των κερμάτων που έχουμε.

81
00:03:30,040 --> 00:03:33,270
>> Κατ 'αρχάς, που προτρέπει το χρήστη
για ένα ποσό της αλλαγής.

82
00:03:33,270 --> 00:03:36,880
Κάθε φορά που θα ασχοληθεί με την είσοδο του χρήστη, κάνει
βεβαιωθείτε ότι έχετε σκεφτεί όλα τα

83
00:03:36,880 --> 00:03:40,010
απαιτήσεις της εισόδου, και μόνο
δέχεται είσοδο που πληροί εκείνες

84
00:03:40,010 --> 00:03:40,880
απαιτήσεις.

85
00:03:40,880 --> 00:03:44,100
Σε αυτή την περίπτωση, θέλουμε να αντιμετωπίσουμε
μια νομισματική αξία σε δολάρια.

86
00:03:44,100 --> 00:03:48,230
>> Οι λειτουργίες GetFloat και GetInt εξασφαλίζουν
ότι η είσοδος είναι αριθμητικό.

87
00:03:48,230 --> 00:03:51,700
Αλλά ο χρήστης έχει τη δυνατότητα να εισάγει
αρνητικές αριθμητικές τιμές.

88
00:03:51,700 --> 00:03:56,260
Έτσι, να θυμάστε να χρησιμοποιείτε μόνο μη αρνητικές
εισροών, η οποία περιλαμβάνει όλες τις αρνητικές

89
00:03:56,260 --> 00:03:58,370
αριθμούς και το μηδέν.

90
00:03:58,370 --> 00:04:00,260
>> Στην περίπτωση αυτή, η είσοδος
θα πρέπει να είναι float.

91
00:04:00,260 --> 00:04:01,960
Με άλλα λόγια, ένας δεκαδικός αριθμός.

92
00:04:01,960 --> 00:04:06,000
Επειδή το σύνολο πρόβλημα spec απαιτεί
να σας ρωτήσω για την είσοδο σε δολάρια.

93
00:04:06,000 --> 00:04:09,540
>> Αλλά σε C, τιμές κινητής υποδιαστολής δεν μπορεί να
να εκπροσωπούνται με ακρίβεια.

94
00:04:09,540 --> 00:04:12,490
Επειδή υπάρχει ένας πεπερασμένος αριθμός
των bits με τα οποία να

95
00:04:12,490 --> 00:04:14,870
αντιπροσωπεύουν απείρου.

96
00:04:14,870 --> 00:04:16,860
Πάρτε τον αριθμό 0.1.

97
00:04:16,860 --> 00:04:21,140
Αν ήθελα να σας ζητήσω να γράψετε 0,1 από
χέρι στο εκατοστό δεκαδικό ψηφίο,

98
00:04:21,140 --> 00:04:24,380
θα γράφετε 1, ακολουθούμενη
από 99 μηδενικά.

99
00:04:24,380 --> 00:04:27,080
Εμείς θα περίμενε κανείς ότι ο υπολογιστής μας θα
εκτυπώσετε ακριβώς το ίδιο πράγμα

100
00:04:27,080 --> 00:04:28,330
αν ζητήσαμε.

101
00:04:28,330 --> 00:04:30,320
>> Ας δούμε λοιπόν τι κάνει.

102
00:04:30,320 --> 00:04:33,150
Θα επανεξετάσει τις τιμές προς εκτύπωση
το τέλος αυτής περπατήσει μέσα.

103
00:04:33,150 --> 00:04:39,270
Προς το παρόν, δείτε εδώ ότι η f% είναι
θέση αντικειμένου για κινητής υποδιαστολής.

104
00:04:39,270 --> 00:04:44,530
Αλλά διευκρινίζει εκ των προτέρων ότι θέλουμε
100 δεκαδικών ψηφίων που εμφανίζονται, και στη συνέχεια μια νέα

105
00:04:44,530 --> 00:04:46,506
γραμμή για καλύτερο μορφοποίηση.

106
00:04:46,506 --> 00:04:51,710
>> Μετά από τη σειρά, επιλέγουμε 0,1 ως η
επιπλέουν ότι θέλουμε να εκτυπώσετε.

107
00:04:51,710 --> 00:04:56,680
Και το αποτέλεσμα, ένα ένα, ακολουθούμενη
από ορισμένους μηδενικά, αλλά στη συνέχεια ένα

108
00:04:56,680 --> 00:04:57,980
σωρό των αριθμών.

109
00:04:57,980 --> 00:05:00,470
Σίγουρα όχι όπως αναμενόταν.

110
00:05:00,470 --> 00:05:03,490
>> Κινητής υποδιαστολής ανακρίβεια μπορεί να εισαγάγει
σφάλματα στρογγυλοποίησης σας

111
00:05:03,490 --> 00:05:07,330
υπολογισμών που θα
σίγουρα θέλουν να αποφύγουν.

112
00:05:07,330 --> 00:05:10,900
Εάν θέλετε να δείτε περισσότερα παραδείγματα, θα
μπορείτε να κατεβάσετε από το imprecision.ce

113
00:05:10,900 --> 00:05:14,880
με τα πόδια μέσω κώδικα, το οποίο είναι ένα απλό
πρόγραμμα που ζητά να επιπλέουν και να εκτυπώνει

114
00:05:14,880 --> 00:05:17,550
πίσω στο εκατοστό δεκαδικό ψηφίο.

115
00:05:17,550 --> 00:05:20,340
Φυσικά, εάν θέλετε να εμφανίσετε
περισσότερο ή λιγότερο δεκαδικά ψηφία

116
00:05:20,340 --> 00:05:22,410
μπορείτε να αλλάξετε τον εαυτό σας.

117
00:05:22,410 --> 00:05:25,740
>> Όπως θα δείτε, αν και η διαφορά
μεταξύ των δύο είναι μικρή, όταν μπορείτε να πάρετε

118
00:05:25,740 --> 00:05:30,460
για τον πολλαπλασιασμό και την προσθήκη αρμάτων, ότι
ασυμφωνία μπορεί τελικά να προσθέσει επάνω.

119
00:05:30,460 --> 00:05:31,790
Back στο Greedy.

120
00:05:31,790 --> 00:05:34,870
Θα θέλουν να αποφύγουν λάθη στρογγυλοποίησης
με την αντιμετώπιση ακέραιους αριθμούς.

121
00:05:34,870 --> 00:05:38,090
Έτσι, μετά παίρνουμε έγκυρη συμβολή
ο χρήστης, ας μετατραπεί αυτή

122
00:05:38,090 --> 00:05:39,550
τιμή του δολαρίου σε σεντ.

123
00:05:39,550 --> 00:05:43,420
>> Διανοητικά, να το κάνουμε αυτό με τον πολλαπλασιασμό
η αξία του δολαρίου κατά 100.

124
00:05:43,420 --> 00:05:46,400
Αλλά να θυμάστε, λόγω της κινητής υποδιαστολής
ανακρίβεια, θέλουμε να κάνουμε

125
00:05:46,400 --> 00:05:48,580
βέβαιος ότι είμαστε με τη σωστή τιμή.

126
00:05:48,580 --> 00:05:52,510
Πολλαπλασιάζοντας με 100 θα κινηθεί ουσιαστικά
το δεκαδικό ψηφίο δύο κενά για να

127
00:05:52,510 --> 00:05:56,640
το δικαίωμα, κόβοντας ή περικοπή
τίποτα μετά.

128
00:05:56,640 --> 00:05:59,430
>> Αν παίξετε γύρω με λίγο περισσότερο
παραδείγματα, θα δείτε ότι δεν θα

129
00:05:59,430 --> 00:06:02,980
πήρε πάντα το σωστό αριθμό, αν
χρησιμοποιούν αυτή τη μέθοδο περικοπή.

130
00:06:02,980 --> 00:06:10,011
Για παράδειγμα, 12,59 εκτυπωθεί σε 100
δεκαδικά ψηφία, που σας δίνει

131
00:06:10,011 --> 00:06:14,050
12.5899, κ.λπ..

132
00:06:14,050 --> 00:06:18,460
Θα παίρνατε 12.58, αν περικοπεί,
Δεν 12.59, όπως χρειάζεστε.

133
00:06:18,460 --> 00:06:21,130
>> Αντ 'αυτού, είναι καλύτερο να στρογγυλοποιεί
ο αριθμός για πρώτη φορά.

134
00:06:21,130 --> 00:06:23,930
Ευτυχώς, C έρχεται με το
λειτουργία που ονομάζεται γύρος.

135
00:06:23,930 --> 00:06:25,040
Είναι στη βιβλιοθήκη μαθηματικά.

136
00:06:25,040 --> 00:06:28,540
>> Αν θέλετε να ξέρετε πώς να χρησιμοποιήσετε Round,
τότε μπορείτε να φέρετε το εγχειρίδιο ή

137
00:06:28,540 --> 00:06:30,550
Η σελίδα man για την εν λόγω λειτουργία.

138
00:06:30,550 --> 00:06:35,510
Μπορείτε να το κάνετε αυτό με την πληκτρολόγηση του ανθρώπου, μικρή για
εγχειρίδιο, και στη συνέχεια η λειτουργία που σας

139
00:06:35,510 --> 00:06:36,620
θέλετε να αναζητήσετε.

140
00:06:36,620 --> 00:06:42,280
Έτσι, πληκτρολογώντας γύρου του άνδρα στο τερματικό
γραμμή εντολών θα εμφανιστεί το εγχειρίδιο.

141
00:06:42,280 --> 00:06:44,790
>> Θα μπορούσε να είναι λίγο δύσκολο να αποκρυπτογραφήσει,
αλλά τελικά θα

142
00:06:44,790 --> 00:06:45,660
το συνηθίσετε αυτό.

143
00:06:45,660 --> 00:06:48,290
Ο άνθρωπος σελίδες σας δείξει ποια είναι η λειτουργία
κάνει, και στη συνέχεια κάποιες

144
00:06:48,290 --> 00:06:50,170
πιθανές χρήσεις του.

145
00:06:50,170 --> 00:06:52,340
Θα σας αφήσω να διερευνήσει
η σελίδα man για το δεύτερο γύρο.

146
00:06:52,340 --> 00:06:55,960
Αλλά να ξέρετε ότι μπορείτε να το χρησιμοποιήσετε για να στρογγυλοποιεί
η αξία κατά τη διάρκεια της μετατροπής από

147
00:06:55,960 --> 00:06:57,180
δολάρια σε σεντ.

148
00:06:57,180 --> 00:06:59,690
>> Γύρος θα σας δώσει πίσω ένα αριθμό
τύπο δεδομένων διπλό.

149
00:06:59,690 --> 00:07:03,810
Και μπορείτε να μετατρέψετε ή χυτό
το σε ένα int μετά.

150
00:07:03,810 --> 00:07:04,980
Μεγάλη.

151
00:07:04,980 --> 00:07:08,120
Μέχρι τώρα έχουμε ζητηθεί από το χρήστη
για ένα χρηματικό ποσό, και

152
00:07:08,120 --> 00:07:09,520
το μετέτρεψε σε σεντ.

153
00:07:09,520 --> 00:07:12,410
Τώρα μπορούμε να εφαρμόσουμε έναν αλγόριθμο
που χρησιμοποιεί πάντα το

154
00:07:12,410 --> 00:07:14,640
μεγαλύτερο κερμάτων διαθέσιμων.

155
00:07:14,640 --> 00:07:17,790
>> Λάβετε υπόψη ότι υπάρχουν πολλαπλές
τρόπων για την υλοποίηση Greedy, όπως ακριβώς

156
00:07:17,790 --> 00:07:21,200
υπάρχουν πολλοί τρόποι για να προσεγγίσει
κάθε πρόβλημα της επιστήμης υπολογιστών.

157
00:07:21,200 --> 00:07:24,040
Βρίσκοντας τον πιο κομψό τρόπο,
αυτό είναι το διασκεδαστικό μέρος.

158
00:07:24,040 --> 00:07:27,030
Κατά τη διάρκεια αυτών των p-σετ, αν το πρόγραμμά σας
δεν ταιριάζει ακριβώς μου

159
00:07:27,030 --> 00:07:29,190
επεξήγηση στα περάσματα,
αυτό είναι εντάξει.

160
00:07:29,190 --> 00:07:32,870
Αλλά ακριβώς σιγουρευτείτε ότι περνά
ελέγχουν το 50, ικανοποιεί όλα τα

161
00:07:32,870 --> 00:07:36,270
απαιτήσεις αυτές αποτελούν τις προδιαγραφές,
και ότι θα εξετάσει κατά πόσον σας

162
00:07:36,270 --> 00:07:37,670
προσέγγιση έχει καλό σχεδιασμό.

163
00:07:37,670 --> 00:07:39,750
>> Με άλλα λόγια, πόσο αποτελεσματική είναι;

164
00:07:39,750 --> 00:07:44,400
Για παράδειγμα, δεν μπορείτε να πληκτρολογήσετε επαναλαμβανόμενες
γραμμές κώδικα, αντί να χρησιμοποιεί ένα βρόχο;

165
00:07:44,400 --> 00:07:47,580
Γράφοντας κώδικα με καλύτερο σχεδιασμό θα
έρχονται εμπειρία, όπως σας πρόοδο

166
00:07:47,580 --> 00:07:49,192
μέσα από την πορεία.

167
00:07:49,192 --> 00:07:52,350
>> Γι 'αυτό τα πόδια μέσα, θα πάω πάνω
δύο μέθοδοι που μπορούν να χρησιμοποιηθούν για την

168
00:07:52,350 --> 00:07:53,540
ολοκληρώσει Greedy.

169
00:07:53,540 --> 00:07:57,160
Η πρώτη μέθοδος είναι μια μέθοδος που χρησιμοποιεί
βρόχους και αφαίρεση.

170
00:07:57,160 --> 00:08:00,050
Νωρίτερα, όταν μιλήσαμε μέσω της
Greedy διαδικασία, είμαστε σε συνεχή

171
00:08:00,050 --> 00:08:03,220
ελέγχεται κατά πόσο θα μπορούσαμε να χρησιμοποιήσουμε ένα τέταρτο,
και να χρησιμοποιηθεί ένα τέταρτο έως ότου η

172
00:08:03,220 --> 00:08:05,670
αξία απέμενε ήταν λιγότερο από $ 0,25.

173
00:08:05,670 --> 00:08:07,990
>> Αυτό μεταφράζεται σε ένα καλά
ενώ η δομή βρόχου.

174
00:08:07,990 --> 00:08:11,550
Ενώ μπορούμε να εξακολουθούν να χρησιμοποιούν
ένα τέταρτο, χρησιμοποιήστε μία.

175
00:08:11,550 --> 00:08:15,900
Ότι ενώ βρόχο θα πρέπει να εκτελέσει, εφόσον
όπως η υπόλοιπη αξία είναι μεγαλύτερη από ό, τι

176
00:08:15,900 --> 00:08:18,240
ή ίση με την τιμή σεντ τριμηνιαία.

177
00:08:18,240 --> 00:08:20,970
Αυτό σημαίνει ότι θα ήθελα επίσης να
να παρακολουθείτε τα υπόλοιπα μετρητά

178
00:08:20,970 --> 00:08:24,570
αξίας, και τον ενημερώνει κάθε
φορά που χρησιμοποιείτε ένα κέρμα.

179
00:08:24,570 --> 00:08:28,350
>> Επίσης, να θυμάστε ότι στο τέλος, σας
εξόδου είναι ο αριθμός των νομισμάτων που χρησιμοποιούνται.

180
00:08:28,350 --> 00:08:32,400
Έτσι, ένα άλλο πράγμα που πρέπει να παρακολουθείτε είναι
τον αριθμό των νομισμάτων που θα χρησιμοποιήσετε.

181
00:08:32,400 --> 00:08:35,450
Μπορείτε να παρακολουθείτε αυτά που χρησιμοποιούν
καλά οι μεταβλητές με όνομα.

182
00:08:35,450 --> 00:08:39,730
Και μέσα στο σώμα του βρόχου σας θα
είναι μια ενημέρωση για αυτές τις μεταβλητές.

183
00:08:39,730 --> 00:08:43,400
Μόλις ο βρόχος για το τρίμηνο τελειώνει, θα
μπορούν να χρησιμοποιήσουν ένα παρόμοιο για δεκάρες,

184
00:08:43,400 --> 00:08:47,180
και ούτω καθεξής και ούτω καθεξής, μέχρι να έχετε
επιστρέφεται το σύνολο των διαθεσίμων.

185
00:08:47,180 --> 00:08:50,640
>> Έχω γράψει κάποια ψευδο-κώδικα εδώ
να σας βοηθήσει να απεικονίσει πόσο η

186
00:08:50,640 --> 00:08:55,080
διαδικασία συζητήσαμε μπορεί να μεταφραστεί σε
Γ. Όπως βλέπετε εδώ, είμαι ακόμα χρησιμοποιώντας

187
00:08:55,080 --> 00:08:55,760
Αγγλικές λέξεις.

188
00:08:55,760 --> 00:08:56,830
Δεν είναι ακόμα C.

189
00:08:56,830 --> 00:08:58,590
Αλλά έχω αρχίσει να παύλα πράγματα.

190
00:08:58,590 --> 00:09:00,690
Έχω βάλει συνθήκες μέσα
παρενθέσεις μου.

191
00:09:00,690 --> 00:09:03,710
Είναι αρχίζουν να κοιτάξουμε λίγο
λίγο σαν κώδικα προγραμματισμού.

192
00:09:03,710 --> 00:09:06,410
>> Ψευδο-code είναι ένας πολύ καλός τρόπος
για να πάρει τον εαυτό σας ξεκίνησε.

193
00:09:06,410 --> 00:09:08,810
Κοίτα τον κωδικό σας πριν
μπορείτε να αναζητήσετε σύνταξη.

194
00:09:08,810 --> 00:09:12,570
Επειδή συχνά το πιο δύσκολο μέρος για μια
το πρόβλημα είναι πραγματικά να κατανοήσει τι

195
00:09:12,570 --> 00:09:14,450
ακριβώς πρέπει να κάνετε.

196
00:09:14,450 --> 00:09:17,490
Μόλις γράψετε το κάτω, τότε είναι
πολύ πιο εύκολο να αναζητήσετε τις λειτουργίες

197
00:09:17,490 --> 00:09:20,390
και ειδικά για σας σύνταξη
γραμμή του ψευδο-κώδικα

198
00:09:20,390 --> 00:09:23,760
>> Λάβετε υπόψη ότι αυτό δεν θα μπορούσε να είναι
ταυτόσημη με το είδος του σκελετού

199
00:09:23,760 --> 00:09:25,560
κωδικό σας που έχετε γράψει.

200
00:09:25,560 --> 00:09:27,640
Υπάρχουν πάντα βελτιστοποιήσεις
πρέπει να γίνουν.

201
00:09:27,640 --> 00:09:31,250
Και ειδικά κατά τη γνώμη μου ψευδο-κώδικα
εδώ, δείτε αν μπορείτε να το καταλάβετε.

202
00:09:31,250 --> 00:09:33,380
>> Αλλά ουσιαστικά η διαδικασία
και ο τρόπος σκέψης

203
00:09:33,380 --> 00:09:35,250
Είναι ακριβώς όπως συζητήσαμε.

204
00:09:35,250 --> 00:09:38,350
Η πρώτη γραμμή μας λέει για την απόκτηση
ένα ορισμένο ποσό σε δολάρια.

205
00:09:38,350 --> 00:09:40,960
Και η δεύτερη μας λέει να
μετατρέπουν σε σεντ.

206
00:09:40,960 --> 00:09:45,640
>> Και στη συνέχεια, μπορεί να χρησιμοποιηθεί, ενώ τρίμηνα, εμείς
θέλουν να αυξήσουν την καταμέτρηση κερμάτων και

207
00:09:45,640 --> 00:09:47,200
να μειώσει το ποσό σε μετρητά.

208
00:09:47,200 --> 00:09:49,880
Το ίδιο ισχύει και για δεκάρες, πεντάρες,
και πένες.

209
00:09:49,880 --> 00:09:53,230
Και τέλος, θα πει ο χρήστης
πόσα νομίσματα που χρησιμοποιούνται.

210
00:09:53,230 --> 00:09:53,750
>> Μεγάλη.

211
00:09:53,750 --> 00:09:55,680
Έτσι, καταλήγει στο συμπέρασμα ότι τη μέθοδο loop.

212
00:09:55,680 --> 00:09:59,720
Τώρα ας μιλήσουμε για την σπονδυλωτή μέθοδο,
η οποία είναι περισσότερο σαν τμήμα.

213
00:09:59,720 --> 00:10:03,630
>> Είμαστε όλοι εξοικειωμένοι με το συν, μείον,
πολλαπλασιασμός και διαίρεση φορείς

214
00:10:03,630 --> 00:10:05,030
έχουμε στη διάθεσή μας.

215
00:10:05,030 --> 00:10:09,060
C έχει και τα τέσσερα από αυτά, αλλά επίσης έχει
τελεστής του υπόλοιπου, εκπροσωπούμενη από την

216
00:10:09,060 --> 00:10:10,640
σύμβολο τοις εκατό.

217
00:10:10,640 --> 00:10:11,940
Modulo είναι πραγματικά τακτοποιημένο.

218
00:10:11,940 --> 00:10:14,880
Αυτό σας δίνει το υπόλοιπο από
διαίρεση των δύο αριθμών.

219
00:10:14,880 --> 00:10:19,910
>> Θυμηθείτε το μεγάλο μήνυμα διαίρεσης, όταν
σας χωρίζουν, ας πούμε, 74 από τα τρία;

220
00:10:19,910 --> 00:10:23,510
Ξεκινώντας με τη θέση των δεκάδων, θα
γνωρίζουμε ότι 3 πηγαίνει σε επτά

221
00:10:23,510 --> 00:10:27,620
δύο φορές για να κάνει έξι με
υπόλοιπο ένα.

222
00:10:27,620 --> 00:10:31,870
Θα ήθελα να γράψω δύο στην κορυφή, και στη συνέχεια
αφαιρούμε 6 από επτά, μεταφέροντας

223
00:10:31,870 --> 00:10:34,980
το υπόλοιπο του 14 έως
επαναλάβετε τη διαδικασία.

224
00:10:34,980 --> 00:10:39,410
>> Τρεις πηγαίνει σε 14 τέσσερις φορές για να
κάνει 12, με υπόλοιπο δύο.

225
00:10:39,410 --> 00:10:40,930
Και τα δύο δεν μεταφέρουν πια.

226
00:10:40,930 --> 00:10:44,170
Έτσι, δύο θα μείνει κατά τη
κάτω καθώς το υπόλοιπο.

227
00:10:44,170 --> 00:10:46,800
>> Και αυτό είναι που δίνει modulo, σας
ότι ο αριθμός στο κάτω μέρος.

228
00:10:46,800 --> 00:10:49,790
Έτσι, 74 modulo τρεις θα σας δώσω δύο.

229
00:10:49,790 --> 00:10:52,980
Και 10 modulo δύο, αλλά και ότι
θα σας δώσει μηδέν.

230
00:10:52,980 --> 00:10:56,500
Διότι δεν υπάρχει οποιαδήποτε υπόλοιπο
όταν χωρίζουν 10 με δύο.

231
00:10:56,500 --> 00:11:00,190
>> Έξι modulo πέντε, και πέντε
πηγαίνει σε έξι φορά.

232
00:11:00,190 --> 00:11:01,830
Και τότε έχει μια αριστερά πάνω.

233
00:11:01,830 --> 00:11:04,720
Έτσι, έξι modulo πέντε είναι ένα.

234
00:11:04,720 --> 00:11:07,950
>> Στη συνέχεια, αν έχετε επτά modulo
εννέα, θα παίρνατε επτά.

235
00:11:07,950 --> 00:11:09,840
Επειδή εννέα είναι μεγαλύτερη από επτά.

236
00:11:09,840 --> 00:11:15,020
Γι 'αυτό δεν είναι όλα τα χωρίζουν σε επτά,
αφήνοντας επτά ως απάντηση σας.

237
00:11:15,020 --> 00:11:18,340
>> Εάν σκέφτεστε για modulo λίγο περισσότερο,
θυμηθείτε ότι σας δίνει την

238
00:11:18,340 --> 00:11:21,020
υπόλοιπο μετά χωρίζουν κάτι.

239
00:11:21,020 --> 00:11:23,620
Σκεφτείτε για το πώς θα μπορούσε να είναι
μπορείτε να το χρησιμοποιήσετε σε άπληστοι.

240
00:11:23,620 --> 00:11:27,620
Ας πούμε ότι ο χρήστης ζητάει $ 400,11.

241
00:11:27,620 --> 00:11:30,470
Τι είναι ένας τρόπος για να υπολογίσετε πόσες
τέταρτα που χρειάζεστε χωρίς να χρειάζεται να

242
00:11:30,470 --> 00:11:32,360
μετρούν το καθένα;

243
00:11:32,360 --> 00:11:37,480
>> Μόλις καταλάβουμε πόσα τέταρτα
μπορείτε να χρησιμοποιήσετε για να κάνετε $ 400.11, πόσο

244
00:11:37,480 --> 00:11:38,880
αλλάξετε ερείπια;

245
00:11:38,880 --> 00:11:42,110
Ίσως ένας συνδυασμός μεταξύ εδώ
modulo και η διαίρεση θα έρθει σε

246
00:11:42,110 --> 00:11:46,200
βολικό για να σας δώσει ένα δροσερό, κομψό
προσεγγίσει στο Greedy πρόβλημα.

247
00:11:46,200 --> 00:11:49,030
Αλλά να θυμάστε ότι το διοικητικό
κανόνας εξακολουθεί να ισχύει.

248
00:11:49,030 --> 00:11:51,610
Να χρησιμοποιείτε πάντα το μεγαλύτερο δυνατό νόμισμα.

249
00:11:51,610 --> 00:11:55,340
>> Μόλις γίνει ο υπολογισμός του πόσο
πολλά νομίσματα σε χρήση, το τελευταίο βήμα

250
00:11:55,340 --> 00:11:57,930
είναι να εκτυπώσετε τον αριθμό των
νομίσματα που θα υπολογιστεί.

251
00:11:57,930 --> 00:12:01,610
Μέχρι στιγμής, έχουμε χρησιμοποιήσει την printf
λειτουργούν αποκλειστικά και μόνο για έγχορδα.

252
00:12:01,610 --> 00:12:05,200
Αλλά όταν θέλετε να εκτυπώσετε μια In, ή
ένα οποιοδήποτε είδος των δεδομένων που είναι αποθηκευμένα

253
00:12:05,200 --> 00:12:09,200
σε μια μεταβλητή, θα πρέπει να αναφέρετε
ότι χρησιμοποιώντας ένα σύμβολο.

254
00:12:09,200 --> 00:12:12,400
>> Εδώ έχω περιλαμβάνονται μόνο μερικές συμβουλές
σχετικά με τον τρόπο εμφάνισης των τιμών.

255
00:12:12,400 --> 00:12:16,390
Εάν έχετε έναν ακέραιο, θα κάνατε
γράψτε σειρά σας χρησιμοποιώντας% d ως

256
00:12:16,390 --> 00:12:17,450
κράτησης θέσης.

257
00:12:17,450 --> 00:12:20,170
Μετά το κλείσιμο των εισαγωγικών
σημάδι, εισαγάγετε ένα κόμμα.

258
00:12:20,170 --> 00:12:24,530
Και στη συνέχεια θα τοποθετούνται στο ακέραιο ότι θα
πάρει τη θέση του% d όταν εκτυπωθούν.

259
00:12:24,530 --> 00:12:27,150
>> Έτσι, μετά την εμφάνιση του αριθμού
των νομισμάτων που χρησιμοποιούνται, είστε

260
00:12:27,150 --> 00:12:28,500
τελείωσε με άπληστοι.

261
00:12:28,500 --> 00:12:32,000
Σιγουρευτείτε για να ελέγξετε όλες τις περιπτώσεις γωνία,
τακτοποιήσει το στυλ σας λίγο, και είστε

262
00:12:32,000 --> 00:12:33,350
όλα έτοιμα για να υποβάλουν.

263
00:12:33,350 --> 00:12:36,000
Στο τέλος αυτού του συνόλου πρόβλημα, θα
είναι πιο εξοικειωμένοι με το CS50

264
00:12:36,000 --> 00:12:39,940
συσκευής, το τερματικό, και θηλιά
δομές και μεταβλητές σε C.

265
00:12:39,940 --> 00:12:41,470
>> Είστε καλά στο δρόμο σας.

266
00:12:41,470 --> 00:12:43,040
Η καμπύλη μάθησης μπορεί να φαίνεται δύσκολο.

267
00:12:43,040 --> 00:12:44,690
Πάρτε λοιπόν αυτό το βήμα προς βήμα.

268
00:12:44,690 --> 00:12:47,110
Βεβαιωθείτε ότι έχετε γράψει από ψευδο-κώδικα
πριν από την κατάδυση πολύ βαθιά

269
00:12:47,110 --> 00:12:49,000
σε άγνωστες σύνταξη.

270
00:12:49,000 --> 00:12:52,030
>> Κάντε μια να κάνει τον κατάλογο, και να διαλύσουν το
εκχώρηση σε μικρότερα, πιο

271
00:12:52,030 --> 00:12:53,440
διαχειρίσιμα καθήκοντα.

272
00:12:53,440 --> 00:12:55,810
Εξερευνήστε όλους τους πόρους CS50.

273
00:12:55,810 --> 00:12:58,270
Εκτός από τη διάλεξη, rewatch
αυτό περπατήσει μέσα.

274
00:12:58,270 --> 00:12:59,790
>> Δώστε ιδιαίτερη προσοχή στην ενότητα.

275
00:12:59,790 --> 00:13:00,710
Ελέγξτε τα σορτς.

276
00:13:00,710 --> 00:13:04,640
Διαβάστε τις ερωτήσεις τους συμμαθητές σου »
Συζήτηση σχετικά με, και να δημοσιεύσετε τις δικές σας.

277
00:13:04,640 --> 00:13:06,110
>> Καλή τύχη με το p-set.

278
00:13:06,110 --> 00:13:07,200
Και ευχαριστώ για την προσοχή.

279
00:13:07,200 --> 00:13:08,690
Αυτό ήταν άπληστοι.

280
00:13:08,690 --> 00:13:15,691
>> [Παίζει μουσική]