>> [Music kucheza]
>> DOUG LLOYD: Pengine kufikiri kwamba kanuni ni tu kutumika kwa kukamilisha kazi.
Kuandika ni nje.
Ni haina kitu.
Hiyo ni pretty kiasi.
>> Wewe kukusanya yake.
Wewe kuendesha programu.
Wewe ni vizuri kwenda.
>> Lakini amini au, kama wewe kanuni kwa muda mrefu,
wewe kweli ili kuja kuona kanuni kama kitu ambacho ni nzuri.
Ni kutatua tatizo katika njia ya kuvutia sana,
au kuna tu kitu kweli nadhifu kuhusu njia inaonekana.
Unaweza kuwa akicheka saa yangu, lakini ni kweli.
Na kujirudia ni njia mojawapo kwa namna ya kupata wazo hili
ya nzuri, kifahari-kuangalia kanuni.
Ni kutatua matatizo kwa njia ambazo ni ya kuvutia, rahisi taswira,
na kushangaza mfupi.
>> Kazi njia kujirudia ni, kazi ya kujirudia
inaelezwa kama kazi kwamba wito yenyewe kama sehemu ya utekelezaji wake.
Hiyo inaweza kuonekana kidogo ajabu, na tutaweza kuona kidogo
kuhusu jinsi hii matendo katika wakati huu.
Lakini tena, hizi taratibu kujirudia ni
kwenda kuwa hivyo kifahari kwa sababu wao wanaenda
kutatua tatizo hili bila kuwa kazi hizi zote nyingine
au hizi mizunguko ya muda mrefu.
Utaona kwamba hizi kujirudia taratibu ni kwenda kuangalia hivyo kwa muda mfupi.
Na kwa kweli ni kwenda kufanya kanuni yako kuangalia mengi nzuri zaidi.
>> Mimi nitakupa mfano ya hii kuona jinsi
utaratibu kujirudia inaweza kuelezwa.
Hivyo kama wewe ni ukoo na hii kutoka hesabu darasani miaka mingi iliyopita,
kuna kitu kinachoitwa factorial kazi, ambayo ni kawaida
ulionyehsa kama mshangao uhakika, ambayo inaelezwa zaidi ya integers yote mazuri.
Na kwa njia hiyo n factorial ni mahesabu
ni wewe kuzidisha yote ya nambari chini ya
au sawa na n together-- integers zote chini ya
au sawa na n pamoja.
>> Hivyo 5 factorial ni mara 5 Mara 4 mara 3 2 mara 1.
Na 4 factorial ni mara 4 Mara 3 2 mara 1 na kadhalika.
Unaweza kupata wazo.
>> Kama programmers, hatufanyi kutumia n, mshangao uhakika.
Hivyo tutaweza kufafanua factorial kazi kama ukweli wa n.
Na tutaweza kutumia factorial kujenga ufumbuzi kujirudia kwa tatizo hilo.
Na nadhani unaweza kupata kuwa ni mengi zaidi kuibua
rufaa ya iterative toleo la hii, ambayo
tutaweza pia tuangalie katika wakati huu.
>> Hivyo hapa ni michache ya facts-- pun intended--
kuhusu factorial-- factorial kazi.
Factorial ya 1, kama nilivyosema, ni 1.
Factorial ya 2 ni 2 mara 1.
Factorial ya 3 ni 3 mara 2 mara 1, na kadhalika.
Kuongelea 4 na 5 tayari.
>> Lakini kuangalia hii, ni hii si kweli?
Si factorial ya 2 tu 2 mara factorial ya 1?
I mean, factorial ya 1 ni 1.
Hivyo kwa nini hatuwezi tu kusema kwamba, tangu factorial ya 2 ni 2 mara 1,
ni kweli tu mara 2 factorial ya 1?
>> Na kisha kupanua wazo hilo, si factorial ya 3
tu mara 3 factorial ya 2?
Na factorial ya 4 ni mara 4 factorial ya 3, na kadhalika?
Kwa kweli, factorial ya idadi yoyote unaweza tu
kuwa walionyesha kama sisi aina ya kubeba huu milele nje.
Tunaweza aina ya kujumlisha Tatizo factorial
kama ni n mara factorial ya n bala 1.
Ni mara n bidhaa za namba zote chini ya mimi.
>> Wazo hili, hii generalization ya tatizo,
inaruhusu sisi recursively kufafanua kazi factorial.
Wakati kufafanua kazi recursively, kuna
mambo mawili ambayo yanahitaji kuwa sehemu yake.
Unahitaji kuwa na kitu kinachoitwa kesi ya msingi, ambayo, wakati wewe kusababisha yake,
kuacha mchakato kujirudia.
>> Vinginevyo, kazi kwamba wito itself-- kama unaweza imagine--
inaweza kuendelea milele.
Kazi wito kazi wito wito kazi
kazi wito kazi.
Kama huna njia na kuacha ni, mpango wako
Itakuwa ufanisi kukwama katika kitanzi usio.
Itakuwa ajali hatimaye, kwa sababu kutakuwa na kukimbia nje ya kumbukumbu.
Lakini hiyo ni kando ya uhakika.
>> Tunahitaji kuwa na njia nyingine kuacha mambo badala ya mpango wetu mshindo,
kwa sababu mpango huo shambulio ni pengine si nzuri au kifahari.
Na hivyo sisi wito huu kesi ya msingi.
Hii ni ufumbuzi rahisi tatizo ambalo haachi
mchakato kujirudia kutoka kutokea.
Hivyo hiyo ni sehemu moja ya kazi ya kujirudia.
>> Sehemu ya pili ni kesi ya kujirudia.
Na hii ni mahali ambapo kujirudia kwa kweli kuchukua nafasi.
Hii ni pale ambapo kazi itakuwa kujiita.
>> Itakuwa si kujiita katika hasa njia ile ile ilikuwa inaitwa.
Ni utakuwa tofauti kidogo kwamba inafanya tatizo ni
kujaribu kutatua teeny kidogo kidogo.
Lakini kwa ujumla hupita mume ya kutatua wingi wa ufumbuzi
mwito tofauti chini ya mstari.
>> Ni yupi kati ya hawa inaonekana kama kesi ya msingi hapa?
Ambayo moja ya inaonekana hawa kama rahisi ufumbuzi wa tatizo?
Tuna kundi la factorials, na tunaweza kuendelea
kwenda on-- 6, 7, 8, 9, 10, na kadhalika.
>> Lakini moja ya inaonekana hawa kama kesi nzuri ya kuwa kesi ya msingi.
Ni ufumbuzi rahisi sana.
Hatuna kufanya kitu chochote maalum.
>> Factorial ya 1 ni 1 tu.
Hatuna kufanya lolote kuzidisha wakati wote.
Inaonekana kama kama tunakwenda kujaribu na kutatua tatizo hili,
na sisi haja ya kuacha kujirudia mahali fulani,
sisi pengine wanataka kuacha ni wakati sisi kupata 1.
Hatutaki kuacha kabla ya hapo.
>> Hivyo kama sisi ni kufafanua kazi yetu factorial,
hapa ni mifupa kwa jinsi sisi anaweza kufanya hivyo.
Tunahitaji kuziba katika wale wawili things-- kesi ya msingi na kesi ya kujirudia.
Nini kesi ya msingi?
Kama n ni sawa na 1, kurudi 1-- hiyo ni Tatizo kweli rahisi kutatua.
>> Factorial ya 1 ni 1.
Siyo 1 mara chochote.
Ni tu 1.
Ni ukweli rahisi sana.
Na hivyo ambayo inaweza kuwa msingi wetu kesi.
Kama sisi kupata kupita 1 katika hii kazi, tutaweza tu kurudi 1.
>> Nini kujirudia kesi pengine kuangalia kama?
Kwa kila idadi vingine badala 1, nini mfano?
Naam, kama sisi ni kuchukua factorial ya n,
ni mara n factorial ya n bala 1.
>> Kama sisi ni kuchukua factorial ya 3, ni mara 3 factorial ya 3 bala 1,
au 2.
Na hivyo kama sisi siyo kuangalia saa 1, vinginevyo
Mara kurudi n factorial ya n bala 1.
Ni pretty moja kwa moja.
>> Na kwa ajili ya kuwa na kidogo safi na zaidi ya kifahari kificho,
kujua kwamba kama tuna single-mstari loops au moja-line matawi masharti,
tunaweza kujikwamua yote ya braces curly inayowazunguka.
Ili tuweze kuimarisha huu kwa hili.
Hii ina sawa utendaji kama hii.
>> Mimi tu kuchukua mbali curly inakabiliwa na, kwa sababu kuna mstari mmoja tu
ndani ya matawi hayo masharti.
Basi hizi kuishi identically.
Kama n ni sawa na 1, kurudi 1.
Vinginevyo kurudi mara n factorial ya n bala 1.
Hivyo sisi ni kufanya tatizo ndogo.
Kama n kuanza nje kama 5, tunakwenda kurudi mara 5 factorial ya 4.
Na tutaweza kuona katika dakika tunapozungumza kuhusu wito stack-- katika video nyingine
ambapo sisi majadiliano juu piga stack-- tutaweza kujifunza
kuhusu nini hasa mchakato huu kazi.
>> Lakini wakati factorial ya 5 inasema kurudi mara 5 factorial ya 4, na 4
ni kwenda kusema, OK, vizuri, kurudi Mara 4 factorial ya 3.
Na kama unaweza kuona, tuko aina ya inakaribia 1.
Sisi ni kupata karibu na karibu na kwamba kesi ya msingi.
>> Na mara moja sisi hit kesi ya msingi, yote ya kazi ya awali
jibu walikuwa wanatafuta.
Factorial ya 2 alikuwa akisema kurudi 2 mara factorial ya 1.
Naam, factorial ya 1 anarudi 1.
Hivyo wito kwa factorial ya 2 wanaweza kurudi mara 2 kwa 1,
na kutoa kwamba nyuma ya factorial ya 3, ambayo ni kusubiri kwa kuwa matokeo.
>> Na kisha unaweza mahesabu matokeo yake, mara 3 2 ni 6,
na kuwapa nyuma kwa factorial ya 4.
Na tena, tuna video juu ya wito mkusanyiko
ambapo hii ni mfano kidogo zaidi ya nini mimi kusema hivi sasa.
Lakini hii ni yake.
Hii peke yake ni ufumbuzi wa kuhesabu factorial ya idadi.
>> Ni mistari minne tu ya kificho.
Hiyo ni pretty baridi, sawa?
Ni aina ya sexy.
>> Hivyo kwa ujumla, lakini si siku zote, kazi ya kujirudia
anaweza kuchukua nafasi kitanzi katika yasiyo ya kujirudia kazi.
Hivyo hapa, bega kwa bega, ni iterative toleo la kazi factorial.
Wote hawa mahesabu hasa kitu kimoja.
>> Wote wawili mahesabu factorial ya n.
Toleo la upande wa kushoto anatumia kujirudia kwa kufanya hivyo.
Toleo la juu ya haki anatumia iteration ya kufanya hivyo.
>> Na taarifa, tuna kutangaza kutofautiana integer bidhaa.
Na kisha sisi kitanzi.
Hivyo muda mrefu kama n ni kubwa kuliko 0, sisi kuweka kuzidisha kuwa bidhaa hiyo na N
na decrementing n mpaka sisi mahesabu ya bidhaa.
Hivyo kazi hizi mbili, tena, kufanya hasa kitu kimoja.
Lakini hawana kufanya hivyo katika hasa kwa njia hiyo.
>> Sasa, inawezekana kwa kuwa na msingi zaidi ya moja
kesi au zaidi ya moja kujirudia kesi, kulingana
juu ya nini kazi yako ni kujaribu kufanya.
Wewe ni si lazima tu mdogo kwa kesi moja ya msingi au kujirudia moja
kesi.
Hivyo mfano wa kitu na kesi nyingi msingi
Haya inaweza kuwa Fibonacci idadi mlolongo.
>> Unaweza kukumbuka kutoka msingi siku shule
kwamba mlolongo Fibonacci inaelezwa kama hii kitu cha kwanza ni 0.
Kipengele cha pili ni 1.
Wote wale ni tu kwa ufafanuzi.
>> Kisha kila kipengele nyingine inaelezwa kama jumla ya n bala 1 na n bala 2.
Hivyo kipengele cha tatu itakuwa 0 pamoja na 1 ni 1.
Na kisha kipengele cha nne itakuwa kipengele cha pili, 1,
pamoja na kipengele cha tatu, 1.
Na kwamba itakuwa 2.
Na kadhalika na kadhalika.
>> Hivyo katika kesi hii, tuna kesi mbili msingi.
Kama n ni sawa na 1, kurudi 0.
Kama n ni sawa na 2, kurudi 1.
Vinginevyo, kurudi Fibonacci wa n bala 1 pamoja Fibonacci wa n bala 2.
>> Hivyo hiyo ni kesi nyingi msingi.
Je kuhusu kesi nyingi kujirudia?
Naam, kuna kitu aitwaye dhana Collatz.
Mimi si kwenda kusema, unajua nini, yaani,
kwa sababu ni kweli mwisho wetu Tatizo kwa video hii tu.
Na ni zoezi wetu kufanya kazi ya pamoja.
>> Hivyo hapa ni nini Collatz dhana is--
inatumika kwa kila sifuri.
Na speculates kwamba ni kila mara inawezekana kupata nyuma
kwa 1 kama wewe kufuata hatua hizi.
Kama n ni 1, kuacha.
Sisi tumepewa nyuma 1 ikiwa n ni 1.
>> Vinginevyo, kwenda kwa njia hii mchakato tena juu ya n kugawanywa na 2.
Na kuona kama unaweza kupata nyuma 1.
Vinginevyo, kama n ni isiyo ya kawaida, kupitia mchakato huu tena juu ya 3n pamoja na 1,
au mara 3 n pamoja na 1.
Hivyo hapa tuna moja kesi ya msingi.
Kama n ni sawa na 1, kuacha.
Sisi siyo kufanya kujirudia tena.
>> Lakini tuna kesi mbili kujirudia.
Kama n ni hata, tunafanya kujirudia moja kesi, wito n kugawanywa na 2.
Kama n ni isiyo ya kawaida, sisi kufanya mbalimbali kujirudia kesi juu mara 3 n pamoja na 1.
>> Na hivyo lengo kwa video hii ni kuchukua pili, pause video,
na kujaribu na kuandika hii kazi ya kujirudia Collatz
ambapo kupita katika thamani n, na ni mahesabu ya hatua wangapi ni
inachukua kupata 1 kama wewe kuanza kutoka n na wewe kufuata hatua hizo hadi hapo juu.
Kama n ni 1, inachukua hatua 0.
Vinginevyo, ni kwenda kuchukua hatua moja pamoja na hata hivyo
hatua nyingi inachukua juu ya n ama kugawanywa na 2 kama n ni hata, au 3n pamoja na 1
kama n ni isiyo ya kawaida.
>> Sasa, nimekuwa kuweka juu ya screen hapa michache ya mtihani mambo kwa ajili yenu,
michache ya kesi ya vipimo kwa ajili yenu, ili kuona nini hawa mbalimbali idadi Collatz ni,
na pia mfano ya hatua ambazo
haja ya kuwa wamekwenda kupitia hivyo unaweza aina ya kuona mchakato huu katika hatua.
Hivyo kama n ni sawa na 1, Collatz ya n ni 0.
Huna kufanya chochote kupata nyuma 1.
Wewe ni tayari pale.
>> Kama n ni 2, inachukua hatua moja ya kupata 1.
Unaweza kuanza kwa 2.
Naam, 2 si sawa na 1.
Hivyo ni kwenda kuwa hatua moja pamoja na hata hivyo wengi hatua hiyo
inachukua n kugawanywa na 2.
>> 2 kugawanywa na 2 ni 1.
Hivyo inachukua hatua moja pamoja na hata hivyo hatua nyingi inachukua kwa 1.
1 inachukua hatua sifuri.
>> Kwa 3, kama unaweza kuona, kuna hatua chache kabisa kushiriki.
Wewe kwenda kutoka 3.
Na kisha kwenda kwa 10, 5, 16, 8, 4, 2, 1.
Inachukua hatua saba kupata nyuma 1.
Na kama unaweza kuona, kuna wanandoa wengine kesi mtihani hapa
mtihani nje mpango wako.
Hivyo tena, pause video.
Na nitakwenda kuruka nyuma sasa kwa nini mchakato halisi ni hapa,
nini dhana hii ni.
>> Kuona kama unaweza kufikiri jinsi ya kufafanua Collatz ya n
hivyo kwamba mahesabu ya jinsi wengi hatua inachukua kupata kwa 1.
Hivyo hopefully, una paused video na wewe si tu kusubiri kwa ajili yangu
kukupa jibu hapa.
Lakini kama wewe ni, vizuri, hapa ni jibu hata hivyo.
>> Hivyo hapa ni ufafanuzi iwezekanavyo ya kazi Collatz.
Msingi wetu case-- ikiwa n ni sawa na 1, sisi kurudi 0.
Haina kuchukua yoyote hatua ya kupata nyuma 1.
>> Vinginevyo, tuna mbili kujirudia cases-- moja kwa idadi hata na kimoja cha isiyo ya kawaida.
Njia ya mimi mtihani kwa idadi hata ni kuangalia kama n Mod 2 sawa na 0.
Hii ni kimsingi, tena, kuuliza swali,
kama unakumbuka kile mod is-- kama mimi mgawanyiko n na 2 ni hakuna salio?
Hiyo itakuwa hata idadi.
>> Na hivyo kama n Mod 2 sawa na 0 ni kupima ni hii hata idadi.
Kama ni hivyo, nataka kurudi 1, kwa sababu hii ni dhahiri
kuchukua hatua moja pamoja na Collatz ya chochote idadi ni nusu ya mimi.
Vinginevyo, nataka kurudi 1 pamoja na Collatz ya mara 3 n pamoja na 1.
Hiyo ilikuwa ni mwingine hatua kujirudia kwamba sisi
inaweza kuchukua kwa mahesabu Collatz-- idadi ya hatua
inachukua kupata nyuma kwa 1 kutokana na idadi.
Hivyo hopefully, mfano huu aliwapa kidogo
ya ladha ya taratibu kujirudia.
Hopefully, unafikiri kificho ni kidogo nzuri zaidi kama zinatekelezwa
katika kifahari, kujirudia njia.
Lakini hata kama si, kujirudia ni kweli zana yenye nguvu hata hivyo.
Na hivyo ni dhahiri kitu kupata kichwa yako karibu,
kwa sababu wewe utakuwa na uwezo wa kujenga mipango pretty baridi kwa kutumia recursion
kwamba ili vinginevyo kuwa ngumu kuandika kama unatumia mizunguko na iteration.
Mimi nina Doug Lloyd.
Hii ni CS50.