1
00:00:00,000 --> 00:00:05,860
>> [MUZIKO Ludante]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Vi probable pensas ke
kodo estas nur uzita por plenumi taskon.

3
00:00:09,530 --> 00:00:10,450
Vi skribas ĝin.

4
00:00:10,450 --> 00:00:11,664
Ĝi faras iun.

5
00:00:11,664 --> 00:00:12,580
Tio estas sufiĉe multe ĝin.

6
00:00:12,580 --> 00:00:13,160
>> Vi kompili ĝin.

7
00:00:13,160 --> 00:00:13,993
Vi kuras la programon.

8
00:00:13,993 --> 00:00:15,370
Vi estas bona iri.

9
00:00:15,370 --> 00:00:17,520
>> Sed, kredu aŭ ne, se
vi kodigi por longa tempo,

10
00:00:17,520 --> 00:00:20,550
vi efektive povus veni vidi
kodo kiel iu kiu estas bela.

11
00:00:20,550 --> 00:00:23,275
Ĝi solvas problemon en
tre interesa maniero,

12
00:00:23,275 --> 00:00:26,510
aŭ ekzistas nur io vere
neta pri la vojo ĝi rigardas.

13
00:00:26,510 --> 00:00:28,750
Vi povus esti ridante
ĉe mi, sed ĝi estas vera.

14
00:00:28,750 --> 00:00:31,530
Kaj rikuro estas maniero
por ia akiri tiun ideon

15
00:00:31,530 --> 00:00:34,090
de bela, eleganta aspekto kodon.

16
00:00:34,090 --> 00:00:37,740
Ĝi solvas problemojn en manieroj kiuj
estas interesa, facila por bildigi,

17
00:00:37,740 --> 00:00:39,810
kaj surprize mallonga.

18
00:00:39,810 --> 00:00:43,190
>> La vojo rekursio verkoj
estas, rekursia funkcio

19
00:00:43,190 --> 00:00:49,291
estas difinita kiel funkcio kiu nomas
sin kiel parto de lia ekzekuto.

20
00:00:49,291 --> 00:00:51,790
Kiuj povus simili iom stranga,
kaj ni vidos iomete

21
00:00:51,790 --> 00:00:53,750
pri kiel tio funkcias en momento.

22
00:00:53,750 --> 00:00:55,560
Sed denove, ĉi tiuj
rekursiaj proceduroj estas

23
00:00:55,560 --> 00:00:57,730
tuj estos tiel eleganta
ĉar ili tuj

24
00:00:57,730 --> 00:01:00,410
solvi tiun problemon sen
havante ĉiujn tiujn aliajn funkciojn

25
00:01:00,410 --> 00:01:02,710
aŭ tiuj longaj bukloj.

26
00:01:02,710 --> 00:01:06,310
Vi vidos ke tiuj rekursiaj
proceduroj tuj serĉos tiel mallonga.

27
00:01:06,310 --> 00:01:10,610
Kaj ili vere intencas fari
via kodo aspektas multe pli bela.

28
00:01:10,610 --> 00:01:12,560
>> Mi donos al vi ekzemplon
de tiu por vidi kiel

29
00:01:12,560 --> 00:01:14,880
rekursia proceduro povus esti difinita.

30
00:01:14,880 --> 00:01:18,202
Do se vi estas familiara kun ĉi
de math klaso multaj jaroj,

31
00:01:18,202 --> 00:01:20,910
Estas io nomata la
faktoriala funkcio, kiu estas kutime

32
00:01:20,910 --> 00:01:25,340
signifita kiel ekkrion punkto, kiu
estas difinita super ĉiuj pozitivaj entjeroj.

33
00:01:25,340 --> 00:01:28,850
Kaj la vojon ke n
faktorialo kalkuliĝas

34
00:01:28,850 --> 00:01:31,050
Estas vi multiplikas ĉiujn
la nombroj malpli ol

35
00:01:31,050 --> 00:01:33,750
aŭ egala al n together--
ĉiuj entjeroj malpli ol

