1
00:00:00,000 --> 00:00:05,860
>> [Zenelejátszási]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Ön talán úgy gondolja, hogy
kód csak használják, hogy egy feladat végrehajtásának.

3
00:00:09,530 --> 00:00:10,450
Akkor írd le.

4
00:00:10,450 --> 00:00:11,664
Ez nem valami.

5
00:00:11,664 --> 00:00:12,580
Ez nagyjából azt.

6
00:00:12,580 --> 00:00:13,160
>> Akkor fordítsuk le.

7
00:00:13,160 --> 00:00:13,993
Futtatja a programot.

8
00:00:13,993 --> 00:00:15,370
Te jó menni.

9
00:00:15,370 --> 00:00:17,520
>> De akár hiszed, akár nem, ha
programozzák sokáig,

10
00:00:17,520 --> 00:00:20,550
hogy tényleg jöhet látni
kódot valamit, ami szép.

11
00:00:20,550 --> 00:00:23,275
Ez megoldja a problémát
Nagyon érdekes módon,

12
00:00:23,275 --> 00:00:26,510
vagy van valami igazán
ügyes abban, ahogy kinéz.

13
00:00:26,510 --> 00:00:28,750
Lehet, hogy nevetve
rám, de ez az igazság.

14
00:00:28,750 --> 00:00:31,530
És rekurzió egyik módja
a fajta kap ez a gondolat

15
00:00:31,530 --> 00:00:34,090
A szép, elegáns megjelenésű kódot.

16
00:00:34,090 --> 00:00:37,740
Ez megoldja a problémákat oly módon, hogy
Érdekes, könnyű elképzelni,

17
00:00:37,740 --> 00:00:39,810
és meglepően rövid.

18
00:00:39,810 --> 00:00:43,190
>> Az út rekurzív munkák
van, olyan rekurzív

19
00:00:43,190 --> 00:00:49,291
úgy definiáljuk, mint egy függvény, amely felhívja
magának az annak végrehajtását.

20
00:00:49,291 --> 00:00:51,790
Ez talán kissé különösnek tűnik,
és majd meglátjuk, egy kicsit

21
00:00:51,790 --> 00:00:53,750
arról, hogyan is működik ez egy pillanat alatt.

22
00:00:53,750 --> 00:00:55,560
De ismétlem, ezek a
rekurzív eljárások

23
00:00:55,560 --> 00:00:57,730
lesz olyan elegáns
mert ők fognak

24
00:00:57,730 --> 00:01:00,410
hogy megoldja ezt a problémát anélkül
mivel ezeket a többi funkció

25
00:01:00,410 --> 00:01:02,710
vagy ezeket a hosszú hurkok.

26
00:01:02,710 --> 00:01:06,310
Látni fogod, hogy ezek a rekurzív
eljárásokat fognak nézni olyan rövid.

27
00:01:06,310 --> 00:01:10,610
És tényleg megy, hogy
a kódot néz ki, szebb.

28
00:01:10,610 --> 00:01:12,560
>> Adok neked egy példát
E látni, hogy

29
00:01:12,560 --> 00:01:14,880
rekurzív eljárást úgy lehetne meghatározni.

30
00:01:14,880 --> 00:01:18,202
Tehát ha ismeri ezt
re matekórán sok évvel ezelőtt,

31
00:01:18,202 --> 00:01:20,910
Van valami az úgynevezett
faktoriális függvény, ami általában

32
00:01:20,910 --> 00:01:25,340
jelöli egy felkiáltójel, amely
meghatározása az összes pozitív egész szám.

33
00:01:25,340 --> 00:01:28,850
És az is, hogy N
faktoros kiszámítása

34
00:01:28,850 --> 00:01:31,050
A megszorozzuk az összes
a számok kisebb, mint

35
00:01:31,050 --> 00:01:33,750
vagy egyenlő n together--
minden egész kevesebb, mint

