1
00:00:00,000 --> 00:00:05,860
>> [TÓNLIST spila]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Þú heldur líklega að
númerið er bara notað til að ná í verkefni.

3
00:00:09,530 --> 00:00:10,450
Þú skrifar það út.

4
00:00:10,450 --> 00:00:11,664
Það gerir eitthvað.

5
00:00:11,664 --> 00:00:12,580
Það er ansi mikið það.

6
00:00:12,580 --> 00:00:13,160
>> Þú þýða það.

7
00:00:13,160 --> 00:00:13,993
Þú keyrir forritið.

8
00:00:13,993 --> 00:00:15,370
Þú ert góður til fara.

9
00:00:15,370 --> 00:00:17,520
>> En trúið því eða ekki, ef
þú kóða í langan tíma,

10
00:00:17,520 --> 00:00:20,550
þú í raun gæti komið að sjá
númer sem eitthvað sem er fallegt.

11
00:00:20,550 --> 00:00:23,275
Það leysa vandamál í
mjög áhugaverð leið,

12
00:00:23,275 --> 00:00:26,510
eða það er bara eitthvað virkilega
sniðugt um hvernig það lítur út.

13
00:00:26,510 --> 00:00:28,750
Þú gætir verið að hlæja
á mig, en það er satt.

14
00:00:28,750 --> 00:00:31,530
Og endurkvæmni er ein leið
til að raða á að fá þessa hugmynd

15
00:00:31,530 --> 00:00:34,090
af falleg, glæsilegur-útlit númer.

16
00:00:34,090 --> 00:00:37,740
Það leysir vandamál á þann hátt sem
eru áhugaverð, auðvelt að sjón,

17
00:00:37,740 --> 00:00:39,810
og furðu stutt.

18
00:00:39,810 --> 00:00:43,190
>> The vegur endurkvæmni verk
er, a endurkvæma virka

19
00:00:43,190 --> 00:00:49,291
er skilgreind sem fall sem kallar
sig sem hluta af framkvæmd hennar.

20
00:00:49,291 --> 00:00:51,790
Það kann að virðast svolítið skrítið,
og við munum sjá smá

21
00:00:51,790 --> 00:00:53,750
um hvernig þetta virkar í smá stund.

22
00:00:53,750 --> 00:00:55,560
En aftur, þetta
endurkvæma aðferðir eru

23
00:00:55,560 --> 00:00:57,730
að fara að vera svo glæsilegur
vegna þess að þeir eru að fara

24
00:00:57,730 --> 00:01:00,410
til að leysa þetta vandamál án þess
hafa allar þessar aðrar aðgerðir

25
00:01:00,410 --> 00:01:02,710
eða þessar lengi lykkjur.

26
00:01:02,710 --> 00:01:06,310
Þú munt sjá að þetta endurkvæma
aðferðir við að líta svo stutt.

27
00:01:06,310 --> 00:01:10,610
Og þeir raunverulega eru að fara að gera
númerið þitt líta mikið fallegri.

28
00:01:10,610 --> 00:01:12,560
>> Ég skal gefa ykkur dæmi
þetta til að sjá hvernig

29
00:01:12,560 --> 00:01:14,880
endurkvæma aðferð má skilgreina.

30
00:01:14,880 --> 00:01:18,202
Svo ef þú ert kunnuglegur með þetta
frá stærðfræði bekknum mörgum árum,

31
00:01:18,202 --> 00:01:20,910
Það er eitthvað sem kallast
þáttatilraun virka, sem er yfirleitt

32
00:01:20,910 --> 00:01:25,340
táknað sem upphrópunarmerki, sem
er skilgreind á allar jákvæðar heiltölur.

33
00:01:25,340 --> 00:01:28,850
Og hvernig sem n
þáttatilraun er reiknað

34
00:01:28,850 --> 00:01:31,050
er þú margfaldar allt
tölurnar minna en

35
00:01:31,050 --> 00:01:33,750
eða jafnt og n together--
allar heiltölur minna en

36
00:01:33,750 --> 00:01:34,880
eða jafnt n saman.