36
00:01:33,750 --> 00:01:34,880
aŭ egala al n kune.

37
00:01:34,880 --> 00:01:39,850
>> Do 5 faktorialo estas 5 fojoj
4 fojoj 3 fojojn 2 fojoj 1.

38
00:01:39,850 --> 00:01:43,020
Kaj 4 faktorialo estas 4 fojoj
3 fojojn 2 fojoj 1 kaj tiel plu.

39
00:01:43,020 --> 00:01:44,800
Vi ricevas la ideon.

40
00:01:44,800 --> 00:01:47,060
>> Kiel programistoj, ni ne
uzi n, ekkrio punkto.

41
00:01:47,060 --> 00:01:51,840
Do ni difini la faktorialo
funkcion kiel fakto de n.

42
00:01:51,840 --> 00:01:56,897
Kaj ni uzos faktorialo krei
rekursia solvo al problemo.

43
00:01:56,897 --> 00:01:59,230
Kaj mi kredas ke vi povus trovi
ke ĝi estas multe pli vide

44
00:01:59,230 --> 00:02:02,380
vokante ol la ripeta
versio de tiu, kiu

45
00:02:02,380 --> 00:02:05,010
ni ankaŭ rigardu en momento.

46
00:02:05,010 --> 00:02:08,310
>> Do tie estas paro de
facts-- vortludo intended--

47
00:02:08,310 --> 00:02:10,169
pri factorial-- la
faktorialo funkcio.

48
00:02:10,169 --> 00:02:13,090
La faktorialo de 1, kiel mi diris, estas 1.

49
00:02:13,090 --> 00:02:15,690
La faktorialo de 2 estas 2 fojoj 1.

50
00:02:15,690 --> 00:02:18,470
La faktorialo de 3 estas 3
tempoj 2 fojoj 1, kaj tiel plu.

51
00:02:18,470 --> 00:02:20,810
Ni parolis pri 4 kaj 5 jam.

52
00:02:20,810 --> 00:02:23,940
>> Sed rigardante tiun, ne tiu vera?

53
00:02:23,940 --> 00:02:28,220
Ne faktorialon 2 ĵus
2 fojoj la faktorialo de 1?

54
00:02:28,220 --> 00:02:31,130
Mi volas diri, la faktorialo de 1 estas 1.

55
00:02:31,130 --> 00:02:34,940
Do kial ni ne povas simple diri ke,
ekde faktorialon 2 estas 2 fojoj 1,

56
00:02:34,940 --> 00:02:38,520
ĝi estas vere nur 2 fojojn
la faktorialo de 1?

57
00:02:38,520 --> 00:02:40,900
>> Kaj tiam etendante ke ideo,
ne estas la faktorialo de 3

58
00:02:40,900 --> 00:02:44,080
nur 3 fojojn la faktorialon 2?

59
00:02:44,080 --> 00:02:50,350
Kaj la faktorialo de 4 estas 4 fojoj
la faktorialo de 3, kaj tiel plu?

60
00:02:50,350 --> 00:02:52,530
Fakte, la faktorialo
de iu nombro povas nur

61
00:02:52,530 --> 00:02:54,660
esprimus se ni ia
de porti ĉi ekstere forever.

62
00:02:54,660 --> 00:02:56,870
Ni povas ia ĝeneraligi
la faktorialo problemo

63
00:02:56,870 --> 00:02:59,910
ŝajnas al n tempoj la
faktorialo de n minus 1.

64
00:02:59,910 --> 00:03:04,840
Ĝi estas n fojoj la produkto de
ĉiuj nombroj malpli ol mi.

65
00:03:04,840 --> 00:03:08,890
>> Ĉi tiu ideo, tiu
ĝeneraligo de la problemo,

66
00:03:08,890 --> 00:03:13,410
nin permesas rikure
difini la faktorialo funkcio.

67
00:03:13,410 --> 00:03:15,440
Kiam vi difinas funkcion
rekursie, ekzistas

68
00:03:15,440 --> 00:03:17,470
du aĵojn kiuj bezonas esti parto de tio.