36
00:01:33,750 --> 00:01:34,880
vagy egyenlő n együttesen.

37
00:01:34,880 --> 00:01:39,850
>> Tehát 5 faktoros 5-ször
4-szer 3-szor 2-szer 1.

38
00:01:39,850 --> 00:01:43,020
És 4 faktoros 4-szer
3-szor 2-szer 1, és így tovább.

39
00:01:43,020 --> 00:01:44,800
Az ötlet.

40
00:01:44,800 --> 00:01:47,060
>> Ahogy a programozók, mi nem
Használja n, felkiáltójel.

41
00:01:47,060 --> 00:01:51,840
Szóval mi határozza meg a faktoriális
a funkciója, mint a tény, n.

42
00:01:51,840 --> 00:01:56,897
És fogjuk használni faktoros létrehozni
rekurzív megoldást a problémára.

43
00:01:56,897 --> 00:01:59,230
És azt hiszem, lehet, hogy talál
hogy ez sokkal több vizuális

44
00:01:59,230 --> 00:02:02,380
tetszetős, mint az iteratív
változata ezen, amely

45
00:02:02,380 --> 00:02:05,010
mi is megnézzük egy pillanat.

46
00:02:05,010 --> 00:02:08,310
>> Tehát itt van egy pár
facts-- szójáték intended--

47
00:02:08,310 --> 00:02:10,169
mintegy factorial-- a
faktoriális függvény.

48
00:02:10,169 --> 00:02:13,090
Faktoriálisát 1, mint mondtam, az 1.

49
00:02:13,090 --> 00:02:15,690
Faktoriálisát 2 2-szer 1.

50
00:02:15,690 --> 00:02:18,470
Faktoriálisát 3 3
szer 2-szer 1, és így tovább.

51
00:02:18,470 --> 00:02:20,810
Beszéltünk a 4. és az 5. már.

52
00:02:20,810 --> 00:02:23,940
>> De néztem ezt, nem igaz ez?

53
00:02:23,940 --> 00:02:28,220
Nem faktoriálisát 2 csak
2 alkalommal faktoriálisát 1?

54
00:02:28,220 --> 00:02:31,130
Úgy értem, faktoriálisát 1 1.

55
00:02:31,130 --> 00:02:34,940
Akkor miért nem tudunk csak mondani, hogy
mivel faktoriálisát 2 2-szer 1,

56
00:02:34,940 --> 00:02:38,520
ez tényleg csak 2-szer
faktoriálisát 1?

57
00:02:38,520 --> 00:02:40,900
>> És akkor kiterjesztve ezt a gondolatot,
nem faktoriálisát 3

58
00:02:40,900 --> 00:02:44,080
mindössze 3-szor faktoriálisát 2?

59
00:02:44,080 --> 00:02:50,350
És faktoriálisát 4 4-szer
faktoriálisát 3, és így tovább?

60
00:02:50,350 --> 00:02:52,530
Tény, hogy a faktoriális
bármely szám csak

61
00:02:52,530 --> 00:02:54,660
kifejezhető, ha azt a fajta
Az e feladatokat örökre.

62
00:02:54,660 --> 00:02:56,870
Mi lehet a fajta általánosítani
A faktoriális probléma

63
00:02:56,870 --> 00:02:59,910
mivel ez n-szer a
faktoriálisát n mínusz 1.

64
00:02:59,910 --> 00:03:04,840
Ez n-szer a termék
az összes számot kevesebb, mint nekem.

65
00:03:04,840 --> 00:03:08,890
>> Ez a gondolat, ez a
általánosítása a probléma,

66
00:03:08,890 --> 00:03:13,410
lehetővé teszi számunkra, hogy rekurzív
meghatározza a faktoriális függvény.

67
00:03:13,410 --> 00:03:15,440
Ha egy függvény definiálása
rekurzív van

68
00:03:15,440 --> 00:03:17,470
Két dolog kell hogy legyen a részét.