37
00:01:34,880 --> 00:01:39,850
>> Svo er 5 þáttatilraun 5 sinnum
4 sinnum 3 sinnum 2 sinnum 1.

38
00:01:39,850 --> 00:01:43,020
Og 4 þáttatilraun er 4 sinnum
3 sinnum 2 sinnum 1 og svo framvegis.

39
00:01:43,020 --> 00:01:44,800
Þú færð þá hugmynd.

40
00:01:44,800 --> 00:01:47,060
>> Sem forritari, eigum við ekki
nota n, upphrópunarmerki.

41
00:01:47,060 --> 00:01:51,840
Þannig að við munum skilgreina þáttatilraun
virka eins og staðreynd n.

42
00:01:51,840 --> 00:01:56,897
Og við munum nota þáttatilraun að búa
endurkvæma lausn á vandamáli.

43
00:01:56,897 --> 00:01:59,230
Og ég held að þú gætir fundið
að það er mikið meira sjónrænt

44
00:01:59,230 --> 00:02:02,380
aðlaðandi en endurtekningu
útgáfa af þessu, þar sem

45
00:02:02,380 --> 00:02:05,010
við munum einnig taka a líta á í smá stund.

46
00:02:05,010 --> 00:02:08,310
>> Svo hér eru nokkrar
facts-- orðaleikur intended--

47
00:02:08,310 --> 00:02:10,169
um factorial-- á
þáttatilraun virka.

48
00:02:10,169 --> 00:02:13,090
The þáttatilraun 1, eins og ég sagði, er 1.

49
00:02:13,090 --> 00:02:15,690
The þáttatilraun af 2 er 2 sinnum 1.

50
00:02:15,690 --> 00:02:18,470
Aðfeldi 3 er 3
sinnum 2 sinnum 1, og svo framvegis.

51
00:02:18,470 --> 00:02:20,810
Við ræddum um 4 og 5 þegar.

52
00:02:20,810 --> 00:02:23,940
>> En að horfa á þetta, er þetta ekki satt?

53
00:02:23,940 --> 00:02:28,220
Er ekki þáttatilraun af 2 bara
2 sinnum aðfeldi 1?

54
00:02:28,220 --> 00:02:31,130
Ég meina, þáttatilraun af 1 er 1.

55
00:02:31,130 --> 00:02:34,940
Svo hvers vegna getum við ekki bara sagt það,
þar þáttatilraun af 2 er 2 sinnum 1,

56
00:02:34,940 --> 00:02:38,520
það er í raun bara 2 sinnum
aðfeldi 1?

57
00:02:38,520 --> 00:02:40,900
>> Og þá nær þessi hugmynd,
er ekki þáttatilraun af 3

58
00:02:40,900 --> 00:02:44,080
bara 3 sinnum aðfeldi 2?

59
00:02:44,080 --> 00:02:50,350
Og þáttatilraun af 4 er 4 sinnum
aðfeldi 3, og svo framvegis?

60
00:02:50,350 --> 00:02:52,530
Í staðreynd, the þáttatilraun
af hvaða númer getur bara

61
00:02:52,530 --> 00:02:54,660
gefin ef vér góður
af bera þetta út að eilífu.

62
00:02:54,660 --> 00:02:56,870
Við getum konar alhæfa
þáttatilraun vandamál

63
00:02:56,870 --> 00:02:59,910
Eins og það er n sinnum
þáttatilraun n mínus 1.

64
00:02:59,910 --> 00:03:04,840
Það er n sinnum afurð
allar tölur minna en mig.

65
00:03:04,840 --> 00:03:08,890
>> Þessi hugmynd, þetta
alhæfing af vandamálinu,

66
00:03:08,890 --> 00:03:13,410
gerir okkur kleift að endurkvæmt
skilgreina þáttatilraun virka.

67
00:03:13,410 --> 00:03:15,440
Þegar þú skilgreint fall
endurkvæmt, það er

68
00:03:15,440 --> 00:03:17,470
tveir hlutir sem þarf að vera hluti af því.