69
00:03:17,470 --> 00:03:20,990
Vi bezonas havi iu nomita
baza kazo, kiu, kiam vi deĉenigi ĝin,

70
00:03:20,990 --> 00:03:22,480
ĉesos la rekursia procezo.

71
00:03:22,480 --> 00:03:25,300
>> Alie, funkcio kiu nomas
itself-- kiel vi povus imagine--

72
00:03:25,300 --> 00:03:26,870
povus daŭrigi eterne.

73
00:03:26,870 --> 00:03:29,047
Funkcio vokas la funkcion
vokas la funkcio alvokoj

74
00:03:29,047 --> 00:03:30,380
la funkcio vokas la funkcio.

75
00:03:30,380 --> 00:03:32,380
Se vi ne havas vojon
halti ĝin, via programo

76
00:03:32,380 --> 00:03:34,760
estos efike senmoviĝita
ĉe senfina ciklo.

77
00:03:34,760 --> 00:03:37,176
Ĝi kraŝos eventuale,
ĉar ĝi devos kuri el memoro.

78
00:03:37,176 --> 00:03:38,990
Sed tio estas apud la punkto.

79
00:03:38,990 --> 00:03:42,210
>> Ni bezonas havi alian rimedon por haltigi
aferoj krom nia programo plorkriado,

80
00:03:42,210 --> 00:03:46,010
ĉar programo kiu kraŝas estas
probable ne bela aŭ eleganta.

81
00:03:46,010 --> 00:03:47,690
Kaj do ni nomas tion la baza kazo.

82
00:03:47,690 --> 00:03:50,610
Simpla solvo
al problemo kiu detenas

83
00:03:50,610 --> 00:03:52,770
la rekursia procezo de okazanta.

84
00:03:52,770 --> 00:03:55,220
Do jen unu parto de
rekursia funkcio.

85
00:03:55,220 --> 00:03:56,820
>> La dua parto estas la rekursiaj kazo.

86
00:03:56,820 --> 00:03:59,195
Kaj tio estas kie la rikuro
efektive okazos.

87
00:03:59,195 --> 00:04:02,200
Tio estas kie la
funkcio nomos sin.

88
00:04:02,200 --> 00:04:05,940
>> Ĝi ne nomas sin en akurate
sammaniere oni nomis.

89
00:04:05,940 --> 00:04:08,880
Ĝi estos malgranda varianto
kiu faras la problemo estas

90
00:04:08,880 --> 00:04:11,497
provante solvi teeny iom pli malgranda.

91
00:04:11,497 --> 00:04:14,330
Sed ĝenerale pasas la cervo
solvi la plejparton de la solvo

92
00:04:14,330 --> 00:04:17,450
al malsama alvoko malsupren la linio.

93
00:04:17,450 --> 00:04:20,290
>> Kiu el tiuj rigardoj
kiel la baza kazo tie?

94
00:04:20,290 --> 00:04:25,384
Kiu el tiuj rigardoj kiel la
simpla solvo al problemo?

95
00:04:25,384 --> 00:04:27,550
Ni havas faskon de faktorialoj,
kaj ni povus daŭrigi

96
00:04:27,550 --> 00:04:30,470
irante on-- 6, 7, 8, 9, 10, kaj tiel plu.

97
00:04:30,470 --> 00:04:34,130
>> Sed unu el tiuj aspektas kiel
bona kazo kiel la baza kazo.

98
00:04:34,130 --> 00:04:35,310
Ĝi estas tre simpla solvo.

99
00:04:35,310 --> 00:04:37,810
Ni ne devas fari ion specialan.

100
00:04:37,810 --> 00:04:40,560
>> La faktorialo de 1 estas nur 1.

101
00:04:40,560 --> 00:04:42,790
Ni ne devas fari ajnan
multipliko ajn.

102
00:04:42,790 --> 00:04:45,248
Ĝi ŝajnas kiel se ni iras
provi kaj solvi tiun problemon,

