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

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Ίσως πιστεύουν ότι
κωδικός χρησιμοποιείται μόνο για να ολοκληρώσει μια εργασία.

3
00:00:09,530 --> 00:00:10,450
Μπορείτε να το γράψω.

4
00:00:10,450 --> 00:00:11,664
Θα κάνει κάτι.

5
00:00:11,664 --> 00:00:12,580
Αυτό είναι λίγο πολύ αυτό.

6
00:00:12,580 --> 00:00:13,160
>> Μπορείτε να το υπολογίσουν.

7
00:00:13,160 --> 00:00:13,993
Μπορείτε να εκτελέσετε το πρόγραμμα.

8
00:00:13,993 --> 00:00:15,370
Είσαι καλό να πάει.

9
00:00:15,370 --> 00:00:17,520
>> Αλλά είτε το πιστεύετε είτε όχι, εάν
που κωδικοποιεί για ένα μεγάλο χρονικό διάστημα,

10
00:00:17,520 --> 00:00:20,550
που πραγματικά θα μπορούσε να έρθει να δει
Κωδικός ως κάτι που είναι όμορφο.

11
00:00:20,550 --> 00:00:23,275
Είναι λύνει ένα πρόβλημα σε
ένα πολύ ενδιαφέρον τρόπο,

12
00:00:23,275 --> 00:00:26,510
ή εκεί ακριβώς κάτι πραγματικά
τακτοποιημένο σχετικά με τον τρόπο που φαίνεται.

13
00:00:26,510 --> 00:00:28,750
Μπορεί να γελάει
σε μένα, αλλά είναι αλήθεια.

14
00:00:28,750 --> 00:00:31,530
Και αναδρομή είναι ένας τρόπος
για να πάρει το είδος αυτής της ιδέας

15
00:00:31,530 --> 00:00:34,090
όμορφη, κομψή εμφάνιση κώδικα.

16
00:00:34,090 --> 00:00:37,740
Δεν λύνει τα προβλήματα με τρόπους που
είναι ενδιαφέρον, εύκολο να απεικονίσει,

17
00:00:37,740 --> 00:00:39,810
και εκπληκτικά σύντομο.

18
00:00:39,810 --> 00:00:43,190
>> Τα έργα τρόπο αναδρομή
είναι μια αναδρομική συνάρτηση

19
00:00:43,190 --> 00:00:49,291
ορίζεται ως μια συνάρτηση που καλεί
τον εαυτό του ως μέρος της εκτέλεσής του.

20
00:00:49,291 --> 00:00:51,790
Αυτό μπορεί να φαίνεται λίγο παράξενο,
και θα δούμε λίγο

21
00:00:51,790 --> 00:00:53,750
σχετικά με το πώς αυτό λειτουργεί σε μια στιγμή.

22
00:00:53,750 --> 00:00:55,560
Αλλά και πάλι, αυτά
αναδρομικές διαδικασίες

23
00:00:55,560 --> 00:00:57,730
πρόκειται να είναι τόσο κομψή
επειδή πρόκειται

24
00:00:57,730 --> 00:01:00,410
να λύσει αυτό το πρόβλημα χωρίς
έχοντας όλες αυτές τις άλλες λειτουργίες

25
00:01:00,410 --> 00:01:02,710
ή αυτοί οι μακρές θηλιές.

26
00:01:02,710 --> 00:01:06,310
Θα δείτε ότι αυτές οι αναδρομικές
Οι διαδικασίες που πρόκειται να φαίνονται τόσο σύντομη.

27
00:01:06,310 --> 00:01:10,610
Και πραγματικά πρόκειται να κάνει
κωδικό σας φανεί πολύ πιο όμορφο.

28
00:01:10,610 --> 00:01:12,560
>> Θα σας δώσω ένα παράδειγμα
αυτό για να δείτε πώς

29
00:01:12,560 --> 00:01:14,880
θα μπορούσε να ορισθεί μια αναδρομική διαδικασία.

30
00:01:14,880 --> 00:01:18,202
Έτσι, εάν είστε εξοικειωμένοι με αυτό
από την τάξη των μαθηματικών πριν από πολλά χρόνια,

31
00:01:18,202 --> 00:01:20,910
υπάρχει κάτι που ονομάζεται
λειτουργία παραγοντικό, η οποία είναι συνήθως

32
00:01:20,910 --> 00:01:25,340
συμβολίζεται με ένα θαυμαστικό, η οποία
ορίζεται πάνω από όλους τους θετικούς ακέραιους.

33
00:01:25,340 --> 00:01:28,850
Και ο τρόπος που n
παραγοντικό υπολογίζεται

34
00:01:28,850 --> 00:01:31,050
είναι πολλαπλασιάστε το σύνολο των
οι αριθμοί κάτω από

35
00:01:31,050 --> 00:01:33,750
ή ίσο με n together--
όλοι οι ακέραιοι λιγότερο από

36
00:01:33,750 --> 00:01:34,880
ή ίσο με n μαζί.