69
00:03:17,470 --> 00:03:20,990
Be kell, hogy egy úgynevezett
alapesetet, amely, ha megnyomod,

70
00:03:20,990 --> 00:03:22,480
leállítja a rekurzív folyamat.

71
00:03:22,480 --> 00:03:25,300
>> Ellenkező esetben, egy funkció, amely felhívja
itself-- mivel lehet imagine--

72
00:03:25,300 --> 00:03:26,870
mehet a végtelenségig.

73
00:03:26,870 --> 00:03:29,047
Funkció meghívja a függvényt
felszólítja a függvény hívások

74
00:03:29,047 --> 00:03:30,380
A funkció meghívja a függvényt.

75
00:03:30,380 --> 00:03:32,380
Ha nincs módja
megállítani, a programot

76
00:03:32,380 --> 00:03:34,760
amelyek ténylegesen beragadt
A végtelen ciklust.

77
00:03:34,760 --> 00:03:37,176
Ez összeomlik végül,
mert akkor elfogy a memória.

78
00:03:37,176 --> 00:03:38,990
De ez a lényeg.

79
00:03:38,990 --> 00:03:42,210
>> Szükségünk van egy másik módja annak, hogy hagyja abba
dolgok mellett a programunk összeomlik,

80
00:03:42,210 --> 00:03:46,010
mert egy program, ami összeomlik az
Valószínűleg nem szép vagy elegáns.

81
00:03:46,010 --> 00:03:47,690
És így hívjuk ezt az alaphelyzetben.

82
00:03:47,690 --> 00:03:50,610
Ez egy egyszerű megoldás
Egy probléma, ami meggátolja

83
00:03:50,610 --> 00:03:52,770
A rekurzív folyamat bekövetkezését.

84
00:03:52,770 --> 00:03:55,220
Szóval ez egy része
Egy rekurzív függvény.

85
00:03:55,220 --> 00:03:56,820
>> A második rész a rekurzív esetében.

86
00:03:56,820 --> 00:03:59,195
És ez az, ahol a rekurzió
valóban sor kerül.

87
00:03:59,195 --> 00:04:02,200
Ez az, ahol a
funkció hívja magát.

88
00:04:02,200 --> 00:04:05,940
>> Ez nem nevezi magát pontosan
ugyanúgy hívták.

89
00:04:05,940 --> 00:04:08,880
Ez lesz egy kis eltérés
ami a probléma, hogy ez

90
00:04:08,880 --> 00:04:11,497
próbálják megoldani egy pici kicsit kisebb.

91
00:04:11,497 --> 00:04:14,330
De általában halad a bak
megoldására a nagy részét a megoldás

92
00:04:14,330 --> 00:04:17,450
egy másik hívást le a pályáról.

93
00:04:17,450 --> 00:04:20,290
>> Ezek közül melyik néz ki
mint az alapeset itt?

94
00:04:20,290 --> 00:04:25,384
Ezek közül a néz ki, a
legegyszerűbb megoldást a problémára?

95
00:04:25,384 --> 00:04:27,550
Van egy csomó factorials,
és még sorolhatnánk

96
00:04:27,550 --> 00:04:30,470
megy on-- 6, 7, 8, 9, 10, és így tovább.

97
00:04:30,470 --> 00:04:34,130
>> De egy ilyen néz ki, mint egy
jó esetben, hogy az alap esetében.

98
00:04:34,130 --> 00:04:35,310
Ez egy nagyon egyszerű megoldás.

99
00:04:35,310 --> 00:04:37,810
Nem kell semmit se csinálni.

100
00:04:37,810 --> 00:04:40,560
>> Faktoriálisát 1 mindössze 1.

101
00:04:40,560 --> 00:04:42,790
Nem kell, hogy nem minden
szorzás egyáltalán.

102
00:04:42,790 --> 00:04:45,248
Úgy tűnik, mintha megyünk
hogy megpróbálja megoldani ezt a problémát,