103
00:04:45,248 --> 00:04:47,600
kaj ni devas halti la
rekursio ie,

104
00:04:47,600 --> 00:04:50,610
ni probable volas halti
ĝi kiam ni atingos 1.

105
00:04:50,610 --> 00:04:54,580
Ni ne volas halti antaŭ tiu.

106
00:04:54,580 --> 00:04:56,660
>> Do se ni difini
nia faktoriala funkcio,

107
00:04:56,660 --> 00:04:58,690
jen skeleto por
kiel ni povus fari tion.

108
00:04:58,690 --> 00:05:03,110
Ni devas ŝtopi en tiuj du things--
la baza kazo kaj la rekursiaj kazo.

109
00:05:03,110 --> 00:05:04,990
Kio estas la bazo kazo?

110
00:05:04,990 --> 00:05:10,150
Se n estas egala al 1, revenu 1-- tio
vere simplan problemon solvi.

111
00:05:10,150 --> 00:05:11,890
>> La faktorialo de 1 estas 1.

112
00:05:11,890 --> 00:05:13,860
Ĝi estas ne 1 fojojn nenion.

113
00:05:13,860 --> 00:05:15,020
Estas nur 1.

114
00:05:15,020 --> 00:05:17,170
Ĝi estas tre facila fakto.

115
00:05:17,170 --> 00:05:19,620
Kaj tial povas esti nia bazo kazo.

116
00:05:19,620 --> 00:05:24,730
Se ni get pasis 1 en tiun
funkcio, ni simple reveni 1.

117
00:05:24,730 --> 00:05:27,320
>> Kio estas la rekursiaj
kazo probable aspektas?

118
00:05:27,320 --> 00:05:32,445
Por ĉiu alia nombro
krom 1, kio estas la mastro?

119
00:05:32,445 --> 00:05:35,780
Nu, se ni prenas
la faktorialo de n,

120
00:05:35,780 --> 00:05:38,160
ĝi estas n fojoj la faktorialo de n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Se ni prenas la faktorialo de 3,
ĝi estas 3 fojoj la faktorialo de 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
Kaj do se ni ne
rigardante 1, alie

124
00:05:47,330 --> 00:05:51,710
reveno n tempoj la
faktorialo de n minus 1.

125
00:05:51,710 --> 00:05:53,210
Ĝi estas bela simpla.

126
00:05:53,210 --> 00:05:57,360
>> Kaj pro havi iomete
purigisto kaj pli eleganta kodo,

127
00:05:57,360 --> 00:06:01,440
scii ke se ni havas unu-linio cikloj
unuop-linio kondiĉaj branĉoj,

128
00:06:01,440 --> 00:06:04,490
Ni povas forigi ĉiujn de la
krispa krampoj ĉirkaŭ ili.

129
00:06:04,490 --> 00:06:06,850
Do ni povas firmigi tion ĉi.

130
00:06:06,850 --> 00:06:09,640
Tio havas ekzakte la saman
funcionalidad kiel ĉi.

131
00:06:09,640 --> 00:06:13,850
>> Mi simple forprenus la krispa
krampoj, ĉar estas nur unu linio

132
00:06:13,850 --> 00:06:18,500
ene de tiuj kondiĉitaj branĉoj.

133
00:06:18,500 --> 00:06:21,160
Do tiuj kondutas idente.

134
00:06:21,160 --> 00:06:23,800
Se n estas egala al 1, 1 reveni.

135
00:06:23,800 --> 00:06:28,351
Alie reveni n fojoj
la faktorialo de n minus 1.

136
00:06:28,351 --> 00:06:29,850
Do ni estas farante la problemo malgranda.

137
00:06:29,850 --> 00:06:33,850
Se n komencas kiel 5, ni tuj
reveni 5 fojoj la faktorialo de 4.

138
00:06:33,850 --> 00:06:37,100
Kaj ni vidos post minuto, kiam ni parolas
pri la alvoko stack-- en alia video

139
00:06:37,100 --> 00:06:39,390
kie ni parolos pri la
voki stack-- ni lernos