37
00:01:34,880 --> 00:01:39,850
>> Έτσι, 5 παραγοντικό είναι 5 φορές
4 φορές 3 φορές 2 φορές 1.

38
00:01:39,850 --> 00:01:43,020
Και 4 παραγοντικό είναι 4 φορές
3 φορές 2 φορές 1 και ούτω καθεξής.

39
00:01:43,020 --> 00:01:44,800
Μπορείτε να πάρετε την ιδέα.

40
00:01:44,800 --> 00:01:47,060
>> Ως προγραμματιστές, δεν το κάνουμε
χρήση n, θαυμαστικό.

41
00:01:47,060 --> 00:01:51,840
Έτσι, θα ορίσουμε το παραγοντικό
λειτουργία ως γεγονός του n.

42
00:01:51,840 --> 00:01:56,897
Και θα χρησιμοποιήσουμε παραγοντικό να δημιουργήσουν
αναδρομικό λύση σε ένα πρόβλημα.

43
00:01:56,897 --> 00:01:59,230
Και νομίζω ότι μπορείτε να βρείτε
ότι είναι πολύ πιο οπτικά

44
00:01:59,230 --> 00:02:02,380
ελκυστική από την επαναληπτική
έκδοση αυτή, η οποία

45
00:02:02,380 --> 00:02:05,010
επίσης θα ρίξουμε μια ματιά σε σε μια στιγμή.

46
00:02:05,010 --> 00:02:08,310
>> Τόσο εδώ είναι μερικά
facts-- λογοπαίγνιο intended--

47
00:02:08,310 --> 00:02:10,169
σχετικά με το factorial--
παραγοντικό λειτουργία.

48
00:02:10,169 --> 00:02:13,090
Το παραγοντικό 1, όπως είπα, είναι 1.

49
00:02:13,090 --> 00:02:15,690
Το παραγοντικό 2 είναι 2 φορές 1.

50
00:02:15,690 --> 00:02:18,470
Το παραγοντικό του 3 είναι 3
2 φορές φορές 1, και ούτω καθεξής.

51
00:02:18,470 --> 00:02:20,810
Μιλήσαμε για 4 και 5 ήδη.

52
00:02:20,810 --> 00:02:23,940
>> Αλλά κοιτάζοντας αυτό, δεν είναι αυτή η αλήθεια;

53
00:02:23,940 --> 00:02:28,220
Δεν είναι παραγοντικό 2 μόνο
2 φορές το παραγοντικό του 1;

54
00:02:28,220 --> 00:02:31,130
Θέλω να πω, το παραγοντικό του 1 είναι 1.

55
00:02:31,130 --> 00:02:34,940
Γιατί λοιπόν να μην μπορούμε να πούμε ότι,
από το παραγοντικό του 2 είναι 2 φορές 1,

56
00:02:34,940 --> 00:02:38,520
είναι πραγματικά ακριβώς 2 φορές
το παραγοντικό του 1;

57
00:02:38,520 --> 00:02:40,900
>> Και στη συνέχεια επεκτείνει αυτή την ιδέα,
Δεν είναι το παραγοντικό του 3

58
00:02:40,900 --> 00:02:44,080
μόλις 3 φορές το παραγοντικό του 2;

59
00:02:44,080 --> 00:02:50,350
Και το παραγοντικό του 4 είναι 4 φορές
το παραγοντικό του 3, και ούτω καθεξής;

60
00:02:50,350 --> 00:02:52,530
Στην πραγματικότητα, η παραγοντικό
της οποιοσδήποτε αριθμός μπορεί απλά

61
00:02:52,530 --> 00:02:54,660
να εκφραστεί, αν έχουμε το είδος
από το υλοποιήσω για πάντα.

62
00:02:54,660 --> 00:02:56,870
Είμαστε είδος μπορεί να γενικεύσει
το παραγοντικό πρόβλημα

63
00:02:56,870 --> 00:02:59,910
όπως είναι η φορές οι
παραγοντικό του n μείον 1.

64
00:02:59,910 --> 00:03:04,840
Είναι n φορές το προϊόν του
όλοι οι αριθμοί κάτω από μένα.

65
00:03:04,840 --> 00:03:08,890
>> Αυτή η ιδέα, αυτή η
γενίκευση του προβλήματος,

66
00:03:08,890 --> 00:03:13,410
μας επιτρέπει να αναδρομικά
καθορίσει το παραγοντικό λειτουργία.

67
00:03:13,410 --> 00:03:15,440
Όταν ορίζουμε μια συνάρτηση
αναδρομικά, υπάρχει

68
00:03:15,440 --> 00:03:17,470
δύο πράγματα που πρέπει να είναι ένα μέρος της.

69
00:03:17,470 --> 00:03:20,990
Πρέπει να έχετε κάτι που ονομάζεται
το βασικό σενάριο, το οποίο, όταν το έναυσμα,

70
00:03:20,990 --> 00:03:22,480
θα σταματήσει την επαναληπτική διαδικασία.

71
00:03:22,480 --> 00:03:25,300
>> Διαφορετικά, μια συνάρτηση που καλεί
itself-- όπως μπορείτε να imagine--

