JASON Hirschhorna: Dobrodošli do trećeg tjedna, svatko. Imamo posla, ali uzbudljivo poglavlje ispred nas. Tako je prvi, jer smo napravili neke napredak u tijeku, ali još uvijek su puno učenja lijevo učiniti, ja sam će pokazati ti dečki neke resurse koja bi trebala dokazati da se nevjerojatno korisna jer ne samo približiti svoje Problem postavlja, ali probaviti sve Materijal smo vam dečki u predavanja i kratke hlače i sekcija. Onda ćemo provesti prvih 20 do 25 minuta poglavlje prelaženju GDB, koje mogu, ali ne moraju koristi u ovom trenutku, već je to nevjerojatno koristan alat koji će vam pomoći ispravljanje svoje programe. Puno vas možda koristi printf u Usred svog programa shvatiti što varijabla jednaka. GDB je čak i bolje nego printf i ne zajebe svoj kôd, jer vam pokrenuti ga na izvršnu datoteku. Dakle, mi ćemo ići preko 10 najviše pomoći naredbe što je potrebno za GDB, a mi smo ići na vježbe zajedno, tako u problemu postaviti tri i izvan nje, te Možete koristiti GDB pomoći debug svoje programe. I na kraju, da ćemo ići preko neke sortiranje i pretraživanje algoritama koje ste vidjeli u predavanju, a mi smo događa se zapravo broj, a ne samo pseudocode, ali kod binarno traženje, mjehurić vrsta, i odabir vrsta. Dakle, prvo, želim ići nad resursima. To je opsežan popis, i to je manji font, jer sam imao puno toga za stati ovdje. No, to ne samo da će vam pomoći, opet, s problemom setovima i probavljanje informacije ste naučili, ali Definitivno, dolaze kviz vrijeme, to će biti nevjerojatno korisno. Tako je prvi, bilješke. Ako idete na cs50.net/lectures i pomaknite se na specifičan tjedan i dan, vidjet ćete da postoje bilješke za svaki predavanje, koje je ne samo prijepis, ali uređena verzija ono što je bilo prekriveno predavanja s kodom isječke i druge korisne sitnice. Ja visoko preporučiti ide preko njih. A onda, kao, postoji izvorni kod dostupni iz svakog predavanja. I opet, ti slajdovi također će biti dostupan online na cs50.net/sections ovu večer. Dakle, drugi su kratke hlače svaki tjedan da pokrivaju teme, obično 5 do 15 minuta. A oni će, nadamo se dati super premaz na različite teme. Treće - i to je potpuno novi to godine - je study.cs50.net. Ako niste ga odjavio, ja Svakako preporučamo da to učinite. Moći ćete odabrati temu. Imamo desetke tema tamo. Tako, primjerice, možete pokupiti funkcije. To vam daje neke slajdove i primjećuje na funkcijama. Oni su zapravo slajdova koji TFS se potiču na korištenje tijekom našeg prezentacije u sekciji. Tu je i savjete i trikove za rješavanje s funkcije, a tu je praksa problemi koji pomažu radite s funkcija. Također smo vam dati linkove na kratko funkcije i vremena koji funkcionira su se u predavanju. Dakle study.cs50.net, potpuno novi to godine, fantastičan izvor. Dalje, imam čovjeka, što je za upotrebu naredbe koje možete izvoditi na naredbenog retka. Dakle, ako imate bilo kakvih pitanja u vezi naredba, primjerice, Rand, koju susreo prošlog tjedna u poglavlju i vjerojatno ste naišli na tvoj problem postaviti pri prolasku kroz generiranje koda, ali ako upišete čovjeka Rand, dobit ćete stranicu koja govori vam sve o rand. To vam daje sve što je potrebno, Parametri što je potrebno, kao i povratak vrstu i kratak opis te funkcije. Dakle provjerite randa. To može biti malo razvučen i zbunjujuće, tako da ponekad ne mogu naći da jednostavno Googling ono što želim znati je Najbolji način za pronaći odgovor. Dakle praksa s Googleom. Nabavite dobar u Google. To će postati vaš najbolji prijatelj. Kao i Google, ako ne mogu ga naći na Googleu, cs50.net/discuss, to je forum za raspravu. Šanse su, ako imate pitanje, jedan Vaših 700 + vršnjaka ima da pitanje i možda su pitali to je već u razgovarati forumi i to odgovorio. Dakle, ako imate zajedničke pitanje ili imate pitanje za koji mislite da možda i drugi ljudi mogli izvoditi u, check out cs50.net/discuss. Konačno, posljednja dva, ako želite razgovarati s pravog ljudskog bića, ured radno vrijeme od ponedjeljka do petka. Tu je i online radno vrijeme za proširenje studenata. I zadnje, ali svakako ne i najmanje važno, ja, uskličnik. Vi svi imaju svoje kontakt podatke. Ako ti nešto treba, molim te nikad ustručavajte se kontaktirati mene. Uvijek slobodno to učinite. Vrlo malo ste mi dodana Gchat, , tako da je bio razočaravajući, ali nadamo se da ćete mijenjati između ove i iduće poglavlje. Bilo kakva pitanja do sada na resursima? Velika. Konačno, još jedan dodatak za šalje, sayat.me/cs50. Možete mi dati povratne informacije anonimno kako radim. To je bilo jako korisno prošlog tjedna. Dobio sam par komentara od vas dečki odmah nakon sekcije, plus iz ostali učenici koji su ga gledali tijekom tjedna, a to bio je nevjerojatno korisna. Ja ću pokušati ograničiti svoju uporabu Riječ "slatka", ali ja neću pojaviti entuzijazma i uzbuđenja i na druge načine. No, tu su i druga dodatna Značajnija povratne informacije, oba pluseve i Delta. Dakle, molim vas, dajem Ti dečki povratne informacije na tvoj problem setovima. Slobodno mi dati povratnu informaciju na moj nastave. Ja sam tu za vas, momci. Velika. To je sve što imam za Prva cjelina. Da li itko ima bilo pitanja do sada? I ja imam na umu za kontrolni centar. Produžni učenici su me messaged rekavši da ne uzimajući bilo koji audio, , ali da je iz moje moći popraviti. Dakle, nadamo se, da dobiva ubrzo riješiti. Ako gledate na internetu, hi, , ali ne možete me čuti. Dakle, prvo, idemo proći kroz GDB. GDB, kao što sam ukazivao na ranije, je alat za uklanjanje pogrešaka puno bolje nego printf. Dakle, da biste započeli s GDB, ti dečki, ako želite otvoriti svoj uređaj i uzeti datoteku koju sam e-poštom na vas ranije - ova datoteka će također biti dostupan online na malo - i pokrenuti GDB. / ime datoteke. Prvo, naravno, morate sastaviti podnijeti jer GDB radi samo o izvršne datoteke. Ali, ako ste ikada željeli pokrenuti GDB, prva stvar koju trebate učiniti, pokrenete gdb. / Cezara. Dakle to je naziv programa mi živimo moramo ići s njim u ovom trenutku. Tako da ću napisati da Cezara, koji će mi dati izvršnu datoteku Ovdje označen zelenom bojom. A onda ću pokrenuti gdb. / Cesar. I tamo idete. Vidite da imamo neki tekst mi govori o verziji GDB, daje mi neke informacije o jamstvu, i onda smo imaju brz BDP-a, koji izgleda vrsta poput naše linije naredbeni redak, ali vidiš da je otvoren zagr, GDB, bliski zagr. Prije nego što nastavite i ispravljanje ovu datoteku da sam poslao svima vama, pogledajmo neke korisne naredbe tako da imamo osjećaj U što ćemo se pokriti. Te naredbe su ovdje navedene u poredak u kojem sam uglavnom ih koriste. Tako sam početi moj program pokretanjem GBD. / Ime programa, u ovom slučaju, Cezar. I onda prvo što mi je činiti 99,9% vremena se Prijelom znači. To postavlja break na glavni. U osnovi, što radiš tu je Program će se zaustaviti na Glavni tako da možete početi ispitivanje to liniju po liniji, a ne trčati put kroz. Možete razbiti na različitim mjestima u vaš broj, ali glavno je općenito dobro mjesto za početak. Naredba koja slijedi Trčim je trčanje. To pokreće program pokrenut, i ako je potrebno unijeti naredbenog retka argumenata, što ga pokrenuti tu naredbu. Trčanje s argumentima. Dakle, budući da se ide preko verziju C, što je Program momci napisao za pset dva - ovo, naravno, ima nekih bugova u tome da se nadam da ćemo naći - idemo na trčanje trčanje s nekim zapovjedništvom argumente, jer je Cezar, što ti dečki znaju po problemu set spec., uzima neke argumente naredbenog retka. Narednih nekoliko naredbi, pored jedan je zapravo zove naprijed. To je jedan vodi vas redak po redak kroz svoj program. Dakle, udarajući n onda Enter vam treba u sljedeći redak, izvršavanju zadnja linija. Korak vas vodi ne samo da Sljedeći linija, ali je Potrebno Vam unutar funkcije. Dakle, ako ste napisali funkciju u vaš broj ili, ako želite istraživati do i, na primjer, možete pogoditi s, a umjesto da ide na sljedeću liniju datoteka koju prolaziš prava Sada, vi ćete zapravo korak u ova funkcija i vidjeti svoj kod. Popis pokazuje se, u vrlo user friendly formata, na 10-ak linije oko gdje se trenutno nalaze u kodu tako da zapravo možete vidjeti sliku umjesto da zamijene natrag i naprijed između različitih pogleda. Ispis je kao i printf, kao njegovo ime implicira. To pokazuje što varijabla jednaka. Info mještani stvarno korisno. To je posebna verzija tiska. Info mještani vam pokazuje sve lokalne varijable, ispisuje ih sve za tebe koji su trenutno dostupni. Tako sam općenito, a ne da ispisali četiri varijable koje sam zanima, ako sam u for petlji, za Na primjer, ja samo pišem info mještanima, i to će mi što moj brojač sam pokazati jednako, kao i niz da sam radi na jednakima. Konačno, i dalje. Tipkanje pauzu zaustavlja vas na točki prekida. Možete prošetati linije skladu s naprijed i korak. Nastavak pokreće program za vaš sljedeći razbiti točku ili dok završetak ako nema više break. Bez uklanja točkama prekida, ako vam odlučio pauze na glavna je neprimjereno, što želite stavi ga negdje drugdje. I na kraju q, prestati, dobiva iz GDB. Dakle, ovaj program,. / Cezar, idemo gledati kroz upravo sada i mi ćemo koristiti GDB pronaći bugovi u ovom programu. Otrčao sam ovaj program ranije s Provjerite 50, a ja sam dobio jednu grimasu. Sve je to postojalo, to sastavio, to prošlo puno testova, ali za Iz nekog razloga, to nije prošao petinu test, okreće BARFOO, sve kape, u E-D-U-I-R-R, sve kape, pomoću tri kao ključ. Dobio sam vrlo blizu. Sam dobio od strane jednog slova. Dakle, postoji neka mala pogreška u ovdje. Ja sam pogledala kroz moj broj. Nisam mogla to shvatiti. Nadajmo se da dečki mogu mi pomoći shvatiti što to bug je. Dakle, to je pogreška smo u potrazi za. Idemo u GDB. Opet, ja sam trčanje GDB. / Cezara, pa sad smo u GDB. I što je prvi što bih trebao napraviti? Upravo sam ušao GDB. Neka mi netko da dobar naredba za ulazak. STUDENT: Break glavna. JASON Hirschhorna: Break glavna. Fantastic. Neka je tip koji u. Vi dečki mogu gledati ovdje ili pratite zajedno na svojim računalima. Break glavna, i vidjet ćete Point Break je bio postavljen na - to mi daje neku čudnu memorijsku adresu, a također mi daje broj linije. Ako mi je da se osvrnem na ovu sliku, Ja bi shvatili da je glavna dogodilo na liniji 21. Što sam trebao pokrenuti naprijed? Je li moj program radi? Ne. Dakle, ono što bih trebao raditi sljedeće? STUDENT: Run. JASON Hirschhorna: Run. Trebam li samo trčanje trčanje, ili bi trebala I još neke stvari u? STUDENT: Trčanje s argumentom. JASON Hirschhorna: Trčanje s Zapovjedna argumenti. A budući da sam za ispravljanje pogrešaka vrlo specifičan slučaj, da unesem da naredbenog retka argument. Dakle, ja ću to raditi tri, koja je, opet, Izlaz sam dobio od Odlazak 50. Pokretanje programa. Prolazimo kroz par redaka. Sada ćete vidjeti da smo na liniji 21. Kako ću znati da smo na liniji 21? Jer ako pogledate na lijevo mog prozora terminala, postoji piše liniju 21. I to mi daje, zapravo, kod koji se nalazi na liniji 21. Tako sam misspoke ranije. Glavni zapravo nije na liniji 21. Glavni je par redaka iznad 21 godine. No, na liniji 21, koji je gdje smo razbijanje. Ova linija koda ima još nije izvršena. To je važno. , Koji vidite nije još izvršen. To je sljedeća linija koda ti si o da izvrši. Dakle, pored linije, kao ti dečki su vjerojatno upoznati s, je li to provjeru stanja vidjeti ako imam ušao naredbenog retka argument je. I to sam, što je drugi dio da se radi? Ono što je za mene? STUDENT: Promjena ga u cijeli broj. JASON Hirschhorna: Žao mi je? STUDENT: Mijenja Argument u cijeli broj. JASON Hirschhorna: Tako da sam mijenja ARG V1 iz niza na cijeli broj. I onda što je to provjera? UČENIK: Ako postoji drugi naredbenog retka argument, na stranu od pokretanja programa. JASON Hirschhorna: A što je Druga polovica to Ček logički izraz? Ovaj dio ovdje, to ja? UČENIK: Ako je negativna. JASON Hirschhorna: Izrada sigurni što? STUDENT: Upućivanje sigurni da je, u stvari, pozitivan. JASON Hirschhorna: Točno. To je provjera da li je negativan, a ako je negativna, ja Imam osjećaj sljedeći redak moć treba mi vikati na korisnika. Pa neka je pogodio kraj izvršiti ovu liniju. Ne vidim tu crtu da ti dečki možda očekivali vidjeti deranja na Korisnik, a zatim se vraćaju, jer ova linija nije izvršavati. Ušao sam tri. Tako sam si, u stvari, unesite dva naredbu argumente, a 3 je veći od nule. Tako smo vidjeli tu liniju, izvršen smo, ali nismo korak unutar Ako stanje. Tako sada, pored, vidim ja postavljanje int ključ jednako se i ARG v1. Tako da je meni stvara promjenjivu ključ. Dakle, ako sam isprintati ključ upravo sada, jer koji vam omogućuje da vidite vrijednost unutar varijable, Ključ iznosi 47. To je malo čudno, ali, naravno, to je zato što nisam izvršiti tu liniju još. Pa sad, ako sam pogodio n, izvršiti tu liniju, i raditi ispis ključ, ključ će biti jednak 3, što je ono što mi očekujemo da će biti jednak. Pa opet, u GDB, na liniji koju vidi se da još nije izvršena. Morate pogoditi n ili e ili broj drugih naredbi da se zapravo izvršiti tu liniju. Ispis ključ. Ključ je u tri. Do sada, tako dobro. String je običan tekst. Idemo izvršiti tu liniju. Idem niz od korisnika. Idemo vidjeti u mom Odlazak 50, ja unesite BARFOO sve kape, tako to je ono što ću ući. Ako ja sada ispisati običan tekst. Vidjet ćete da je jednako niz. To mi daje neku drugu čudnu heksadecimalni broj, ali to čini u Činjenica reći da mi je struna BARFOO. Ako sam htio vidjeti što ključ iznosio na ovom trenutku, kako bih mogao provjeriti ključ? STUDENT: Print ključ. JASON Hirschhorna: Ispis ključ, točno. A zapravo, postoji prečac. Ako ste se umorili od tipkanja ispis, možete samo upisati str. Dakle p ključ radi istu stvar točno. I opet, ne vidim da je jednako tri. Ako sam želio saznati što su obojica tipku i BARFOO iznosila istovremeno , ali sam bio umoran od tipkanja svaka jedan pojedinačno, sam mogao upisati info mještanima. To mi daje ključne jednako 3. Običan tekst jednako BARFOO. To također daje mi ove dvije čudne stvari na vrhu, ova varijabla i i ova varijabla n. Oni su zapravo postojeće u mom glavnom programu. Mi ih nismo susreli još, ali kao pregled, onima postoji u mom for petlje. Dakle, upravo sada, oni jednaki neki čudan brojevi, jer oni nisu bili inicijaliziran još, ali oni još uvijek ne postoje u memoriji, pa oni su samo postavili do neke smeća vrijednosti. No, mi ne vidimo ključ u ravnici tekst upravo tamo. Tako ću izvršiti ovu liniju, linije 34, za petlju. Mi ćemo skočiti u za petlju skom n. I mi smo unutar for petlje. Mi smo u našoj prvoj provjeri. A opet, to bi trebalo nekako izgleda upoznat s tobom, jer je to bio Cezar je program koji je napisan, ali opet, ima nekakav bug. A sad, ako mi je činiti info mještanima, jer sam unutra da se za petlje, vidjet ćete da sam jednak nuli, kao što smo očekivali. To je ono što smo ga postavili na i inicijaliziran to da se u for petlji. n = 6. To također ima smisla, jer smo postavili je na strlen od običnog teksta. Zato volim raditi info mještanima ili otisak za varijablu često kako bi bili sigurni da je sve je uvijek ono što Ja očekujem da jednaka. U tom slučaju, sve ono što sam očekivao da će biti jednak. Pa krenimo kreće kroz ovo za petlju. Linija sam na je red 36, ako je obični Tekst I je veća od te obični Tekst I je manja od ili jednaka z. Znam da moj problem nije moj prvi pismo, to je s drugom pismu. Ako se osvrnemo na check 50, B ide na E kaznom. Uzimam A i ostavljajući ga kao , ne mijenja na D. So nešto nije u redu s drugo pismo. Tako da ću se preseliti postoji u sekundi. Ali, ako sam htio provjeriti što ravnicu Tekst sam iznosio u ovom konkretnom slučaj, mislim da bi trebao biti što? Što bi običan tekst kime u to Prvi krug kroz za petlje? STUDENT: Nula? JASON Hirschhorna: Običan tekst I? Dakle, to bi trebao biti glavni B. I, naravno, jednak nuli, ali običan tekst Nosač nula zatvorena zagrada jednaka B zbog žice, kao što smo vidjeli prošlog tjedna, su niz, tako da smo uzimajući Prvi znak toga. Pa opet, ako sam isprintati običan tekst Ja, ja, u stvari, dobili karakter B. A to je uredan, zar ne? Ja zapravo ne imati običan tekst I. To nije jedna od varijabli sam postavljenih ili inicijaliziran, ali možete ispisati se cijeli niz stvari Ako želite. No, krenimo putem. Ako običan tekst sam veći od A i Običan tekst da je manja od ili jednaka Z, koji jasno je istina, jer imamo kapital B. ću pokrenuti neke naredbe na njemu. Vidjeli smo da je matematika prošli tjedan, pa ćemo uzeti zdravo za gotovo da se to radi Pravo prema Provjerite 50. Ove vitičastim zagradama, prvi pokazali su da sam se izlaska, ako stanje, a drugi je pokazao da sam izlaska za petlju. I sad kad sam udario Dalje, vidjet ćemo vratili smo se u for petlji opet. Idemo kroz za petlju ponovno. Idemo zapravo korak u sekundi iteracija za petlje i vrsti info mještani. Tako smo u drugoj iteraciji našeg za petlju. I jednak 1, što očekujemo. N iznosi 6, koji smo očekivali. Ključ iznosi 3, koji smo očekivali. I običan tekst, vidjet ćete, jednako EARFOO sada, ne BARFOO više jer u našem prethodnom iteraciji, B je promijenjen u kapitalu E. Tako smo o da se susrećemo s problemom, tako da je ovo Ovdje ćemo zaroniti u ispravljanje pogrešaka. Ali ne bilo tko ima bilo kakvih pitanja o onome što smo do sada učinili? Fantastic. Dakle, mi smo o tome da izvrši ovo ako stanje, običan tekst nosač zatvorena sam Nosač veći od A i običan tekst sam manji od ili jednak, ali prije Z. Ja ulaziti u to, jer to je mjesto gdje Znam moja pogreška, želim istaknuti iz običnog teksta I. Dakle neka je stavi ispisati. To čini jednak karakter, tako da Čini se do sada, sve je dobro i dobro. Dakle, očekujem ovaj redak po mojoj logici, ova linija trebala biti istina. To je slovo. Ali, ako sam pogodio n, mi shvaćamo da je to linija, u stvari, nije izvršavati. Skočio sam dolje na drugi ako. Zašto se to dogodilo? UČENIK: Zato što imate vaše stanje od običnog teksta je veća od, nije jednaka ili veća od. JASON Hirschhorna: Tako sam imao moj običan tekst Da je veći od, ne veća od ili jednaka. Dakle, jasno, kapital nije aktiviraju ovo ako stanje, a mi smo učinili Ne korak u tome i uspjeli smo Ne učinite nužan zaokret. Tako da je to, zapravo. I shvatio moju grešku. Mogao bih se vratiti u moje izvorne datoteke, ga promijeniti, a to ažurirati i pokrenuti Provjerite 50 opet. No, vidjet ćemo, samo za pedagogiju-a sake, ako sam zadržati ide. Drugo, ako ne izvrši bilo, ali ono, umjesto jednaka je naredba to ne mijenja. Dakle, to nije promijenilo na sve, a ako sam ispisati običan tekst ovdje, vidjet ćemo idući kroz koji za petlju nije, u stvari, promijeniti taj drugi lik uopće. To je još uvijek glavni A. Pa opet, debugged smo našu pogrešku. Shvatili smo da je neke logike nedostaje. I mi to debugged ispred vremena prije stvarno izvršenje tu liniju, ali ti bi primijetili smo imali samo pogodio Next i skok na drugo da li, to znači da, ako stanje nije istina. Nismo, zapravo, dobili Rezultat smo očekivali. Pa onda smo mogli biti zatraženo, imala nismo bili tako pronicljivi, pogledati da, ako stanje i provjerite je li, u stvari, Naš uvjet treba ocijeniti da Istina je u trenutnom kontekstu. To je sve za ispravljanje pogrešaka ovaj program. Ima li tko kakvih pitanja? Ono što sam zapovijed mogao pogoditi prestati GDB? P: I onda ću se tražiti, Svejedno otkaz? Da ili ne. Ja ću pogoditi da, a ja ću se prestati GDB. Tako da je brzi premaz za GDB. Zapravo, u realnom scenariju, Ja sam to u uredovno vrijeme. Ja GDBed ovu točan program na radno vrijeme s učenikom. A ako se vratimo na naredbe koje smo vidjeli prije, koristili smo pauzu glavnom, prvo stvar koju smo učinili. Koristili smo trčanje s naredbenog retka argumente, Druga je stvar što smo učinili. Mi smo koristili pored puno kretati nas preko linije. I opet, kratka verzija od naprijed je n. To je u zagradama u sivoj boji na tobogan. Nismo koristili korak, ali nismo nužno je potrebno za ovaj slučaj. No, možemo ga koristiti u malo kasnije danas, ako smo za ispravljanje pogrešaka, za Primjer, pretraživanje po binarnom kad binarna traži se zove u odvojenim funkcija, ali postoji neka pogreška s njim. Idemo žele stupiti u Poziv na binarnom pretragu i zapravo to debug. Popis nismo iskoristili bilo jer smo imali dobar smisao našeg koda, ali ako sam htjela dobiti osjećaj za ono što sam kod bio u blizini, ja samo mogu koristiti popis. Ispis koristili smo, info mještanima smo se koriste. Nastavak nismo morali koristiti u ovom slučaj, niti je moramo iskoristiti onemogućiti, ali nismo korištenje otkaz. Opet, tih 10 zapovijedi, prakticiraju ih. Ako ste razumjeli ovih 10 zapovijedi, što bi trebao biti postavljen za ispravljanje pogrešaka bilo izdati GDB. Dakle, mi smo o tome da se ide dalje, opet, na poanta dijelu danas, ide preko to sortiranje i pretraživanje algoritmi. Prije nego što smo to učinili, opet, bilo kakva pitanja, komentari, zabrinutost za GDB? Tako se svatko ide na korištenje GDB umjesto printf? Dakle, svi su, za ime vječnost je, svatko je kimao glavom svoje pravo sada, tako da ću vas vidjeti u uredovno vrijeme i svi TFS će vas i vidjeti oni će reći, pokazati mi kako koristiti GDB, a vi ćete biti u mogućnosti im pokazati, zar ne? Vrsta? Možda nadamo. Cool. Tako ćemo se preseliti u sortiranje i pretraživanje. Vidjet ćete imam popis već sortiran za nas, ali to se ne događa biti slučaj uvijek. Tako je u problemu postaviti specifikacija za Problem postaviti tri, imate gaćice koje možete gledati, a to je zapravo pita vas gledati one kratke hlače. Također u predavanju prošli tjedan, razgovarali smo o Puno tih algoritama, pa sam neće trošiti vrijeme na satu ide iznova ovih algoritama ili crtež Slike za koliko je to algoritmi rade. Opet, da informacije možete ponovno gledati Predavanje, ili da informacije je osvojio izvanredno na gaćice za ove pretraga, sve koji su dostupni na cs50.net. Dakle, umjesto, što ćemo učiniti je napisati ove programe. Imamo osjećaj, mentalni model, o tome oni rade, i tako što ćemo učiniti jest ih kod za real. Idemo da se taj mentalni model, ta slika, ako hoćete, u Stvarni broj. A ako ste bili malo zbunjeni ili maglovita o mentalnom modelu, totalno razumijem. Nismo zapravo ide odaberi kod ravnini. Dakle, dok je ovaj redak u ovom slajdu pita što to kod binarnog pretraživanja, i zapravo, iterativan verzija binarno pretraživanje, prva stvar koju sam Stvarno želim da učinite je napisati neki pseudocode. Tako ćete imati taj mentalni model kako binarno pretraživanje funkcionira. Izvadite list papira, ako imate jedan lako dostupni, ili se otvaraju tekst editor, i ja bih svatko pisati. Uzmi četiri minute pisati pseudocode binarni pretragu. Opet, razmislite o tom mentalnom modelu. Ja ću doći oko, ako imate pitanja i možemo izvući sliku iz. Ali prvo, prije nego što počnemo programiranje, Htio bih napisati pseudocode za pretraživanje s binarnim pa kad smo zaronite u, imamo neke smjeru kao do mjesta gdje trebamo ići. STUDENT: Možemo li pretpostaviti niz Vrijednosti koje su dobili već riješeno? JASON Hirschhorna: Pa za binarnom pretragu za rad - izvrsno pitanje - što moraju uzeti u sortirani Niz vrijednosti. Dakle, pretpostavimo da će raditi. Vratit ćemo se na ovom slajdu. Vidjet ćete u purpurne funkciji Deklaracija je bool binary_search int vrijednost, int vrijednosti, int n. To bi trebao izgledati poznato, ako ste Već prilazi ili stečen Vaše ruke prljave s problemom setu. No, to je tvoja funkcija izjava. Opet, ne treba se brinuti o toliko u ovom trenutku. Ono što ja stvarno želim učiniti je uzeti Četiri minute do pseudocode binarnog traži, a onda ćemo ići preko koje kao skupina. I ja ću navratiti. Ako imate pitanja, osjećam besplatno podići svoju ruku. Zašto ne uzeti više od dvije minute završiti na pseudocode? Znam da to može izgledati smiješno da trošimo toliko vremena na nešto što nije ni zapravo u C, ali posebno za njih više izazovnim algoritama i problema setovi koju moramo shvatiti, s početkom u pseudocode ne brinući o sintaksi, samo brige o Logika je nevjerojatno korisna. I na taj način, niste rješavanje dva nevjerojatno teškim problemima odjednom. Vi ste samo s naglaskom na logici, a onda se krećete u sintaksi. OK. Počnimo prolazi kroz pseudocode. Ja sam napisao ovdje, binarna traži pseudocode. Mi ćemo napisati ovo na ukrcati zajedno. Ili ću ga napisati, a vi ćete dati mi upute što trebam. Dakle, može li netko dati mi prvi put linija pseudocode ste napisao za pretraživanje s binarnim? Da, Annie? STUDENT: Dok duljina Popis je veći od nule. JASON Hirschhorna: Dok dužina liste veći od nule. A opet, vidimo neke C-potrazi sintaktičke stvari na ovdje. No, većina je to na engleskom jeziku. Je li itko ima bilo koju liniju su stavili Prije toga u svojoj pseudo-koda? STUDENT: Dobiti niz od razvrstani brojeve. JASON Hirschhorna: Napisao si "dobiti Niz sortiranost brojeva. "Per Funkcija deklaracija, mi ćemo se prolazu Niz razvrstanih brojeva. STUDENT: [nečujan]. JASON Hirschhorna: Tako morat ćemo to. Ali da, ako nismo imali da smo će morati izdvojiti našu lepezu brojevi, jer binarno pretraživanje radi samo o razvrstanih polja. Dakle, dok je dužina popisa jednak nuli, ja sam će se staviti u nekim vitičastim zagradama da izgleda malo više kao C. No, dok je, čini se mapirati na dok petlje, tako da unutar tog vremena loop što trebamo učiniti za binarno pretraživanje? Netko drugi koji mi nije dao odgovor još, ali tko je to napisao? STUDENT: Idi na sredinu ljestvice. JASON Hirschhorna: Tom. Idi na sredinu ljestvice. I follow-up pitanje, što radimo kada smo na Sredina popisu? STUDENT: Dali ček bilo da je broj tražite. JASON Hirschhorna: Izvrsno. Idi na sredinu ljestvice i provjerite ako je naša vrijednost je tu - fantastična. Je li itko ima bilo što drugo koji je bio drugačiji od ovoga? To je točno. Prvo što nam je činiti u binarnom pretragu se ići na sredini popisa i provjeriti je li naša vrijednost je tu. Pretpostavljam, ako naša vrijednost postoji, što nam je činiti? STUDENT: Vraćamo nulu [nečujan]. JASON Hirschhorna: Da, ako je naš vrijednost je tamo, našli smo. Dakle, možemo reći na neki način, no to Funkcija se definira, možemo reći korisnik smo ga pronašli. Ako to ne postoji, međutim, da je gdje se to dobiva lukav. Dakle, ako to ne postoji, netko drugi tko se radi na binarnom pretragu ili je ideju sada, što nam je činiti? STUDENT: Pitanje. JASON Hirschhorna: Da? STUDENT: Je niz već riješeno? JASON Hirschhorna: Da, mi smo uz pretpostavku Niz je već riješeno. UČENIK: Pa onda morate provjeriti je li vrijednost koja vidite veći od vrijednost koju želite, možete premjestiti u sredini druge polovice. JASON Hirschhorna: Dakle, ako je sredina Popis je veća od onoga što smo mi u potrazi za, onda smo to što? Mi smo premjestiti gdje? STUDENT: Vi želite da se presele u polovica popisa s brojeva niže od toga. JASON Hirschhorna: pa ćemo pozvati da lijevo. Dakle, ako je srednja veća, možemo tražiti lijeva polovica na popisu. I onda po potrazi, ono mislim pod potrazi? STUDENT: [nečujan]. JASON Hirschhorna: Idemo u sredini. Mi zapravo ponoviti ovu stvar. Vraćamo se preko našeg while petlje. Ja ću vam dati posljednju - drugo, ako je, srednje je manje od onoga što radimo, što da radimo ovdje? STUDENT: Idite na desno. JASON Hirschhorna: Traži pravo. To izgleda dobro, ali ne bilo tko imati sve što možemo da nedostaje ili Sve ostalo što ste stavili u svom pseudo-koda? Dakle, to je ono što smo do sada. Dok duljina popisa je veća od nule, da ćemo ići na sredinu ljestvice i provjerite je li naša vrijednost je tu. Ako srednja veća, idemo na traži napustio, drugo, ako je srednji manje, idemo tražiti pravo. Dakle, svi smo imali neke upoznatost s pojmovi koje koristimo u računalnoj znanosti i alati imamo. No, već ćete primijetiti da smo govoreći na engleskom jeziku, ali smo našli puno stvari koje se činilo da mapirati na alata koje imamo u našem kodiranja kompleta alata. Dakle, pravo isključiti šišmiš, nismo će još zapravo koda. Što smo vidjeli ovdje na engleskom da se karte na stvari koje možemo napisati u C? STUDENT: Dok. JASON Hirschhorna: Dok. Pa to dok ovdje karte na što? STUDENT: while petlja. JASON Hirschhorna: while petlja? Ili, vjerojatno, općenitije, loop. Želimo učiniti nešto više i više. Dakle, idemo to kod petlje. A mi već znamo, jer smo učinili to nekoliko puta, a mi ima dosta primjera vani, Kako zapravo napisati taj indeks za petlju. Tako da bi trebao biti prilično jednostavan. Trebali bismo biti u mogućnosti da biste dobili da započeo prilično brzo. Što još možemo vidjeti ovdje? Koje druge strukture syntaxes, stvari da smo upoznate sa C, to smo Već imaju osjećaj Like od od riječi koje se koriste? Da, Anna? [Nečujan] Samo se šalim. Anna, samo naprijed. UČENIK: Ako i drugdje. JASON Hirschhorna: Ako i drugo - ovdje. Pa što oni izgledaju? STUDENT: ako drugi izjavu. JASON Hirschhorna: Da, uvjetima, zar ne? Dakle, vjerojatno ćemo morati pisati neke uvjete. I opet, iako možda i zbunjujuće na Prvo, mi općenito imaju smisla kako napisati uvjete i sintaksa za uvjetima. A ako to ne učinimo, možemo samo gledati sintaksa za uvjete, izrezati i zalijepiti da, zato što smo mi znali treba stanje ovdje. Sve ostale stvari vidimo tu kartu na stvari koje smo možda trebati učiniti u C? Da, Aleha? STUDENT: To bi moglo biti očito, po samo provjeru ako vrijednost jednaka nešto. JASON Hirschhorna: Pa kako ćemo provjeriti i - kako ići u sredinu ljestvice i provjerite je li naša vrijednost je tamo? Kako ćemo to učiniti u C? Što je sintaksa za to? STUDENT: Jednako, jednako. JASON Hirschhorna: Jednako, jednako. Dakle, ovo je vjerojatno će provjeriti biti jednaka, jednaka. Dakle, mi ćemo znati što je potrebno da negdje. A zapravo, baš u to pisanje, vidimo one druge stvari. Mi ćemo morati napraviti neke usporedbu operateri tamo - fantastična. Dakle, to zapravo izgleda, tako i Veliki, nismo napisali Riječ C kod još. No, dobili smo mentalni model dolje putem predavanja i one kratke hlače. Napisali smo pseudo-koda kao skupina. I već imamo 80%, ako ne i 90% od onoga što trebamo učiniti. Sada samo trebamo da kod to, što je opet, je ne-beznačajan problem riješiti. Ali barem smo zapeli na logiku. Barem sad kad odemo na radno vrijeme, Ja mogu reći, ja znam što mi treba to učiniti, ali može li podsjetiti ja od sintakse? Ili, čak i ako su radno vrijeme gužve, te Može li Google za sintaksu, a nego se zaglavi na logiku. I opet, umjesto da pokušavate riješiti logiku i sintaksu problemi sve odjednom, što je često mnogo bolje razbiti te dvije teške probleme off u dvije bolje upravljati one i učiniti pseudo-koda, a zatim kod u C Pa da vidimo što sam učinio za pseudo-koda ispred vremena. Dok duljina popisa je veća od nule, pogled na sredini popisa. Ako se utvrdi da broj vratio istina, ostalo ako je broj veći, traži lijevo. Drugo ako je broj manji, traži Dobro, povratak false. Tako da izgleda gotovo identično, ako ne gotovo identičan onome što je napisao. Zapravo, Tom, ono što je rekao prvi put, razbijanje sredinu ljestvice, a ako Broj pronađena u dva izvještaja je zapravo ono što sam učinio. Ja ih u kombinaciji postoji. Trebao sam slušao što prvi put. Tako da je pseudo-koda imamo. Ako želite da se sada, ispričavam se, idite natrag na naš početni problem. Idemo kod binary.c. Dakle provesti iterativni verziju binarno pretraživanje pomoću sljedećih Funkcija izjava. I ne morate kopirati to dolje samo još. Ja sam zapravo će otvoriti do ovdje binary.c. Dakle, tu je funkciju deklaracija u sredini zaslona. I vidjet ćete što sam uzeo pseudo-koda od na moje strane, ali gotovo identične to što smo pisali, a staviti u za vas. Pa sad, idemo uzeti pet minuta da kod ove funkcije. I ponovno, ako imate bilo kakvih pitanja, podići svoju ruku, javite mi, ja ću navratiti. STUDENT: [nečujan]. JASON Hirschhorna: Zato sam uzeo binarni definicija traži na vrh, na liniji 12. To je ono što sam dobio za slajd. I onda sve to pseudo-koda sam samo kopirati i zalijepiti iz slajda, pseudo-koda slide. Ja sam još uvijek nije čuo [nerazumljivo]. Dakle, ako ste završili svoje Provedba, želim da ga provjerite. Poslana sam vam helpers.h datoteku ranije u ovoj klasi. I to će biti dostupan na internetu, kao i za preuzimanje za promatranje ljudi ovaj put poglavlje odgođen. A ja samo koristi generički raspodjelu Kod sa pset3. Zato sam uzeo find.C, koristiti svoj helpers.h datoteku umjesto helpers.h datoteke koji je dao u distribucijskom kodu. I ja sam morao napraviti još jednu promjenu u find.C nego zvati jednostavno pretraživanje, nazvati binary_search. Dakle, ako želite testirati svoj kôd, Znam da je to kako se to radi. U stvari, kad ćemo prikazivati ​​ovaj kod upravo sada, upravo sam napravio kopiju moj pset3 imenik, opet, zamijenili pomagača datoteke, a zatim je napravio da promijeniti u find.C nazvati binary_search nego jednostavno traži. JASON Hirschhorna: Da. Imate pitanje? STUDENT: Nevermind. JASON Hirschhorna: Bez brige. Pa, počnimo. Mi ćemo kodirati to kao grupa. Još jedna napomena. Opet, to je, lako se može zamijeniti u za problematične postavila tri. Ja imam svoj helpers.h datoteku koja, umjesto od helpers.h nam je dan, izjavljuje binarno pretraživanje, balon sortiranje i odabir vrsta. I u find.c ćete primjetiti na liniji, što je to, linija 68, zovemo binarni traži, a ne traži. Pa opet, kod koji je dostupan online ili kod koji ste stvarajući upravo sada se može lako zamijeniti u za p postaviti 3 to provjeriti. No, prvo, idemo kodirati binarne pretragu. Naš funkciju deklaracija, vraćamo se bool. Mi se cijeli broj zove vrijednost. Mi se niz brojeva zove vrijednosti, a uzmemo n biti Veličina polja. Na liniji 10, upravo ovdje, imam Oštar uključuju stdbool.h. Zna li itko zašto je to bilo? Dakle, što to linija koda učiniti? STUDENT: To vam omogućuje da se koristiti povratnu bool vrstu. JASON Hirschhorna: Točno. STUDENT: Ili je to knjižnica koja omogućuje koristiti povratnu bool vrstu. JASON Hirschhorna: Dakle oštra uključuju stdbool.h linija mi daje neke definicije i deklaracije za stvari da smijem koristiti u ova knjižnica. Tako među onima koji je rekao da postoji Ova vrsta se zove bool, a to može biti istina ili laž. Dakle, to je ono što čini da je linija. A ako nisam imao tu crtu, ja bih dobiti u nevolji za pisanje ovaj Riječ ovdje, bool, upravo tamo. Točno u pravu. Dakle, trebam da se u ovom kodeksu. OK. Pa to je, opet, je iterativan verzija, nije rekurzivna jedan. Pa neka nam početak. Počnimo s ovom prvom Linija pseudo koda. I nadamo se, hoćemo - ili ne nadamo. Mi ćemo ići po sobi. Ići ćemo redak po redak, a ja ću vam pomoći što shvatiti crtu koja nam je potrebna napisati prvi. Dakle, dok je dužina popisa je veći od nule. Krenimo naprijed. Na koji sam trebao pisati Ovdje, u kodu? STUDENT: Dok zagrada n je veći od 0. JASON Hirschhorna: Dok n je super od 0. Tako je n veličina popisu, a mi provjere da li - [ubačenih GLASOVI] JASON Hirschhorna: - Molim? UČENIK: Kako znamo da je n je veličina popisa? JASON Hirschhorna: Žao mi je. Po specifikaciji pset, traži i sortirati funkcije morate pisati, n je veličina popisa. Zaboravio sam objasniti da je ovdje. No, da. n je veličina Popis, u ovom slučaju. Dakle, dok je n veći od 0. OK. To se može pokazati malo problematično iako, ako stvari krenu dalje. Zato ćemo i dalje znati Veličina popisa tijekom ove funkcija, ali kažu da smo krenuli s nizom od pet brojeva. I mi proći i mi smo Sada ga suzio Niz od dva kafića. Koja 2 cijeli brojevi je to? Veličina je 2 sada kada želimo pogledati, ali koji 2 je to? Da li to smisla, to pitanje? OK. Ja ću opet pitati. Tako smo krenuli s ovim nizom od 5 cijeli brojevi, a n = 5, zar ne? Mi ćemo pokrenuti kroz ovdje. vjerojatno ćemo promijeniti veličinu, Dobro, kako stvari idu dalje. Koji je ono što mi kažemo što želimo učiniti. Ne želimo tražiti puna stvar opet. Dakle, reći ćemo ga promijeniti dva. Mi se pola popis koji je čudno. Dakle, samo pokupiti dvije. Dakle, sada je n = 2. Ja se ispričavam za siromašne suho brisanje markera. Zar ne? I mi smo u potrazi kroz popis Ponovno s popisom veličine 2. Pa, naš niz još od veličine 5. Kažemo samo želimo da se traži dva mjesta u njoj. Pa što 2 mjesta su oni? Ima li to smisla? Jesu li ostavili 2 mjesta? Jesu li oni pravo 2 mjesta? Jesu li oni srednji 2 mjesta? Mi smo razbijena problem dolje, ali mi zapravo ne znam koji dio Problem mi smo još uvijek u potrazi na, samo što ove dvije varijable. Zato nam je potrebno malo više od, a n je veći od 0. Moramo znati gdje je to n je u našem stvarnom polju. Znači li itko ima promijeniti ove linije? Većina tog pravca je savršeno točna. Ima još jedan dodatak? Možemo li zamijeniti nešto za n na čine ovu liniju malo bolje? Aha? STUDENT: Možete li inicijalizirati varijablu kao i dužinu na n da onda ćete se koristi kasnije u funkciji? JASON Hirschhorna: Dakle započeti promjenjive duljine do n, i mi koristimo da kasnije? No, onda mi samo ažurirati duljinu i mi Još uvijek upasti u ovaj problem, gdje smo smanjiti dužinu našeg problema, ali nikad se ne zna gdje je, zapravo, da je dužina preslikava na. UČENIK: Nije li da će se dogoditi kasnije, kada govoriš, traži napustio, traži pravu? Ti ćeš ići na različita području vašeg - JASON Hirschhorna: Idemo ići na tom području, ali kako znamo koji su ići? Ako imamo samo niz i to n, kako znamo gdje idu u polje. U leđa, zar ne? STUDENT: Imate li, kao, manji vezan i gornju granicu varijabla ili nešto slično? JASON Hirschhorna: OK. Dakle, ovo je još jedna ideja. Umjesto da jednostavno praćenje veličina, možemo pratiti niže i gornju granicu promjenjiva. Pa kako ćemo izračunati veličinu od donju granicu i gornju granicu? [ubačenih GLASOVI] JASON Hirschhorna: oduzimanje. I također praćenje niža vezan i gornja granica da nas obavijestite, tražimo ovu dvojicu? Jesmo li u potrazi ovu dvojicu ovamo? Jesmo li u potrazi srednji dva? Vjerojatno ne srednji dva, jer to, u stvari, je binarno pretraživanje. No, sada ćemo biti u mogućnosti da biste dobili veličinu, ali i granice polja. U biti, ako mi imamo diva telefonski imenik, mi ga potegnuti na pola. Sada znamo gdje je manja Telefon je knjiga. No, nismo zapravo sjajna stvar telefonski imenik na pola. Još trebamo znati gdje nove granice našeg problema. Da li itko ima bilo kakvih pitanja o tome? Da? STUDENT: Želite li raditi stvaranjem promjenjiva, ja, da li onda samo pomak I položaj u odnosu na njegovu Trenutni položaj i duljina, n? JASON Hirschhorna: A što je ja? STUDENT: Kao što sam se kao svojevrsno - Kao što bi započeti i biti srednji položaj u nizu. A onda, ako je vrijednost na poziciji sam u Usred polja u utvrdi da biti manje od vrijednosti koju je potrebno, i sada postaje duljina niza, plus vrijednost i podijeljena dva. Kao, vidiš, ja pomak - JASON Hirschhorna: Točno. STUDENT: - do - JASON Hirschhorna: Pa ja sam gotovo pozitivno je što će raditi. Ali point biće, potreban vam dva dijelovi informacija ovdje. Možete to učiniti s početka i kraja, ili to možete učiniti s veličinom, a zatim neki marker. No, to ne treba dva komada informacija ovdje. Ne možete dobiti tako da sa samo jednim. Da li to ima smisla? Tako ćemo proći, a idemo raditi [nečujan] i stvoriti neke markere. Pa što si pisati u kodu? STUDENT: Samo sam rekao int granicu jedan je jednak 0. JASON Hirschhorna: Nazovimo da je int, počevši. STUDENT: U redu. JASON Hirschhorna: To čini više smisla za mene. I? STUDENT: rekao sam, valjda, int završava. JASON Hirschhorna: int završava. STUDENT: Mislim, n minus 1, ili nešto slično. Kao, posljednji element. JASON Hirschhorna: Pa što je napisao, int s početkom = 0, zarez, i int završetak jednako n minus 1, točke-zareza. Dakle, u biti, ono što mi radimo Ovdje 0 do prvog mjesta. A kao što znamo u polja, oni ne idu do n, odu do nje minus 1. Dakle, imamo neke granice naše polje. I ove početne granice dogoditi da bude početne granice našeg problema. OK. Tako da zvuči dobro. Zatim, ako se vratimo na ovoj liniji, dok je Duljina popisa je veći od 0, što je, umjesto N, trebao stavili smo ovdje? STUDENT: Napišite završava minus početak. JASON Hirschhorna: Dok je završio minus Početak je veći od 0? OK. I što smo mogli, ako smo htjeli bi da malo ljepše, što drugo mogli? Ako smo htjeli očistiti ovaj broj se malo? Kako možemo dobiti osloboditi od 0? To je samo pitanje stila. To je točno upravo sada. STUDENT: Završna ne jednaka početak? JASON Hirschhorna: Možemo raditi što? [ubačenih GLASOVI] STUDENT: Završetak je veći? JASON Hirschhorna: Da. Mi samo možemo učiniti, a završava je veći od početka. Točno. Dodali smo na početku druge strane o da, i što smo se riješili na 0. Dakle, to samo izgleda malo čišći. OK. Dakle, dok je duljina liste 0, što je napisao da, a završio je veća nego na početku. Mi ćemo staviti na naš neophodno vitičastim zagradama, a onda prva stvar želimo učiniti je pogledati ih u malom popisu. Vi? Možete li mi dati - UČENIK: Ako zagrada Vrijednost uglata zagrada - JASON Hirschhorna: Ako zagrade Vrijednost uglata zagrada. STUDENT: Ending podijeljena dva. JASON Hirschhorna: Završetak? STUDENT: Vidim problem s vašim - JASON Hirschhorna: OK. Pa, pogledaj na sredini. Kako znamo što je srednji? Da. Pa neka mi obrisati taj kod. Kako znamo što je srednji? U svemu, kada imate početak i na kraju, kako se pronaći Srednji? STUDENT: Vi prosjek. STUDENT: Možete ih dodati zajedno i zatim - JASON Hirschhorna: Stavi ih zajedno, a onda? STUDENT: I ​​ti prosjek. Razdijelite po dva. JASON Hirschhorna: Stavi ih zajedno i podijeliti po dva. Dakle int srednje jednaka? Tom, možete mi ga dati? STUDENT: Početak plus završava - JASON Hirschhorna: Početak plus završava. STUDENT: Sve, nosač, podijeljena dva. JASON Hirschhorna: Sve, u zagradama, podijeljena dva. Tako da mi daje u sredini ništa, ispraviti? STUDENT: Također je potrebno da ga zaokružiti. JASON Hirschhorna: Što vam je činiti znači, moram ga zaokružiti? [ubačenih GLASOVI] STUDENT: Jer ako je čudno broj, onda je to - JASON Hirschhorna: Pa, u redu. Tako sam mogao zaokružiti. Ali, ako je neparan broj, 5, mogu i ja uzimanje jednog od sredine. Ili, ako je to još broj, a, to je bolji slučaj. Ako je 4, imamo samo četiri, ja mogu uzeti Prvi "srednji", citat, završiti citat ili Drugi "srednja«. Ili će raditi za binarnu pretragu, pa ja zapravo i ne treba ga obići. No, tu je još jedna stvar koju sam trebate pogledati na ovoj liniji. Mi ne bi mogli ostvariti ga još, , ali mi ćemo se vratiti na to. Budući da ova linija zapravo još uvijek treba još jednu stvar. No, do sada smo pismeni četiri linije koda. Imamo naš početak , a završava markere. Mi imamo while petlje, koja mapira Na izravno na našoj pseudocode. Gledamo sredini koja preslikava izravno na naše pseudocode. Rekao bih da to ide na sredini popisa, ova linija koda. A onda, kada idemo u sredini Popis, sljedeća stvar koju trebate učiniti je provjeriti je li naša vrijednost je tamo pseudocode smo ranije pisali. Pa kako ćemo provjeriti da li je naša vrijednost je na sredini popisa? Vi. Zašto ne to učiniti? UČENIK: Ako je naša vrijednost je je u sredini je jednak god smo postavili - Mislim jednaka jednaka - JASON Hirschhorna: To - OK. STUDENT: Nisam siguran što varijabla što smo u potrazi Jer iako je, jer - [ubačenih GLASOVI] STUDENT: [nečujan]. JASON Hirschhorna: Točno. Po funkciji deklaracije, mi smo u potrazi za vrijednošću. Dakle, mi smo u potrazi za vrijednošću u niz vrijednosti. Dakle, ti si baš dobro. Vi ćete učiniti, ako otvorena zagrada vrijednost nosač Srednji zatvorena zagrada dosegne jednaka vrijednosti, au njoj ono što trebamo učiniti? Ako je naša vrijednost je tamo, što trebamo učiniti? [ubačenih GLASOVI] STUDENT: Povratak nuli. JASON Hirschhorna: Povratak istina. STUDENT: Povratak istina. JASON Hirschhorna: Michael, što to crta učiniti? STUDENT: [nečujno] program pokrenuti svojim tijekom, a to je više, a vi ste ono što trebate učiniti? JASON Hirschhorna: Program ili što? U ovom slučaju? STUDENT: funkcija. JASON Hirschhorna: funkcija. I tako, kako bi se vratili na ono što se zove to i dati mu vrijednost, istina. Točno u pravu. Glavni. Što je povratni tip od glavne, Michael? STUDENT: int, cijeli broj? JASON Hirschhorna: int, točno. Cijeli broj. To je samo pitanje kako bi bili sigurni ti dečki su bili na vrhu. Što to obično vrati, ako sve stvari rade dobro? STUDENT: Zero. JASON Hirschhorna: Zero. Točno u pravu. UČENIK: Ako ovo samo true nema informacija što je dobio o tome - Oh, to samo govori da je ta Vrijednost je unutar polja. JASON Hirschhorna: Točno. Ovaj program ne daje informacije gdje je točno vrijednost. On je samo rekao, da, pronašli smo to, ili ne, nismo ga pronašli. Dakle, ako je broj našao, povratak istina. Pa, zapravo smo upravo učinio da stvarno brzo s tom jednom retku koda. Dakle, ja ću pomaknuti tu liniju pseudocode. STUDENT: Ne trebamo za promjenu niz? To bi trebao biti vrijednosti, a ne vrijednost, zar ne? JASON Hirschhorna: Žao mi je. Hvala Vam. STUDENT: Da. JASON Hirschhorna: Ova linija bi trebala biti vrijednosti. Točno u pravu. OK. Tako smo gledali na sredini popisa. Ako je broj našao povratak istina. Nastavljajući s našim pseudocode, ako Srednji je veća, traži napustio. Tako sam imala ovdje, ako je broj viša, traži napustio. Konstantin, možete li dati meni ova linija koda? UČENIK: Ako je vrijednost sredini - JASON Hirschhorna: Dakle, ako vrijednost - ako otvorena zagrada vrijednosti nosač Srednji blizu nosač - STUDENT: Je li manja od vrijednosti? JASON Hirschhorna: Je manje. STUDENT: Manje od vrijednosti. JASON Hirschhorna: Vrijednost. Pa, zapravo, želite provjerite je li broj - Oprostite. To je malo zbunjujuće. No, drugo ako je broj u Sredina popisu veći. STUDENT: Oh, u redu. JASON Hirschhorna: Ja ću to promijeniti. Inače, ako je srednja veća, mi želite tražiti lijevo, u redu? I što nam je činiti u to ako je stanje? STUDENT: Mogu li napraviti malu promjenu stanje, promijeniti ga na drugo, ako? JASON Hirschhorna: Inače, ako? OK. Dakle, ovaj broj će se izvršiti o istom. No, lijepa stvar o korištenju, ako, ostalo ako je, inače, ako ili ako se, inače, ako, ostalo znači da je samo jedan od onih koji će treba provjeriti, ne sva trojica, potencijalno. I to je malo čini ljepše na računalu koje je izvodi svoj program. Dakle [? Konstantin?] budemo u ovoj liniji, inače ako vrijednosti, Nosač srednje blizu nosač je veća od vrijednosti. Što trebamo učiniti? Moramo tražiti lijevo. Kako ćemo to učiniti? Ja ću vam dati start. Imamo ove dvije stvari zove počinje i završava. Dakle, ono što treba da se desi na početku? Ako želite pretraživati ​​lijevoj Popis, dobili smo našu trenutnu početak. Ono što trebamo učiniti? STUDENT: Mi smo postavili na početku na sredini plus 1. JASON Hirschhorna: Pa, ako smo traži lijevo? STUDENT: Nažalost, srednji minus - tako je završio bi srednji minus 1 i početak - JASON Hirschhorna: A što se događa na početku? STUDENT: To ostaje ista. JASON Hirschhorna: Tako smisao ostaje isti. Ako ste u potrazi lijevo, mi smo koristeći isti početak - točno u pravu. I završava? Žao nam je, što se Ponovno je završio jednaka? STUDENT: Bliski minus 1. JASON Hirschhorna: Bliski minus 1. Sada, zašto je minus 1, ne samo srednje? STUDENT: Srednji je iz slika je već, jer smo imali provjeriti da je out? JASON Hirschhorna: To je točno u pravu. Srednji je iz slike. Već smo provjerili u sredini. Dakle, mi ne želimo "u sredini", citat Citat završen, da i dalje bude u polje koje mi tražimo. Pa to je fantastično. Inače, ako nosač vrijednosti srednje veća od vrijednosti završava dosegne Srednji minus 1. Jeff, što je s ovom zadnjom linijom? STUDENT: Else. Vrijednosti srednje manja od vrijednosti? JASON Hirschhorna: Mi ćemo ti si mi daju drugi. Dakle, ako mi ne daju - UČENIK: Pa onda na početku će biti srednje plus 1. JASON Hirschhorna: Početak jednaki Srednji plus 1, ponovno, za isti Razlog da je Konstantin Dao nam je ranije. I na kraju, tko nije dao mi linija koda još? Povratak lažno, Aleha, što da pišemo ovdje? STUDENT: Povratak lažna. JASON Hirschhorna: Povratak lažna. I moramo učiniti, jer ako smo nemojte ga naći, moramo kažemo nisu ga pronašli. I rekli smo da ćemo se vratiti bool, pa ćemo svakako morati vratiti bool negdje. Tako ćemo pokrenuti taj kod. Ja sam zapravo ide - tako da smo u terminalu. Mi ćemo očistiti naš prozor. Idemo napraviti sve. Otkrili smo da je jedna pogreška. Tu je pogreška na liniji 15, očekuje se zarez na kraju deklaracija. Dakle, što sam zaboravio? STUDENT: Točka-zarez. JASON Hirschhorna: Točka-zarez zar ovdje. Mislim da je bio Tomov code. Dakle Tom, [nečujan]. Šalim se. Idemo to napraviti sve ponovno. STUDENT: Što Dropbox imenik trebamo se u za to? JASON Hirschhorna: Pa što možete samo gledati tu bit. Ali opet, ako su željeli da se to kod u svoj pset3 imenik pokušati to se, to je ono što sam učinio. Ako ćete primijetiti ovdje - Žao nam je, dobro pitanje. [? LS,?] Imam ovdje find.c kod iz ovotjednog distro koda. Imam helpers.h. Imam Make datoteku da sam zapravo uredio malo da i te nove slika pišemo. Sve to kod će biti dostupna, ne Distribucija kod, a novi Make datoteku, novi helpers.h datoteka će biti dostupna online za preuzimanje. Opet, kako su to Tipski imamo. Tako bi sve, po toj liniji, čini naći, binarna, izbor mjehur - čini sva trojica i sastavlja u to izvršni kod otkriće. Dakle, općenito, ne želimo to ravno na check50. Želimo pokrenuti neke testove na svoje. No, samo tako možemo ubrzati taj malo, check50 2013 pset3.find će proći u helpers.c-- moja loša. Nemam da je upravo sada. Tako smo zapravo ide pokrenuti kôd za real. Usage.find /, znate što to znači? STUDENT: Potrebna vam je drugi komandna linija na njemu. JASON Hirschhorna: trebam Drugi naredbenog retka. I po specifikaciji, trebam ući ono što tražimo. Pa pogledajmo za 42. Mi ćemo ga zadržati u sortiran, jer smo nisu napisali funkciju sortiranje još - 42, 43, 44. I Kontrola D nisu pronašli igla u plastu sijena. To je loše. To je definitivno postoji. Idemo probati nešto drugo. Možda je to zato što sam stavio je na početku. Učinimo 41, 42, 43. Tu smo. To ga pronašao. Idemo ga stavili na kraju sada, samo tako da možemo biti temeljit - 40, 41, 42. Niste pronašli iglu. Pa sam to spomenuo ranije. Nažalost, znao sam to što će se dogoditi. No, za pedagoške svrhe, to je dobro da se to istraži. To ne radi. Iz nekog razloga, ne mogu ga naći. Mi znamo što je unutra, ali nismo ga pronaći. Dakle, jedna stvar koju smo mogli učiniti je proći kroz GDB ga naći, ali ne bilo tko, bez prolazi kroz GDB, imaju Osjećaj gdje smo zeznuli? [? Madu? ?] STUDENT: Mislim da bi to moglo biti, kada završava je jednak početku, a to je Samo jedan popis elemenata. Onda ga samo ga ignorira, umjesto zapravo ga provjere. JASON Hirschhorna: To je točno u pravu. Kad je završio jednako početak, zar ne Još uvijek ima element u našem popisu? STUDENT: Da. JASON Hirschhorna: Da, u stvari, mi imati jedan i samo jedan element. I to će se najvjerojatnije dogoditi kada, po koda smo testirali, mi smo na Prednji dio plastu sijena ili na kraj plastu sijena. To je mjesto gdje početak i kraj će jednaka jedan, s binarnim pretragu. Tako je u ta dva slučaja nije radilo, , jer je završio bio je jednak početku. Ali, ako je završio jednak početku, to while petlja izvršiti? To ne. A mogli smo provjeriti da opet kroz GDB. Pa kako možemo popraviti ovaj kod, jer kada je završio, a jednaka na početku, želimo to while petlja pokrenuti. Pa što fix možemo učiniti da se postroje 18? STUDENT: [nečujno] veća od ili jednaka. JASON Hirschhorna: Točno u pravu. Dok je kraj je veća nego ili jednak početka. Tako sada, mi bi bili sigurni da se to kutak slučaj na kraju. Pa da vidimo. Idemo pokrenuti ovaj još jednom. Učinimo sve. Opet, morat ćete se samo pratite ovdje zajedno. Nađi 41 ovaj put. Samo što bi dosljedan. Traži 42. Idemo ga stavili na početku - 42, 43, 44. Pronašli smo ga. Tako da je to doista promjene trebamo napraviti. To je puno kodiranja smo samo učinio, binarno pretraživanje. Da li itko ima bilo kakvih pitanja prije I poći u linijama smo pisali u pretraživanje po binarnom ili kako smo mislili što nismo shvatiti? Prije nego pređemo na, također želim naglasiti iz toga i veliki, možemo mapirati naš pseudo-koda jedan jedan na našoj koda. Mi smo imali tu škakljivo shvatiti s počinje i završava. Ali je ne to shvatio, vi bi napisali prilično mnogo identičan broj, osim te dvije gornje linije. I onda bi shvatio kad što ga je napravio u čekovima i slučajeva da vam je potrebno nešto drugo. Dakle, čak i ako je slijedio naš pseudo-koda liniju na liniji, što bi mi dobivši sve osim dvije linije kodirati li potrebno pisati. I ja bih biti spremni kladiti da vi momci Sve bi to shvatio prilično brzo, da li je potrebno staviti nekakva dva protivnička igrača tamo shvatiti gdje ste bili. To opet je moć radi pseudo-koda ispred vremena. Dakle, što možemo učiniti logiku, a onda možemo brinuti o sintaksi. Da smo bili zbunjeni o logici dok je pokušavao napisati ovaj kod u C, mi bi dobivši sve zabrljao. A onda ćemo se raspitivati ​​o logika i sintakse i umreženje ih sve zajedno. I mi bi imati stečen izgubljena u tome što se brzo može postati vrlo težak problem. Pa krenimo sad u izbor vrste. Imamo 20 minute. Dakle, imam osjećaj da neće biti u mogućnosti dobiti kroz sve selekcije vrste i mjehurića vrsta. No, neka nas barem pokušati završiti odabir vrsta. Dakle provesti izbor vrsta pomoću Sljedeće funkcije deklaraciju. Opet, ovo je preuzet iz Problem postaviti specifikaciju. Interesi vrijednosti je zagrade, je niz brojeva. I int.n je veličina tog polja. Izbor vrsta ide sortirati ovaj niz. Dakle, po našem mentalnom modelu izbora vrsta, vučemo - Prvo, idemo po popisu prvi Vrijeme, naći najmanji broj, staviti ga na početku, naći drugi Najmanji broj, staviti ga u Druga pozicija ako želimo vrsta u rastućem poretku. Ja ne tjera da pišete pseudo-koda upravo sada. No, prije nego što smo to kod kao klasa u pet minuta, mi ćemo napisati pseudo-koda, tako da imamo neki osjećaj od kuda idemo. Dakle, pokušati napisati pseudo-koda na svoju ruku. A onda pokušati pretvoriti da pseudo-koda u kodu. Mi ćemo to učiniti kao grupa u pet minuta. I naravno, da mi javite ako Imate li pitanja. STUDENT: To je to? JASON Hirschhorna: Pogledajte kako daleko možete dobiti u više od dvije minute. Ja razumijem da nećeš biti u mogućnosti završiti. No, mi ćemo ići preko toga kao skupina. Svi ste kodiranja tako [nečujan], pa sam Žao nam je za pauzu što radite. No, idemo kroz to kao grupa. I opet, binarno pretraživanje, svi daju mi je jedan, ako ne i više linija koda. Hvala vam na tome. Mi ćemo učiniti istu stvar Ovdje, kod zajedno kao grupa. Dakle, izbor vrsta - idemo pisati neke brze pseudo-koda. Po mentalnom modelu, može mi netko dati Prva linija pseudo-kod, molim te? Što želim učiniti? STUDENT: Dok je popis ne radi. JASON Hirschhorna: OK, dok je Popis je izvan upotrebe. A što misliš "izvan funkcije?" STUDENT: Dok [nečujan] nije riješeno. JASON Hirschhorna: Dok je popis ne radi, što nam je činiti? Daj mi drugu liniju, molim te, Marcus. UČENIK: Pa naći sljedećeg Najmanji broj. To će biti uvučen. JASON Hirschhorna: Pa naći Sljedeći najmanji broj. I onda netko drugi? Nakon što smo pronašli pokraj najmanji broj, što nam je činiti? Ja ću reći pronašli najmanji broj. To je ono što želimo učiniti. Dakle, naći najmanji broj. Onda što nam je činiti? STUDENT: [nečujan] na početku. JASON Hirschhorna: Žao mi je? STUDENT: Stavite ga u početku popisa. JASON Hirschhorna: Pa to mjesto u početak popisa. I što nam je činiti kako bi se stvar to je bilo u početku na popisu, zar ne? Mi prepisati nešto. Dakle, gdje smo stavili to? Da, Anna? STUDENT: Gdje najmanji broj bio? JASON Hirshhorn: Pa stavi početak popisa kojoj najmanji broj je bio. Dakle, dok se popis ne radi, naći Najmanji broj, stavite ga u početak popisa, stavio početku popisa kojoj najmanji broj je bio. Marcus, možeš preformulirati ovu liniju a popis je iz reda? STUDENT: Dok su brojevi nisu razvrstani? JASON Hirshhorn: U redu, tako da bi se Znam da su brojevi nisu razvrstani, što trebamo učiniti? Koliko nam je potrebno da se proći kroz ovaj popis? UČENIK: Pa mislim da za petlje, ili a, dok su brojevi provjeriti je manje od duljine popisa? JASON Hirshhorn: U redu, to je dobro. Mislim da misphrased moje pitanje loše. Samo sam pokušavao doći ćemo morati ići kroz cijeli popis. Dakle, dok se popis ne radi, za mene, teško je mapirati na. Ali u osnovi, to je kako Mislim da o tome. Prođite kroz cijeli popis, naći Najmanji broj, stavite ga u na početku - zapravo, u pravu si. Idemo ih oboje stavio. Dakle, dok se popis ne radi, mi morati proći kroz cijeli popis Jednom, naći najmanji broj, mjesto se u početku popisa, stavi početak popisa kojoj najmanji broj je bio, a onda, ako Popis je još uvijek izvan reda, mi smo Moram ići kroz to Proces opet, zar ne? Zato izbor sortiranje, Big-O Runtime od odabira vrste, bilo tko? STUDENT: n na kvadrat. JASON Hirshhorn: n na kvadrat. Jer kao što je Marcus i ja shvatila ovdje ćemo morati proći kroz popis popis broj puta. Tako će kroz nešto od duljine n n broj puta je u stvari n na kvadrat. Dakle, ovo je naša pseudocode. To izgleda vrlo dobro. Da li itko ima bilo kakvih pitanja o pseudocode? Jer zapravo izbor vrsta trebala Vjerojatno se jedna do jedan, kod od pseudocode. Dakle, bilo pitanja o Logika pseudocode? Molimo pitajte ga sada. Izbor vrsta - a popis je iz reda, idemo proći kroz njega i pronaći najmanji svaki put i staviti ga u prednjem. Dakle, dok se popis ne radi, može netko bi mi tu liniju koda koji nije mi nije dao liniju koda, ali, molim te? To zvuči kao što? STUDENT: To je za petlju. JASON Hirshhorn: To zvuči Sviđa za petlju. U redu, možete li mi dati za petlje? Za - STUDENT: i jednak je 0. JASON Hirshhorn: ja ili - Što nam nedostaje? Što se događa ovdje? STUDENT: Int. JASON Hirshhorn: Točno. (Int i = 0; - STUDENT: i