103
00:04:45,248 --> 00:04:47,600
és meg kell állnunk a
Rekurzió valahol,

104
00:04:47,600 --> 00:04:50,610
azt kellene leállítani
amikor eljutunk 1.

105
00:04:50,610 --> 00:04:54,580
Nem akarjuk, hogy ne az előtt.

106
00:04:54,580 --> 00:04:56,660
>> Tehát ha már meghatározó
a faktoriális függvény,

107
00:04:56,660 --> 00:04:58,690
itt egy vázát
hogyan lehet csinálni.

108
00:04:58,690 --> 00:05:03,110
Meg kell csatlakoztatni a két things--
Az alapeset és a rekurzív esetében.

109
00:05:03,110 --> 00:05:04,990
Mi a alapeset?

110
00:05:04,990 --> 00:05:10,150
Ha n = 1, visszatér 1-- ez
egy nagyon egyszerű problémát megoldani.

111
00:05:10,150 --> 00:05:11,890
>> Faktoriálisát 1 1.

112
00:05:11,890 --> 00:05:13,860
Ez nem 1 alkalommal semmit.

113
00:05:13,860 --> 00:05:15,020
Ez csak 1.

114
00:05:15,020 --> 00:05:17,170
Ez egy nagyon egyszerű tény.

115
00:05:17,170 --> 00:05:19,620
És így lehet a mi alapeset.

116
00:05:19,620 --> 00:05:24,730
Ha kap telt 1 ebbe
funkciót, akkor csak vissza 1.

117
00:05:24,730 --> 00:05:27,320
>> Mi a rekurzív
esetében valószínűleg kinéznie?

118
00:05:27,320 --> 00:05:32,445
Minden más szám
mellett 1, mi a minta?

119
00:05:32,445 --> 00:05:35,780
Nos, ha elvisszük
faktoriálisát n,

120
00:05:35,780 --> 00:05:38,160
ez n-szer faktoriálisát n mínusz 1.

121
00:05:38,160 --> 00:05:42,130
>> Ha elvisszük faktoriálisát 3,
ez 3-szor faktoriálisát 3 mínusz 1,

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

123
00:05:43,070 --> 00:05:47,330
És így van, ha nem
néztem 1, egyébként

124
00:05:47,330 --> 00:05:51,710
hozam n-szer a
faktoriálisát n mínusz 1.

125
00:05:51,710 --> 00:05:53,210
Ez elég egyértelmű.

126
00:05:53,210 --> 00:05:57,360
>> És kedvéért, amelynek kissé
tisztább és sokkal elegánsabb kódot,

127
00:05:57,360 --> 00:06:01,440
tudom, hogy ha van egy-zsinórhurkokat
vagy egysoros feltételes elágazások,

128
00:06:01,440 --> 00:06:04,490
tudunk megszabadulni az összes
kapcsoszárójele körülöttük.

129
00:06:04,490 --> 00:06:06,850
Így tudjuk megszilárdítása e.

130
00:06:06,850 --> 00:06:09,640
Ez pontosan ugyanaz
funkciók, mint ez.

131
00:06:09,640 --> 00:06:13,850
>> Én csak elvegyék a göndör
nadrágtartó, mert ott csak egy sort

132
00:06:13,850 --> 00:06:18,500
belül e feltételes elágazások.

133
00:06:18,500 --> 00:06:21,160
Tehát ezek viselkedni.

134
00:06:21,160 --> 00:06:23,800
Ha n értéke 1, visszatér 1.

135
00:06:23,800 --> 00:06:28,351
Ellenkező esetben térjen vissza n-szer
faktoriálisát n mínusz 1.

136
00:06:28,351 --> 00:06:29,850
Szóval, hogy a probléma kisebb.

137
00:06:29,850 --> 00:06:33,850
Ha n indul ki, mint 5, megyünk
visszatérni 5-ször faktoriálisát 4.

138
00:06:33,850 --> 00:06:37,100
És majd meglátjuk, egy perc, amikor beszélünk
a hívás stack-- másik videó