72
00:03:25,300 --> 00:03:26,870
θα μπορούσε να συνεχιστεί για πάντα.

73
00:03:26,870 --> 00:03:29,047
Λειτουργία καλεί τη συνάρτηση
καλεί τις κλήσεις συναρτήσεων

74
00:03:29,047 --> 00:03:30,380
η συνάρτηση καλεί τη συνάρτηση.

75
00:03:30,380 --> 00:03:32,380
Εάν δεν έχετε έναν τρόπο
να σταματήσει, το πρόγραμμα σας

76
00:03:32,380 --> 00:03:34,760
θα κολλήσει αποτελεσματικά
σε ένα άπειρο βρόχο.

77
00:03:34,760 --> 00:03:37,176
Θα συντριβή τελικά,
γιατί αυτό θα ξεμείνει από μνήμη.

78
00:03:37,176 --> 00:03:38,990
Αλλά αυτό είναι δίπλα από το σημείο.

79
00:03:38,990 --> 00:03:42,210
>> Πρέπει να έχουμε κάποιον άλλο τρόπο για να σταματήσει
πράγματα εκτός από συντριβή το πρόγραμμά μας,

80
00:03:42,210 --> 00:03:46,010
επειδή ένα πρόγραμμα που συντρίβει είναι
πιθανόν να μην όμορφη ή κομψό.

81
00:03:46,010 --> 00:03:47,690
Και έτσι αυτό που λέμε η βασική περίπτωση.

82
00:03:47,690 --> 00:03:50,610
Αυτή είναι μια απλή λύση
σε ένα πρόβλημα το οποίο σταματά

83
00:03:50,610 --> 00:03:52,770
η αναδρομική διαδικασία από την εμφάνιση.

84
00:03:52,770 --> 00:03:55,220
Έτσι, αυτό είναι ένα μέρος της
μια αναδρομική συνάρτηση.

85
00:03:55,220 --> 00:03:56,820
>> Το δεύτερο μέρος είναι η αναδρομική περίπτωση.

86
00:03:56,820 --> 00:03:59,195
Και αυτό είναι όπου η αναδρομή
θα λάβει πράγματι χώρα.

87
00:03:59,195 --> 00:04:02,200
Αυτό είναι όπου η
λειτουργία θα αυτοαποκαλείται.

88
00:04:02,200 --> 00:04:05,940
>> Δεν θα μπορεί να θέσει υπό ακριβώς
με τον ίδιο τρόπο ονομάστηκε.

89
00:04:05,940 --> 00:04:08,880
Θα είναι μια ελαφρά παραλλαγή
που καθιστά το πρόβλημα αυτό είναι

90
00:04:08,880 --> 00:04:11,497
προσπαθεί να λύσει ένα teeny λίγο μικρότερο.

91
00:04:11,497 --> 00:04:14,330
Αλλά γενικά περνάει το μπαλάκι
επίλυσης του όγκου του διαλύματος

92
00:04:14,330 --> 00:04:17,450
σε ένα διαφορετικό κάλεσμα κάτω από τη γραμμή.

93
00:04:17,450 --> 00:04:20,290
>> Ποια από αυτά τα βλέμματα
όπως και το βασικό σενάριο εδώ;

94
00:04:20,290 --> 00:04:25,384
Ποια από τις παρακάτω μοιάζει με το
απλούστερη λύση σε ένα πρόβλημα;

95
00:04:25,384 --> 00:04:27,550
Έχουμε μια δέσμη των παραγοντικών,
και θα μπορούσαμε να συνεχίσουμε

96
00:04:27,550 --> 00:04:30,470
πηγαίνει on-- 6, 7, 8, 9, 10, και ούτω καθεξής.

97
00:04:30,470 --> 00:04:34,130
>> Αλλά ένα από αυτά μοιάζει με ένα
καλή περίπτωση για να είναι η βασική περίπτωση.

98
00:04:34,130 --> 00:04:35,310
Είναι μια πολύ απλή λύση.

99
00:04:35,310 --> 00:04:37,810
Δεν έχουμε να κάνουμε κάτι το ιδιαίτερο.

100
00:04:37,810 --> 00:04:40,560
>> Το παραγοντικό 1 απέχει μόλις 1.

101
00:04:40,560 --> 00:04:42,790
Δεν έχουμε να κάνουμε οποιοδήποτε
πολλαπλασιασμός καθόλου.

102
00:04:42,790 --> 00:04:45,248
Φαίνεται σαν αν θα πάμε
να προσπαθήσει να επιλύσει αυτό το πρόβλημα,

103
00:04:45,248 --> 00:04:47,600
και πρέπει να σταματήσει η
Αναδρομή κάπου,

104
00:04:47,600 --> 00:04:50,610
που πιθανόν να θέλετε να σταματήσετε
όταν φτάσουμε στο 1.

105
00:04:50,610 --> 00:04:54,580
Δεν θέλουμε να σταματήσει πριν από αυτό.