140
00:06:39,390 --> 00:06:41,630
pri kial ĝuste tiu procezo funkcias.

141
00:06:41,630 --> 00:06:46,970
>> Sed dum faktorialo de 5 Diras
reveni 5 fojojn faktorialo de 4, kaj 4

142
00:06:46,970 --> 00:06:49,710
tuj diri, OK, nu, reveno
4 fojoj la faktorialo de 3.

143
00:06:49,710 --> 00:06:51,737
Kaj kiel vi povas vidi, ni estas
ia alproksimiĝanta 1.

144
00:06:51,737 --> 00:06:53,820
Ni nun estas pli kaj
pli proksima al tiu bazo kazo.

145
00:06:53,820 --> 00:06:58,180
>> Kaj iam ni batis la baza kazo,
ĉiuj la antaŭaj funkcioj

146
00:06:58,180 --> 00:07:00,540
havas la respondon ili serĉis.

147
00:07:00,540 --> 00:07:03,900
Faktorialon 2 estis diranta reveno
2 fojoj la faktorialo de 1.

148
00:07:03,900 --> 00:07:06,760
Nu, faktorialo de 1 estas 1.

149
00:07:06,760 --> 00:07:10,090
Do la alvokon por faktorialo
de 2 povas reveni 2 fojoj 1,

150
00:07:10,090 --> 00:07:13,980
kaj donu ke reen al faktorialon
3, rezervate ke rezulto.

151
00:07:13,980 --> 00:07:17,110
>> Kaj tiam ĝi povas kalkuli
lia rezulto, 3 fojojn 2 estas 6,

152
00:07:17,110 --> 00:07:18,907
kaj donu al faktorialon 4.

153
00:07:18,907 --> 00:07:20,740
Kaj cetere, ni havas
vídeo sur la alvoko pilo

154
00:07:20,740 --> 00:07:23,810
kie tio estas ilustrita iom
pli ol kion mi diras nun.

155
00:07:23,810 --> 00:07:25,300
Sed tio estas ĝi.

156
00:07:25,300 --> 00:07:29,300
Tiu sole estas la solvo al
kalkulanta la faktorialo de nombro.

157
00:07:29,300 --> 00:07:31,527
>> Ĝi estas nur kvar linioj de kodo.

158
00:07:31,527 --> 00:07:32,610
Tio estas sufiĉe malvarma, ĉu ne?

159
00:07:32,610 --> 00:07:35,480
Estas speco de sexy.

160
00:07:35,480 --> 00:07:38,580
>> Do ĝenerale, sed ne
ĉiam, rekursia funkcio

161
00:07:38,580 --> 00:07:41,190
povas anstataŭi maŝo en
ne-rekursia funkcio.

162
00:07:41,190 --> 00:07:46,100
Do tie, flanko ĉe flanko, estas la ripeta
versio de la funkcio faktorialo.

163
00:07:46,100 --> 00:07:49,650
Ambaŭ tiuj kalkuli
ĝuste la sama afero.

164
00:07:49,650 --> 00:07:52,170
>> Ili ambaŭ kalkuli la faktorialo de n.

165
00:07:52,170 --> 00:07:54,990
La versio sur la maldekstra
uzas rekursio fari ĝin.

166
00:07:54,990 --> 00:07:58,320
La versio sur la dekstra
uzas ripeto fari ĝin.

167
00:07:58,320 --> 00:08:02,050
>> Kaj rimarki, ni devas deklari
ŝanĝiĝema entjero produkto.

168
00:08:02,050 --> 00:08:02,940
Kaj tiam ni buklo.

169
00:08:02,940 --> 00:08:06,790
Tiel longe kiel n estas pli granda ol 0, ni
teni multiplikante ke produkto de n

170
00:08:06,790 --> 00:08:09,890
kaj decrementing n ĝis
ni kalkulas la produkton.

171
00:08:09,890 --> 00:08:14,600
Do tiuj du funkcioj, denove,
fari precize la sama afero.

