JASON Hirschhorn: Welcome do troch týždňov, všetci. Máme plné ruky práce, ale vzrušujúce časť pred nami. Takže prvý, pretože sme urobili niektoré Angličtina s kurzom, ale stále majú veľa učenia zostáva urobiť, som ukážem vy nejaké zdroje , Ktorá by mala ukázať, že je neuveriteľne užitočné, pretože vám nielen priblížiť svoj problém sady, ale aj stráviť všetky Materiál sme vám chalani v prednášky a šortky a časť. Potom budeme tráviť prvý 20 do 25 minút po časť deja cez GDB, ktoré môže alebo nemusí mať použitý v tomto mieste, ale je to neuveriteľne užitočný nástroj, ktorý bude pomôže ladenie programov. Mnoho z vás mohol použiť printf v uprostred svojho programu prísť čo premennú rovnal. GDB je ešte lepší ako printf a nie je skrutka svoj kód, pretože tí spustiť na spustiteľný súbor. Tak pôjdeme cez 10 najviac užitočné príkazy, ktoré potrebujete pre GDB, a my sme ísť na cvičenie spoločne, aby v probléme nastaviť tri a mimo nej, môžete GDB možno používať na ladenie pomoc vaše programy. A konečne, budeme ísť cez niektoré triedenie a vyhľadávanie algoritmy ktoré ste videli v prednáške, a my sme bude vlastne kód, a to nielen pseudokódu, ale kód binárne vyhľadávanie, bublina triedenie a výber triediť. Tak za prvé, ja chcem ísť nad zdrojmi. Ide o rozsiahly zoznam, a je to menšie písmo, pretože som mal veľa vojde na tu. Ale to vám pomôže nielen, znova, s problémovými sád a trávenie informácie, ktoré ste sa naučili, ale určite, no kvíz čas, budú tieto byť nesmierne užitočná. Takže najprv konštatuje, prednáška. Ak pôjdete do cs50.net/lectures a prejdite na konkrétny týždeň a deň, uvidíte, že tam sú poznámky pre každý prednáška, ktorá nie je len Prepis, ale Upravená verzia čo bola pokrytá v prednáške s kódom úryvky a ďalšie užitočné kúsky. Vrelo odporúčam ísť cez tie. A potom tiež, že je zdrojový kód k dispozícii od každej prednáške. A opäť, bude tiež táto šmykľavky k dispozícii on-line na cs50.net/sections dnes večer. Takže druhá sú šortky každý týždeň, že Kryt tém, zvyčajne 5 až 15 minút na dĺžku. A tí, dúfajme, že sa vám veľký náter na rôzne témy. Tretia - a to je zbrusu nový táto rok - je study.cs50.net. Ak ste si to overil, som Dôrazne odporúčame, aby si to. Môžete si vybrať tému. Máme desiatky tém tam. Tak napríklad, si vyberiete funkcií. To vám dáva nejaké diapozitívy a berie na vedomie, na funkciách. Tí, ktorí sú v skutočnosti diapozitívy, že TFS sa odporúča používať pri našej prezentácie v oddiele. K dispozícii je tiež tipy a triky pre prácu s funkciami, a tam je Problémy praxe, ktoré pomáhajú budete pracovať s funkciami. Tiež vám odkazy na krátky na funkcie a časy, ktoré funguje prišli v prednáške. Takže study.cs50.net, zbrusu nový táto rok, fantastický zdroj. Ďalej mám muža, ktorý je manuálne príkaz, ktorý môžete spustiť na príkazového riadku. Takže ak máte akékoľvek otázky týkajúce sa príkaz, napríklad, Rand, ktoré sa stretol minulý týždeň v oddiele a vy ste pravdepodobne narazili na váš problém nastaviť, keď prechádza generovanie kódu, ale ak ste typ muža rand, dostanete na stránku, ktorá vám povie všetko o rand. To vám dáva to, čo to znamená, Parametre to trvá, rovnako ako návrat Druh a stručný popis tejto funkcie. Tak pozrite sa rand. To môže byť trochu rozvláčny a mätúce, takže niekedy som zistil, že jednoducho Googling to, čo chcem vedieť, je Najlepší spôsob, ako nájsť odpoveď. Takže cvičiť s firmou Google. Získať dobrý Google. To sa stane vaším najlepším priateľom. Rovnako ako Google, ak nemôžete nájsť na Google, cs50.net/discuss, je to diskusné fórum. Šance sú, ak máte nejakú otázku, kto Vašich 700 + rovesníkmi tiež, že Otázka a môže sa spýtal to už v diskusii fóra a boli to odpovedal. Takže ak máte všeobecný dotaz alebo Máte otázku, na ktorú si myslíte, že Možno, že ostatní ľudia mohli naraziť, pozrite sa na cs50.net/discuss. Konečne, posledné dva, ak chcete hovoriť o skutočnej ľudskej bytosti, v kancelárii hodín od pondelka do piatku. K dispozícii je tiež on-line úradné hodiny pre rozšírenie študentov. A posledná, ale určite nie najmenej, me, výkričník. Tie majú svoju kontaktné informácie. Ak budete niečo potrebovať, prosím, nikdy neváhajte ma kontaktovať. Vždy, neváhajte tak urobiť. Len veľmi málo z vás, ktorí ma majú na Gchat, tak, aby bolo sklamaním, ale dúfajme, že bude meniť medzi Tento a ďalšie časť. Akékoľvek otázky tak ďaleko na zdroje? Skvelé. A konečne, ďalšie konektor pre spätná väzba, sayat.me/cs50. Môžete mi dať anonymný spätnú väzbu o tom, ako robím. To bolo naozaj užitočné minulý týždeň. Dostal som pár komentárov od vás hneď po časť, a od ostatní študenti, ktorí ho sledovali, v priebehu týždňa, a to bola nesmierne užitočná. Budem sa snažiť a obmedziť svoju použitie slovo "sladké", ale ja vám ukážem môj nadšenie a vzrušenie iným spôsobom. Ale boli tam ďalší ďalší vecné spätnej väzby, ako plusy a delta. Takže, prosím, dám vy spätnú väzbu na vašich problémov sád. Neváhajte a dajte mi spätnú väzbu na mojom učenie. Som tu pre vás. Skvelé. To je všetko, čo mám na prvá časť. Má niekto nejaké otázky tak ďaleko? A mám poznámku k riadiace stredisko. Predlžovací študenti ma messaged hovorí, že nedostávajú žiadny zvuk, ale to je z mojej moci opraviť. Takže dúfajme, že dostane vyriešený krátko. Ak sledujete on-line, hi, ale môžete ma počuť. Takže najprv sa budeme prejsť GDB. GDB, ako som naznačil vyššie, je ladiaci nástroj oveľa lepšie ako printf. Takže, ako začať s GDB, vás, ak Ak chcete otvoriť svoj prístroj a mať súbor, ktorý som zaslané e-mailom na vás skôr - tento súbor bude tiež k dispozícii on-line na chvíľu - a spustite GDB. / názov súboru. Po prvé, samozrejme, budete musieť kompilovať súbor, pretože GDB možno použiť len na spustiteľné súbory. Ale ak ste niekedy chceli spustiť GDB, prvá vec, ktorú urobíte, spustenie GDB. / Caesara. Tak to je názov programu sme ísť s ním hneď. Takže budem písať, aby Caesara, ktorý bude mi spustiteľný súbor tu zvýraznené zelene. A potom budem spúšťať GDB. / Cesar. A tam idete. Vidíte, máme nejaký text mi povedať, o verzii GDB, dáva mi niektoré informácie o záruke a potom sme mať dotaz HDP, ktorý vyzerá trochu zo ako náš príkazového riadku riadku, ale vidíte, že je to otvorené paren, GDB, v blízkosti zátvorka. Než budeme pokračovať a ladenie tento obrázok že som poslal k vám všetkým, poďme sa pozrieť na niektoré užitočné príkazy, takže máme pocit, z toho, čo sa deje na krytie. Tieto príkazy sú tu uvedené v Poradie, v ktorom som sa všeobecne používajú je. Takže začnem program beží GBD. / Názov programu, V tomto prípade, Caesar. A potom prvá vec, ktorú urobím 99.9% v čase, keď je typ prestávka na mysli. To stanovuje bod zlomu na hlavnej. V podstate, čo ste tam robil je program, sa nezastaví na Hlavným takže môžete začať skúmať ju linku linkou, skôr než beh všetkých cesta cez. Môžete rozdeliť na rôznych miestach vo váš kód, ale hlavné je všeobecne dobré miesto pre štart. Ďalší príkaz spustiť, je beh. To začína beh programu, a Ak potrebujete zadať príkazový riadok argumenty, môžete to spustiť tento príkaz. Beh s argumentmi. Takže od tej doby sme sa ísť cez verziu C, čo je program, vy písal pre pset dva - tento, samozrejme, má nejaké chyby v tom, že snáď nájdeme - budeme bežať bežať s nejakým príkazom argumenty sú preto Caesar, ako vy viete, na probléme nastaviť spec, má niektoré argumenty príkazového riadku. Ďalší pár príkazov, ďalšie kto je vlastne volal ďalší. Ten, kto sa vám riadok po riadku prostredníctvom svojho programu. Takže biť n a stlačte klávesu Enter vám vezme na ďalší riadok, vykonávanie predchádzajúci riadok. Krok vás zavedie nielen na ďalší riadok, ale sa vám vnútri funkcie. Takže ak ste napísali funkciu Váš kód, alebo ak si budete chcieť prezrieť na i, napríklad, môžete hit s, a skôr než ísť na ďalší riadok súbor, ktorý sa chystáte cez pravé teraz, budete skutočne krok do táto funkcia a vidieť jeho kód. Zoznam ukazuje, vo veľmi užívateľsky prívetivý formát, sa 10 alebo tak linky okolo kde sa práve nachádzate v kóde takže sa môžete skutočne vidieť súbor skôr než by ste museli vymeniť späť a prepínať medzi rôznymi zobrazeniami. Tlač je ako printf, ako jeho názov napovedá. To vám ukáže, čo premenná rovná. Informácie o miestnych je naozaj užitočné. Toto je špeciálna verzia tlače. Informácie o miestni obyvatelia vám ukáže všetky miestne premenné, vytlačí všetky pre vás ktoré sú v súčasnej dobe k dispozícii. Takže všeobecne, skôr než na vytlačiť štyri premenné, ktoré som zvedavý, či som v cykle for, pre Napríklad som len napísať info miestnych obyvateľov, a to sa ma, čo mi počítadlo Ukážem rovná, rovnako ako pole, že som pracovať na sebe rovnými. A konečne, aj naďalej. Zadaním prestávku vám zastaví v bode zlomu. Môžete prejsť linke linka s ďalšou a krok. Pokračovať spustí program pre váš ďalší bod zlomu alebo do ukončenia v prípade, nie sú žiadne ďalšie prestávka bodov. Zakázať odstráni body prerušenia, ak vám rozhodol prestávka na hlavné bolo nevhodné, ktorú chcete nastavte ju niekde inde. A konečne q, prestať, dostane z GDB. Takže tento program,. / Caesar, budeme prezrieť práve teraz a my sa chystáte použiť GDB nájsť chyby v tomto programe. Bežal som tento program skôr sa Skontrolujte, či 50, a mám jeden zamračený pohľad. Všetko to existovalo, je zostavený, je prešiel mnoho skúšok, ale nejaký dôvod, že neprešiel pätinu test, sústruženie BARFOO, všetky čiapky, do E-D-U-I-R-R, všetky čiapky, používať tri ako kľúč. Mám celkom blízko. Vystúpil som jedným písmenom. Takže tam je nejaká malá chyba tu. Díval som sa cez môj kód. Nemohol som na to prísť. Dúfajme, že vy mi môže pomôcť zistiť, čo táto chyba je. Tak to je chyba, že sme vyhľadávanie. Poďme do GDB. Opäť som bežať GDB. / Caesar, takže teraz sme v GDB. A čo je prvá čo mám robiť? Práve som vstúpil GDB. Niekto mi dať dobrý príkaz zadať. STUDENT: Prestávka hlavné. JASON Hirschhorn: Prestávka hlavné. Fantastic. Poďme typ, ktorý palcov Vy môžete sledovať tu alebo sledovať so sebou na svojich počítačoch. Prestávka hlavné, a uvidíte, bod zlomu bol nastavený na - to mi dáva nejaký divný adresu v pamäti, a to mi tiež dáva číslo riadku. Keby som sa obzrieť na tomto súbore, Ja by som si uvedomiť, že hlavným stalo na riadku 21. Čo by som mal bežať ďalej? Je môj program beží? Nie. Takže to, čo by som mal bežať ďalej? STUDENT: Spustiť. JASON Hirschhorn: Spustiť. Mal by som len spustiť beh, alebo by Aj pridať nejaké ďalšie veci? STUDENT: Beh s argumentom. JASON Hirschhorn: Beh s príkaz argumenty. A pretože som ladenie veľmi špecifické prípad, mám zadať, že argument riadok príkaz. Tak som si to spustiť tri, čo je, opäť, Výstup som dostal od Odchod 50. Spustenie programu. Ideme cez niekoľko riadkov. Teraz budete vidieť, že sme na riadku 21. Ako mám vedieť, že sme na riadku 21? Pretože keď sa pozriete na ľavej strane okná môjho terminálu, tam sa hovorí, že riadok 21. A to mi dáva, v skutočnosti, kód, ktorý je na riadku 21. Tak som misspoke skôr. Hlavné je to vlastne na riadku 21. Hlavné je pár riadkov nad 21 rokov. Ale na riadku 21, ktorý je kde sme lámanie. Tento riadok kódu má ešte nie je vykonaný. To je dôležité. Linka vidíte nemá bol vykonaný ešte. To je ďalší riadok kódu sa chystáte vykonať. Takže ďalší riadok, pretože vy ste pravdepodobne oboznámení s, je to kontrolu stavu, či mám zadali argument príkazového riadku. A aby aj to, čo je druhý časť, ktorá robí? Čo je na i? STUDENT: Zmena na celé číslo. JASON Hirschhorn: Je nám ľúto? STUDENT: Je to mení argument celé číslo. JASON Hirschhorn: Tak sa aj mení arg v1 z reťazca na celé číslo. A potom to, čo je to kontrola? STUDENT: Ak je druhý Argument príkazového riadku, stranou od spustenia programu. JASON Hirschhorn: A čo je Druhá polovica tohto Kontrola Logický výraz? Táto časť sem, aby aj? STUDENT: Ak je to negatívne. JASON Hirschhorn: Uistite sa, čo? STUDENT: Uistite sa, že je, v skutočnosti, pozitívne. JASON Hirschhorn: Presne tak. Toto je kontrola, či je to negatívne, a ak je negatívny, som majú pocit na ďalší riadok silu sa mi revať na užívateľa. Takže poďme hit koniec na vykonanie tohto riadku. Nechceme vidieť, že riadok, ktorý vy Možno, že uvidí kričí na používateľ a potom sa vracať, pretože tento riadok nebolo vykonané. Aj vstúpil 3. Tak som robil, v skutočnosti, zadajte dve príkaz argumenty sú, a 3 je väčší ako nula. Takže sme videli, že linka, sme vykonali, ale my sme nemali krokom vnútri if stave. Takže teraz, nabudúce, vidím, že som nastavenie int key rovná sa i arg v1. Tak to je mi vytvoriť premennú kľúč. Takže ak som vytlačiť kľúč práve teraz, pretože , Ktorý vám umožní vidieť hodnota v premennej, kľúč sa rovná 47. To je divné, ale samozrejme, to preto, že nemám vykonané ešte tento riadok. Takže teraz, ak som narazila n, prevedenie tohto riadku, a robiť tlačovú kľúč, kľúč bude rovnať 3, čo je to, čo očakávame, že sa rovnať. Takže znovu, v GDB, riadok, ktorý vidieť doteraz vykonané. Musíte sa trafiť n alebo S alebo číslo ďalších príkazov skutočne vykonanie tohto riadku. Tlač kľúč. Kľúčové je na 3. Tak ďaleko, tak dobrý. String je obyčajný text. Poďme spustiť tento riadok. Začínam reťazec od užívateľa. Poďme sa pozrieť, v mojom Odchod 50, som zadajte BARFOO všetky kryty, takže to je to, čo budem zadávať. Keby som teraz vytlačiť vo formáte obyčajného textu. Uvidíte, že sa rovná reťazec. To mi dáva nejaký iný podivný šestnástkovej číslo, ale to robí v Skutočnosť, že môj reťazec BARFOO. Ak by som chcel vidieť, čo kľúč predstavoval v tento bod, ako by som mohol zistiť kľúč? STUDENT: Print kľúč. JASON Hirschhorn: Print kľúč, presne tak. A v skutočnosti, tam je skratka. Ak ste unavení písanie tlač, môžete zadať p Tak p kľúč robí presne rovnaký vec. A opäť, vidím, že sa rovná 3. Ak som chcel zistiť, čo oba kľúče a BARFOO rovnal zároveň ale bol som unavený z písania každého jeden z jednotlivo, Aj mohol písať info miestnych obyvateľov. To mi dáva kľúčové rovná 3. Obyčajný text sa rovná BARFOO. To tiež dáva mi tieto dve podivné veci na vrchole, je táto premenná i, a táto premenná n Tí, ktorí sú skutočne existujúce vo svojom hlavnom programe. Ešte sme sa s nimi stretli ešte, ale ako náhľad, tí, existujú v mojom cykle for. Takže teraz, že sa rovnajú nejaký divný čísla, pretože neboli inicializovaný ešte, ale oni ešte existujú v pamäti, takže sú to len nastaviť nejaké odpadky hodnotu. Ale my sme to vidieť kľúč obyčajný texte práve tam. Tak idem na vykonanie tohto riadku, riadok 34, pre slučky. Chystáme sa skočiť do pre sláčiky biť n A my sme vnútri slučky for. Sme na našej prvej kontrole. A opäť, to by tak nejako vyzerať poznáte, pretože to bolo Caesar program, ktorý bol napísaný, ale znovu, má nejaké chyby. A teraz keď to urobím info miestnych obyvateľov, pretože som vo vnútri, ktorá pre sláčiky, uvidíte že aj rovná nule, ako sme očakávali. To je to, čo sme ju nastaviť na a inicializovaný že v cykle for. n sa rovná 6.. To tiež dáva zmysel, pretože sme si stanovili je k strlen obyčajného textu. Tak som chcel robiť info miestnych obyvateľov alebo tlač do premennej sa často, aby sa uistil, že všetko je vždy to, čo Očakávam, že sa rovnať. V tomto prípade, všetko je čo som sa očakávať, že sa rovnať. Takže začnime pohybujúce sa to pre sláčiky. Linka Som na je linka 36, ​​ak je prostý Text aj je väčšia ako a prostý text i je menšie alebo rovné Z. Viem, že môj problém nie je s to môj prvý list, je to s druhým písmenom. Ak sa pozrieme späť pri príchode 50, B ide do E pokuty. Beriem na A a na výstupe ako , Nemení to D. Takže niečo, čo je zlé druhý list. Takže budem sa pohybovať tam v sekunde. Ale keď som si chcete skontrolovať, čo prostý Text som robil v tomto konkrétnom prípad, myslím, že by to malo byť, čo? Čo je potrebné obyčajného textu som sa rovnajú v tejto Prvé kolo pomocou slučky for? STUDENT: Zero? JASON Hirschhorn: Obyčajný text Aj? Tak to by malo byť hlavným B. Ja, samozrejme, rovná nule, ale holý text držiak nula uzavretá zátvorka rovná B pretože reťazca, ako sme videli minulý týždeň, sú polia, takže dostávame Prvý znak z toho. Takže ešte raz, keď som vytlačiť obyčajný text Ja, ja, v skutočnosti sa znak B. A to je pekné, že jo? Nemám vlastne mať vo formáte obyčajného textu I. To nie je jedna z premenných I uvedenej alebo inicializácii, ale môžete tlačiť z celej rady vecí ak by ste chceli. Ale poďme prejsť. Ak holý text Aj je väčší ako A a holý text Aj je menšie alebo rovné Z, ktorá je samozrejme pravda, pretože máme kapitál B. idem spustiť nejaký príkaz na to. Videli sme, že matematika minulý týždeň, takže budeme brať ako samozrejmosť, že to funguje právo podľa Kontrola 50. Tieto zložené zátvorky, prvý ukázal, že som sa ukončenie, ak stav, druhý ukázal že som ukončenie cyklu for. A tak teraz, keď som narazila na Next, uvidíme sme späť pri cykle for znova. Ideme cez pre znovu slučky. Poďme vlastne krok do druhej iterácie pre sláčiky a typu Informácie o miestni obyvatelia. Takže sme v druhej iterácii našej pre sláčiky. Ja sa rovná 1, ktoré očakávame. N sa rovná 6, ktorý očakávame. Kľúč sa rovná 3, ktoré očakávame. A obyčajný text, uvidíte, sa rovná EARFOO teraz, nie BARFOO už preto, že V našej predchádzajúcej iterácii, B bol sa zmenil na imaní E. Takže sme o stretnúť problém, takže to je miesto, kde budeme ponoriť do ladenia. Ale má niekto nejaké otázky, o tom, čo sme robili doteraz? Fantastic. Takže sa chystáme spustiť to, či stav, holý text držiak som zavrel Držiak väčšie ako A a holý text Aj menšie ako alebo rovná Z. Ale predtým, než Idem do toho, pretože to je miesto, kde Viem, že moja chyba, chcem upozorniť z obyčajného textu I. A poďme dať vytlačiť von. To robí rovnať znaku A, takže sa zdá byť tak ďaleko, všetko je v poriadku. Tak som sa očakávať, že tento riadok pre moju logiku, táto linka by mala byť pravda. Je to veľké písmeno. Ale keď som narazila n, my si uvedomiť, že tento linka, v skutočnosti nebolo vykonané. Zoskočil som na else if. Prečo sa to stalo? STUDENT: Pretože máte váš stav obyčajného textu je väčšia ako, nie je rovné alebo väčšie ako. JASON Hirschhorn: Tak som mal obyčajný text Aj je väčší ako A, nie je väčšia alebo rovné. Tak jasne, kapitál nie spustiť to, či podmienka, a my sme nie je krok do neho, a my Nie je to potrebné posun. Tak takto to je, v skutočnosti. Som prišiel na svoju chybu. Mohol by som ísť späť do zdrojového súboru, zmeniť a aktualizovať ju a spustiť znova skontrolujte 50. Ale uvidíme, len pre pedagogika je sake, keď som ďalej. Else if nevykoná jeden, ale čo miesto rovná sa príkaz ktoré sa nemenia. Tak to vôbec nezmenila, a keď som vytlačiť obyčajný text tu, uvidíme deje cez to pre slučku nie, v skutočnosti, zmeniť, že druhý znak vôbec. Je to stále kapitál A. Takže znova, budeme ladiť naša chyba. Uvedomili sme si, že to tam bolo niektoré logika chýba. A to ladiť sa dopredu pred skutočného vyhotovenia tohto riadku, ale ty by si všimli, mali sme len hit Ďalšie a prejdete na iný, že v prípade, to znamená, že v prípade, že podmienka Nebola to pravda. Nechceli sme, v skutočnosti, sa výsledok sme očakávali. Takže by sme mohli byť vyzvaní, mal sme neboli tak šikovný, aby sa na , Že v prípade, stavu a skontrolovať, či v skutočnosti, naša podmienka by mala vyhodnotiť na platí v aktuálnom kontexte. To je všetko pre ladenie tohto programu. Má niekto nejaké otázky? Čo príkaz by som mohol zasiahnuť prestať GDB? Q. A potom budem vyzvaný, skončiť rovnako? Áno, alebo nie. Budem hit áno, a ja sa prestal GDB. Tak to bol rýchly náter na GDB. V skutočnosti, v reálnom prípade, Urobil som to v úradných hodinách. GDBed som presne tento program na úradné hodiny sa študent. A keď sa vrátime k príkazom, ktoré sme videli predtým, než sme použili zlomu Main, najprv vec, ktorú sme urobili. Použili sme bežať s argumentmi príkazového riadku, Druhá vec, ktorú sme urobili. Použili sme vedľa veľa sa pohybovať nám prostredníctvom linky. A opäť, krátka verzia budúci n To je v zátvorke šedej farby na snímke. Nepoužili sme krok, ale my nie nevyhnutne potrebné pre tento prípad. Ale my sme ho mohli použiť v trochu neskôr dnes sme Ak ladenie, pre príklad, binárne vyhľadávanie, kedy binárne hľadanie sa nazýva v samostatnej funkcie, ale je tu niektoré chyby s ním. Budeme chcieť vstúpiť do volania na binárne vyhľadávanie a vlastne ladiť. Zoznam by sme nemali používať buď preto, že sme mali dobrý pocit z nášho kódu, ale ak som to chcú, aby si o tom, čo kód Aj bolo okolo, mohol som použiť zoznam. Vytlačiť sme použili, info miestnych obyvateľov, ktoré sme použili. Pokračovať sme nemuseli použiť v tomto prípad, ani to musíme použiť zakázať, ale my sme použitie prestať. Opäť platí, že tieto príkazy 10, prax je. Ak ste pochopili tieto 10 príkazy, mali by ste byť nastavený na ladenie akékoľvek vydať s GDB. Takže sa chystáme ísť ďalej, opäť sa Jadrom časti dnes deje cez Tieto triedenie a vyhľadávanie algoritmy. Než tak urobíme, opäť nejaké otázky, pripomienky, obáv o GDB? Takže sa každý bude používať GDB skôr než printf? Takže všetci, pre perpetuity boží, každý je prikyvovanie hlavou právo teraz, tak som ťa vidieť v úradných hodinách a všetky TFS vás a uvidíte, povedia, ukáž mi, ako používať GDB, a budete sa môcť im ukázať, že jo? Druh? Možno, snáď. V pohode. Takže budeme pohybovať do triedenie a vyhľadávanie. Uvidíte Mám zoznam už je zoradený pre nás, ale to nebude že tomu tak vždy. Takže problém nastaviť špecifikácii pre problém nastaviť tri, máte šortky ktoré môžete sledovať, a to vlastne spýta sa pozerať na tie šortky. Tiež v prednáške minulý týždeň, sme šli cez Mnoho z týchto algoritmov, takže som nebude tráviť čas v triede deje nad týmito algoritmami znovu alebo výkresu fotografie pre ako tieto algoritmy pracujú. Opäť platí, že informácie, môžete re-watch prednáška, alebo že informácie je zachytený výnimočne na kraťasy pre tieto vyhľadávania, všetky ktoré sú k dispozícii na cs50.net. Takže namiesto toho, čo budeme urobiť, je napísať tieto programy. Máme pocit, mentálny model, ako pracujú, a tak to, čo budeme urobiť, je kód je naozaj. Chystáme sa obrátiť, že mentálny model že obraz, ak chcete, do skutočný kód. A ak ste trochu zmätený alebo hmlisté na mentálne modeli, som úplne pochopiť. Nie sme v skutočnosti bude skok na kód rovinke. Takže, keď to výzva v tejto snímke sa pýta ste na kód binárne vyhľadávanie, a v skutočnosti, iteratívny verzia binárne vyhľadávanie, prvá vec, ktorú som Naozaj chcem, aby si ich napísať nejaký pseudokódu. Takže máte túto mentálny model, ako binárne hľadanie práce. Vezmite si list papiera, ak máte jeden ľahko dostupné, alebo otvoriť textový editor, a ja by som všetci písať. Potom sa vykonajú štyri minúty napísať pseudokódu pre binárne vyhľadávanie. Opäť, myslím, že o tom, že mentálny model. Prídem okolo, ak máte otázky a môžeme nakresliť obrázok von. Ale najprv, než začneme programovať, Chcel by som napísať pseudokódu pre binárne vyhľadávanie, takže keď sme sa ponoriť, máme nejaký smer ako tam, kde by sme mali zamieriť. STUDENT: Môžeme predpokladať, že pole hodnoty, dostaneme sa už je zoradený? JASON Hirschhorn: Takže pre binárne vyhľadávanie pracovať - ​​vynikajúca otázku - ste vziať v zoradené pole hodnôt. Takže predpokladám, že to bude fungovať. Vrátime sa k tomuto snímku. Uvidíte vo fialovej funkcii vyhlásenie bool binary_search int hodnota, int hodnoty, int n To by malo pripadať povedomý, ak ste už dosiahnutý alebo dostali svoj špinavé ruky s problémom sady. Ale to je vaša funkcia vyhlásenie. Opäť platí, že by sa nemusíte starať o že moc v tomto okamihu. Čo naozaj chcem, aby ste urobiť, je vziať štyri minúty do pseudokódu binárne vyhľadávať, a potom pôjdeme na ktoré ako skupina. A prídem okolo. Ak máte otázky, pocit zadarmo, zdvihnite ruku. Prečo ste sa ďalšie dve minúty dokončiť až v pseudokódu? Viem, že sa to môže zdať smiešne, že budeme tráviť toľko času na niečo, čo ani nie je skutočne C, ale najmä pre tie viac náročné algoritmy a problém sady, že máme prísť na to, začína v pseudokódu nestará o syntax, len starosti logika, je nesmierne užitočná. A to spôsobom, nie ste riešenie dvoch neuveriteľne zložité problémy naraz. Len sa zameraním na logiku, a potom sa presunúť do syntaxe. OK. Začnime prechádza pseudokódu. Napísal som tu, binárne Hľadanie pseudokódu. Budeme písať o tejto rade spolu. Alebo budem písať to a dám me, že výzvy potrebujem. Takže môže mi niekto dať prvý riadok pseudokódu si písal pre binárne vyhľadávanie? Áno, Annie? STUDENT: Aj keď dĺžka list je väčšia ako nula. JASON Hirschhorn: Aj keď dĺžka zo zoznamu väčšia ako nula. A opäť, môžeme vidieť niektoré C-hľadá syntaktické veci na tu. Ale väčšina z toho je v angličtine. Mal niekto nejaké linky dali pred tým v ich pseudo-kódu? STUDENT: Získajte pole na radené čísel. JASON Hirschhorn: napísal si "sa Pole triedených čísel. "Per deklarácie funkcie, budeme okolo pole zoradených čísel. STUDENT: [nepočuteľné]. JASON Hirschhorn: Tak budeme mať, že. Ale áno, ak sme nemali to, že sme bude musieť vyriešiť našu ponuku čísla, pretože binárne vyhľadávanie funguje iba na triedené pole. Takže zatiaľ čo dĺžka zoznamu sa rovná nule, som dám v niektorých zložených zátvoriek aby to vyzeralo trochu ako C. Ale zatiaľ čo sa zdá máp na zatiaľ čo slučky, takže v tejto chvíli slučka čo potrebujeme urobiť pre binárne vyhľadávanie? Niekto, kto mi nedal odpoveď, ale zatiaľ, kto to napísal? STUDENT: Choďte do stredu zoznamu. JASON Hirschhorn: Tom. Prejsť na polovici zoznamu. A nadväzujúce otázka, čo budeme robiť, až budeme na stredná zoznamu? STUDENT: Do kontrolu, či, ktorý je počet hľadáte. JASON Hirschhorn: Výborný. Choďte doprostred zoznamu a skontrolujte, ak naše hodnota je tam - fantastické. Mal niekto niečo iné to bolo niečo iné, ako toto? To je presne to pravé. Prvá vec, ktorú robíme v binárnom vyhľadávanie , Je ísť do stredu zoznamu a skontrolujte, či je naša hodnota je tam. Takže predpokladám, že ak naše hodnota je tam, čo budeme robiť? STUDENT: Vraciame sa k nule [nepočuteľný]. JASON Hirschhorn: Jo, ak naše hodnota je tam, to sme zistili. Takže môžeme povedať nejaký spôsob, avšak toto Funkcia je definovaná, povieme užívateľovi sme ho našli. Ak to tam nie je, aj keď, to je kde sa to dostane zložité. Takže ak to tam nie je, niekto iný, kto pracoval na binárne vyhľadávanie alebo má predstavu o tom teraz, čo budeme robiť? STUDENT: Otázka. JASON Hirschhorn: Áno? STUDENT: Je poľa už je zoradený? JASON Hirschhorn: Áno, my sme za predpokladu, že Pole už je zoradený. Žiak: Takže potom budete musieť skontrolovať, či hodnota, ktorú vidíte, je väčší než hodnota, ktorú chcete, môžete presunúť do stredu druhej polovice. JASON Hirschhorn: Takže keď stred Zoznam je väčšia ako to, čo sme hľadáte, potom my, čo? Sťahujeme kde? STUDENT: Ak chcete prejsť na polovica zoznamu s čísla nižšia, než je. JASON Hirschhorn: Takže budeme volať, že ľavá. Takže ak prostredný je väčšia, môžeme hľadať ľavej polovici zoznamu. A potom hľadanie, čo mám na mysli vyhľadávania? STUDENT: [nepočuteľné]. JASON Hirschhorn: Ideme do stredu. Vlastne sme opakovať túto vec. Ideme naspäť cez naše slučke while. Dám vám ten posledný - inak, v prípade, prostredný je menšie ako to, čo robíme, čo robíme tu? STUDENT: Choďte doprava. JASON Hirschhorn: Hľadať právo. To vyzerá dobre, ale niekto čokoľvek, čo nám môže chýbať alebo niečo iné, že ste dal v pseudo-kódu? Takže to je to, čo máme tak ďaleko. Aj keď dĺžka zoznamu je väčšia ako nula, budeme pokračovať do polovice zoznamu a skontrolujte, či naša hodnota je tam. Je-li stredná hodnota je vyššia, budeme hľadať vľavo, inak v prípade, že stred je menej, budeme hľadať právo. Takže sme všetci mali nejakú znalosť termíny, ktoré používame v informatike a nástroje máme. Ale budete už všimnúť, že sme hovorí v angličtine, ale zistili sme, Veľa vecí, ktoré sa zdalo máp na nástroje máme v našom kódovaní sade náradia. Takže hneď bat, nie sme bude ešte vlastne kód. Čo vidíme tu v angličtine, že mapy na čo sa môžeme napísať v jazyku C? STUDENT: Kým. JASON Hirschhorn: Kým. Takže to, keď tu Mapy na to, čo? STUDENT: while. JASON Hirschhorn: while? Alebo možno, všeobecnejšie, slučka. Chceme urobiť niečo znovu a znovu. Takže ideme na kód slučky. A my už vieme, pretože sme urobili to párkrát a my majú veľa príkladov tam, ako vlastne písať tento index pre sláčiky. Tak to by malo byť celkom jednoduché. Mali by sme byť schopní sa dostať, že začal celkom rýchlo. Čo ešte môžeme vidieť tu? Aké ďalšie štruktúry syntaxe, veci že sme oboznámení s v C, my Už máte pocit Based off slov sme použili? Áno, Anna? [Nepočuteľný] len srandu. Anna, choďte do toho. STUDENT: Je-li a inde. JASON Hirschhorn: Je-li a inde - tu. Tak čo ty vyzerajú? STUDENT: v prípade iného vyhlásenia. JASON Hirschhorn: Jo, podmienky, že jo? Takže budeme pravdepodobne musieť napísať nejaké podmienky. A opäť, aj keď možno mätúce Po prvé, majú všeobecne zmysel teraz o tom, ako písať a podmienky Syntax podmienky. A keď nie, sme len vyhľadať Syntax podmienky, vyberaní a vkladaní že, pretože my vieme, Tu treba podmienku. Akékoľvek ďalšie veci, ktoré vidíme, že mapy na veci, ktoré by sme mohli potrebovať v C? Jo, Aleh? STUDENT: To by mohlo byť zrejmé, len o kontrolu, či hodnota sa rovná niečo. JASON Hirschhorn: Tak ako sme sa zistiť a - tak choďte do stredu zoznamu a skontrolujte, či naša hodnota je tam? Ako to urobíme v C? Čo je syntax pre to? STUDENT: Rovná, rovná. JASON Hirschhorn: Rovná, rovná. Takže táto kontrola sa pravdepodobne bude sa byť rovná, rovná. Takže budeme vedieť, že potrebujeme, aby niekde. A skutočne, nielen v písaní, vidíme tie ostatné veci. Budeme musieť urobiť nejaké Operátormi nákupný tam - fantastické. Takže to vlastne vyzerá, a a veľký, sme nenapísal Slovo C kódu ešte. Ale máme mentálny model, dole prostredníctvom prednášok a krátkych filmov. Napísali sme pseudo-kódu ako skupina. A už máme 80% ak nie 90% z toho, čo musíme urobiť. Teraz, len je treba kódovať to, čo je opäť netriviálne problém k riešeniu. Ale aspoň sme prilepené na logike. Aspoň teraz, keď ideme do úradných hodinách, Môžem povedať, ja viem, čo potrebujem robiť, ale môžete pripomenúť, mi syntaxe? Alebo aj keď úradné hodiny sú preplnené, vám Môže Google pre syntax, skôr než je prilepené na logike. A opäť, skôr než sa snažiť vyriešiť logika a problémy syntaxe všetky naraz, je často oveľa lepšie rozbiť tie dva pevné problémy sa do dvaja z nich viac zvládnuteľné a to pseudo-kódu ako prvý, a potom kód v jazyku C. Takže poďme sa pozrieť, čo som urobil pre pseudo-kódu dopredu. Aj keď dĺžka zoznamu je väčšia ako nula, pozrite sa na stredu zoznamu. Ak je číslo nájdených vrátil hodnotu true, inak Ak je číslo vyššie, hľadanie vľavo. Else if číslo nižšie, hľadanie právo, vráti false. Takže to vyzerá skoro identické, ak nie takmer totožný s tým, čo sme napísali. Vlastne, Tom, čo si povedal ako prvý, lámanie uprostred zoznamu a ak počet nájdených do dvoch výkazoch je vlastne to, čo som urobil. Kombinovaný som ich tam. Mal som počúval ste prvýkrát. Takže to je pseudo-kódu máme. Ak chcete, aby sa, je mi ľúto, prejdite späť k našej pôvodnej problém. Poďme kód binary.c. Takže realizovať iteratívny verzia binárne vyhľadávanie pomocou nasledujúcich Deklarácie funkcie. A nemusíte kopírovať to sa len zatiaľ. Ja som vlastne ísť otvoriť až tu binary.c. Takže tam je deklarácia funkcie v strede obrazovky. A uvidíte, vzal som pseudo-kódu zo na mojej strane, ale takmer totožný na to, čo sme napísali, a dal, že pre vás. Takže teraz, poďme päť minút kódovať túto funkciu. A opäť, ak máte nejaké otázky, zdvihnúť ruku, dajte mi vedieť, budem prísť okolo. STUDENT: [nepočuteľné]. JASON Hirschhorn: Tak som vzal binárne Definícia hľadanie na Hore na linke 12. To je to, čo som dostal k môjmu snímke. A potom sa to všetko pseudo-kód som skopírovať a vložiť zo snímky, pseudo-kód slide. Stále som nepočul [nepočuteľný]. Takže, ak ste dokončili svoj implementácia, chcem to skontrolovať. Aj e-mailom vám súbor helpers.h skôr v tejto triede. A to bude k dispozícii on-line, ako k stiahnutiu pre ľudí sledujú Tentoraz časť omeškania. A ja som len použil všeobecný distribúciu Kód z pset3. Tak som vzal find.C, používať svoj helpers.h súbor skôr ako súbor helpers.h , Ktorý je uvedený v distribučnej kódu. A musel som urobiť ešte jednu zmenu v find.C skôr než volanie jednoducho hľadanie, volajte binary_search. Takže ak si chcete vyskúšať svoje kód, viem, že to je, ako to urobiť. V skutočnosti, keď budeme spustení tohto kódu práve teraz, práve som urobil kópiu môj pset3 adresár, opäť odložené Pomocníci súbory a potom robil, že zmeniť find.C volať binary_search skôr ako jednoducho vyhľadávať. JASON Hirschhorn: Áno. Máte otázku? STUDENT: Nevermind. JASON Hirschhorn: Žiadne starosti. Dobre, poďme začať. Budeme kódovať to ako skupina. Jeden ďalší poznámka. Znovu, toto je možné ľahko zameniť Pre problémov nastaviť tri. Mám helpers.h súbor, ktorý skôr než helpers.h sme vzhľadom, prehlasuje, binárne vyhľadávanie, bublinu triedenie a výber triediť. A v find.c si všimnete, on-line, čo je to, linka 68, nazývame binárne hľadať skôr než hľadanie. Takže znovu, kód, ktorý je k dispozícii on-line alebo kód, ktorý ste vytváranie teraz dá ľahko vymeniť Pre p set 3 pozrieť sa na to. Ale najprv poďme kód binárne vyhľadávanie. Naše funkcie vyhlásenie, sa vracia bool. Berieme celé číslo s názvom hodnotu. Berieme pole celých čísel volal hodnoty, a vezmeme n byť Veľkosť poľa. Na riadku 10, priamo tu, mám ostré patrí stdbool.h. Vie niekto, prečo to tam je? Takže čo to riadok kódu urobiť? STUDENT: To vám umožní použiť typ bool návrate. JASON Hirschhorn: Presne tak. STUDENT: Alebo je to knižnica, ktorá umožňuje použiť typ bool návrate. JASON Hirschhorn: Tak ostré patrí stdbool.h linka mi niečo dáva definície a vyhlásenie pre veci že som dovolené používať v táto knižnica. Takže medzi tými, sa hovorí, že je Tento typ tzv bool, a to môže byť true alebo false. Tak to je to, čo to robí vedenie. A keby som nemal tú linku, by som dostať do problémov pre písanie tejto slovo tu, bool, hneď tam. Presne tak. Tak som potrebné, že v tomto kóde. OK. Takže to, opäť, je iteratívny verzie, nie je rekurzívne jeden. Tak poďme začať. Začnime s tým prvým rad pseudo kódu. A dúfajme, že budeme - alebo nie snáď. Chystáme sa ísť po miestnosti. Pôjdeme riadok po riadku, a ja vám pomôže môžete prísť na riadok, ktorý potrebujeme napísať ako prvý. Takže zatiaľ čo dĺžka zoznamu je väčšia ako nula. Začnime v prednej časti. Čo riadku mám napísať Tu, v kóde? STUDENT: Kým zátvorka n je väčšie ako 0. JASON Hirschhorn: Kým n je vyšší ako 0. Tak n je veľkosť zoznamu, a budeme kontrolovať, či - [Vložením VOICES] JASON Hirschhorn: - Prosím? STUDENT: Ako môžeme vedieť, že n je veľkosť zoznamu? JASON Hirschhorn: Ospravedlňujem sa. Podľa špecifikácie pset, hľadanie a druh funkcie, ktoré potrebujete písať, n je veľkosť zoznamu. Zabudol som sa mu vysvetliť, že tu. Ale áno. n je veľkosť zoznamu, v tomto prípade. Takže, keď n je väčšie ako 0. OK. To sa môže ukázať ako trochu problematické aj keď, ak to pôjde ďalej. Pretože budeme aj naďalej vedieť, veľkosť zoznamu v celom tomto funkcie, ale povedať, že sme začať s radom 5 čísel. A my sme prejsť a my máme Teraz ju znížil na pole 2 čísel. Čo 2 celé čísla, je, že? Veľkosť je 2 teraz, že chceme pozrite sa na, ale 2 je, že? Má to zmysel, na túto otázku? OK. Budem ho opýtať znova. Takže začneme s tohto poľa 5 celé čísla, a n sa rovná 5, nie? Budeme prejsť tu. budeme pravdepodobne zmeniť veľkosť, Dobre, ako sa veci ďalej. Čo je to, čo hovoríme, že chceme robiť. Nechceme hľadať plné vec znovu. Tak, že by sme to zmeniť na 2. Berieme pol zoznam, ktorý je divné. Takže len vybrať 2. Takže teraz n sa rovná 2. Ospravedlňujem sa za chudobných suché markery vymazať. Je to tak? A my prehľadávanie zoznamu opäť sa zoznamom veľkosti 2. No, naše pole je stále o veľkosti 5. Hovoríme, že chceme len, aby hľadať 2 miesta v ňom. Tak toho 2 miesta sú? Má to zmysel? Sú ľavé 2 miesta? Sú správne 2 miesta? Sú v strede 2 body? Sme prelomili problém dole, ale my vlastne neviem, ktorá časť problém, sme stále pri pohľade na, len tým, že tieto dve premenné. Takže potrebujeme trochu viac než, keď n je väčšie ako 0. Musíme vedieť, kde to n je v našom aktuálnom poli. Takže nemá niekto zmeniť na tejto trati? Väčšina z tejto rady je úplne správne. Je tu ďalší prírastok? Môžeme vymeniť niečo z pre n do aby túto líniu o niečo lepšie? Mm-hm? STUDENT: Môžete inicializovať premennú ako dĺžku až n, ktoré vám potom môžu byť použité neskôr vo funkcii? JASON Hirschhorn: Tak inicializovať premennej dĺžky N, a budeme používať neskôr? Ale potom sme sa len aktualizovať dĺžku a my ešte narazíte na tento problém, kde sme znížiť dĺžku nášho problému, ale nikdy nevieme, kde vlastne, že dĺžka mapy na. STUDENT: Nie je to nestane neskôr, keď hovoríš, hľadanie vľavo, hľadať pravdu? Budeš chodiť na rôzne oblasť vášho - JASON Hirschhorn: Chystáme sa ísť do priestoru, ale ako vieme, ktoré majú ísť? Ak máme len polia a to n, ako vieme, kde ísť na v poli. V zadnej, áno? STUDENT: Máte, ako, nižšia hranica a horná hranica premennej alebo niečo také? JASON Hirschhorn: OK. Takže to je ďalší nápad. Skôr než len sledovanie veľkosť, môžeme sledovať nižšie a horná medza premenné. Tak ako vypočítať veľkosť od dolná hranica a horná hranica? [Vložením VOICES] JASON Hirschhorn: odčítanie. A tiež sledovanie nižšia viazaný a horná hranica, dajte nám vedieť, sme vyhľadávania tyhle dva? Sme hľadanie tyhle dva tu? Sme vyhľadávania prostredný dva? Pravdepodobne nie prostredný dva, pretože to, v skutočnosti, je binárne vyhľadávanie. Ale teraz budeme mať možnosť získať veľkosť, ale tiež hranice poľa. V podstate, ak máme obra telefónny zoznam, sme to rip na polovicu. Teraz vieme, kde to menšie telefónny zoznam. Ale my nie sme v skutočnosti kopírovanie telefónny zoznam na polovicu. Stále potrebujeme vedieť, kde nové hranice nášho problému je. Má niekto nejaké otázky, o tom? Áno? STUDENT: Bude to fungovať vytvorením variabilný, aj, že potom stačí posunúť pozície aj vzhľadom k jeho aktuálnej pozície a dĺžka, n? JASON Hirschhorn: A čo je aj? STUDENT: Ako som bol ako druh - Ako by ste inicializovať aj byť stredná poloha poľa. A potom, v prípade, že hodnota na pozíciu aj v stred poľa vo zistené, byť nižšia ako hodnoty, ktorú vykoná, aj teraz sa dĺžka poľa, a hodnota aj delené 2. Ako vidieť, môžete presunúť aj - JASON Hirschhorn: Správne. STUDENT: - do - JASON Hirschhorn: Tak som si takmer pozitívne, že bude fungovať. Ale ide o bytosť, budete potrebovať dva kúsky informácií tu. Môžete to urobiť s počiatkom a koncom, alebo si môžete urobiť to s veľkosťou, a potom niektorí značka. Ale vy potrebujete dva kusy odtiaľ informácií. Nemôžete dostať sa len jeden. Znamená to, že má zmysel? Takže ideme prejsť, a budeme robiť, [nepočuteľný] a vytvoriť nejaké značky. Tak čo píšete vo svojom kóde? STUDENT: Len som povedal, int medza jeden je rovné 0. JASON Hirschhorn: Hovorme že int, začína. STUDENT: OK. JASON Hirschhorn: To robí väčší zmysel pre mňa. A? STUDENT: Povedal som, myslím, int koniec. JASON Hirschhorn: int končí. STUDENT: Myslím, n mínus 1, alebo niečo také. Ako posledný prvok. JASON Hirschhorn: Takže si napísal, int začína sa rovná 0, bodkočiarka, a int koniec sa rovná n mínus 1, bodkočiarku. Takže v podstate, čo robíme tu, 0 na prvej pozícii. A ako vieme, v poliach, nejdú až n, idú až n mínus 1. Takže máme nejaké hranice nášho poľa. A tieto počiatočné odhady sa stalo, že počiatočné hranice nášho problému. OK. Tak to znie dobre. Potom, ak sa vrátime k tejto línii, zatiaľ čo dĺžka zoznamu je väčšia ako 0, čo, miesto N, by mal dáme sem? STUDENT: Napíšte ukončenie mínus začiatok. JASON Hirschhorn: Pri ukončení mínus začiatok je väčšia ako 0? OK. A čo sme mohli, ak by sme chceli aby to trochu krajšie, čo iného sme mohli robiť? Ak by sme chceli vyčistiť Tento kód sa trochu? Ako sa môžeme zbaviť 0? To je len otázka štýlu. Je to práve teraz správne. STUDENT: Ending nie je rovná začiatok? JASON Hirschhorn: Môžeme robiť, čo? [Vložením VOICES] STUDENT: Ukončenie je väčší? JASON Hirschhorn: Jo. Môžeme len robiť, keď končí je väčší ako začiatok. Správne. Pridali sme začiatok na druhú stranu na to, že sme sa zbavili 0. Tak to proste vyzerá trochu čistejšie. OK. Takže, zatiaľ čo dĺžka zozname je 0, sme písali , Že, zatiaľ čo koniec je väčší ako na začiatku. Chystáme sa dať na naše potreby zložené zátvorky, a potom prvá vec, chceme urobiť, je pozrieť sa na je v malom zozname. Vy? Môžeš mi dať - STUDENT: Ak zátvorka Hodnota hranatá zátvorka - JASON Hirschhorn: Ak zátvorky hodnota hranatá zátvorka. STUDENT: Ending delené 2. JASON Hirschhorn: Ukončenie? STUDENT: Vidím problém s - JASON Hirschhorn: OK. No, pozrite sa na stredu. Ako môžeme vedieť, čo je uprostred? Jo. Takže dovoľte mi odstrániť tento kód. Ako môžeme vedieť, čo je uprostred? V ničom, ak máte začiatok a koniec, ako si nájsť stredná? STUDENT: Ty priemer. STUDENT: Môžete pridať dohromady a potom - JASON Hirschhorn: Pridať im dohromady a potom? STUDENT: A vy priemer. Rozdeľte ju 2. JASON Hirschhorn: Pridať im spoločne a vydeľte 2. Takže int strednej rovná? Tom, môžete mi to dať? STUDENT: Začiatok a koniec - JASON Hirschhorn: Začiatok a končí. STUDENT: Všetko, držiak, delené 2. JASON Hirschhorn: Všetko v zátvorkách, delené 2. Tak to mi dáva stred nič, opraviť? STUDENT: Tiež je potrebné zaokrúhliť nahor. JASON Hirschhorn: Čo si Teda, musím zohnať to? [Vložením VOICES] STUDENT: Vzhľadom k tomu, či je to divné číslo, potom je to ako - JASON Hirschhorn: Dobre, OK. Tak som si to mohol zaokrúhliť nahor. Ale či je to nepárne číslo, 5, môžem pričom jeden od stredu. Alebo či je to párne číslo, miesto, to je lepší prípad. Ak je to 4, len máme 4, môžem vziať Prvý "stredné", citácie, koniec citátu alebo Druhý "stredné" jeden. Buď bude pracovať pre binárne vyhľadávanie, takže nemám skutočne potrebujú, aby to zaokrúhľovať. Ale je tu ešte jedna vec, ktorú som je potrebné sa pozrieť na tento riadok. Mohli by sme si to neuvedomujete ešte, ale vrátime sa k nej. Pretože táto linka v skutočnosti stále potrebuje ešte jednu vec. Ale tak ďaleko, písali sme štyri riadky kódu. Máme našu začiatok a koncovú značkou. Máme while, ktorý mapuje na priamo na našu pseudokódu. Pozeráme sa na stredu, ktorý mapuje priamo na našom pseudokódu. Povedal by som, že to ide do stredu zoznamu, tento riadok kódu. A potom, raz pôjdeme do stredu zoznam, ďalšia vec, ktorú musíme urobiť, je zistiť, či naša hodnota je tu pre pseudokódu sme písali už skôr. Tak ako sme sa zistiť, či naše hodnoty je v strede zoznamu? Vy. Prečo ste to urobil? STUDENT: Ak je naša hodnota je v strede je rovná čo sme si stanovili - Myslím equal to - JASON Hirschhorn: Je - OK. STUDENT: Nie som si istý, čo Premenná hľadáme pretože aj keď, je to, že - [Vložením VOICES] STUDENT: [nepočuteľné]. JASON Hirschhorn: Presne tak. Na deklaráciu funkcie, hľadáme hodnotu. Takže sme hľadali hodnote v poli hodnôt. Takže ty si úplnú pravdu. Budete robiť, ak je otvorené zátvorka hodnota držiak stredná zatvorené držiaku rovná sa rovná hodnote, a vo vnútri Čo musíme urobiť? Ak sa naša hodnota je tam, čo to musíme urobiť? [Vložením VOICES] STUDENT: Návrat na nulu. JASON Hirschhorn: Vracia true. STUDENT: Vracia true. JASON Hirschhorn: Michael, čo tento riadok robiť? STUDENT: [nepočuteľné] program spustite jej priebeh, a to je u konca, a ste to, čo musíte urobiť? JASON Hirschhorn: Program alebo čo? V tomto prípade? STUDENT: funkcie. JASON Hirschhorn: funkcie. A tak, pre návrat na čokoľvek tzv a dať mu hodnotu, to je pravda. Presne tak. Hlavné. Čo je návratový typ z hlavnej, Michael? STUDENT: int, integer? JASON Hirschhorn: int, presne tak. Číslo. To bola len otázka, aby sa ubezpečil, vy ste boli na vrchole. Čo je to zvyčajne vráti, ak všetky veci fungujú dobre? STUDENT: Zero. JASON Hirschhorn: Zero. Presne tak. STUDENT: Ak je to len vráti hodnotu true, nie informácie sú uvedené o tom, čo - Oh, je to len hovorí, že hodnota je vo vnútri poľa. JASON Hirschhorn: Presne tak. Tento program nie je poskytovanie informácií kde presne je hodnota. Je to len hovorí, áno, sme zistili, to, alebo nie, sme nenašli ho. Takže ak číslo nájdené, vráti hodnotu true. No, vlastne sme práve urobili, že naozaj rýchlo, že jeden riadok kódu. Takže budem pohybovať, že rad pseudokódu. STUDENT: Nepotrebujeme pre zmenu polia? Malo by byť hodnoty, nie hodnoty, nie? JASON Hirschhorn: Ospravedlňujem sa. Ďakujem. STUDENT: Jo. JASON Hirschhorn: Tento riadok by mali byť hodnoty. Presne tak. OK. Takže sme sa pozrel na strednej zoznamu. Ak je číslo nájdených návrat pravda. Pokračovanie na našej pseudokódu, ak prostredný je väčšia, hľadanie vľavo. Tak som tu, ak počet vyššia, hľadanie vľavo. Constantine, môžete dať me tento riadok kódu? STUDENT: Ak je hodnota uprostred - JASON Hirschhorn: Takže ak hodnota - ak je otvorené zátvorka hodnoty držiak stredná zátvorka - STUDENT: Je menší ako hodnota? JASON Hirschhorn: Je menší ako. STUDENT: Menej ako hodnota. JASON Hirschhorn: Hodnota. No, vlastne, ktorú chcete skontrolujte, či je číslo - Prepáčte. To je trochu mätúce. Ale inak, ak je číslo v uprostred zoznamu je väčšia. STUDENT: Oh, OK. JASON Hirschhorn: budem zmeniť. Inak v prípade, strednej vyššej, sme chcete vyhľadávať doľava, OK? A čo budeme robiť dovnútra to, či podmienka? STUDENT: Môžem si urobiť malú zmenu stav, zmeňte ju na else if? JASON Hirschhorn: Else chcete? OK. Takže tento kód bude vykonávať zhruba rovnaký. Ale pekná vec, o použití, ak iný v prípade, inak v prípade, alebo v prípade, else if, inak Znamená to, že iba jedna z nich bude byť kontrolované, nie všetky tri z nich, potenciálne. A že je to trochu krajšie na počítači, ktorý je spustením programu. Tak [? Constantine,?] Sme v tomto riadku, inak, ak sú hodnoty, držiak stredný zátvorka je väčšia ako hodnota. Čo musíme urobiť? Musíme hľadať vľavo. Ako to urobíme? Chystám sa vám štart. Máme tieto dve veci zvané začína a končí. Takže to, čo potrebuje, aby sa stalo na začiatok? Ak chcete vyhľadávať ľavej strane Zoznam, dostaneme našu súčasnú začiatok. Čo musíme urobiť? STUDENT: My nastaviť začiatok do polovice a 1. JASON Hirschhorn: Takže keď sme vyhľadávanie vľavo? STUDENT: Je nám ľúto, stredná mínus - takže koniec bude stredná mínus 1 a začiatok - JASON Hirschhorn: A čo sa stane na začiatku? STUDENT: To zostane rovnaký. JASON Hirschhorn: Tak význam zostáva rovnaký. Ak budeme hľadať na ľavej strane, my sme použitie rovnakého začiatok - Presne tak. A koniec? Ospravedlňujeme sa, ale to, čo robí končí opäť v rovnováhe? STUDENT: Stredná mínus 1. JASON Hirschhorn: Stredná mínus 1. A teraz, prečo mínus 1, a to nielen strednej? STUDENT: uprostred je z obraz už, pretože sme mali skontrolovať, že je to vonku? JASON Hirschhorn: To je Presne tak. Stred je z obrázku. Sme už skúmali stred. Takže nechceme, "stred", citovať koniec citátu, aby aj naďalej v pole, ktoré sa pozeráme. Tak to je fantastický. Else if hodnoty držiak stredný väčší než hodnota končiace rovná stredná mínus 1. Jeff, čo o tomto poslednom riadku? STUDENT: Else. Hodnoty prostredný je menšia ako hodnota? JASON Hirschhorn: Budeme Dávaš mi viac. Takže ak nechcete, aby ma - STUDENT: Takže začiatok by stredná plus 1. JASON Hirschhorn: Začiatok rovná stredná plus 1, opäť, pre rovnakú Dôvod, že Constantine nám dal už skôr. A na konci, ktorý nie je uvedený me riadok kódu ešte? Return false, Aleh, čo budeme písať tu? STUDENT: return false. JASON Hirschhorn: Návrat false. A musíme to urobiť, pretože ak by sme nenájdete to, musíme povedať, že sme nenašiel. A my sme povedali budeme vracať bool, takže určite musieť vrátiť bool niekde. Takže poďme sa spustením tohto kódu. Ja som vlastne bude - takže sme v termináli. Budeme vyčistiť naše okno. Poďme Make všetko. Zistili sme, že je to jedna chyba. Tam je chyba na riadku 15, očakáva, že bodkočiarku na konci roka vyhlásenie. Takže to, čo som zabudol? STUDENT: bodkočiarku. JASON Hirschhorn: bodkočiarku až tu. Myslím, že to bol Tomov kód. Takže Tom, [nepočuteľný]. Len si robím srandu. Poďme urobiť, aby všetko znova. STUDENT: Aké adresára Dropbox Mali by sme byť za to? JASON Hirschhorn: Takže môžete Len pozor na tohto bitu. Ale na druhú stranu, ak by ste chceli presunúť tento kód do pset3 adresára vyskúšať it out, to je to, čo som urobil. Ak si všimnete tu - Ospravedlňujem sa, dobrá otázka. [? LS,?] Mám tú find.c kód z tohto týždňa distro kódu. Mám helpers.h. Mám súbor, aby to som vlastne upravovať trochu zahrnúť tieto nové Súbory sme písanie. Všetky tohto kódu bude mať k dispozícii, nie je distribúcia kód, ale nový Uistite sa súbor, bude nový helpers.h súbor byť k dispozícii on-line na prevzatie. Opäť, tak tie sú ďalšie kódy máme. Tak, aby všetci, na tejto trati, robí si, binárne, výber bublina - značky všetky tri z nich a kompiluje do Tento spustiteľný kód nájsť. Takže všeobecne, nechceme sa rovno do check50. Chceme urobiť nejaké testy na vlastnú päsť. Ale rovnako tak môžeme urýchliť tento kúsok, check50 2013 pset3.find prejde v helpers.c-- moja chyba. Nemyslím si, že práve teraz. Takže sme vlastne bude spustiť kód pre Real. Usage.find /, viete, čo to znamená? STUDENT: Musíte druhý príkazový riadok na neho. JASON Hirschhorn: Potrebujem druhý príkazového riadku. A podľa špecifikácií, musím zadať, čo sme hľadali. Tak sa poďme pozrieť na 42 rokov. Budeme udržiavať ju v triedený, pretože sme nenapísal funkciu triedenia ešte - 42, 43, 44. A riadenie D nenašiel ihla v kope sena. To je zlé. Je to určite tam. Skúsme niečo iné. Možno je to preto, že som si že na začiatku. Poďme urobiť, 41, 42, 43. Tam ideme. Je to našiel. Povedzme to na konci teraz, len takže môžeme byť dôkladné - 40, 41, 42. Nenašli ihlu. Takže som sa zmienil už skôr. Bohužiaľ, toto vedel som, sa bude diať. Ale na pedagogické účely, to je dobré preskúmať. To nefunguje. Z nejakého dôvodu nemôže nájsť. Vieme, čo je tam, ale nie sme nájsť. Takže jedna vec, ktorú môžeme urobiť, je ísť cez GDB ju nájsť, ale nemá nikoho, bez prostredníctvom GDB, majú Pocit, kde sme to pokašlal? [? Madu? ?] STUDENT: Myslím, že by to mohlo byť, keď končí sa rovná začiatku, a to je len zoznam jeden prvok. Potom to jednoducho ignoruje miesto skutočne to kontrole. JASON Hirschhorn: To je Presne tak. Pri ukončení sa rovná začiatku, my ešte prvok v našom zozname? STUDENT: Áno. JASON Hirschhorn: Áno, v skutočnosti sme majú jeden a len jeden prvok. A, ktorá bude s najväčšou pravdepodobnosťou stane, keď, podľa kódu sme testovali, sme na predné kope sena alebo koniec kope sena. To je miesto, kde začiatok a koniec sa bude rovnať jeden, s binárne vyhľadávanie. Takže v týchto dvoch prípadoch to nebude fungovať, preto, že koniec bol rovný začiatku. Avšak v prípade, ukončenia sa rovná začiatku, to while vykonať? To nie je. A mohli sme kontrolovať že opäť cez GDB. Takže, ako môžeme opraviť tento kód, pretože kedy pri ukončení sa rovná začiatok, chceme tiež tento while spustiť. Takže to, čo oprava môžeme urobiť na linku 18? STUDENT: [nepočuteľné] je väčšia alebo rovné. JASON Hirschhorn: Presne tak. Aj keď koniec je väčší ako alebo rovná na začiatok. Takže teraz sme sa uistite sa, že si, že roh prípad na konci. A pozrime sa. Poďme spustiť tento ešte raz. Poďme urobiť všetko. Opäť platí, že budete mať len postupujte podľa tu. Nájdite 41 tentoraz. Len aby to v súlade. Nájdite 42. Povedzme to na začiatku - 42, 43, 44. Našli sme ho. Takže to bola naozaj zmena sme potrebovali urobiť. To bolo veľa kódovanie my práve urobil, binárne vyhľadávanie. Má niekto nejaké otázky pred Aj ďalej do riadkov, ktoré sme urobili v roku binárne vyhľadávanie, alebo ako sme prišli z toho, čo sme zistili? Než budeme pokračovať, chcem tiež upozorniť sa, že aj veľké, sme zmapovali náš pseudo-kód, kto jeden na nášho kódu. My sme si to ošemetná vec prísť na to, s začína a končí. Ale mal by ste na to prišiel, si by písali do značnej miery totožný kód, s výnimkou tie horné dva riadky. A potom by ste si uvedomili, keď si ho kontrol a prípadov, ktoré budete potrebovať niečo iné. Takže aj keď ste nasledovali náš pseudo-kód linky na linku, by ste dostali všetci ale dva riadky kód, ktorý potreboval napísať. A bol by som ochotný sa staviť, že vy by si všetko vymyslel, že sa celkom rýchlo, že ste potrebovali dať nejaké značky tam prísť , Kde ste boli. To je opäť moc robiť pseudo-kódu dopredu. Takže, čo môžeme urobiť logiku ako prvý, a potom môžeme starať o syntax. Keby sme boli zmätení o logike a zároveň sa snaží napísať tento kód v C, by sme sa dostali všetko spackal. A potom by sme sa vypytovať logika a syntaxe a záberu ich všetky dohromady. A my by sme sa stratiť v tom, čo sa môže rýchlo stať veľmi ťažký problém. Takže poďme ďalej teraz na výber druhu. Máme 20 minút života. Takže mám pocit, že už nebude môcť dostať cez všetky voľby druhu a bubble sort. Ale poďme aspoň pokus dokončiť výber druhu. Takže realizovať výber triediť pomocou Nasledujúce deklarácie funkcie. Znova, toto je prevzaté z problém nastaviť špecifikáciu. Int hodnoty je konzola, je pole celých čísel. A INT.NO je veľkosť tohto poľa. Výber radenia sa deje triediť toto pole. Takže na našej mentálny model výberu triedenie, vytiahneme - Najprv sme sa prejsť v zozname ako prvé čas, nájsť najmenšie číslo, dať to na začiatku, nájsť druhé najmenšie číslo, vložte ho do Druhé miesto, ak chceme triediť vo vzostupnom poradí. Nebudem vás núti písať pseudo-kód práve teraz. Ale skôr, než budeme robiť kód ako triedy, vo päť minút budeme písať pseudo-kód, takže máme nejaký zmysel kde ideme. Takže pokus o zápis pseudo-kódu na vlastnú päsť. A pokúste sa obrátiť, že pseudo-kódu do kódu. Budeme robiť, že ako skupina za päť minút. A samozrejme, dajte mi vedieť, či Ak máte akékoľvek otázky. STUDENT: To, že? JASON Hirschhorn: Pozrite sa, ako ďaleko sa môžete dostať do ďalších dvoch minút. Chápem, že nie byť schopní dokončiť. Ale pôjdeme na to ako skupina. Ste všetci kódovanie, takže [nepočuteľné], takže som Ospravedlňujem sa, pozastaviť, čo robíte. Ale poďme prejsť to ako skupina. A opäť, binárne vyhľadávanie, všetci dávajú mi jeden, ak nie viac riadkov kódu. Ďakujem vám za to. Chystáme sa robiť to isté tu, kód spoločne ako skupina. Takže výber triediť - poďme napísať niektoré rýchle pseudo-kódu. Na duševnej modelu, môže niekto dať mi prvý riadok pseudo-kód, prosím? Čo chcem robiť? STUDENT: Kým zoznam je mimo prevádzky. JASON Hirschhorn: OK, zatiaľ čo Zoznam je mimo prevádzky. A čo myslíš tým "mimo poradia?" STUDENT: Kým [nepočuteľné] nebola uvedená. JASON Hirschhorn: Kým zoznam je mimo prevádzku, čo budeme robiť? Daj mi druhú linku, prosím, Marcus. Žiak: Takže nájsť ďalšie najmenšie číslo. To bude odsadený. JASON Hirschhorn: Takže tu ďalšie najmenšie číslo. A potom niekto iný? Akonáhle nájdeme ďalšie najmenší číslo, čo budeme robiť? Budem hovoriť nájsť najmenšie číslo. To je to, čo chceme robiť. Takže nájsť najmenšie číslo. Tak čo budeme robiť? STUDENT: [nepočuteľné] na začiatok. JASON Hirschhorn: Je nám ľúto? STUDENT: umiestnite ho do začiatku zoznamu. JASON Hirschhorn: Tak umiestnite ho do začiatok zoznamu. A čo budeme robiť na vec , Ktorá bola na začiatku zoznamu, nie? Sme prepísanie niečo. Tak kde sme to dať? Jo, Anna? STUDENT: Kde najmenší číslo bolo? JASON Hirshhorn: Tak si na začiatok zoznamu, ak Najmenšie číslo je. Takže zatiaľ čo zoznam je mimo prevádzku, nájsť najmenšie číslo, vložte ju do začiatok zoznamu, dať začiatku zoznamu, kde Najmenšie číslo je. Marcus, môžete preformulovať tento riadok zatiaľ čo zoznam je mimo prevádzku? STUDENT: Kým počty neboli radené? JASON Hirshhorn: OK, tak aby vedia, že čísla neboli ďalej, čo musíme urobiť? Koľko potrebujeme prejsť tohto zoznamu? Žiak: Takže myslím, že pre sláčiky, alebo kým, zatiaľ čo kontroluje čísla je menej ako je dĺžka zoznamu? JASON Hirshhorn: OK, to je dobré. Myslím, že misphrased moja otázka zle. Len som sa snažil dostať na budeme musieť ísť celý zoznam. Takže zatiaľ čo zoznam je mimo prevádzky, pre mňa je ťažké zmapovať na. Ale v podstate, to je ako Myslím, že o tom. Prejdite si celý zoznam, nájsť najmenšie číslo, vložte ju do začiatok - vlastne, máš pravdu. Poďme si ich oboch. Takže zatiaľ čo zoznam je mimo prevádzky, sa musí prejsť celý zoznam raz, nájsť najmenšie číslo, miesto sa na začiatku zoznamu, dal začiatku zoznamu, do ktorého najmenší počet bol, a potom v prípade, Zoznam je stále mimo prevádzky, máme musím ísť cez tento proces znovu, nie? To je dôvod, prečo voľba druhu, Big-O runtime výberového druhu, niekto? STUDENT: n na druhú. JASON Hirshhorn: n na druhú. Vzhľadom k tomu, ako Marcus a ja som si uvedomil, tu, budeme musieť prejsť Zoznam počet opakovaní. Takže prechádza niečo dĺžka n n koľkokrát je v skutočnosti n na druhú. Tak toto je naša pseudokódu. To vyzerá veľmi dobre. Má niekto nejaké otázky, o pseudokódu? Pretože v skutočnosti voľba triedenia by pravdepodobne Poďte na jedno-, kód od pseudokódu. Takže akékoľvek otázky týkajúce sa Logika pseudokódu? Prosím, spýtajte sa ho hneď. Výber sort - zatiaľ čo zoznam je vonku objednávky, budeme sa prejsť a nájsť najmenší zakaždým a vložte ho do prednej časti. Takže zatiaľ čo zoznam je mimo prevádzky, môže niekto mi dať ten riadok kódu, ktorý je mi nedal linku kódu ešte, prosím? Znie to ako čo? STUDENT: To je pre slučke. JASON Hirshhorn: To znie Páči sa mi na slučke. OK, môžete mi dať na slučke? Pre - STUDENT: i rovná 0. JASON Hirshhorn: i alebo - Čo nám chýba? Čo sa deje tu? STUDENT: Int. JASON Hirshhorn: Presne tak. (Int i = 0; - STUDENT: i