139
00:06:37,100 --> 00:06:39,390
ahol beszélünk
hívja stack-- tanulunk

140
00:06:39,390 --> 00:06:41,630
arról, hogy miért éppen ez a folyamat működik.

141
00:06:41,630 --> 00:06:46,970
>> De míg faktoriálisát 5 mond
visszatérni 5 alkalommal faktoriálisát 4 és 4

142
00:06:46,970 --> 00:06:49,710
azt fogja mondani, OK, nos, cserébe
4-szer faktoriálisát 3.

143
00:06:49,710 --> 00:06:51,737
És mint látható, nem vagyunk
fajta közeledik 1.

144
00:06:51,737 --> 00:06:53,820
Mi egyre közelebb és
közelebb, hogy alapeset.

145
00:06:53,820 --> 00:06:58,180
>> És ha egyszer elérjük a alapeset,
az összes előző funkciók

146
00:06:58,180 --> 00:07:00,540
Megvan a válasz kerestek.

147
00:07:00,540 --> 00:07:03,900
Faktoriálisát 2 mondott hozam
2 alkalommal faktoriálisát 1.

148
00:07:03,900 --> 00:07:06,760
Nos, faktoriálisát 1értéke 1.

149
00:07:06,760 --> 00:07:10,090
Tehát a felhívás faktoros
2 visszatérhet 2-szer 1,

150
00:07:10,090 --> 00:07:13,980
és adja, hogy vissza faktoriálisát
3, amely arra vár, hogy eredményt.

151
00:07:13,980 --> 00:07:17,110
>> És akkor ki tudja számítani
annak eredménye, 3-szor 2 6,

152
00:07:17,110 --> 00:07:18,907
és adja vissza faktoriálisát 4.

153
00:07:18,907 --> 00:07:20,740
És megint van egy
videó hívás verem

154
00:07:20,740 --> 00:07:23,810
ahol ezt az ábrán egy kicsit
több, mint amit mondok most.

155
00:07:23,810 --> 00:07:25,300
De ez az.

156
00:07:25,300 --> 00:07:29,300
Ez önmagában a megoldást
kiszámításakor faktoriálisának száma.

157
00:07:29,300 --> 00:07:31,527
>> Ez csak négy sornyi kódot.

158
00:07:31,527 --> 00:07:32,610
Ez elég jó, nem?

159
00:07:32,610 --> 00:07:35,480
Elég szexi.

160
00:07:35,480 --> 00:07:38,580
>> Tehát általában, de nem
Mindig, olyan rekurzív

161
00:07:38,580 --> 00:07:41,190
helyettesítheti a hurok egy
nem rekurzív függvény.

162
00:07:41,190 --> 00:07:46,100
Tehát itt, egymás mellett, az iteratív
változata a faktoriális függvény.

163
00:07:46,100 --> 00:07:49,650
Mindkét kiszámolása
pontosan ugyanezt.

164
00:07:49,650 --> 00:07:52,170
>> Mindketten számítani faktoriálisát n.

165
00:07:52,170 --> 00:07:54,990
A verzió a bal
használja rekurzió csinálni.

166
00:07:54,990 --> 00:07:58,320
A verzió a jobb
használja iteráció csinálni.

167
00:07:58,320 --> 00:08:02,050
>> És észre, van, hogy állapítsa
egy változó egész szám termék.

168
00:08:02,050 --> 00:08:02,940
És akkor mi hurok.

169
00:08:02,940 --> 00:08:06,790
Mindaddig, amíg az n nagyobb, mint 0, mi
tartsa megszorozzuk Termék n

170
00:08:06,790 --> 00:08:09,890
és a csökkentés n-ig
kiszámítjuk a termék.

171
00:08:09,890 --> 00:08:14,600
Szóval ezt a két funkciót, ismét,
nem pontosan ugyanaz a dolog.