69
00:03:17,470 --> 00:03:20,990
Þú þarft að hafa eitthvað sem kallast
stöð að ræða, sem, þegar þú kalla það,

70
00:03:20,990 --> 00:03:22,480
mun stoppa endurkvæma aðferð.

71
00:03:22,480 --> 00:03:25,300
>> Annars fall sem kallar
itself-- eins og þú might imagine--

72
00:03:25,300 --> 00:03:26,870
gæti haldið áfram að eilífu.

73
00:03:26,870 --> 00:03:29,047
Virka símtöl aðgerðina
kallar virka símtöl

74
00:03:29,047 --> 00:03:30,380
virka kallar virka.

75
00:03:30,380 --> 00:03:32,380
Ef þú ert ekki með leið
til að stöðva það, program

76
00:03:32,380 --> 00:03:34,760
verður í raun fastur
á óendanlega lykkju.

77
00:03:34,760 --> 00:03:37,176
Það verður hrun á endanum,
vegna þess að það verður keyrt út af minni.

78
00:03:37,176 --> 00:03:38,990
En það er við hliðina á benda.

79
00:03:38,990 --> 00:03:42,210
>> Við þurfum að hafa einhverja aðra leið til að stöðva
það auki program hrun okkar,

80
00:03:42,210 --> 00:03:46,010
vegna þess að forrit sem hrun er
sennilega ekki fallegt eða glæsilegt.

81
00:03:46,010 --> 00:03:47,690
Og svo við köllum þetta stöð raunin.

82
00:03:47,690 --> 00:03:50,610
Þetta er einföld lausn
á vandamáli sem stoppar

83
00:03:50,610 --> 00:03:52,770
endurkvæma aðferð frá viðburður.

84
00:03:52,770 --> 00:03:55,220
Svo er það einn hluti af
endurkvæma virka.

85
00:03:55,220 --> 00:03:56,820
>> Seinni hluti er endurkvæma raunin.

86
00:03:56,820 --> 00:03:59,195
Og þetta er þar sem endurkvæmni
mun í raun fara fram.

87
00:03:59,195 --> 00:04:02,200
Þetta er þar sem
aðgerð mun kalla sig.

88
00:04:02,200 --> 00:04:05,940
>> Það mun ekki kalla sig í nákvæmlega
á sama hátt og það var kallað.

89
00:04:05,940 --> 00:04:08,880
Það verður smávægileg breyting
sem gerir vandamál það er

90
00:04:08,880 --> 00:04:11,497
reyna að leysa a teeny aðeins minni.

91
00:04:11,497 --> 00:04:14,330
En það fer yfirleitt peninginn
að leysa megnið af lausninni

92
00:04:14,330 --> 00:04:17,450
í annan hringja niður í línu.

93
00:04:17,450 --> 00:04:20,290
>> Hver af þessum útlit
eins grunn tilfelli hér?

94
00:04:20,290 --> 00:04:25,384
Hver einn af þessum lítur út eins og
Einfaldasta lausnin á vandamáli?

95
00:04:25,384 --> 00:04:27,550
Við höfum fullt af factorials,
og við gátum haldið áfram

96
00:04:27,550 --> 00:04:30,470
fara on-- 6, 7, 8, 9, 10, og svo framvegis.

97
00:04:30,470 --> 00:04:34,130
>> En einn af þessum lítur út eins og
gott mál að vera undirstaða raunin.

98
00:04:34,130 --> 00:04:35,310
Það er mjög einföld lausn.

99
00:04:35,310 --> 00:04:37,810
Við þurfum ekki að gera neitt sérstakt.

100
00:04:37,810 --> 00:04:40,560
>> Aðfeldi 1 er bara 1.

101
00:04:40,560 --> 00:04:42,790
Við þurfum ekki að gera eitthvað
margföldun á öllum.

102
00:04:42,790 --> 00:04:45,248
Það virðist eins og ef við erum að fara
til að reyna að leysa þetta vandamál,

103
00:04:45,248 --> 00:04:47,600
og við þurfum að stöðva
endurkvæmni einhvers staðar,

104
00:04:47,600 --> 00:04:50,610
við viljum líklega að hætta
það þegar við komum til 1.

