>> 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 <n; i + +).
>> JASON Hirshhorn: pribitý, Jeff.
Ideme do zoznamu, nie?
Už sme videli, že kód.
Perfect.
Takže poďme dať naše zložené zátvorky tu.
Chystám sa dať niektoré zložené zátvorky tu.
>> Takže aj keď je 0, musíme ísť celý zoznam.
Takže zakaždým, keď sme sa prejsť v zozname, to, čo chceme sledovať?
>> STUDENT: Ak sú swapy vyrobené.
>> JASON Hirshhorn: Hľadať najmenšie číslo.
Takže by sme mali pravdepodobne sledovať Najmenší počet zakaždým.
Takže linka môžem sledovať najmenšieho počtu?
Aleh, ako môžem sledovať stopa niečoho?
>> STUDENT: Začať novú premennú.
>> JASON Hirshhorn: Začať novú premennú.
Takže poďme vytvoriť premennú.
Aký typ?
>> STUDENT: Int.
>> JASON Hirshhorn: Int.
Hovorme tomu najmenší.
A čo to rovnať, keď sme práve začínate?
Ešte sme prešli v zozname ešte.
Sme v prvej časti Zoznam našich prvýkrát prejsť.
Čo je to rovnaké, Najmenšie číslo?
>> STUDENT: Hodnoty i
>> JASON Hirshhorn: Hodnoty i
To znie presne tak, jo?
Najmenej na začiatku je tam, kde sme.
Takže teraz máme naše najmenšie, a my potrebujeme prejsť celý zoznam a
porovnať to najmenšie na všetko ostatné.
Takže sme sa prejsť na zozname znova?
Michael?
>> STUDENT: Je potrebné, aby sa ďalšie slučky for.
>> JASON Hirshhorn: Ďalšie pre sláčiky.
Poďme na to.
Daj mi nejaký kód.
>> STUDENT: pre sláčiky -
pre najmenších -
pravý j, dalo by sa povedať?
= 0, tak, že -
>> JASON Hirshhorn: No, ak chceme prejsť celý zoznam -
>> STUDENT: j <n, j + +).
>> JASON Hirshhorn: Fantastic.
Chystáme sa prejsť pre sláčiky znova.
A ako sme sa nájsť Najmenšie číslo?
Tom?
Máme aktuálne najmenšie číslo, tak ako sme sa nájsť nový najmenší?
>> STUDENT: Môžeme zistiť, či najmenší Číslo máme je väčší než
hodnoty držiak j
>> JASON Hirshhorn: Takže jestli najmenších je vyššie ako hodnoty držiaku j
Takže ak náš súčasný najmenší je väčší ako -
Chystám sa presunúť tieto dva riadky kódu tam za sekundu.
Pretože predtým, než sme robiť žiadne odkladanie, sme musí prejsť celý zoznam.
Takže to pseudokódu by vlastne byť mimo, že vnútorné slučky for.
Takže prejsť celý zoznam.
Ak je väčšia ako najmenšie Hodnoty j čo potom?
>> Žiak: Takže najmenší rovná hodnoty j
>> JASON Hirshhorn: Fantastic.
Jeden rýchly dotaz -
Prvýkrát sme sa prejsť tejto slučky, aj to bude rovnať 0, j sa deje
rovnať 0, akonáhle sme sa sem dostali.
Takže budeme sa porovnanie číslo k sebe.
Je to efektívny?
Nie, to naozaj nie je efektívne.
Tak sa naše j musieť ísť od 0 do n zakaždým?
Máme vždy je potrebné skontrolovať celý zoznam?
[Nepočuteľný]?
>> STUDENT: Začnite sa i miesto.
>> JASON Hirshhorn: j plechovka začať s čím?
>> STUDENT: i
>> JASON Hirshhorn: j môže začať s i
Takže teraz sme sa porovnať začína s jedným Sme na.
Ale aj potom, je, že efektívne, ako je to možné?
>> STUDENT: i + 1.
>> JASON Hirshhorn: i + 1 sa zdá byť najúčinnejší, pretože
už som.
Sme o tom, že ako Najmenší v rade 15.
Chystáme sa začať s budúci automaticky.
Tak sme sa prejsť na slučku.
Pôjdeme cez každej dobe.
Pôjdeme cez množstvo časov.
Teraz sme sa dostali cez Tento vnútorný slučky for.
Máme najmenšia hodnota uloží.
Musíme ho umiestniť na začiatku zoznamu.
Tak ako to mám umiestniť ho na začiatku zoznamu?
Čo je premenná, ktorá sa týka na začiatku zoznamu?
Sme v tomto vonkajšej slučky for, tak čo sa týka
začiatku zoznamu?
>> STUDENT: Hodnoty i
>> JASON Hirshhorn: Presne tak.
Hodnoty i je začiatok -
alebo ľúto, nie začiatok.
To bolo mätúce.
To je miesto, kde sme na začiatku roka netriedený časť zoznamu.
Takže hodnoty i
A to, čo robí, že rovné?
>> STUDENT: Najmenší.
>> JASON Hirshhorn: Hodnoty i rovná čo?
>> STUDENT: Najmenší.
>> JASON Hirshhorn: Najmenší.
Presne tak.
Takže sme ju umiestniť na začiatku zoznamu, a teraz musíme dať
začiatok zoznamu, kde najmenší počet bol.
Tak ako to mám napísať, kde najmenší počet bol?
Hodnoty čoho?
>> STUDENT: 0.
>> JASON Hirshhorn: malá číslo je na 0?
>> STUDENT: Jo.
>> JASON Hirshhorn: Čo keď najmenší číslo bolo na konci
Tento netriedený zoznam?
>> STUDENT: Ospravedlňujeme sa, aká bola otázka?
>> JASON Hirshhorn: Kde je najmenšie číslo?
Vzali sme najmenší a dať to na začína sa tento riadok tu.
>> STUDENT: Mal by mať bola uložená do niektorej z nich -
>> STUDENT: Hodnoty j
>> JASON Hirshhorn: No, je to nie nevyhnutne hodnoty j
To ani neexistuje v tomto bode.
>> STUDENT: Musíte vyhlásiť, variabilný a skôr
potom priradiť -
keď zistíte, najmenšie číslo, priradiť index tohto čísla sa
niektoré premenné alebo niečo také.
>> JASON Hirshhorn: Tak môže hovoríte, že znovu?
>> Žiak: Takže, kde ste vyhlásil, int najmenšie, mali by ste tiež deklarovať int
Najmenší index = i, alebo niečo také.
>> JASON Hirshhorn: Tak, kde som to pravý najmenší, mal by som držať nielen sledovať
hodnoty, ale na mieste.
int smallest_location = v tomto prípad, budeme proste robiť i
Musíme vedieť, kde to je.
Máme na konci kódu, a my uvedomili sme mali tušenie, kde to bolo.
A tak opäť sme mapovanie o tento jedna k jednej.
Vy kódovanie to na vlastnej vôle pravdepodobne dostanete na rovnaký problém.
Ako to sakra mám nájsť?
A potom si uvedomíte, počkaj, ja je potrebné sledovať, že.
>> Takže v prípade, najmenší je väčšia ako hodnoty j
Vydali sme najmenšie rovná hodnoty j
Čo ešte musíme zmeniť?
Constantin, čo iného robiť musíme zmeniť?
>> STUDENT: umiestnenie.
>> JASON Hirshhorn: Presne tak.
Tak mi daj ten riadok kódu.
>> STUDENT: smallest_location = j
>> JASON Hirshhorn: Presne tak.
A potom sa na konci, ak chceme dal na začiatku zoznamu, kde
najmenší počet bol, ako budeme odkazovať na miesto, kde
najmenší počet bol?
Marcus?
>> STUDENT: najmenší počet bol sa nachádza na najmenšom mieste.
>> JASON Hirshhorn: Takže v hodnotách smallest_location.
A čo sme tam dal?
Začiatok zoznam, čo je to?
>> STUDENT: No, naozaj neviem už preto, že sme prepísali.
Takže je to len vymenili miesta z týchto dvoch liniek?
Ak prepnete tie dva riadky okolo.
>> JASON Hirshhorn: OK, takže to nie je už nie, pretože sme znovu linku
ako hodnoty aj na najmenších.
Tak sme prišli o tú počiatočnú hodnotu.
Takže ste povedal, odkladacia tieto dva riadky.
Takže teraz dal na začiatku zoznamu kde najmenší počet bol.
Takže smallest_location rovná hodnoty i
To je presunutie začiatku tohto netriedeného časť zoznamu na
Najmenší umiestnenie.
A potom do hodnoty aj sťahujeme že najmenšie číslo.
>> Dáva to zmysel, prečo sme musel robiť, že výmenu?
Radi by sme sa prepíše túto hodnotu - Ďalšia vec, ktorú pravdepodobne bude mať
prišiel a našiel v HDP.
Takže sme sa postarali o všetky pseudokódu.
Je ešte niečo, čo by sme je potrebné písať tu?
Môže niekto myslieť na nič iné?
>> STUDENT: Ako viete, Až budete hotoví?
>> JASON Hirshhorn: Ako sme vedieť, až budeme hotoví?
Veľká otázka.
Tak ako vieme, keď sme hotoví.
>> STUDENT: Vytvorenie premenné udržať počet v prípade, že je výmena vykonaná, alebo nie
a prejsť priechodom.
>> JASON Hirshhorn: OK.
To bude fungovať v bubline druhu.
Ale pre výber druhu, ak to neurobíme vykonať výmenu, ktorá by mohla byť len
pretože najmenšia hodnota je v ňom svoje správne miesto.
Mohli by sme mať zoznam 1, 2, 4, 3.
Druhýkrát cez my nebude vykonávať žiadne swapy.
Budeme sa na číslo 2, ale budeme Stále je potrebné ísť ďalej.
Takže sa musíme sledovať, kedy sme hotoví, alebo si jednoducho chcete ísť
až toto skončí?
>> STUDENT: Môžeme len tak až je to hotové.
>> JASON Hirshhorn: Môžeme len ísť až je to hotové.
V bubline druhu, máš úplnú pravdu, Jeff a Aleh, s riešením -
Je skvelé sledovať, koľko swapy ste urobili, pretože v bubline
triediť, ak si v skutočnosti robiť žiadne swapy, máte hotovo a môžete potrebné znížiť vaše
Problém trochu dole.
Ale pre výber druhu, ste naozaj ísť až do konca roka
Zoznam zakaždým okolo.
>> Tak to je, že.
Máme dve minúty.
Poďme urobiť všetko.
Dovoľte mi len otvorené Nájdite tu a aby , Že som v skutočnosti vyvolaní -
Nebudem volať bublinkové triedenie.
Zmeňme to, aby výber druhu.
aby všetky. / nájsť.
Poďme nájsť 42.
Tentoraz budeme odovzdávať netriedený zoznam, pretože to by malo vyriešiť
Prvý, na Nájsť kódu - by mala vyriešiť prvou pomocou nášho triedenia funkciu a potom
pozrite sa na niečom.
Držím palce všetkým.
>> Ach môj bože.
Whoa, moje srdce tĺklo.
Tak to je správne.
V skutočnosti, keď sme bežali to viac značne, kód, ak môžem
povedať, je úplne správne.
Tam sú niektoré návrhy, Ja by som pre teba.
Napríklad, 15 a 16 sa zdá trochu nadbytočný.
Vyzerá to, že nemusíte nutne je potrebné uložiť ako ty.
Ak máte najmenšie umiestnenie, Môžete ľahko nájsť najmenšiu hodnotu
Len zadaním hodnoty i
>> Takže ak sa mi bude triedenie kódu, ktoré som v skutočnosti byť, by som
pravdepodobne trvať off bod, ak vrátane oboch z nich, pretože vám
Nemusíte obaja z nich.
Ak máte miesto, môžete veľmi ľahko získať hodnotu.
A zdá trochu divné uložiť obaja.
Možno, že ani mať pravdu, ale určite komentovať, že je možná
nie je štylistický výber je potrebné vykonať.
Samozrejme, kód stále beží dobre.
>> Takže bohužiaľ sme nemali dostať do bublinkovej druhu.
Je mi ľúto, že.
Urobili sme cieľovú výber druhu.
Má niekto nejaké konečné otázky o výbere druhu?
>> OK, predtým, než vyrazíme, chcem ťa otvoriť svoj prehliadač Chrome.
Je nám ľúto, že bol len do očí bijúce zástrčka pre jeden typ internetového prehliadača.
Môžete otvoriť ľubovoľný typ prehliadača, ale to bude pravdepodobne Chrome.
A ísť na to po stránkach -
sayat.me/cs50.
Ak si nie ste písanie na počítači práve teraz, ste jasne
nerobím to, Tom.
>> A urobte to buď priamo teraz alebo v ďalšej hodine -
daj mi nejakú spätnú väzbu.
To je len časť dve.
Máme veľa viac spolu, tak som majú veľký priestor pre zlepšenie.
Dúfam, že som tiež robil niektoré veci dobre.
Takže si môžete urobiť cítim tak zlé, ale ak budete tiež chcieť, aby mi smajlík
tvár, ocenil by som, že rovnako.
Vyplňte že palcov
>> A vľavo o jednu minútu že bol tri týždne.
Ja budem stáť vonku trochu Ak máte nejaké otázky.
Uvidím vás chlapov prednáška zajtra.