172
00:08:14,600 --> 00:08:19,980
De nem csinálni
pontosan ugyanolyan módon.

173
00:08:19,980 --> 00:08:22,430
>> Most, lehetséges, hogy
több mint egy bázis

174
00:08:22,430 --> 00:08:25,770
esetben, vagy több, mint egy
rekurzív esetben, attól függően,

175
00:08:25,770 --> 00:08:27,670
hogy milyen a funkciót próbál tenni.

176
00:08:27,670 --> 00:08:31,650
Nem feltétlenül csak kizárólag a
Egyetlen alapeset, vagy egy rekurzív

177
00:08:31,650 --> 00:08:32,370
esetében.

178
00:08:32,370 --> 00:08:35,320
Tehát egy példa valamit
több alap esetben

179
00:08:35,320 --> 00:08:37,830
Lehet, hogy a this--
Fibonacci számsor.

180
00:08:37,830 --> 00:08:41,549
>> Talán emlékeznek re
általános iskola nap

181
00:08:41,549 --> 00:08:45,740
hogy a Fibonacci-sorozat definíciója
mint this-- az első elem 0.

182
00:08:45,740 --> 00:08:46,890
A második elem 1.

183
00:08:46,890 --> 00:08:49,230
Mindkettő csak definíció szerint.

184
00:08:49,230 --> 00:08:55,920
>> Ezután az összes többi elemhez van meghatározva
összegeként n mínusz 1 és n mínusz 2.

185
00:08:55,920 --> 00:09:00,330
Így a harmadik elem
lenne 0 plusz 1 jelentése 1.

186
00:09:00,330 --> 00:09:03,280
És akkor a negyedik elem
lenne a második elem, 1,

187
00:09:03,280 --> 00:09:06,550
valamint a harmadik elem, 1.

188
00:09:06,550 --> 00:09:08,507
És ez lenne 2.

189
00:09:08,507 --> 00:09:09,340
És így tovább és így tovább.

190
00:09:09,340 --> 00:09:11,680
>> Tehát ebben az esetben, van két alap esetben.

191
00:09:11,680 --> 00:09:14,850
Ha n értéke 1, vissza 0.

192
00:09:14,850 --> 00:09:18,560
Ha n értéke 2, vissza 1.

193
00:09:18,560 --> 00:09:25,930
Ellenkező esetben térjen vissza Fibonacci n
mínusz 1 plusz Fibonacci n mínusz 2.

194
00:09:25,930 --> 00:09:27,180
>> Szóval ez több bázisállomás esetekben.

195
00:09:27,180 --> 00:09:29,271
Mi a helyzet a több rekurzív esetekben?

196
00:09:29,271 --> 00:09:31,520
Nos, van valami
az úgynevezett Collatz sejtést.

197
00:09:31,520 --> 00:09:34,630
Nem fogom azt mondani,
Tudja, mi az,

198
00:09:34,630 --> 00:09:38,170
mert valójában a végső
probléma az adott videót.

199
00:09:38,170 --> 00:09:43,220
És ez a mi testmozgás
hogy együtt dolgozunk.

200
00:09:43,220 --> 00:09:46,760
>> Tehát itt van, amit a
Collatz sejtés is--

201
00:09:46,760 --> 00:09:48,820
ez vonatkozik minden pozitív egész szám.

202
00:09:48,820 --> 00:09:51,500
És úgy okoskodik, hogy ez
mindig lehetséges, hogy újra

203
00:09:51,500 --> 00:09:55,060
1, ha az alábbi lépéseket.

204
00:09:55,060 --> 00:09:57,560
Ha n értéke 1, stop.

205
00:09:57,560 --> 00:10:00,070
Megvan vissza 1, ha n értéke 1.

206
00:10:00,070 --> 00:10:05,670
>> Egyébként végig ezt
folyamat ismét n osztva 2.

207
00:10:05,670 --> 00:10:08,200
És nézd meg, hogy kap vissza 1.