105
00:04:50,610 --> 00:04:54,580
Við viljum ekki að hætta áður.

106
00:04:54,580 --> 00:04:56,660
>> Þannig að ef við erum að skilgreina
þáttatilraun virka okkar,

107
00:04:56,660 --> 00:04:58,690
hér er beinagrind fyrir
hvernig við gætum gert það.

108
00:04:58,690 --> 00:05:03,110
Við þurfum að stinga í þær tvær things--
grunn tilfelli og endurkvæma raunin.

109
00:05:03,110 --> 00:05:04,990
Hvað er stöð málið?

110
00:05:04,990 --> 00:05:10,150
Ef n er jafnt og 1, að fara aftur 1-- það er
mjög einfalt vandamál að leysa.

111
00:05:10,150 --> 00:05:11,890
>> The þáttatilraun af 1 er 1.

112
00:05:11,890 --> 00:05:13,860
Það er ekki 1 sinni neitt.

113
00:05:13,860 --> 00:05:15,020
Það er bara 1.

114
00:05:15,020 --> 00:05:17,170
Það er mjög auðvelt staðreynd.

115
00:05:17,170 --> 00:05:19,620
Og svo að hægt er að byggja mál vor.

116
00:05:19,620 --> 00:05:24,730
Ef við fá liðið 1 inn í þetta
virka, við verðum bara að fara aftur 1.

117
00:05:24,730 --> 00:05:27,320
>> Hvað er endurkvæma
Málið sennilega líta út?

118
00:05:27,320 --> 00:05:32,445
Fyrir hvert annað númer
auk 1, hvað er mynstur?

119
00:05:32,445 --> 00:05:35,780
Jæja, ef við erum að taka
þáttatilraun n,

120
00:05:35,780 --> 00:05:38,160
það er n sinnum þáttatilraun n mínus 1.

121
00:05:38,160 --> 00:05:42,130
>> Ef við erum að taka þáttatilraun af 3,
það er 3 sinnum þáttatilraun af 3 mínus 1,

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

123
00:05:43,070 --> 00:05:47,330
Og svo ef við erum ekki
horfa á 1, annars

124
00:05:47,330 --> 00:05:51,710
Arðsemi n sinnum
þáttatilraun n mínus 1.

125
00:05:51,710 --> 00:05:53,210
Það er frekar einfalt.

126
00:05:53,210 --> 00:05:57,360
>> Og fyrir sakir þess að hafa örlítið
hreinni og glæsilegur númer,

127
00:05:57,360 --> 00:06:01,440
vita að ef við höfum einn-lína lykkjur
eða einn-lína skilyrt útibú,

128
00:06:01,440 --> 00:06:04,490
við getum að losna við allt í
hrokkið axlabönd kringum þá.

129
00:06:04,490 --> 00:06:06,850
Þannig að við getum styrkja þetta að þessu.

130
00:06:06,850 --> 00:06:09,640
Þetta hefur nákvæmlega sömu
virkni og þetta.

131
00:06:09,640 --> 00:06:13,850
>> Ég ætla bara að taka í burtu hrokkið
axlabönd, því það er bara ein lína

132
00:06:13,850 --> 00:06:18,500
inni af þeim skilyrt greinum.

133
00:06:18,500 --> 00:06:21,160
Svo þetta hegða samur.

134
00:06:21,160 --> 00:06:23,800
Ef n er jafnt og 1, skila 1.

135
00:06:23,800 --> 00:06:28,351
Annars aftur n sinnum
þáttatilraun n mínus 1.

136
00:06:28,351 --> 00:06:29,850
Þannig að við erum að gera vandamálið minna.

137
00:06:29,850 --> 00:06:33,850
Ef n byrjar sem 5, við erum að fara að
aftur 5 sinnum aðfeldi 4.

138
00:06:33,850 --> 00:06:37,100
Og við munum sjá í eina mínútu þegar við tölum
um kalla stack-- í öðru vídeó

139
00:06:37,100 --> 00:06:39,390
þar sem við tölum um
kalla stack-- lærum