172
00:08:14,600 --> 00:08:19,980
Sed ili ne faras ĝin en
ĝuste la sama maniero.

173
00:08:19,980 --> 00:08:22,430
>> Nun, ĝi eblas
havi pli ol unu bazo

174
00:08:22,430 --> 00:08:25,770
kazo aŭ pli ol unu
rekursiaj kazo, depende

175
00:08:25,770 --> 00:08:27,670
sur kio via funkcio provas fari.

176
00:08:27,670 --> 00:08:31,650
Vi ne nepre limiĝas al
sola bazo kazo aŭ sola rekursiaj

177
00:08:31,650 --> 00:08:32,370
kazo.

178
00:08:32,370 --> 00:08:35,320
Do ekzemplo de io
kun multoblaj bazo kazoj

179
00:08:35,320 --> 00:08:37,830
povus esti this-- la
Fibonaĉi-nombroj sekvenco.

180
00:08:37,830 --> 00:08:41,549
>> Vi eble memoras de
elementa lernejo tagoj

181
00:08:41,549 --> 00:08:45,740
ke la Fibonaĉi sinsekvo estas difinita
kiel this-- la unua elemento estas 0.

182
00:08:45,740 --> 00:08:46,890
La dua elemento estas 1.

183
00:08:46,890 --> 00:08:49,230
Ambaŭ tiuj estas nur per difino.

184
00:08:49,230 --> 00:08:55,920
>> Tiam ĉiu alia elemento estas difinita
kiel sumo de n minus 1 kaj n minus 2.

185
00:08:55,920 --> 00:09:00,330
Do la tria ero
estus 0 plus 1 estas 1.

186
00:09:00,330 --> 00:09:03,280
Kaj poste la kvara elemento
estus la dua elemento, 1,

187
00:09:03,280 --> 00:09:06,550
plus la tria elemento, 1.

188
00:09:06,550 --> 00:09:08,507
Kaj ke estus 2.

189
00:09:08,507 --> 00:09:09,340
Kaj tiel plu kaj tiel plu.

190
00:09:09,340 --> 00:09:11,680
>> Do en ĉi tiu kazo, ni havas du bazo kazoj.

191
00:09:11,680 --> 00:09:14,850
Se n estas egala al 1, revenu 0.

192
00:09:14,850 --> 00:09:18,560
Se n estas egala al 2, revenu 1.

193
00:09:18,560 --> 00:09:25,930
Alie, redoni Fibonacci de n
minus 1 plus Fibonacci de n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Do jen multoblaj bazo kazoj.

195
00:09:27,180 --> 00:09:29,271
Kio pri multoblaj rekursia kazoj?

196
00:09:29,271 --> 00:09:31,520
Nu, estas io
nomata _Collatz_ konjekto.

197
00:09:31,520 --> 00:09:34,630
Mi ne intencis diri,
vi scias, kio tio estas,

198
00:09:34,630 --> 00:09:38,170
ĉar ĝi estas fakte nia fina
problemo por tiu aparta video.

199
00:09:38,170 --> 00:09:43,220
Kaj estas nia ekzerco
labori pri kune.

200
00:09:43,220 --> 00:09:46,760
>> Do jen kion la
_Collatz_ Konjekto is--

201
00:09:46,760 --> 00:09:48,820
ĝi aplikas al ĉiu pozitiva entjero.

202
00:09:48,820 --> 00:09:51,500
Kaj ĝi spekulas ke ĝi estas
ĉiam eblas reiri

203
00:09:51,500 --> 00:09:55,060
al 1 se vi sekvas ĉi tiujn paŝojn.

204
00:09:55,060 --> 00:09:57,560
Se n estas 1, ĉesi.

205
00:09:57,560 --> 00:10:00,070
Ni havas reen al 1 se n estas 1.

206
00:10:00,070 --> 00:10:05,670
>> Alie, iru tra tiu
procezo denove sur n dividita per 2.

207
00:10:05,670 --> 00:10:08,200
Kaj vidu se vi povas reiri al 1.