208
00:10:08,200 --> 00:10:13,260
Ellenkező esetben, ha n páratlan, menjen át
ez a folyamat újra 3n + 1,

209
00:10:13,260 --> 00:10:15,552
vagy 3-szor n + 1.

210
00:10:15,552 --> 00:10:17,010
Tehát itt van egy alap esetében.

211
00:10:17,010 --> 00:10:18,430
Ha n értéke 1, stop.

212
00:10:18,430 --> 00:10:20,230
Mi nem csinálunk többé rekurzió.

213
00:10:20,230 --> 00:10:23,730
>> De van két rekurzív esetben.

214
00:10:23,730 --> 00:10:28,750
Ha n páros, akkor tegye rekurzív
ügyben, amelyben n osztva 2.

215
00:10:28,750 --> 00:10:33,950
Ha n páratlan, mi más
rekurzív esetben a 3-szor n + 1.

216
00:10:33,950 --> 00:10:39,120
>> És így a cél ez a videó
hogy egy második, szünetelteti a videót,

217
00:10:39,120 --> 00:10:42,440
és megpróbálja írni ezt
rekurzív függvény Collatz

218
00:10:42,440 --> 00:10:47,640
ahol át egy értéket n, és
kiszámítja, hogy hány lépést is

219
00:10:47,640 --> 00:10:52,430
ahhoz, hogy kap 1 ha elkezd n
és hajtsa végre azokat fölé.

220
00:10:52,430 --> 00:10:56,660
Ha n értéke 1, tart 0 lépéseket.

221
00:10:56,660 --> 00:11:00,190
Egyébként ez lesz
egy lépést plusz azonban

222
00:11:00,190 --> 00:11:06,200
sok lépést tart mindkét n
osztva 2, ha n páros, vagy 3n plusz 1

223
00:11:06,200 --> 00:11:08,100
ha n páratlan.

224
00:11:08,100 --> 00:11:11,190
>> Most, tettem fel a képernyőn itt
Pár tesztet dolog az Ön számára,

225
00:11:11,190 --> 00:11:15,690
Pár tesztek esetben az Ön számára, hogy
amit ezek a különböző Collatz számok,

226
00:11:15,690 --> 00:11:17,440
és egy illusztráció
azokat a lépéseket,

227
00:11:17,440 --> 00:11:20,390
kell ment keresztül, így tudsz
fajta látni ezt a folyamatot működés közben.

228
00:11:20,390 --> 00:11:24,222
Tehát, ha n egyenlő
1, Collatz n értéke 0.

229
00:11:24,222 --> 00:11:26,180
Nem kell csinálni
semmit, hogy újra 1.

230
00:11:26,180 --> 00:11:27,600
Te már ott van.

231
00:11:27,600 --> 00:11:30,550
>> Ha n jelentése 2, tart
egy lépés eljutni 1.

232
00:11:30,550 --> 00:11:31,810
Elkezdesz 2.

233
00:11:31,810 --> 00:11:33,100
Nos, 2 nem egyenlő 1.

234
00:11:33,100 --> 00:11:36,580
Szóval ez lesz az egyik lépés
plusz azonban számos lépést meg

235
00:11:36,580 --> 00:11:38,015
veszi n osztva 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2. osztva 2 1.

238
00:11:42,910 --> 00:11:47,200
Tehát vesz egy lépéssel plusz azonban
sok lépést tart az 1.

239
00:11:47,200 --> 00:11:49,720
1 vesz nulla lépéseket.

240
00:11:49,720 --> 00:11:52,370
>> 3, mint látható, van
jó néhány lépésből.

241
00:11:52,370 --> 00:11:53,590
Menj a 3.

242
00:11:53,590 --> 00:11:56,710
És akkor megy
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Tart hét lépésben, hogy újra 1.

244
00:11:58,804 --> 00:12:01,220
És mint látható, van egy
pár másik teszt eseteket itt