140
00:06:39,390 --> 00:06:41,630
um hvers vegna þetta ferli virkar.

141
00:06:41,630 --> 00:06:46,970
>> En á meðan þáttatilraun af 5 segir
aftur 5 sinnum þáttatilraun af 4, og 4

142
00:06:46,970 --> 00:06:49,710
er að fara að segja, OK, vel, aftur
4 sinnum þátta af 3.

143
00:06:49,710 --> 00:06:51,737
Og eins og þú sérð, við erum
konar nálgast 1.

144
00:06:51,737 --> 00:06:53,820
Við erum að fá nær og
nær að grunn tilfelli.

145
00:06:53,820 --> 00:06:58,180
>> Og þegar við högg grunn tilfelli,
allar fyrri aðgerðir

146
00:06:58,180 --> 00:07:00,540
hafa svarið sem þeir voru að leita að.

147
00:07:00,540 --> 00:07:03,900
Factorial af 2 var að segja aftur
2 sinnum aðfeldi 1.

148
00:07:03,900 --> 00:07:06,760
Jæja, þáttatilraun af 1 skilar 1.

149
00:07:06,760 --> 00:07:10,090
Svo kalla Hrópmerkt
af 2 getur aftur 2 sinnum 1,

150
00:07:10,090 --> 00:07:13,980
og gefa það aftur til aðfeldi
3, sem er að bíða eftir að niðurstöðu.

151
00:07:13,980 --> 00:07:17,110
>> Og þá er það er hægt að reikna
þess vegna, 3 sinnum 2 er 6,

152
00:07:17,110 --> 00:07:18,907
og gefa það aftur til Hrópmerkt af 4.

153
00:07:18,907 --> 00:07:20,740
Og aftur, höfum við
vídeó á símtali mánudaginn

154
00:07:20,740 --> 00:07:23,810
þar sem þessi er sýnd smá
meira en það sem ég er að segja núna.

155
00:07:23,810 --> 00:07:25,300
En þetta er það.

156
00:07:25,300 --> 00:07:29,300
Þetta eitt og sér er lausn á
reikna aðfeldi tölu.

157
00:07:29,300 --> 00:07:31,527
>> Það er aðeins fjórum línum af kóða.

158
00:07:31,527 --> 00:07:32,610
Það er laglegur kaldur, ekki satt?

159
00:07:32,610 --> 00:07:35,480
Það er góður af kynþokkafullur.

160
00:07:35,480 --> 00:07:38,580
>> Svo almennt, en ekki
alltaf, endurkvæma virka

161
00:07:38,580 --> 00:07:41,190
Hægt er að skipta lykkju a
ekki endurkvæma virka.

162
00:07:41,190 --> 00:07:46,100
Svo hér, hlið við hlið, er endurtekningu
útgáfa af þátta virka.

163
00:07:46,100 --> 00:07:49,650
Báðir þessir Reikna
nákvæmlega það sama.

164
00:07:49,650 --> 00:07:52,170
>> Þeir báðir reikna aðfeldi n.

165
00:07:52,170 --> 00:07:54,990
The útgáfa á vinstri
notar endurkvæmni til að gera það.

166
00:07:54,990 --> 00:07:58,320
The útgáfa á hægri
notar endurtekning til að gera það.

167
00:07:58,320 --> 00:08:02,050
>> Og takið eftir, verðum við að lýsa
a breyta heiltala vara.

168
00:08:02,050 --> 00:08:02,940
Og þá erum við lykkja.

169
00:08:02,940 --> 00:08:06,790
Svo lengi sem n er stærra en 0, við
halda að margfalda þá vöru af N

170
00:08:06,790 --> 00:08:09,890
og decrementing n til
við reiknum vöruna.

171
00:08:09,890 --> 00:08:14,600
Svo þessar tvær aðgerðir, aftur,
gera nákvæmlega það sama.

172
00:08:14,600 --> 00:08:19,980
En þeir gera það ekki í
nákvæmlega sama hátt.

173
00:08:19,980 --> 00:08:22,430
>> Nú, það er hægt að
hafa fleiri en einn basa