106
00:04:54,580 --> 00:04:56,660
>> Έτσι, αν είμαστε καθορισμό
παραγοντικό λειτουργία μας,

107
00:04:56,660 --> 00:04:58,690
εδώ είναι ένας σκελετός για
πώς θα μπορούσαμε να το κάνουμε αυτό.

108
00:04:58,690 --> 00:05:03,110
Πρέπει να συνδέσετε αυτά τα δύο things--
το βασικό σενάριο και η αναδρομική περίπτωση.

109
00:05:03,110 --> 00:05:04,990
Ποια είναι η βασική περίπτωση;

110
00:05:04,990 --> 00:05:10,150
Αν το n είναι ίσο με 1, επιστρέφουν 1-- ότι είναι
ένα πολύ απλό πρόβλημα προς επίλυση.

111
00:05:10,150 --> 00:05:11,890
>> Το παραγοντικό 1 είναι 1.

112
00:05:11,890 --> 00:05:13,860
Δεν είναι τίποτα 1 φορές.

113
00:05:13,860 --> 00:05:15,020
Είναι μόλις 1.

114
00:05:15,020 --> 00:05:17,170
Είναι μια πολύ εύκολη γεγονός.

115
00:05:17,170 --> 00:05:19,620
Και έτσι ώστε να μπορεί να είναι βασική μας υπόθεση.

116
00:05:19,620 --> 00:05:24,730
Αν έχουμε περάσει σε αυτό το 1
λειτουργία, εμείς θα επιστρέψει μόλις 1.

117
00:05:24,730 --> 00:05:27,320
>> Ποια είναι η αναδρομική
περίπτωση ίσως μοιάζει;

118
00:05:27,320 --> 00:05:32,445
Για κάθε άλλο αριθμό
εκτός από 1, ποιο είναι το σχέδιο;

119
00:05:32,445 --> 00:05:35,780
Λοιπόν, εάν παίρνετε
το παραγοντικό του n,

120
00:05:35,780 --> 00:05:38,160
είναι n φορές το παραγοντικό του n μείον 1.

121
00:05:38,160 --> 00:05:42,130
>> Εάν παίρνετε το παραγοντικό 3,
Είναι 3 φορές το παραγοντικό του 3 μείον 1,

122
00:05:42,130 --> 00:05:43,070
ή 2.

123
00:05:43,070 --> 00:05:47,330
Και έτσι, αν δεν είμαστε
κοιτάζοντας 1, αλλιώς

124
00:05:47,330 --> 00:05:51,710
επιστροφή n φορές οι
παραγοντικό του n μείον 1.

125
00:05:51,710 --> 00:05:53,210
Είναι αρκετά απλό.

126
00:05:53,210 --> 00:05:57,360
>> Και για λόγους που έχουν ελαφρώς
καθαρότερο και πιο κομψό κώδικα,

127
00:05:57,360 --> 00:06:01,440
Γνωρίζουμε ότι αν έχουμε βρόχους μονής γραμμής
ή μιας γραμμής υποκαταστήματα υπό όρους,

128
00:06:01,440 --> 00:06:04,490
μπορούμε να απαλλαγούμε από όλα τα
αγκύλες γύρω τους.

129
00:06:04,490 --> 00:06:06,850
Έτσι μπορούμε να εδραιώσει αυτή σε αυτό.

130
00:06:06,850 --> 00:06:09,640
Αυτό έχει ακριβώς το ίδιο
λειτουργικότητα με αυτό.

131
00:06:09,640 --> 00:06:13,850
>> Είμαι απλά αφαιρώντας το σγουρό
τιράντες, γιατί υπάρχει μόνο μία γραμμή

132
00:06:13,850 --> 00:06:18,500
στο εσωτερικό των εν λόγω όρους υποκαταστημάτων.

133
00:06:18,500 --> 00:06:21,160
Έτσι, αυτά συμπεριφέρονται με τον ίδιο τρόπο.

134
00:06:21,160 --> 00:06:23,800
Αν το n είναι ίσο με 1, επιστροφή 1.

135
00:06:23,800 --> 00:06:28,351
Διαφορετικά επιστρέψει n φορές
το παραγοντικό του n μείον 1.

136
00:06:28,351 --> 00:06:29,850
Έτσι είμαστε καθιστώντας το πρόβλημα μικρότερα.

137
00:06:29,850 --> 00:06:33,850
Εάν n ξεκινά ως 5, θα πάμε να
επιστρέψετε 5 φορές το παραγοντικό 4.

138
00:06:33,850 --> 00:06:37,100
Και θα δούμε σε λίγο, όταν μιλάμε
σχετικά με την stack-- κλήση σε ένα άλλο βίντεο

139
00:06:37,100 --> 00:06:39,390
όπου μιλάμε για το
καλέστε stack-- θα μάθουμε

140
00:06:39,390 --> 00:06:41,630
σχετικά με το γιατί ακριβώς αυτή η διαδικασία λειτουργεί.