245
00:12:01,220 --> 00:12:02,470
kipróbálni a programot.

246
00:12:02,470 --> 00:12:03,970
Tehát ismét szünetelteti a videót.

247
00:12:03,970 --> 00:12:09,210
És én megyek ugrik vissza most
mi a tényleges folyamat itt,

248
00:12:09,210 --> 00:12:11,390
mi ez a sejtés.

249
00:12:11,390 --> 00:12:14,140
>> Nézd meg, hogy kitaláljuk,
hogyan határozzák meg Collatz n

250
00:12:14,140 --> 00:12:19,967
oly módon, hogy kiszámítja, hogy hány
lépéseket kell ahhoz, hogy az 1.

251
00:12:19,967 --> 00:12:23,050
Így remélhetőleg, akkor megállt a videót
és akkor nem csak arra vár,

252
00:12:23,050 --> 00:12:25,820
hogy megadja a választ itt.

253
00:12:25,820 --> 00:12:29,120
De ha, nos,
Itt a válasz egyébként.

254
00:12:29,120 --> 00:12:33,070
>> Tehát itt egy lehetséges definíciója
A Collatz funkciót.

255
00:12:33,070 --> 00:12:35,610
A bázis case-- ha n
egyenlő 1, visszatérünk 0.

256
00:12:35,610 --> 00:12:38,250
Ez nem tesz
lépéseket, hogy újra 1.

257
00:12:38,250 --> 00:12:42,710
>> Egyébként van két rekurzív Esetek
egy a páros számok és egy a páratlan.

258
00:12:42,710 --> 00:12:47,164
Én úgy tesztelje a páros számok
hogy ellenőrizze, ha n mod 2 értéke 0.

259
00:12:47,164 --> 00:12:49,080
Ez alapvetően, ismét,
kérdezi a kérdést,

260
00:12:49,080 --> 00:12:54,050
ha felidézni, mit mod is-- ha
oszd n 2 nem látható a többi?

261
00:12:54,050 --> 00:12:55,470
Ez lenne páros szám.

262
00:12:55,470 --> 00:13:01,370
>> És így ha n mod 2értéke 0
tesztelés ez páros szám.

263
00:13:01,370 --> 00:13:04,250
Ha igen, szeretnék visszatérni 1,
mert ez határozottan

264
00:13:04,250 --> 00:13:09,270
hogy egy lépést plusz Collatz a
bármilyen szám felem.

265
00:13:09,270 --> 00:13:13,910
Ellenkező esetben, szeretnék visszatérni 1
plusz Collatz 3-szor n + 1.

266
00:13:13,910 --> 00:13:16,060
Ez volt a másik
rekurzív lépés, hogy

267
00:13:16,060 --> 00:13:19,470
vehetné kiszámításához
Collatz-- a lépések száma

268
00:13:19,470 --> 00:13:22,610
tart, hogy újra
1 kap egy számot.

269
00:13:22,610 --> 00:13:24,610
Így remélhetőleg ez a példa
kaptál egy kicsit

270
00:13:24,610 --> 00:13:26,620
Egy kis ízelítőt a rekurzív eljárások.

271
00:13:26,620 --> 00:13:30,220
Remélhetőleg, úgy gondolja, a kód egy
kicsit szebb, ha végre

272
00:13:30,220 --> 00:13:32,760
Az elegáns, rekurzív módon.

273
00:13:32,760 --> 00:13:35,955
De még ha nem, rekurzió egy
Nagyon hatékony eszköz mégis.

274
00:13:35,955 --> 00:13:38,330
És ez így biztosan valami
hogy a fejed körül,

275
00:13:38,330 --> 00:13:41,360
mert akkor lesz képes létrehozni
nagyon klassz programok segítségével rekurzió

276
00:13:41,360 --> 00:13:45,930
amelyek egyébként bonyolult a levelet
ha használ hurkok és ismétlés.

277
00:13:45,930 --> 00:13:46,980
Én Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Ez CS50.

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