174
00:08:22,430 --> 00:08:25,770
tilvik eða fleiri en eitt
endurkvæma ræða, eftir

175
00:08:25,770 --> 00:08:27,670
á hvaða virka er að reyna að gera.

176
00:08:27,670 --> 00:08:31,650
Þú ert ekki endilega bara takmarkað við
einni stöð ræða eða eitt endurkvæma

177
00:08:31,650 --> 00:08:32,370
ræða.

178
00:08:32,370 --> 00:08:35,320
Svo dæmi um eitthvað
með mörgum tilfellum grunn

179
00:08:35,320 --> 00:08:37,830
gæti verið this-- að
Fibonacci talnarunu.

180
00:08:37,830 --> 00:08:41,549
>> Þú getur muna frá
grunnskólabörn daga skóla

181
00:08:41,549 --> 00:08:45,740
að Fibonacci raðar er skilgreind
eins this-- fyrsti þátturinn er 0.

182
00:08:45,740 --> 00:08:46,890
Annað þáttur er 1.

183
00:08:46,890 --> 00:08:49,230
Bæði af þeim eru bara með skilgreiningu.

184
00:08:49,230 --> 00:08:55,920
>> Þá annað hvert frumefni er skilgreint
sem summa n mínus 1 og n mínus 2.

185
00:08:55,920 --> 00:09:00,330
Svo þriðja þáttur
væri 0 plús 1 er 1.

186
00:09:00,330 --> 00:09:03,280
Og þá fjórði þáttur
væri annað þáttur, 1,

187
00:09:03,280 --> 00:09:06,550
auk Þriðji þáttur 1.

188
00:09:06,550 --> 00:09:08,507
Og það væri 2.

189
00:09:08,507 --> 00:09:09,340
Og svo framvegis og svo framvegis.

190
00:09:09,340 --> 00:09:11,680
>> Þannig að í þessu tilfelli, höfum við tvær grunn tilvikum.

191
00:09:11,680 --> 00:09:14,850
Ef n er jafnt og 1, aftur 0.

192
00:09:14,850 --> 00:09:18,560
Ef n er jafnt og 2, skila 1.

193
00:09:18,560 --> 00:09:25,930
Annars skal skila Fibonacci n
mínus 1 plus Fibonacci n mínus 2.

194
00:09:25,930 --> 00:09:27,180
>> Svo er það margar tilvikum grunn.

195
00:09:27,180 --> 00:09:29,271
Hvað um margra endurkvæma tilvikum?

196
00:09:29,271 --> 00:09:31,520
Jæja, það er eitthvað
kallað Collatz ágiskanir.

197
00:09:31,520 --> 00:09:34,630
Ég ætla ekki að segja,
þú veist hvað það er,

198
00:09:34,630 --> 00:09:38,170
vegna þess að það er í raun endanlega okkar
Vandamálið fyrir þessa tilteknu vídeó.

199
00:09:38,170 --> 00:09:43,220
Og það er æfing okkar
að vinna saman.

200
00:09:43,220 --> 00:09:46,760
>> Svo er hér það sem
Collatz conjecture is--

201
00:09:46,760 --> 00:09:48,820
það á við um sérhverja jákvæða heiltölu.

202
00:09:48,820 --> 00:09:51,500
Og það veltir að það er
alltaf hægt að fá til baka

203
00:09:51,500 --> 00:09:55,060
1 ef þú fylgir þessum leiðbeiningum.

204
00:09:55,060 --> 00:09:57,560
Ef n er 1, hætta.

205
00:09:57,560 --> 00:10:00,070
Við höfum fengið til baka 1 ef n er 1.

206
00:10:00,070 --> 00:10:05,670
>> Annars er farið í gegnum þetta
Ferlið aftur á n deilt með 2.

207
00:10:05,670 --> 00:10:08,200
Og sjá hvort þú getur fengið aftur til 1.

208
00:10:08,200 --> 00:10:13,260
Annars, ef n er oddatala, fara í gegnum
Þetta ferli aftur á 3N plús 1,

209
00:10:13,260 --> 00:10:15,552
eða 3 sinnum n plús 1.