141
00:06:41,630 --> 00:06:46,970
>> Αλλά ενώ παραγοντικό 5 λέει
επιστρέψετε 5 φορές παραγοντικό 4, και 4

142
00:06:46,970 --> 00:06:49,710
πρόκειται να πω, εντάξει, καλά, επιστροφή
4 φορές το παραγοντικό του 3.

143
00:06:49,710 --> 00:06:51,737
Και όπως μπορείτε να δείτε, είμαστε
το είδος της προσέγγισης 1.

144
00:06:51,737 --> 00:06:53,820
Είμαστε όλο και πιο
πιο κοντά σε αυτή την βασική περίπτωση.

145
00:06:53,820 --> 00:06:58,180
>> Και τη στιγμή που θα χτυπήσει η βασική περίπτωση,
όλα τα προηγούμενα λειτουργίες

146
00:06:58,180 --> 00:07:00,540
έχουν την απάντηση που έψαχναν.

147
00:07:00,540 --> 00:07:03,900
Παραγοντικό 2 έλεγε επιστροφή
2 φορές το παραγοντικό 1.

148
00:07:03,900 --> 00:07:06,760
Λοιπόν, παραγοντικό 1 επιστρέφει 1.

149
00:07:06,760 --> 00:07:10,090
Έτσι, η έκκληση για παραγοντικό
2 μπορεί να επιστρέψει 2 φορές 1,

150
00:07:10,090 --> 00:07:13,980
και να δώσει ότι πίσω στο παραγοντικό
3, το οποίο περιμένει το αποτέλεσμα.

151
00:07:13,980 --> 00:07:17,110
>> Και τότε μπορεί να υπολογίσει
αποτέλεσμα, 3 φορές του 2 είναι 6,

152
00:07:17,110 --> 00:07:18,907
και να της δώσει πίσω στο παραγοντικό 4.

153
00:07:18,907 --> 00:07:20,740
Και πάλι, έχουμε μια
βίντεο στη στοίβα κλήσεων

154
00:07:20,740 --> 00:07:23,810
όπου αυτό απεικονίζεται μια μικρή
περισσότερο από ό, τι λέω τώρα.

155
00:07:23,810 --> 00:07:25,300
Αλλά αυτό είναι.

156
00:07:25,300 --> 00:07:29,300
Αυτό από μόνο του είναι η λύση στα
υπολογισμό του παραγοντικό ενός αριθμού.

157
00:07:29,300 --> 00:07:31,527
>> Είναι μόνο τέσσερις γραμμές κώδικα.

158
00:07:31,527 --> 00:07:32,610
Αυτό είναι αρκετά δροσερό, έτσι δεν είναι;

159
00:07:32,610 --> 00:07:35,480
Είναι το είδος του σέξι.

160
00:07:35,480 --> 00:07:38,580
>> Έτσι, σε γενικές γραμμές, αλλά όχι
πάντα, μια αναδρομική συνάρτηση

161
00:07:38,580 --> 00:07:41,190
μπορεί να αντικαταστήσει έναν βρόχο σε ένα
μη-αναδρομική συνάρτηση.

162
00:07:41,190 --> 00:07:46,100
Μέχρι εδώ, πλάι-πλάι, είναι η επαναληπτική
έκδοση του παραγοντικού λειτουργία.

163
00:07:46,100 --> 00:07:49,650
Και οι δύο αυτές υπολογίζουν
ακριβώς το ίδιο πράγμα.

164
00:07:49,650 --> 00:07:52,170
>> Και οι δύο υπολογίζουν το παραγοντικό του n.

165
00:07:52,170 --> 00:07:54,990
Η έκδοση στα αριστερά
χρησιμοποιεί αναδρομή για να το κάνουμε.

166
00:07:54,990 --> 00:07:58,320
Η έκδοση για το δικαίωμα
Χρησιμοποιεί επανάληψη για να το κάνουμε.

167
00:07:58,320 --> 00:08:02,050
>> Και ειδοποίηση, θα πρέπει να δηλώσουν
μια μεταβλητή ένα προϊόν ακέραιος.

168
00:08:02,050 --> 00:08:02,940
Και τότε θα βρόχο.

169
00:08:02,940 --> 00:08:06,790
Εφ 'όσον η είναι μεγαλύτερο από μηδέν, εμείς
κρατήσει τον πολλαπλασιασμό του εν λόγω προϊόντος από n

170
00:08:06,790 --> 00:08:09,890
και Decrementing n μέχρι
υπολογίζουμε το προϊόν.

171
00:08:09,890 --> 00:08:14,600
Έτσι οι δύο αυτές λειτουργίες, και πάλι,
κάνουν ακριβώς το ίδιο πράγμα.

172
00:08:14,600 --> 00:08:19,980
Αλλά μην το κάνετε σε
τον ίδιο ακριβώς τρόπο.

173
00:08:19,980 --> 00:08:22,430
>> Τώρα, είναι δυνατόν να
έχουν περισσότερες από μία βάσεις

174
00:08:22,430 --> 00:08:25,770
περίπτωση ή περισσότερα από ένα
αναδρομική περίπτωση, ανάλογα