208
00:10:08,200 --> 00:10:13,260
Alie, se n estas nepara, trairu
tiu procezo denove sur 3n plus 1,

209
00:10:13,260 --> 00:10:15,552
aŭ 3 fojoj n plus 1.

210
00:10:15,552 --> 00:10:17,010
Do jen ni havas ununuran bazon kazo.

211
00:10:17,010 --> 00:10:18,430
Se n estas egala al 1, ĉesi.

212
00:10:18,430 --> 00:10:20,230
Ni ne faras plu rekursio.

213
00:10:20,230 --> 00:10:23,730
>> Sed ni havas du rekursiaj kazoj.

214
00:10:23,730 --> 00:10:28,750
Se n estas para, ni faru unu rekursiaj
kazo, nomante n dividita per 2.

215
00:10:28,750 --> 00:10:33,950
Se n estas nepara, ni faru alian
rekursiaj kazo sur 3 fojoj n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Kaj tial la objektivo por ĉi tiu video estas
preni duan, paŭzo la vídeo,

217
00:10:39,120 --> 00:10:42,440
kaj provi kaj skribi ĉi
rekursia funkcio _Collatz_

218
00:10:42,440 --> 00:10:47,640
kie pasas en valoro n, kaj
ĝi kalkulas kiom da paŝoj li

219
00:10:47,640 --> 00:10:52,430
prenas akiri al 1, se vi komencas de n
kaj vi sekvas tiujn paŝojn ĝis supre.

220
00:10:52,430 --> 00:10:56,660
Se n estas 1, ĝi prenas 0 paŝoj.

221
00:10:56,660 --> 00:11:00,190
Alie, ĝi tuj
preni unu paŝon pli tamen

222
00:11:00,190 --> 00:11:06,200
multaj ŝtupoj prenas cxiuflanke n
dividite per 2 se n estas para, aŭ 3n plus 1

223
00:11:06,200 --> 00:11:08,100
se n estas nepara.

224
00:11:08,100 --> 00:11:11,190
>> Nu, mi jam metis supre sur la ekrano tie
paro de testo por Vi

225
00:11:11,190 --> 00:11:15,690
kelkaj provoj kazoj por vin viziti
kion tiuj diversaj _Collatz_ numeroj estas,

226
00:11:15,690 --> 00:11:17,440
kaj ankaŭ ilustraĵo
de la paŝoj kiuj

227
00:11:17,440 --> 00:11:20,390
devas esti irinta tra tiel vi povas
ia vidi ĉi procezon en ago.

228
00:11:20,390 --> 00:11:24,222
Do se n estas egala al
1, _Collatz_ de n estas 0.

229
00:11:24,222 --> 00:11:26,180
Vi ne devas fari
ion reiri al 1.

230
00:11:26,180 --> 00:11:27,600
Vi jam tie.

231
00:11:27,600 --> 00:11:30,550
>> Se n estas 2, ĝi prenas
unu paŝo por atingi 1.

232
00:11:30,550 --> 00:11:31,810
Vi komencas kun 2.

233
00:11:31,810 --> 00:11:33,100
Nu, 2 estas ne egala al 1.

234
00:11:33,100 --> 00:11:36,580
Do ĝi estas tuj estos unu paŝo
plus tamen multaj paŝoj

235
00:11:36,580 --> 00:11:38,015
prenas sur n dividita per 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 dividita per 2 estas 1.

238
00:11:42,910 --> 00:11:47,200
Do ĝi prenas unu paŝon pli tamen
multaj ŝtupoj prenas por 1.

239
00:11:47,200 --> 00:11:49,720
1 prenas nulon paŝoj.

240
00:11:49,720 --> 00:11:52,370
>> Por 3, kiel vi povas vidi, ekzistas
tre kelkajn paŝojn implikita.

241
00:11:52,370 --> 00:11:53,590
Vi iru el 3.

242
00:11:53,590 --> 00:11:56,710
Kaj poste vi iros al
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Ĝi prenas sep ŝtupojn reiri al 1.