210
00:10:15,552 --> 00:10:17,010
Svo hér höfum við einn grunn tilfelli.

211
00:10:17,010 --> 00:10:18,430
Ef n er jafnt og 1, hætta.

212
00:10:18,430 --> 00:10:20,230
Við erum ekki að gera eitthvað meira endurkvæmni.

213
00:10:20,230 --> 00:10:23,730
>> En við höfum tvær endurkvæma tilvikum.

214
00:10:23,730 --> 00:10:28,750
Ef n er jafnvel, gera við einn endurkvæma
ræða, köllun n deilt með 2.

215
00:10:28,750 --> 00:10:33,950
Ef n er oddatala, gera við aðra
endurkvæma málið á 3 sinnum N plús 1.

216
00:10:33,950 --> 00:10:39,120
>> Og svo markmið fyrir þetta vídeó er
að taka annað, gera hlé á vídeó,

217
00:10:39,120 --> 00:10:42,440
og reyna að skrifa þetta
endurkvæma virka Collatz

218
00:10:42,440 --> 00:10:47,640
þar sem þú framhjá í gildi n, og
það reiknar hversu mörg skref það

219
00:10:47,640 --> 00:10:52,430
tekur að fá 1 ef þú byrjar frá n
og þú fylgir þessum skrefum upp hér að ofan.

220
00:10:52,430 --> 00:10:56,660
Ef n er 1, það tekur 0 skrefum.

221
00:10:56,660 --> 00:11:00,190
Annars, það er að fara að
taka eitt skref auk hins vegar

222
00:11:00,190 --> 00:11:06,200
margir stíga það tekur að annaðhvort n
deilt með 2 ef n er jafnvel, eða 3n auk 1

223
00:11:06,200 --> 00:11:08,100
ef n er oddatala.

224
00:11:08,100 --> 00:11:11,190
>> Nú, ég hef sett upp á skjánum hér
a par af próf hlutum fyrir þig,

225
00:11:11,190 --> 00:11:15,690
a par af próf tilfelli fyrir þig, til að sjá
hvað þessar mismunandi Collatz tölur eru,

226
00:11:15,690 --> 00:11:17,440
og einnig mynd sem sýnir
af þeim skrefum sem

227
00:11:17,440 --> 00:11:20,390
þarf að vera farinn í gegnum svo þú getur
konar sjá þetta ferli í aðgerð.

228
00:11:20,390 --> 00:11:24,222
Þannig að ef n er jafnt og
1, Collatz af n er 0.

229
00:11:24,222 --> 00:11:26,180
Þú þarft ekki að gera
allt til að komast aftur til 1.

230
00:11:26,180 --> 00:11:27,600
Þú ert nú þegar.

231
00:11:27,600 --> 00:11:30,550
>> Ef n er 2, það tekur
eitt skref til að fá til 1.

232
00:11:30,550 --> 00:11:31,810
Þú byrjar með 2.

233
00:11:31,810 --> 00:11:33,100
Ja, 2 er ekki jafnt og 1.

234
00:11:33,100 --> 00:11:36,580
Svo það er að fara að vera einu skrefi
auk hins vegar margir skref IT

235
00:11:36,580 --> 00:11:38,015
tekur á n deilt með 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 deilt með 2 er 1.

238
00:11:42,910 --> 00:11:47,200
Þannig að það tekur eitt skref auk hins vegar
margir stíga það tekur fyrir 1.

239
00:11:47,200 --> 00:11:49,720
1 tekur núll skref.

240
00:11:49,720 --> 00:11:52,370
>> Fyrir 3, eins og þú geta sjá, það er
alveg nokkur skref sem taka þátt.

241
00:11:52,370 --> 00:11:53,590
Þú ferð frá 3.

242
00:11:53,590 --> 00:11:56,710
Og þá fara að
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Það tekur sjö skref til að komast aftur til 1.

244
00:11:58,804 --> 00:12:01,220
Og eins og þú geta sjá, það er
nokkrar aðrar tilvikum próf hér

245
00:12:01,220 --> 00:12:02,470
til að prófa forritið þitt.