175
00:08:25,770 --> 00:08:27,670
σε ό, τι η λειτουργία σας προσπαθεί να κάνει.

176
00:08:27,670 --> 00:08:31,650
Δεν είναι αναγκαστικά περιορίζεται μόνο στην
μία περίπτωση βάσης ή ένα μόνο αναδρομικό

177
00:08:31,650 --> 00:08:32,370
περίπτωση.

178
00:08:32,370 --> 00:08:35,320
Έτσι, ένα παράδειγμα για κάτι
με πολλές περιπτώσεις βάσης

179
00:08:35,320 --> 00:08:37,830
θα μπορούσε να είναι η this--
Fibonacci αριθμός ακολουθίας.

180
00:08:37,830 --> 00:08:41,549
>> Μπορείτε να ανακαλέσετε από
δημοτικό σχολείο ημέρες

181
00:08:41,549 --> 00:08:45,740
ότι η ακολουθία Fibonacci ορίζεται
όπως this-- το πρώτο στοιχείο είναι 0.

182
00:08:45,740 --> 00:08:46,890
Το δεύτερο στοιχείο είναι 1.

183
00:08:46,890 --> 00:08:49,230
Και τα δύο αυτά είναι μόνο εξ ορισμού.

184
00:08:49,230 --> 00:08:55,920
>> Στη συνέχεια, κάθε άλλο στοιχείο ορίζεται
ως το άθροισμα των n 1 και μείον n μείον 2.

185
00:08:55,920 --> 00:09:00,330
Έτσι το τρίτο στοιχείο
θα είναι 0 και 1 είναι 1.

186
00:09:00,330 --> 00:09:03,280
Και στη συνέχεια το τέταρτο στοιχείο
θα είναι το δεύτερο στοιχείο, 1,

187
00:09:03,280 --> 00:09:06,550
συν το τρίτο στοιχείο, 1.

188
00:09:06,550 --> 00:09:08,507
Και αυτό θα είναι 2.

189
00:09:08,507 --> 00:09:09,340
Και ούτω καθεξής και ούτω καθεξής.

190
00:09:09,340 --> 00:09:11,680
>> Έτσι, σε αυτή την περίπτωση, έχουμε δύο περιπτώσεις βάσης.

191
00:09:11,680 --> 00:09:14,850
Αν το n είναι ίσο με 1, 0 επιστρέψει.

192
00:09:14,850 --> 00:09:18,560
Αν το n είναι ίσο με 2, 1 επιστρέψει.

193
00:09:18,560 --> 00:09:25,930
Διαφορετικά, επιστροφή Fibonacci Ν
μείον 1 συν Fibonacci ν μείον 2.

194
00:09:25,930 --> 00:09:27,180
>> Έτσι, αυτό είναι πολλαπλές περιπτώσεις βάσης.

195
00:09:27,180 --> 00:09:29,271
Τι γίνεται με πολλαπλές αναδρομικές περιπτώσεις;

196
00:09:29,271 --> 00:09:31,520
Λοιπόν, υπάρχει κάτι
ονομάζεται η εικασία Collatz.

197
00:09:31,520 --> 00:09:34,630
Δεν πρόκειται να πω,
ξέρετε τι είναι αυτό,

198
00:09:34,630 --> 00:09:38,170
γιατί είναι πραγματικά τελικό μας
πρόβλημα για το συγκεκριμένο βίντεο.

199
00:09:38,170 --> 00:09:43,220
Και αυτό είναι η άσκηση μας
να εργαστούν από κοινού.

200
00:09:43,220 --> 00:09:46,760
>> Έτσι, εδώ είναι ό, τι η
Collatz εικασίες is--

201
00:09:46,760 --> 00:09:48,820
ισχύει για κάθε θετικό ακέραιο.

202
00:09:48,820 --> 00:09:51,500
Και αυτό εικάζει ότι είναι
πάντα δυνατό να πάρει πίσω

203
00:09:51,500 --> 00:09:55,060
με 1 αν ακολουθήσετε τα παρακάτω βήματα.

204
00:09:55,060 --> 00:09:57,560
Αν το n είναι 1, να σταματήσει.

205
00:09:57,560 --> 00:10:00,070
Έχουμε πίσω στο 1 αν το n είναι 1.

206
00:10:00,070 --> 00:10:05,670
>> Σε αντίθετη περίπτωση, να περάσουν από αυτό
διαδικασία πάλι από το n διαιρείται δια 2.

207
00:10:05,670 --> 00:10:08,200
Και δείτε αν μπορείτε να πάρετε πίσω στο 1.

208
00:10:08,200 --> 00:10:13,260
Διαφορετικά, αν ο n είναι περιττός, περνούν από
Αυτή η διαδικασία και πάλι στην 3η συν 1,

209
00:10:13,260 --> 00:10:15,552
ή 3 φορές n συν 1.

210
00:10:15,552 --> 00:10:17,010
Έτσι, εδώ έχουμε μια ενιαία βασική περίπτωση.

