[Powered by Google Translate] [§ 3] [méně komfortní] [Nate Hardison] [Harvard University] [To je CS50.] [CS50.TV] Dobře, pojďme začít. Vítejte do týdne 4 CS50. Pokud jste otevřít webový prohlížeč a otevřít PSet 3, Scramble s CS50, budeme začít chodit prostřednictvím sekce otázek tam. Stejně jako minulý týden, budeme pracovat v CS50 Spaces, pokud budete také vytáhnout, že se stejně, a pokud budete pokračovat a navštivte tento odkaz, na který jsem dostal tady nahoře. Je čas začít. Máme naši malou hi programu zde. Nic blázen. Jedna z prvních věcí, které chci udělat s vámi dnes probrat několik řešení k problému Set 1, takovým příkladem řešení, jen tak můžete získat pocit, pro to, co druhy kódu zaměstnanců je psaní, jaké studentů kódu ostatních píší, a máte se na to podívat, protože vím, že je to divné když zadáte řešení problému nastavení a získat připomínky na své vlastní verzi, ale někdy je to užitečné vidět, jak ostatní lidé dělali to, zejména ty, které jsou pěkně vypadající. Pro nejvíce se rozdělit, byl jsem opravdu ohromen s řešením, které jste produkoval. Ještě jsem začal hledat na seznam 2s Problem Set, ale v případě, že jste něco jako první, znamená to, že nic, ale dobré věci. Pokud se podíváte na mé verzi, začněme celou cestu dolů na revize 1, a budeme se rychle podívat na řešení Mario. Pokud budete tahat doplnila, tyto programy, které budeme prezentovat jsou správné. Nebylo správnost problémy s těmito problémy, ale spíše, chceme mluvit trochu o různých konstrukčních problémů , které byly použity zde. Jedna z věcí, která byla zajímavá o řešení je to, že používá tento nový konstrukt s názvem libra definovat, někdy také označována jako hash definovat. Dovolte mi, abych se zaměřit na to tady. # Define umožňuje dát jména těchto čísel v programu. V tomto případě je maximální výška pyramidy v Mario byl 23 a spíše než dávat 23 v mém kódu, bychom odkazují k tomu, jak pevný kódování 23 - Namísto toho dává název MAX_HEIGHT na toto číslo, tak, aby se tady v mém do-while můžete vlastně se odkazovat na MAX_HEIGHT místo toho, aby počet 23 palců [Student] Jaká je výhoda dělat, že? To je velká otázka. Jedním z nich je čitelnost. Výhodou použití tohoto # define je čitelnost. Když čtu tento kód, vidím, co se děje. Vidím v tomto stavu zde testujeme pro výšku je <0, které jsme také mohl definovány být minimální výška nebo min výška. Další výhodou je, že se může potom přečíst zbytek řádku vidět že jsme také kontrolu, aby se ujistil, že výška není větší než výška max., protože budeme pokračovat, zatímco výška je větší než výška max. Další výhodou je, když jsem vzdálíte trochu sem- když jsem spustit tento program, a já jej spustit, řekněme, s 23 právě teď, vám vypíše všechny řádky 23 jen jako, že. Ale říct, že jsem chtěl změnit výšku max, a teď chci omezit maximální výšku pyramid být pouze říci-man, který byl zděšený. # Include , # define MAX_HEIGHT, a řekněme, že jsme chtěli nastavit výši 10. V tomto okamžiku, vše, co jsem musel udělat, bylo změnit v tomto jednom místě. Mohu překompilovat kód, a teď, když se snažím a zadejte 12, to bude výzva mě znovu. V tomto případě, jsme pouze pomocí MAX_HEIGHT jednou. Není to tak velký potíží jít a změnit ji v cyklu while, pokud potřebujete. Ale v programech, kde jste odkazující na stejné magické číslo znovu a znovu, to # define mechanismus je opravdu šikovný protože stačí změnit to jednou v horní části souboru je obvykle kam jste je uložili, a změna prosakuje přes zbytek souboru. Další věci, které jsem chtěl poznamenat, v tomto úkolu, že jsem si myslel, vypadal opravdu pěkné, jeden byl pojmenování proměnných. Vidíte zde, že máme celočíselné proměnné s názvem řádku a tzv. výšku. Prostory, křížky, to pomáhá, aby se kód trochu čitelnější, dělá to trochu srozumitelnější, co se vlastně děje. Toto je v kontrastu k používání, řekněme, náhodná písmena nebo jen hatmatilka úplně. Poslední věc, kterou jsem si zdůraznit, je, že v pro smyčky, často tyto iterátor proměnné, tyto pulty, které používáte ve vaší pro smyčky, je to standardní a konvenční start je buď i a potom j a pak k a jít na odtamtud, pokud potřebujete více proměnných, a to je jen konvence. Existuje spousta úmluv. To závisí na programovacím jazyku, který používáte. Ale v C, jsme obvykle začínají s i. To nedává smysl používat, řekněme, nebo b v závislosti na situaci. To je to pro tento jeden. Pokud nyní vytáhnout Revize 2, uvidíte další Mario, a toto je podobná té druhé, které jsme právě viděli, ale to dělá něco docela fajn. Podíváme-li se v této sekci tady uvnitř vnitřní smyčky for, že používáte nějaký šílený hledáte syntaxe tu právě v tomto oboru. Toto se nazývá ternární operátor. Je-li else zhuštěné do jednoho řádku. Podmínkou je tato část v závorkách. Je to jako tvrdit, pokud j > Sam. Sam. Stejně jako Sam řekl, že lineární procesu hledání bude opravdu pomalé, a místo toho s binární vyhledávání, to funguje tak, že pokaždé, když jsme se projít iterace našeho hledání algoritmu, budeme rozdělit seznam na polovinu, v podstatě, do dvou menších seznamů. A pak na další iteraci smyčky, budeme rozdělovat znovu do jiných menších seznamů. Jak můžete vidět, problém je čím dál menší a menší protože zachováváme Škrt polovinu seznamu pokaždé. Jak to discard práci? Stejně jako připomínka, co budeme dělat, když jsme byli počítač a my jsme byli, řekněme, vyhledáváme pro číslo 5 v tomto seznamu je to, že bychom si vybrat číslo uprostřed. Ve středu tohoto seznamu, protože tam jsou 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 čísel, bychom vybrat číslo buď na 4. místě nebo na 5. pozici, a my bychom zavolat, že uprostřed našeho seznamu. Vyberte číslo uprostřed. Pak, stejně jako Sam řekl, budeme testovat, zda toto číslo se rovná na číslo, které chceme získat nebo si požadované číslo. Pokud je to stejné, pak jsme ho našli. Vyhráli jsme. Pokud to není stejné, pak existuje pár případů. Tyto dva případy jsou buď počet musí být větší než počet díváme, nebo je to méně než. Pokud je to větší, jsme se přesunout doprava. A pokud je to méně, jsme se přesunout doleva. A pak jsme celý proces opakovat znovu buď na pravé, nebo na levé poloviny poloviny seznamu. První problém v dnešním oddílu je zjistit, jak můžeme skutečně začít vyjadřovat toto v C kód. Máme pseudokódu zde. Co budeme začít dělat je, že jsem si vytáhnout zcela nový prostor, uložit tuto revizi tak, že máme tyto poznámky na později, budeme mazat, to vše a potom zkopírovat a vložit z problémového souboru tato informace do našich prostor, a doufejme, že to nepraskne. Perfect. Pokud jste vše dělat, zkopírujte a vložte tento kód do nového prostoru, do prázdnou. Pojďme zkusit Daniel. Pokud zkompilovat a spustit tento program, to funguje? Ne >> Co to říká? To říká, že kontrolní dosáhne konce non-void funkce. Jo, tak mi dovolte zkuste ji spustit. Už jste viděli tohle? Víte, co to znamená? Dobře, pojďme rozebrat to trochu. Je to řekl na file.c na řádku 9, sloupec 1 máme chybu, stejně jako jste řekl, a říká, že je to vyplývající z chyby varování a zpáteční typu varování. Vypadá to, že se něco děje s návratový typ, který dává smysl. Máme non-void funkci, což znamená, že máme funkci že nevrací neplatné. Void funkce je ten, který vypadá takto: void foo (), a je to neplatná, protože návratový typ je void, což znamená, že pokud bychom měli něco tady jako návrat 1, měli bychom se chyba kompilátoru pro to. Nicméně, máme non-void funkce. Naše non-void funkce v tomto případě je naše vyhledávací funkce protože má návratový typ bool. Když to říká, že kontrolní dosáhne konec non-void funkce, je to proto, že hledání nemá return. Není to vrací nic typu bool. Můžeme opravit to, a co vy na to vyhledávání by se měl vrátit ve výchozím nastavení? Jaký by měl být výchozí návratová hodnota hledání? Vzhledem k tomu, že to, co můžeme dát na konec. Charlotte, máš nějaké-? Pravda nebo lež? >> Pravda nebo lež. Který z nich? False. Nevím. False? Pojďme to zkusit. Proč si to return false? To je skvělé intuici. [Charlotte] Nevím. Budeme se vrátit false v tomto případě, protože to bude náš výchozí pokud z nějakého důvodu je seznam prázdný, nebo je jehla že jsme hledali neexistuje. Pak na samém konci, když nemáme vrátí true dříve v této funkci, vždy víme, že tato funkce bude říkat Ne, to není v poli. Není to v kupce sena. Nyní, když jsme se sestavit a spustit to, dovolte mi, abych uložit to tak můžeme vytáhnout ho nahoru. Nyní, když jsme se sestavit a spustit náš program, buduje. Dostaneme naši malou řádku. Pokud jsem trefil 4-uh-oh. Nebylo vytisknout nic. Vypadá to jako všechno skončilo dobře. Musíme vyplnit tento palců Mluvili jsme o tom algoritmu v pseudokódu trochu dříve. Ukažte, uložte tento, a já vytáhnout, že algoritmus opět probudí. Jdeme toho chlapa. Ne. Tady to je. Jak to uděláme? Co by být dobrá strategie pro rozjíždění tento kód? Musíte vybrat číslo uprostřed. Jak jsme si vybrat číslo uprostřed pole? Nějaké návrhy? [Student] strlen děleno 2. Strlen děleno 2. To je veliký. Strlen práce s speciálními druhy polí. Jaké druhy polí? String pole, pole znaků. Je to ten samý druh konceptu, který chceme použít, ale nemůžeme použít strlen, protože nemáme pole znaků. Máme řadu ints. Ale co strlen si pro nás? Víte, co to bude pro nás? [Student] strlen získá nám délku. Přesně tak, to bude nám délku. Strlen dostane délku pole pro nás. Jak jsme se dostali, že v našem programu binární vyhledávání? Jak byste si délku pole? [Student] strlen? Můžete si délku správně formátovaný pole řetězce C s strlen. Problém však je, že nemáme pole řetězců. Podíváme-li se zpět na tento kód, máme tuto integer pole. Jak můžeme vědět, jak dlouho to je? [Student] Je tam ekvivalent jeden pro koncový bod, jako je int l nebo tak něco? Ukazuje se, že ve skutečnosti není, a tak v jistém smyslu to je jedna z těch věcí, které je jen dobré vědět o C, že neexistuje žádný způsob, jak dostat délku pole pokud vše, co jsem vám je pole. Důvod, proč pracuje s řetězci, důvod strlen práce, Je tomu tak proto, pokud řetězec je správný formát, bude mít zvláštní, že \ 0 znak na samém konci. Můžete si také představit, pokud máte nesprávně formátovaný řetězec a není tam žádný \ 0 znak tam, pak celá věc nefunguje. [Student] Můžete přidat \ 0? My by v tomto případě. Mohli bychom přidat nějaký \ 0 nebo nějaký znamenat charakter a pak ji využít. Ale to není úplně to fungovat protože \ 0 je pro char typu, a tady máme ints. Druhá věc je, pokud bychom měli použít speciální hodnotu jako -1 označit konec pole pak bychom mohli po uložení -1 v našich celočíselných polí. Měli bychom být přilepená. Ukazuje se, že jediný způsob, jak se dostat na délku z pole v C je skutečně pamatovat když jej nastavit a pak projít kolem s poli tak, že kdykoli mám funkci, která to udělá nějakou práci na pole celých čísel nebo plováky nebo čtyřhra, nebo to, co jste, Také jsem dát tato funkce Array na délku, a to je přesně to, co jsme udělali tady v vyhledávací funkce. Když se podíváte, co jsme udělali, když jsme se projít v našem poli tady, jsme také projít v délce, velikosti. Prostě se to stane, že jsme nazvali tuto proměnnou zde, tento parametr nebo argument. To se nazývá funkce, je seznam argument nebo parametr seznam, a tito jsou také nazýváni argumenty nebo parametry. Lidé používají různé termíny v různých časech. Někdy střídat je sám. To jen tak se stane, že tato proměnná je zde pojmenovány podobně k tomu # define tady. Ale nejsou to samé. Kapitalizace záleží. Pokud se podíváte na to, co se zde děje, prohlašujeme naše int pole, které jsme jen čísla. Dali jsme to na naši velikost, která odpovídá našemu # definovat až na vrcholu. Bude to být 8. A pak, když jsme se pak zavolat na naši funkci vyhledávání dole, jsme se projít v počtu chceme hledat, které jsme vyzváni, dostal od uživatele. Míjíme v poli, tento čísla, a pak také musíme projít ve velikosti pole, a pak je hodnota velikosti 8 je uložena nebo předány k této celočíselné proměnné nazvané velikosti. Máme velikost pole. Nyní, když se vrátíme k tomu, co mluvili dříve, Myslím, že Missy vychován myšlenku, že to, co jsme potřebovali udělat, je dostat délku pole a rozdělit ji 2, a že nám dá polovinu. Pojďme se podívat,. Mohu mít někdo napsat, a uložte jej ve svém vesmíru? Jak o Leila? Mohu mít píšete to v? Napište první řádek, kde budete mít délku pole a získat polovinu a uložit jej do nové proměnné. Dám vám pár sekund. Jste připraveni? [Student neslyšitelný] Jistě, mohl jsem tě vypočítat střed z haystack pole uvnitř vyhledávací funkce pomocí délku haystack pole, což je velikost variabilní? Nic složité tady. [Leila] Jen velikost / 2 a just- A uložit jej, a udeřil na tlačítko Uložit tady nahoře, a my vytáhněte ji. Perfect. Tam jdeme. Awesome. Jak je, že se to sestavit? [Leila] No, to musí být vyšší. [Nate] Jo, tak co budeme dělat? [Leila] Jako int střed, nebo tak něco. Awesome. Jo, pojďme to udělat, int midpoint = velikost. Bude to sestavit? Pojďme smazat tento komentář a dostat ji z cesty. Co se to zkompilovat o tom? Neděláme nic s integer, takže musíme ji vytisknout, nebo něco takového. Jo, přesně tak. Dostaneme nepoužívané proměnné. Co jiného se nebude pracovat o to? Myslím, že jsi říkal něco, Sam. Středníky. Jo, jsem tu chybí ty středníky. Je to bude konstantní věc v celém průběhu funkčního období. Poslední věc udělám je, že jsem si dal nějaký bílý prostor na obou stranách tohoto operátora zde, protože to je obvykle, jak to děláme podle našeho stylu průvodce. Máme polovinu našeho pole. Nyní, když si vzpomeneme zpět do našeho algoritmu, co byl druhý krok, který jsme museli dělat, když máme střed? [Student] Pokud to je větší [neslyšitelné]. Jo, takže musíme udělat nějaký srovnání, a to, co jsme porovnáním tady? Říkal jste, že pokud je větší než. Co je v této větě na mysli? Počet, že přijde, pokud je to větší než středu, pak se do pole? Přesně tak, číslo, které přichází, když jsme- Jehla, takže jsme ve srovnání s jehlou, a co jsme porovnáním proti jehly? Vzhledem k tomu, jehla je to, co jsme hledali. Jsme srovnání se dostat do středu. Ale to smysl zkontrolovat, Pokud needle = střed? Dává to smysl? Má někdo nesouhlasí? Pojďme to zkusit, pokud (jehla == střed). [Student] Líbí printf jste ji našli. [Nate] printf ("Našli jsme ji \ n!"); Jinak-Jdu začít dělat něco jiného tady. Chystám se začít dávat rovnátka kolem if celou dobu jen proto, že když přidáme další věci, pak nemáme se kompilátory. Jo, Sam. Máš pravdu. Problém je, že střed představuje pozici v poli, ale můžete dostat která představuje hodnotu v této poloze v poli. To je skvělé místo. Bylo všichni slyšeli, co řekl Sam? On říkal, že střed, jak je představuje jen místo v poli, ale není to skutečný prvek pole. Pokud si myslíte, že informace o kódu, jako písemné teď, Podíváme-li se na tomto poli se sem, který má 8 elementy v tom, co je hodnota střed bude v této funkci? [Student] 4. [Nate] 4. Podíváme-li se na čísla 4 - a my můžeme jen spustit tento kód a dát trochu smutný obličej v tu protože jsme nenašli to, když narazíme tento kód jak je teď, nahrát, stavebniny, dovolte mi, abych přejděte dolů, a když se podíváme na čísla 4, jsme ho našli, ale my jsme nedostali to printf ano. Jedním z důvodů je to, že jsme neměli vrátit true, ale jsme opravdu najít číslo 4? A Sam se říkat ne. Co jsme zjistili? Jsme opravdu našli střed, který, pokud se díváme na pole tady dole, to bude prvek na indexu 4, že se díváme na, která je 23. Jak se vlastně dostat, že prvek ve středu a ne jen střed sám? [Student] Rádi bychom zadat char, nebo tak něco? Co by to bylo, jen ze zvědavosti? Můžete upřesnit, trochu víc? Musíte změnit pozici v počtu, takže musíš dělat některé připojení Myslím, že je to char, ale to nemusí být. Jo, to je dobrá připomínka. Dělali jsme hodně tohoto konvertujícího pozic do znaků, tyto znaky, v prvních dvou problémových souborů. Ukazuje se, že zde je to téměř podobné přístup k Ith znak v řetězci, pokud to dává smysl. Zde chceme získat přístup k midpoint prvek. Jak to uděláme? Kevin, máte nějaké návrhy, jak bychom mohli udělat, že? Dalo by se to kupka sena, otevřený držák, střední, uzavřená držák. Můžete napsat, že pro nás? Uložte ho tady, a my vytáhnout, že až. Díváme se na tomto řádku 9, a my jsme si uvědomili, že nechceme srovnávat jehlu do středu, ale místo toho, chceme porovnat jehlu k prvku v poloze středu v naší haystack pole. Cool. Tam jdeme. Jo, to vypadá docela dobře, pokud (jehla == haystack [midpoint]). Našli jsme ho. Nyní, když jsme se spustit kód-Dáme zpět do trochu- sestavuje, běží, a teď když se podíváme na 4, nenašli jsme ho, protože teď jsme vlastně stále číslo 23. Jsme získání hodnoty 23, a to je to, co jsme v porovnání s naší jehly. Ale to je dobře. To je krok správným směrem. To je to, co se snažíme dělat. Nesnažíme porovnání jehlu proti pozic v poli ale proti skutečných prvků v poli. Podíváme-li se zpět hned na další krok v našem algoritmu, jaký je další krok? Leila již zmínil krátce. [Student] Zkontrolujte, zda je to větší nebo menší než a pak se rozhodnout, jakým způsobem se pohybovat. [Nate] Jo, to by tak jak to uděláme? Můžete dát do nějaké-Já zachránit tuto revizi, a pak, když dáte v některých linek, které budou dělat, že. Jo, Charlotte. >> Mám dotaz. Neměl by to být střed - 1, protože první věc, kterou je je to 0 indexovány, takže když dáme 4, že to není ve skutečnosti charakter jsme hledali? Ano, a další problém s tím je- to je skvělý úlovek, protože to, co se chystá skončit se děje možná pokud budeme dál a my už nikdy nastavit původně? Myslím, že to, co bychom mohli skončit dělat se pokouší získat přístup prvek na 8. pozici pole, který je v tomto případě neexistuje. Budeme chtít udělat nějaké účetnictví za to, že máme nějakou nulovou indexování. [Charlotte] Omlouvám se, myslel jsem polovinu - 1 v hranatých závorkách. Můžeme to udělat, že. Vrátíme se k této otázce v jen trochu. Jakmile začneme se dostat do skutečné smyčky, to je, když budeme opravdu vidět vstupují do hry. V současné době, můžeme to udělat, ale ty jsi naprostou pravdu. To nula indexování bude mít vliv, že musíme činit. Pojďme se podívat,. Jak je větší než a menší než-? [Student] jsem si, jak to udělat větší než a menší než druhé. Jen jsem si nebyl jistý, co tisknout, pokud zjistíte, že je to méně než haystack středu nebo větší než. Zde mohu zachránit, co I've- [Nate] Jo, pokud si zachránit to, co máte, a my vytáhněte ji. Tam jdeme. [Student] A dal jsem otazníky, co jsem nevěděl. [Nate] To vypadá skvěle. Zde máme otazníky, protože stále nevíme co budeme dělat docela ještě. Co bychom chtěli dělat, pardon, máme nějaké závorky všichni funky na nás. Budeme opravit tyto rovnátka. Tam jdeme. A tak to, co chceme dělat, podle našeho algoritmu, pokud nebudeme najít jehlu? Řekněme, že v případě, že jehla je menší než to, co jsme při pohledu na. Kevin. Jen se podívat na levé polovině. Dobře, takže budeme dát komentář zde říká "podívej se na levé polovině." A v případě, že jehla je větší než kupce sena na středu, co chceme dělat? [Student] Pak se podíváte na pravé polovině. Podívejte se na pravé polovině, "podívej se na pravé poloviny." Není tak špatný. Dobře, takže v tomto bodě, co se hledá docela dobře. Problém s kódem psaným je to, co? [Student] Nemáte koncové body pro polovin. Dobře, nemáme koncové body pro polovin. Také jsme se jen jít přes to jednou. Jsme teprve ve chvíli, se podívat na jeden střed. Buď prvek je tam, nebo to není. V zájmu dokončení tohoto, budeme muset udělat nějaké opakování. Musíme neustále opakují, dokud nezjistíme, že buď element je tam proto, že jsme zúžil a nakonec zjistil, že je, nebo je to tam není, protože jsme se podíval přes všechny věci, v příslušných polovin pole a zjistil, že nic je tam. Kdykoliv jsme dostali toto opakování děje, co budeme používat? [Student] smyčka. Nějaký smyčky. Ano. [Student] Můžeme udělat do-while, a mít to dělat, a pak při jehla není rovno-nejsem jistý, kde jsem šel s tím. Ale něco jako to, že tak dlouho, jak to dělá ne stejná hodnota, kterou uživatel vstup. Jo, tak se pojďme podívat, jak to může psát sám? Říkal jsi, že jdeme použít do-while. Kde se to začalo? [Student] Hned po velikost / 2. [Nate] Dobře, a co budeme dělat? Budeme vyplnit chvíli později. Co budeme dělat? [Student] Copak chceme dělat všechny ty věci, které máme v případě části? [Nate] Do všechny ty věci, skvělé. Kopírování a vkládání. Oh, člověče. Uvidíme, jestli to funguje, jestli to půjde karta to znovu. Krásné. Dobře, a šetříme to tak vy si to. Dobře, a my se chystáme udělat to při- to, co bylo, když podmínka, že jsi po? [Student] Zatímco se jehla není rovno, tak jako vykřičník. Ale nejsem si jistý, co přesně to je ještě. [Nate] Jo, to je jeden způsob, jak to udělat. Sam, máte napsat komentář? [Sam] jsem si vzpomněl, když jsem se podívala na videa, Vzal jsem si screenshot z jednoho z-jako když jsme dělali pseudokódu pro to, tam byl nějaký vztah mezi max. a min. Myslím, že to bylo něco jako když max je stále méně než min. Mám to. [Sam] Nebo jako když max není menší než min nebo něco takového, protože to by znamenalo, že jste hledali všechno. Jo, tak co to znít jako max a min byly na mysli? [Sam] Hodnoty že-celá čísla, které se chystáte změnit vzhledem k místu, kde jsme dali polovinu. Přesně tak. [Sam] V tomto bodě, bude to [neslyšitelné] výpočet max. a min. Střed je to max a min nápad. Dává to smysl, aby lidi? Pokud bychom měli začít uvažovat o tom, jak budeme dělat tuto iteraci, máš naprostou pravdu, že chceme použít nějaký do-while. Ale myslím, že pokud bychom si vzpomenout, co se děje na místě tohoto pole a co se vlastně děje, já se chystám napsat sem- při prvním opakování binárního vyhledávání, máme- Budu používat B a E k označení začátku. A pak konec našeho pole. Víme, že začátek je na 4 támhle, a víme, že konec je na 108. Řekněme, že hledáte pro číslo 15. Poprvé jsme to, jak jsme viděli dříve, střed je buď bude 16 nebo 23 v závislosti na tom, jak vypočítat věci. Vzhledem k tomu, rovnoměrně rozdělit v polovině by nám tento prostor mezi 16 a 23, nemůžeme rovnoměrně rozdělit nebo rozdělit a dostat na pravé středu. My se podíváme na 16. Budeme si uvědomit, "Hey, 16> 15, které jsme hledali." Poté pohled na levé polovině pole co skončíme dělá, je odhazovat celý tento horní část a řekl: "Dobrá, nyní naše koncový bod bude tady." Další iterace našeho smyčky, jsme nyní podíváme na tomto poli, efektivně, co jste vyloučili tuto část, protože teď pokud budeme brát polovinu být rozdíl mezi začátkem a koncem, najdeme naše střed na 8, které pak můžeme otestovat 8 vidět, kde je ve vztahu k počtu jsme hledali, 15, zjistíme, že 15 je větší, takže se musíme přesunout do pravé části seznamu, které známe, protože jsme lidé, a my můžeme vidět to. Víme, že pravá část bude tam, kde jsme ho najít, ale počítač neví, že, takže to, co budeme dělat, je my budeme skutečně se to jít nahoru, a teď na začátku a na konci jsou stejné místo, takže střed stává jediným číslo v seznamu v tomto bodě, který je o 15, a našli jsme ho. Znamená to, že vrhnout nějaké světlo na tom, kde to celé max a min zápis se děje, sledování koncových bodů pole, aby se zjistit jak zúžit věci dolů? Co by se stalo, kdyby to nebylo rovno 15 teď? Co když jsme hledali 15, a místo toho, toto číslo bylo také 16? Rádi bychom říci: "Ach, to je větší. Chceme se vrátit k levé. " A my bychom přesunout náš e doprava, na kterém místě máme koncový bod, který by byl konfliktní. To by nebylo možné vyhledávat pro všechny více prvků protože teď máme koncový bod a naše počáteční bod, naše max a naše min, jsou nyní převrácený. Hledáme přes celé pole. Nemůžeme nic najít. To je bod, ve kterém bychom chtěli říci, "Dobře, budeme zastavit tento algoritmus. Nenašli jsme nic. My víme, že to tu není. " Jak se to děje? [Student] Jak přesně počítač přepne do konce? Jak konec skončit před začátkem? Konec skončí před začátkem protože matematiky, že budeme dělat pokaždé, když jsme se to udělat. Způsob, jakým jsme se vyměnit, je, když se podíváte na poprvé jsme udělat swapu kde máme začátek na 4 a konec celou cestu dolů na 108 a naše střed, řekněme, na 16 - Chystám se obnovit tuto zpátky do 15-li hledáme pro 15, věděli jsme, že to, co jsme udělali, když jsme zkontrolovali 16 a viděl, že to bylo větší a chtěl odhodit celou pravou část seznamu, jsme viděli, že to, co jsme chtěli udělat, je přesunout tento e tady. Účinně, dostal e dojatá k jednomu před středem. Podobně, když jsme dělali tuto iteraci algoritmu a střed byl v 8, Zjistili jsme, že 8 <15, a tak jsme chtěli přesunout b jedna minulost středu. Nyní, na začátku a na konci jsou oba společně v tomto 15. Pokud bychom se děje se podívat na jinou hodnotu, ne 15, nebo je-li to 15 místo toho byl 16, bychom zjistili, že e chceme přesunout jeden před středem. Nyní e by se tam hodil méně než b. Projděme jak jsme vlastně skončili kódování tohoto algoritmu. Víme, že chceme mít tuto midpoint výpočet. Víme také, že chceme sledovat začátek a konec pole z našeho aktuálního pole, takže můžeme zjistit kde tento levá polovina seznamu a kde pravá polovina seznamu je. Děláme, že se buď začíná a končí, nebo můžeme jim říkat min a max. Budu používat začínat a končit tentokrát. Když začneme, podíváme-li se zpět na náš příklad tady dole, náš začátek byl nastaven na samém začátku pole, jako přírodní. Co index to bylo? Co by naše začít být? Daniel. [Daniel] Haystack [0]. [Nate] Jo, takže jsme mohli nastavit rovná kupce sena [0]. Problém však je, že tento nám není pozici prvního prvku. To nám dává index prvního prvku nebo skutečnou hodnotou v této první pozici. [Student] To bude konvertovat k 0,20? [Nate] Co to bude dělat, je-dobře, nebude to dělat žádné konverze. Co to bude dělat, je to uloží 4 v zahájení, a pak to bude velmi těžké provést srovnání proti zahájení protože begin uspořádá hodnotu 4, která je na začátku našeho pole, ale chceme sledovat indexy v poli oproti hodnotám. Budeme vlastně používat 0, takhle. Pro ukončení pole-Charlotte přinesla to až o něco dříve. To je místo, kde se budeme brát v úvahu nulovou indexování. Charlotte, co je konec pole? Co je index na konci? [Charlotte] Velikost - 1. Jo, a jakou velikost bychom měli používat? Měli bychom použít kapitálu velikosti nebo malými písmeny velikost? Capital velikost. V tomto případě může být použití kapitálové velikosti. Pokud bychom chtěli tuto funkci je přenosný a používejte tuto funkci v jiných programech, můžeme skutečně využít malá písmena velikosti. Je to taky v pohodě. Ale Charlotte je naprosto správné, že chceme mít velikost - 1. V tomto bodě, [Student] Jak je to, že můžete použít velká velikost? Jak je možné, že bychom mohli použít velká velikost? Ukazuje se, že tyto # definuje jsou opravdu, pod kapotou, text jako najít a nahradit, pokud to dává smysl. Při kompilaci kódu, předzpracování fáze překladače prochází souboru, a vypadá to všude možně, že jste napsali kapitálu velikosti, a nahrazuje tento text doslova s ​​8, stejně jako to. V tomto smyslu je velmi odlišné od proměnné. Neznamená to však trvat nějaké místo v paměti. Je to jednoduchý textový nahradit trik. V tomto případě, budeme používat velikost. Odtud jsme chceš dělat nějaké opakování, a my jsme na správné cestě s naší do-while. Chceme udělat něco, dokud podmínka neplatí už, a jak jsme viděli dříve, viděli jsme, že tato podmínka byl opravdu, že nechceme konec být menší než začne. To je naše zastavení stav. Pokud k tomu dojde, chceme zastavit a prohlásit jako, "Hele, my jsme nic nenašli." Chcete-li vyjádřit to, my chceme použít nějaký smyčky. V tomto případě, že by bylo do-while, pro smyčky, zatímco smyčka? Máme do-while zde. Líbí se vám kluci líbí tohoto přístupu? Myslíte si, že bychom měli zkusit jiný přístup? Kevin, nějaké myšlenky? Mohli bychom mít while, protože víme, že maximální by byly vyšší než min na začátku tak jako tak. Jo, takže to není inicializace, která se musí stát. Tyto do-while smyčky jsou skvělé, když máte inicializovat předtím zkoušení, vzhledem k tomu, zde víme, že nebudeme mít reinitializing jak začít a skončit každé kolo ze smyčky. Víme, že chceme inicializovat, pak navštivte naše podmínky. V tomto případě, to jsem vlastně jít s jednoduchým smyčce while. Ukazuje se, že do-while smyčky jsou používány docela zřídka. Mnoho míst ani učit se while. Jsou dobré pro zpracování vstupů uživatele, takže jsme viděli mnoho z nich tak daleko. Ale normální a while jsou mnohem častější. Ukazuje se, že tato podmínka, jak jsou psány nebude opravdu nám moc dobře, a proč je to? Je mi líto, já nevím, jak se jmenuješ. Jsem Jerry. >> Líto? Je to B-O-R-U-I. Oh, dobře. Nevidím tě na mém seznamu. Oh, je to proto, že-oh, to dává smysl. Máte představu o tom, proč tato while nemusí fungovat, jak bylo zamýšleno, jak je napsáno s podmínkou? [Jerry] Myslíš jako chcete všechny ty věci po něm do-? Jo, takže to je jedna. Mohli bychom dát všechny tyto věci do smyčky while, což je naprosto pravdivé. Další věc, která je trochu problematičtější, i když, je to, že tato podmínka nebude fungovat. [Student] Musíte odhodit. Správně, takže tato podmínka nebude nikdy platit zpočátku jak jsme o tom mluvili. Chceme udělat něco do konce > Plus začít? [Student] Na konci. Vzhledem k tomu, je to jen počítá polovina délky. Musíte přidat začít. [Nate] Co by to spočítat pro nás? Budeme-li uvažovat o konci této úplně první iteraci smyčky, end bude v poloze indexu 7. Začněte v pozici 0. Pamatujte si, že my hledáme buď pozice 3 nebo 4 pozici. Podíváme-li se na tento matematice, jen aby to trochu víc konkrétní, dát nějaká čísla tady, máme 7, 0, tak 7-0, a pak / 2 je 3 v celé číslo, které je. Pak si musíme pak přidat zpět naše začít? Nevíme v tomto případě. Na prvním iteraci, bude to v pořádku, protože end je 0. Ale jak jsme pokrok, děláme opravdu všechno stačí end - začít / 2. Je tu ještě jedna Trik je zde, a to je právě jedna z priorit. [Student] Potřebujeme závorky? [Nate] Přesně tak, a to proto, že pokud se nám nepodaří dát tyto závorky, pak tato linka bude vykládat místo jako (konec) - (začátek / 2), který se rozhodně nechceme. Dejte si pozor na ty pravidla přednost. [Student] Proč není konec + začít? Proč není konec + začít? [Student] Proč je to tak, že? Proč by to bylo +? Myslím, že máš pravdu. [Student] Vzhledem k tomu, že je to průměr? [Nate] End + zahájení, máš naprostou pravdu. Wow, jsem totálně podělal. Máš pravdu. Pokud bychom dělali minus, bychom chtěli přidat začít znovu přihlásit V tomto případě jste velmi správné, že chceme, aby se průměr dvou, tak jsme si chceš přidat, jak protichůdný k odečíst je. [Student] To by také fungovat, pokud jste konec - začít / 2 + začít. To by, kdyby se do-myslím, že ano. Například, pokud jsme se dívali na začátek, a my posunul ho sem na 15. Nyní můžete začít na pozici 2. Konec je na pozici 7. Pokud odečteme je, dostaneme 5. Rozdělte že 2, dostaneme 2. A pak přidáme 2 zpět, a že nás dostane na 4. pozici, která je právě zde, což je na střed. [Student] Líbí se musíme postarat o balení? V jakém smyslu se musíme postarat o balení? Pokud součet nebo rozdíl mezi v závislosti na tom, jak to udělat, je to sudé číslo. Pak počítač dostane zmatený, zda-li je to 2,5; se přesunete vlevo nebo vpravo určit, které je na střed? Mám to. Ukazuje se, že s celočíselném dělení, nemáme vůbec dostat tyto plovoucí desetinnou čárkou čísla. Nikdy jsme se desetinu. Je to úplně zlikvidovat. Pokud máte počítač dělení dvou int proměnné, a jeden je 7, a druhý je 2, nezískáte 3,5 jako výsledek. Bude se 3. Zbytek budou zahozeny, tak je to skutečně zaokrouhlení není kolo, ale podlaha, pokud jste obeznámeni s tím v matematice, kde jste úplně zbavit desetinné, a tak jste v podstatě zkracovat ji dolů na nejbližší Vcelku pozice, na nejbližší celé číslo. [Student] Ale pak je to problematické, protože pokud máte pole 7 prvků pak to automaticky bere třetí prvek z středu místo 4.. Jak se s tím vypořádat? Je to problematické, protože pokud jsme měli řadu 7, to by si vybral třetí místo 4.. Mohl byste vysvětlit trochu víc? [Student] Protože pokud máte 7 prvků pak 4. prvek by být středem, ne? Nezapomeňte svůj komentář o tom, že nula indexovány, ačkoli. [Student] Jo, tak v poloze 3. To by bylo na střed. Jo. Oh, dobře. Chápu, co máte na mysli. Je to trochu divné, jak jsme si zvyknout na celé této představě jak se zbavit desetinných míst. To je skvělé místo. Pojďme dokončit tuto nahoru. Jsme počítá náš střed. Testujeme, zda naše jehla se rovná střední hodnotě. Jsme tisk, že jsme ho našli, ale opravdu, co chceme dělat v této situaci? Našli jsme to, a tak chceme, aby volající, že jsme ho našli. Máme funkci, která je boolean zadaný funkce. Jak jsme signál k volajícímu naší funkce, která jsme připraveni jít je řekneme, "Hele, to je pravda." Jak bychom to dělali, Kevine? Jste kývl hlavou. >> [Kevin] Přidat return true. [Nate] Přesně tak, vrátí true. Nyní, pokud to není stejné, jak by se podíváme na levé polovině? Nějaké nápady? Stella, nějaké nápady? Musíte nastavit novou pozici pro konec. Jo. Takže musíme udělat pozice středu - konec. Great. Musíme nastavit novou pozici na konci podívat se na levé polovině. To bylo to, co jsme o tom mluvili před, kde Pořád se vrací k tomuto příkladu. Jsem začít tady, a pak jsem se nakonec všichni cestu přes tu. Opět platí, že pokud jsme hledali 15, a náš střed je 16, a my si uvědomit, "Oops, 16 je větší. Chceme přesunout na levou polovinu. " Pak bychom přesunout konec 15, a my, že tím, že jeden od středu a nastavení, které jako náš nový konci. Podobně, pokud se chcete podívat na pravou polovinu, jak by to dělali? Máte nějaký nápad? [Student] Stačí nastavit začít midpoint + 1. [Nate] Great. A nyní v případě, že jsme nic nenajdeme, to, že se postaral o pro nás? Daniel, to, že si postaráno o nás? [Daniel] č. [Nate] Pokud bychom dělat to přes celé pole a my nic nenajdeme, kde by to být postaráno, nebo bychom měli postarat se o to? [Daniel], zatímco podmínka. [Nate] Jo, a zároveň podmínka, přesně. To se bude starat o prochází celé pole, pokud nenajdeme nic. Tento cyklus while skončí. Nikdy nebudeme se setkali tuto podmínku, a můžeme se vrátit false. Můžeme také nechat tuto možnost, pokud tady takhle protože pokud tuto možnost, pokud tvrzení je pravdivé, a naše funkce vrátí, a tak budeme podstatě přeruší tato funkce v tomto bodě když se vrátíme true. Ale co se stane s touto strukturou tady? Bude to fungovat úplně, nebo je tam nějaký logický chyba tam? Tam je nějaký logický chyba tam, s tím, jak to nastavit. Co by mohlo být? [Student] Proč potřebujete - a + 1s? , Která stanovuje naší nabídku tak, aby byly naše nová levá polovina a pravá polovina. [Student] Ale proč by nemohla to udělat, aniž by - 1s a + 1s? [Nate] Dalo by se nastavit rovná středu? Co by mohlo být problematické, že? [Student] Myslím, že je to neefektivní, protože máte kontrolu hodnotu, která je již zkontrolovat. [Nate] Přesně tak, Sam je úplně pravdu. Pokud se nastavit konec a začne se rovná středu místo - 1 a + 1 zamyšleně, v určitém okamžiku v budoucnosti budeme nakonec kontrolu střed znovu. [Student] Začal jsem PSet, a pak jsem měl něco takového kde jsem zapomněl + 1, a to uvízl v nekonečné smyčce. Jasně, protože v určitém okamžiku budete nikdy dostat začít a skončit skutečně překrývají. Cool. Je tu ještě jedna logická chyba, a to je, že by to mělo být určitě else if. Proč by to mohlo být? Důvodem je, pokud to není jinak, pokud-jsi viděl, Kevin? [Kevin] Jo, protože měníte koncový bod. [Nate] Přesně tak. Měníme koncový bod, a pokud je to napsáno takto-Dáme aby mezery mezi- bude kontrolovat tento případ. Tento případ, pokud se podaří, zmizí, z funkce. Pak to bude kontrolovat tuto další případ, a je-li to podaří, upraví na koncový bod, a pak to bude pokračovat a zjistit tento případ. Ale v tomto bodě, nechceme, aby i nadále kontrolu. Naštěstí, jsme se obnovit polovinu tady, a víme, že tento případ nebude úspěšná. Ale my určitě chceme dát else, pokud tam i přesto, že by mohl v tomto případě protože nejsme nastavení středového bodu, by to dělat rozdíl? Ne, protože tyto případy jsou exkluzivní. Opět, můj špatný. Nechceme, myslím, je třeba tuto else if. Můžeme to zkusit a spustit jej a uvidíte, co se stane. Budova, došlo k chybě. Je to pravděpodobně proto, že jsem opustil to b je a ŽP tady. Mám víc těch, kteří se na vrcholu? To nevypadá to. My oddálit, vybudovat, tam to jde, takže teď, když hledáme 15, Ano. Dovolte mi, abych Zoom 15, ano. Můžeme spustit znovu. Nahrání zdrojový kód, stavební, běh. Můžeme hledat něco jako 13, a nemáme dostat něco vytisknout, tak to není zjištění, že pro nás. To je skvělé, protože to není v našem seznamu. Jsme nyní opožděně. To bude mít to pro tento týden. Díky za vstup, a uvidíme se později. [CS50.TV]