246
00:12:02,470 --> 00:12:03,970
Svo aftur, gera hlé á vídeó.

247
00:12:03,970 --> 00:12:09,210
Og ég ætla að fara að hoppa til baka núna til
hvað í raun ferli er hér,

248
00:12:09,210 --> 00:12:11,390
hvað þetta conjecture er.

249
00:12:11,390 --> 00:12:14,140
>> Athugaðu hvort þú getur fundið út
hvernig á að skilgreina Collatz á n

250
00:12:14,140 --> 00:12:19,967
þannig að það reiknar hversu margir
skref sem það tekur að fá til 1.

251
00:12:19,967 --> 00:12:23,050
Svo vonandi hefur þú bið vídeó
og þú ert ekki bara að bíða eftir mér

252
00:12:23,050 --> 00:12:25,820
til að gefa þér svarið hér.

253
00:12:25,820 --> 00:12:29,120
En ef þú ert vel,
hér er svarið samt.

254
00:12:29,120 --> 00:12:33,070
>> Svo hér er hægt skilgreining
af Collatz virka.

255
00:12:33,070 --> 00:12:35,610
Stöð okkar case-- ef n er
jöfn 1, aftur við 0.

256
00:12:35,610 --> 00:12:38,250
Það þýðir ekki að taka eitthvað
skref til að komast aftur til 1.

257
00:12:38,250 --> 00:12:42,710
>> Annars höfum við tvær endurkvæma cases--
einn fyrir sléttar tölur og einn fyrir skrýtið.

258
00:12:42,710 --> 00:12:47,164
Og ég prófa að jafnvel tölur
er að athuga hvort n unga fólkið 2 jafngildir 0.

259
00:12:47,164 --> 00:12:49,080
Þetta er í grundvallaratriðum, aftur,
spyrja spurningu,

260
00:12:49,080 --> 00:12:54,050
ef þú manst hvað unga fólkið is-- ef ég
skipta n um 2 er engin afgangurinn?

261
00:12:54,050 --> 00:12:55,470
Það væri jafnvel tala.

262
00:12:55,470 --> 00:13:01,370
>> Og svo ef n unga fólkið 2 er 0 er
próf er þetta slétt tala.

263
00:13:01,370 --> 00:13:04,250
Ef svo er, ég vil skila 1,
vegna þess að þetta er örugglega

264
00:13:04,250 --> 00:13:09,270
taka eitt skref auk Collatz af
hvað sem tala er helmingur af mér.

265
00:13:09,270 --> 00:13:13,910
Annars vil ég að skila 1
auk Collatz 3 sinnum n plús 1.

266
00:13:13,910 --> 00:13:16,060
Það var hinn
endurkvæma skref sem við

267
00:13:16,060 --> 00:13:19,470
gæti tekið að reikna
Collatz-- fjölda skrefa

268
00:13:19,470 --> 00:13:22,610
það tekur að komast aftur
til 1 gefið númer.

269
00:13:22,610 --> 00:13:24,610
Svo vonandi, þetta dæmi
gaf þér svolítið

270
00:13:24,610 --> 00:13:26,620
af bragð af endurkvæma málsmeðferð.

271
00:13:26,620 --> 00:13:30,220
Vonandi finnst þér númerið er
lítið fallegri ef til framkvæmda

272
00:13:30,220 --> 00:13:32,760
í glæsilegri, endurkvæma hátt.

273
00:13:32,760 --> 00:13:35,955
En jafnvel ef ekki, endurkvæmni er
mjög öflugt tól engu að síður.

274
00:13:35,955 --> 00:13:38,330
Og svo er það örugglega eitthvað
að fá höfuðið í kring,

275
00:13:38,330 --> 00:13:41,360
vegna þess að þú munt vera fær til að búa til
laglegur kaldur forrit með endurkvæmni

276
00:13:41,360 --> 00:13:45,930
sem annars gæti verið flókið að skrifa
ef þú ert að nota lykkjur og ítrun.

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

278
00:13:46,980 --> 00:13:48,780
Þetta er CS50.

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