211
00:10:17,010 --> 00:10:18,430
Αν το n είναι ίσο με 1, να σταματήσει.

212
00:10:18,430 --> 00:10:20,230
Εμείς δεν κάνουμε πια αναδρομή.

213
00:10:20,230 --> 00:10:23,730
>> Αλλά έχουμε δύο αναδρομικές περιπτώσεις.

214
00:10:23,730 --> 00:10:28,750
Αν το n είναι άρτιο, κάνουμε μία αναδρομική
περίπτωση, καλώντας n διαιρείται δια 2.

215
00:10:28,750 --> 00:10:33,950
Αν n είναι περιττός, κάνουμε μια διαφορετική
αναδρομική περίπτωση στις 3 φορές n + 1.

216
00:10:33,950 --> 00:10:39,120
>> Και έτσι ο στόχος για αυτό το βίντεο είναι
να λάβει μια δεύτερη, παύση του βίντεο,

217
00:10:39,120 --> 00:10:42,440
και να προσπαθήσουμε και να γράψω αυτό
αναδρομική συνάρτηση Collatz

218
00:10:42,440 --> 00:10:47,640
όπου μπορείτε να περάσετε σε μια τιμή n, και
υπολογίζει πόσα βήματα θα

219
00:10:47,640 --> 00:10:52,430
χρειάζεται για να φτάσετε στο 1, αν ξεκινήσετε από n
και να ακολουθήσετε αυτά τα βήματα μέχρι πάνω.

220
00:10:52,430 --> 00:10:56,660
Εάν το η είναι 1, παίρνει 0 βήματα.

221
00:10:56,660 --> 00:11:00,190
Διαφορετικά, πρόκειται να
πάρτε ένα βήμα συν ωστόσο

222
00:11:00,190 --> 00:11:06,200
πολλά βήματα που χρειάζεται για κάθε n
διαιρούμενο με 2 αν n είναι ακόμη, ή 3n συν 1

223
00:11:06,200 --> 00:11:08,100
αν ο n είναι περιττός.

224
00:11:08,100 --> 00:11:11,190
>> Τώρα, έχω βάλει επάνω στην οθόνη εδώ
μερικά πράγματα τεστ για σας,

225
00:11:11,190 --> 00:11:15,690
ένα ζευγάρι των δοκιμών περιπτώσεις για σας, για να δείτε
ποιες είναι αυτές οι διάφοροι αριθμοί Collatz,

226
00:11:15,690 --> 00:11:17,440
και επίσης μια απεικόνιση
από τα βήματα που

227
00:11:17,440 --> 00:11:20,390
πρέπει να περάσει ώστε να μπορείτε να
είδος δουν αυτή τη διαδικασία σε δράση.

228
00:11:20,390 --> 00:11:24,222
Έτσι, αν η είναι ίσο με
1, Collatz του n είναι μηδέν.

229
00:11:24,222 --> 00:11:26,180
Δεν χρειάζεται να κάνετε
τίποτα για να πάρει πίσω στο 1.

230
00:11:26,180 --> 00:11:27,600
Είσαι ήδη εκεί.

231
00:11:27,600 --> 00:11:30,550
>> Εάν το η είναι 2, παίρνει
ένα βήμα για να φτάσετε στο 1.

232
00:11:30,550 --> 00:11:31,810
Μπορείτε να ξεκινήσετε με 2.

233
00:11:31,810 --> 00:11:33,100
Λοιπόν, 2 δεν είναι ίση με 1.

234
00:11:33,100 --> 00:11:36,580
Γι 'αυτό πρόκειται να είναι ένα βήμα
συν ωστόσο πολλά βήματα που

235
00:11:36,580 --> 00:11:38,015
παίρνει n διαιρείται δια 2.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 διαιρείται με 2 είναι 1.

238
00:11:42,910 --> 00:11:47,200
Γι 'αυτό παίρνει ένα βήμα συν ωστόσο
πολλά βήματα που χρειάζεται για 1.

239
00:11:47,200 --> 00:11:49,720
1 παίρνει μηδέν βήματα.

240
00:11:49,720 --> 00:11:52,370
>> Για 3, όπως μπορείτε να δείτε, δεν υπάρχει
αρκετά βήματα που εμπλέκονται.

241
00:11:52,370 --> 00:11:53,590
Μπορείτε να πάτε από 3.

242
00:11:53,590 --> 00:11:56,710
Και τότε θα πάμε να
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Χρειάζονται επτά βήματα για να πάρετε πίσω στο 1.

244
00:11:58,804 --> 00:12:01,220
Και όπως μπορείτε να δείτε, υπάρχει μια
ζευγάρι άλλες περιπτώσεις δοκιμής εδώ

245
00:12:01,220 --> 00:12:02,470
να δοκιμάσετε το πρόγραμμά σας.

246
00:12:02,470 --> 00:12:03,970
Έτσι και πάλι, παύση του βίντεο.

247
00:12:03,970 --> 00:12:09,210
Και θα πάω πίσω τώρα έτοιμοι να
ποια είναι η πραγματική διαδικασία είναι εδώ,