244
00:11:58,804 --> 00:12:01,220
Kaj kiel vi povas vidi, ke estas
Paro aliaj testo kazoj tie

245
00:12:01,220 --> 00:12:02,470
testi vian programon.

246
00:12:02,470 --> 00:12:03,970
Do denove, paŭzo la vídeo.

247
00:12:03,970 --> 00:12:09,210
Kaj mi eniros salti reen nun al
kion la efektiva procezo estas ĉi tie,

248
00:12:09,210 --> 00:12:11,390
kion tiu konjekto estas.

249
00:12:11,390 --> 00:12:14,140
>> Kontrolu cxu vi povas diveni
kiel difini _Collatz_ de n

250
00:12:14,140 --> 00:12:19,967
tiel ke ĝi kalkulas kiom da
paŝas ĝi prenas akiri al 1.

251
00:12:19,967 --> 00:12:23,050
Do espereble, vi paŭzis la video
kaj vi ne nur atendis min

252
00:12:23,050 --> 00:12:25,820
doni al vi respondon ĉi tie.

253
00:12:25,820 --> 00:12:29,120
Sed se vi estas, nu,
jen la respondo ĉiuokaze.

254
00:12:29,120 --> 00:12:33,070
>> Do jen ebla difino
de la _Collatz_ funkcio.

255
00:12:33,070 --> 00:12:35,610
Nia bazo case-- se n estas
egala al 1, ni revenos 0.

256
00:12:35,610 --> 00:12:38,250
Ĝi ne prenas ajnan
paŝoj reiri al 1.

257
00:12:38,250 --> 00:12:42,710
>> Alie, ni havas du rekursiaj cases--
unu por numeroj kaj unu por nepara.

258
00:12:42,710 --> 00:12:47,164
La maniero mi testi pri numeroj
estas kontroli se n mod 2 egalas 0.

259
00:12:47,164 --> 00:12:49,080
Tiu estas esence, denove,
petante la demandon,

260
00:12:49,080 --> 00:12:54,050
se vi memoras kion mod is-- se mi
dislimo n per 2 estas tie neniu cetero?

261
00:12:54,050 --> 00:12:55,470
Tio estus para nombro.

262
00:12:55,470 --> 00:13:01,370
>> Kaj do se n mod 2 egalas 0 estas
testado estas ĉi para nombro.

263
00:13:01,370 --> 00:13:04,250
Se jes, mi volas reveni 1,
ĉar tiu estas definitive

264
00:13:04,250 --> 00:13:09,270
prenante unu paŝon plie _Collatz_ de
ajn nombro estas duono de mi.

265
00:13:09,270 --> 00:13:13,910
Alie, mi volas reveni 1
plus _Collatz_ de 3 fojoj n plus 1.

266
00:13:13,910 --> 00:13:16,060
Tio estis la alia
rekursia paŝo kiun ni

267
00:13:16,060 --> 00:13:19,470
povus preni por kalkuli la
Collatz-- la nombro de paŝoj

268
00:13:19,470 --> 00:13:22,610
ĝi prenas akiri reen
al 1 donita nombro.

269
00:13:22,610 --> 00:13:24,610
Do espereble, tiu ekzemplo
donis vi iomete

270
00:13:24,610 --> 00:13:26,620
de gusto de rekursiaj proceduroj.

271
00:13:26,620 --> 00:13:30,220
Espereble, vi pensas kodo estas
iom pli bela se implementado

272
00:13:30,220 --> 00:13:32,760
en eleganta, rekursiaj vojo.

273
00:13:32,760 --> 00:13:35,955
Sed eĉ se ne, rekursio estas
vere potenca ilo tamen.

274
00:13:35,955 --> 00:13:38,330
Kaj do ĝi estas definitive ion
akiri vian kapon ĉirkaŭe,

275
00:13:38,330 --> 00:13:41,360
ĉar vi povos krei
bela malvarmeta programojn uzante rekursio

276
00:13:41,360 --> 00:13:45,930
kiuj povus alie esti kompleksa skribi
se vi uzas maŝojn kaj iteracio.

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

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

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