248
00:12:09,210 --> 00:12:11,390
ό, τι αυτό είναι εικασία.

249
00:12:11,390 --> 00:12:14,140
>> Δείτε αν μπορείτε να καταλάβω
πώς να καθορίσει Collatz Ν

250
00:12:14,140 --> 00:12:19,967
έτσι ώστε να υπολογίζει πόσες
τα βήματα που χρειάζεται για να φτάσετε στο 1.

251
00:12:19,967 --> 00:12:23,050
Έτσι, ελπίζουμε, έχετε παύση το βίντεο
και δεν είναι απλώς περιμένει για μένα

252
00:12:23,050 --> 00:12:25,820
για να σας δώσει την απάντηση εδώ.

253
00:12:25,820 --> 00:12:29,120
Αλλά αν είστε, επίσης,
εδώ είναι η απάντηση έτσι κι αλλιώς.

254
00:12:29,120 --> 00:12:33,070
>> Έτσι, εδώ είναι ένας πιθανός ορισμός
της λειτουργίας Collatz.

255
00:12:33,070 --> 00:12:35,610
Η βάση μας case-- αν το n είναι
ίσο προς 1, θα επιστρέψουμε 0.

256
00:12:35,610 --> 00:12:38,250
Δεν λαμβάνει οποιαδήποτε
βήματα για να πάρετε πίσω στο 1.

257
00:12:38,250 --> 00:12:42,710
>> Σε αντίθετη περίπτωση, έχουμε δύο αναδρομικές cases--
ένα ακόμη αριθμούς και μία για περίεργο.

258
00:12:42,710 --> 00:12:47,164
Ο τρόπος που έχω δοκιμάσει ακόμη αριθμούς
είναι να ελέγξετε αν ο n mod 2 ισούται με 0.

259
00:12:47,164 --> 00:12:49,080
Αυτό είναι βασικά, και πάλι,
την ερώτηση,

260
00:12:49,080 --> 00:12:54,050
αν θυμηθούμε τι mod is-- αν μου
Ν διαίρεσης από 2 δεν υπάρχει υπόλοιπο;

261
00:12:54,050 --> 00:12:55,470
Αυτό θα ήταν ένας ακόμη αριθμός.

262
00:12:55,470 --> 00:13:01,370
>> Και έτσι, αν n mod 2 ισούται με 0 είναι
δοκιμή είναι αυτός ένας άρτιος αριθμός.

263
00:13:01,370 --> 00:13:04,250
Αν ναι, θέλω να επιστρέψω 1,
επειδή αυτό είναι σίγουρα

264
00:13:04,250 --> 00:13:09,270
ένα βήμα συν Collatz της
ανεξάρτητα από τον αριθμό είναι το μισό μου.

265
00:13:09,270 --> 00:13:13,910
Σε αντίθετη περίπτωση, θέλω να επιστρέψω 1
συν Collatz από 3 φορές n συν 1.

266
00:13:13,910 --> 00:13:16,060
Αυτό ήταν το άλλο
αναδρομικό βήμα που θα

267
00:13:16,060 --> 00:13:19,470
θα μπορούσε να λάβει για τον υπολογισμό της
Collatz-- τον αριθμό των βημάτων

268
00:13:19,470 --> 00:13:22,610
που χρειάζεται για να πάρει πίσω
να δοθεί 1 έναν αριθμό.

269
00:13:22,610 --> 00:13:24,610
Έτσι, ελπίζουμε, αυτό το παράδειγμα
Σας έδωσα ένα μικρό κομμάτι

270
00:13:24,610 --> 00:13:26,620
της μια γεύση των αναδρομικών διαδικασιών.

271
00:13:26,620 --> 00:13:30,220
Ας ελπίσουμε ότι, νομίζετε ότι είναι ένας κώδικας
λίγο πιο όμορφο, αν εφαρμοστούν

272
00:13:30,220 --> 00:13:32,760
σε ένα κομψό, αναδρομικό τρόπο.

273
00:13:32,760 --> 00:13:35,955
Αλλά ακόμα και αν δεν είναι, είναι μια αναδρομή
πραγματικά ισχυρό εργαλείο παρ 'όλα αυτά.

274
00:13:35,955 --> 00:13:38,330
Και γι 'αυτό είναι σίγουρα κάτι
για να πάρει το κεφάλι σας γύρω,

275
00:13:38,330 --> 00:13:41,360
επειδή θα είστε σε θέση να δημιουργήσουν
αρκετά δροσερό προγράμματα χρησιμοποιούν αναδρομή

276
00:13:41,360 --> 00:13:45,930
που θα μπορούσαν αλλιώς να είναι πολύπλοκο να γράψω
αν χρησιμοποιείτε βρόχους και επανάληψη.

277
00:13:45,930 --> 00:13:46,980
Είμαι ο Νταγκ Lloyd.

278
00:13:46,980 --> 00:13:48,780
Αυτό είναι CS50.

279
00:13:48,780 --> 00:13:50,228