ROB Bowden: Saluton, mi estas Rob Bowden, kaj tuj parolos quiz0. Do, unua demando. Tiu estas la demando, kie vi bezonas por kodigi la nombro 127 en la duuma bulboj. Se vi volas, vi povus fari la regula konvertiĝo el bi-- aŭ el dekuma al duuma. Sed tio probable iri preni multan tempon. Mi volas diri, vi povis diveni ke, OK, 1 estas en tie, 2 estas en tie, 4 estas en tie, 8 estas en tie. Facilan vojon, 127 estas 128 minus unu. Tio plej maldekstra ampolo estas la 128-bito. Do 127 estas vere ĝuste ĉiuj de la aliaj ampoloj, ekde tiu estas la plej maldekstra ampolo minus 1. Estas tio por tiu demando. Demando unu. Do kun 3 bitoj vi povas reprezentas 8 distingaj valoroj. Kial, do, estas 7 la plej nenegativaj dekuma entjero povas reprezenti? Nu, se ni povas nur reprezentas 8 distingaj valoroj do kion ni tuj estos reprezenti estas 0 tra 7. 0 okupas unu el la valoroj. Demando du. Kun n bitoj, kiom distinga valoroj povas reprezenti? Do kun n bitojn, oni havas 2 eblaj valoroj por ĉiu bito. Do ni havos 2 eblaj valoroj por la unua bito 2 eblaj valoroj por la dua, 2 ebla por la tria. Kaj tiel tio estas 2 fojoj 2 fojoj 2, kaj fine la respondo estas 2 al la n. Demando tri. Kio 0x50 en duuma? Do memoru tio deksesuma havas tre simpla konvertiĝo al duuma. Do jen, ni nur bezonas rigardi la 5 kaj la 0 sendepende. Do kio estas 5 en duuma? 0101, estas la 1 biton kaj la 4 bitoj. Kio estas 0 en duuma? Ne malfacila. 0000. Do ĝuste kunmeti ilin, kaj tio estas la plena nombro de duuma. 01010000. Kaj se vi volas vi povus forlevu ke plej maldekstra nulo. Estas pala. Do tiam alternative, kio estas 0x50 en dekuma? Se vi volas, vi could-- se vi estas pli komforta kun la duuma, vi povus preni ke duumaj respondon kaj igi ke en dekuma. Aŭ ni povus simple memori ke deksesuma. Tiel ke 0 estas en la 0-a loko, kaj la 5 estas en la 16 al la unua loko. Do jen ni havas 5 fojoj 16 al la unue, plus 0 fojojn 16 al la nulo, estas 80. Se vi rigardis la titolo al la demando, estis CS 80, kiu estis speco de aludo al la respondo al ĉi tiu problemo. Demando kvin. Ni havas ĉi Scratch skripto, kiu estas ripetante 4 fojoj arakido butero ĵeleo. Nu do kiel ni nun kodon en C? Nu, ni havas here-- la parto en negrita Estas la sola parto kiu devis apliki. Do ni havas 4 buklo ke'S looping 4 tempoj, printf-ing arakido butero ĵeleo, kun nova linio kiel la problemo petas. Demando ses, alia Scratch problemon. Ni vidas, ke ni estas en eterna buklo. Ni diris la variablo i kaj tiam pliigante i per 1. Nun ni volas fari tion en C. Estas multnombraj manieroj ni povus fari tion. Tie okazis Kodo ĉiam buklo kiel dum (vera). Do ni deklaros la variablo i, simple kiel ni havis variablo i en Scratch. Klarigu la variablo i, kaj ĉiam dum (vera), ni diru la variablo i. Do printf% i-- aŭ vi povus esti uzita% d. Ni diru, ke variablo, kaj tiam pliigo ĝi, i ++. Demando sep. Nun ni volas fari iun tre simila Mario dot c el problemo starigis unu. Ni volas presi tiujn hashtags, ni volas presi kvin per tri rektangulo de tiuj hashes. Do kiel ni faros tion? Nu, ni donos al vi tutan faskon de kodo, kaj vi nur devas plenigi la truon krado funkcio. Do kion signifas PrintGrid aspektas? Nu vi estas preter la larĝo kaj la alto. Do ni havas eksteran 4 buklo, tio looping super ĉiuj el la vicoj de ĉi krado, ke ni volas presi. Do ni havos la interlingva ingita 4 buklo, tio pres super ĉiu kolumno. Do por ĉiu vico, ni presi por ĉiu kolumno, sola hash. Tiam ĉe la fino de la vico ni presi sola nova linio por iri al la sekva linio. Kaj tio estas por la tuta reto. Demando ok. Funkcio kiel PrintGrid laŭdire havas flankan efikon, sed ne reveno valoro. Klarigi la distingon. Do ĉi dependas sur vi memorante kia kromefikon estas. Nu, rondveturo value-- Ni scias PrintGrid ne havi reveno valoro, ekde ĉi tie ĝi diras malplenon. Do io kiu revenu malplena vere ne revenos nenion. Do kio estas la kromefikon? Nu, flanka efekto estas ion tian persistas post la funkcio randoj kiu ne ĝuste revenis, kaj ne nur de la eniroj. Do, ekzemple, ni povus ŝanĝi tutmonda variablo. Tio estus kromefikon. En ĉi tiu aparta kazo, tre grava flanko efekto estas videbligi al la ekrano. Do kiu estas flanka efiko ke PrintGrid havas. Ni presas tion al la ekrano. Kaj vi povas pensi ke kiel kromefikon, ekde tiu estas io kion persistas post tiu funkcio finiĝas. Tio estas io ekster la medio de tiu funkcio, ke finfine estas ŝanĝata, La enhavon de la ekrano. Demando naŭ. Konsideri la programo sube, al kiu linio nombroj estis aldonitaj por pro diskuto. Do en tiu programo, ni estas nur nomante GetString, stokante ĝin en tiu variablo s, kaj tiam videbligi ke variablo s. OK. Do klarigi kial linio oni ĉeestas. #include cs50 dot h. Kial ni bezonas #include cs50 dot h? Nu ni vokas la GetString funkcio, kaj GetString difiniĝas en la cs50 biblioteko. Do se ni ne havis #include cs50 dot h, ni akirus ke implica deklaro de la GetString funkcio eraro de la tradukilo. Do ni bezonas por inkludi la library-- ni bezonas por inkludi la kaplinio dosieron, alie la tradukilo ne rekoni ke GetString ekzistas. Klarigi kial linio du ĉeestas. Do normo io dot h. Estas ĝuste la sama kiel la antaŭa problemo, krom anstataŭ kontraktanta kun GetString, ni parolas pri printf. Do se ni ne diris ke ni bezonas inkludi normo io dot h, tiam ni ne povos uzi la printf funkcio, ĉar la tradukilo ne volis scii pri tio. Why-- kio estas la signifo de malplena en linio kvar? Do jen ni havas int main (void). Tio nur diras ke ni Ili ne ricevas neniun komandlinio argumentoj por ĉefa. Memoru ke ni povus diri int ĉefa int argc kordo argv krampoj. Do jen ni simple diri malplena diri ni ignoras komandlinio argumentoj. Klarigi, kun respekto al la memoro, precize kio GetString en linio ses revenas. GetString revenas blokon memoro, tabelo de signoj. Ĝi estas vere reveni al montrilon al la unua karaktero. Memoru ke kordoj estas char stelo. Do s estas puntero al la unua gravulo ajn la kordo estas kiun la uzanto eniris en la klavaro. Kaj tiu memoro pasas al malloced, tiel ke memoro estas en la havaĵo. Demando 13. Konsideri la programo sube. Do ĉiuj ĉi programo faras estas printf-ing 1 dividita per 10. Do kiam kompilis kaj ekzekutitaj, ĉi programo eligoj 0.0, kvankam 1 dividita per 10 estas 0.1. Do kial 0.0? Nu, tio estas pro tio de entjera divido. Tiel 1 estas entjero 10 estas entjero. Do 1 dividita per 10, ĉio estas traktata kiel entjeroj, kaj en C, kiam ni faros entjera divido, ni senpintigas ajna dekuma punkto. Do 1 dividita per 10 estas 0, kaj tiam ni provas presi tion kiel float, do nulo presita kiel float estas 0.0. Kaj tio estas kial ni atingos 0.0. Konsideri la programo sube. Nun ni presi 0.1. Do ne entjera divido, Ni nur presi 0.1, sed ni videbligi ĝin 28 dekumaj lokoj. Kaj ni preni ĉi 0,1000, tuta aro da de nuloj, 5 5 5, bla bla bla. Do la demando tie estas kial ĝi presi ke, anstataŭ ĝuste 0.1? Do la kialo jen nun glitpunktaj imprecision. Memoru ke float nur 32 bitoj. Do ni povas nur reprezenti finia nombro de glitpunktaj valoroj kun tiuj 32 bitojn. Nu tie estas finfine malfinie multaj glitpunktaj valoroj kaj ekzistas malfinie multaj flotante punkto valorojn inter 0 kaj 1, kaj ni evidente povis reprezentas eĉ pli valoroj ol tio. Do ni devas fari oferojn al povi reprezenti plej valorojn. Do valoron kiel 0,1, ŝajne ni ne povas reprezenti ke ĝuste. Do anstataŭ reprezenti 0.1 ni faru bona kiu povas reprezenti ĉi 0.100000 5 5 5. Kaj tio estas sufiĉe proksima, sed por multaj aplikoj Vi devas maltrankviligi glitpunktaj imprecision, ĉar ni simple ne povas reprezenti ĉiuj flosante punktoj ekzakte. Demando 15. Konsideri la kodon sube. Ni nur presi 1 plus 1. Do estas nenia artifiko tie. 1 plus 1 taksas al 2, kaj tiam ni presi tion. Tiu simple presu 2. Demando 16. Nun ni presi la karaktero 1 plus la karaktero 1. Do kial faras ĉi ne presi la saman aferon? Nu la karaktero 1 plus la karaktero 1, la karaktero 1 havas ASCII valoro 49. Do tio estas vere dirante 49 plus 49, kaj fine tiu tuj presi 98. Do tio ne presi 2. Demando 17. Kompletigi la apliko de nepara malsupre en tia vojo ke la funkcio redonas vera se n estas nepara kaj malvera se n estas vespero. Tiu estas granda celo cxar la mod operatoro. Do ni prenu nian argumento n, se n mod 2 egalas 1, bone tio signifas ke n dividita per 2 havis restaĵon. Se n dividita per 2 havis restaĵon, ke signifas ke n estas nepara, do ni revenos vera. Alie ni revenos malvera. Vi ankaŭ povus esti farita n Mod 2 egaluloj nulo, revenu falsa, alie redoni vera. Konsideri la rekursia funkcio sube. Do se n estas malpli ol aŭ egala al 1, revenu 1 alie reveno n fojoj f n minus 1. Do kio estas tiu funkcio? Nu, tio estas nur la faktoriala funkcio. Tiu estas bonguste reprezentitaj kiel n faktorialo. Do pridubi 19 Nun, ni volas prenu ĉi rekursia funkcio. Ni volas fari ripeta. Do kiel ni faru tion? Bone por la ŝablono solvon, kaj denove ekzistas multnombraj manieroj vi povus esti farita ke ni komencu per tiu int produkto estas 1. Kaj laŭlonge ĉi por buklo, ni iras esti multiplikante produkto finfine finas kun la plena faktorialon. Do por int i egalas 2, i estas malpli ol aŭ egala al n, i ++. Vi povus mirantaj kial i egalas 2. Nu, memoru, ke ĉi tie ni devas certigi nia bazo kazo estas korekta. Do se n estas malpli ol aŭ egala 1, ni ĵus revenis 1. Do ĉi tie, ni komencos je i egalas 2. Nu, se i estis 1, tiam the-- aŭ se n estis 1, tiam la por buklo ne ekzekuti ajn. Kaj tial ni volas nur reveno produkto, kiu estas 1. Simile, se n estis io malpli ol 1-- se ĝi estis 0, negativa 1 whatever-- ni volas ankoraŭ reveni 1 kiu estas ĝuste kio la rekursiaj versio faras. Nun, se n estas pli granda ol 1, do ni iras fari almenaŭ unu ripeto de ĉi maŝo. Tiel diru n estas 5, tiam ni faros produkto tempoj egalas 2. Do nun produkto estas 2. Nun ni tuj faros produkto tempoj egalas 3. Nun estas 6. Produkto tempoj egalas 4, nun estas 24. Produkto tempoj egalas 5, nun estas 120. Do tiam finfine, ni reveni 120, kiu estas ĝuste 5 faktorialon. Demando 20. Tio estas la unu kie vi devas plenigi en tiu tablo kun ajna donita algoritmo, tio kion ni jam vidis, ke zonas tiuj algoritma run fojoj tiuj asimptota run fojojn. Do kio estas algoritmo kiu Estas omega de 1, sed granda O de n? Do povus esti senfine multajn respondojn tie. Kiu ni vidis probable plej ofte estas nur lineara serĉo. Do, en la plej bona kazo scenaro, la eron ni serĉas estas en la komencante de la listo kaj tiel en omega el 1 paŝojn, ni unue kontroli, ni nur tuj revenos kiun ni trovis la elementon. En la plej malbona kazo scenaro, la eron estas ĉe la fino, aŭ eron ne estas en la listo iel ajn. Do ni devas serĉi la tutan liston, ĉiuj n elementoj, kaj tial ĝi estas o de n. Do nun estas io tio estas ambaŭ omega n log n, kaj granda O de n log n. Nu la plej grava afero ni vidis tie estas kunfandi varo. Do kunfandi speco, memoru, estas finfine theta de n log n, kie theta difiniĝas se ambaŭ omega kaj granda O estas la sama. Ambaŭ n log n. Kio estas iu kiu estas omega de n, kaj O de n kvadratoj? Nu, denove ne estas multnombraj eblaj respondoj. Tie okazos diri bobelo varo. Inserción speco ankaŭ laboros tie. Memoru ke bobelo speco havas tiun optimumigo kie, Se vi estas kapabla akiri tra la tutan liston sen neceso fari ajna interŝanĝojn do bone, ni povas tuj reveni ke la lerta estis ordo por komenci kun. Do, en la plej bona kazo scenaro, estas nur omega de n. Se ĝi ne estas nur bele ordigita listo komenci kun, tiam ni havi O de n kvadratoj interŝanĝojn. Kaj fine, ni havas selektadon speco por n kvadratoj, ambaŭ omega kaj granda O. Demando 21. Kio estas entjero overflow? Nu denove, simila al pli fruaj, Ni havas nur finie multaj bitoj reprezenti entjero, do eble 32 bitoj. Supozu ke ni havas subskribita entjero. Tiam finfine la plej alta pozitiva nombro povas reprezenti estas 2 al la 31 minus 1. Do kio okazas se ni provas tiam pliigo ke entjero? Nu, ni iras, por foriri de 2 al la 31 minus 1, la tutan vojon malsupren al negativa 2 al la 31. Do tiu entjero overflow estas kiam vi konservos pliigante, kaj finfine ne povas akiri ajnan pli altan kaj nur kovras la tutan vojon reen ĉirkaŭe al negativa valoro. Kio pri buffer overflow? Do buffer overflow-- memoru kion buffer estas. Estas nur eron de memoro. Io kiel tabelo estas bufro. Do buffer overflow estas kiam provu aliri memoro preter la fino de tiu tabelo. Do se vi havas tabelo de amplekso 5 kaj vi provu aliri tabelo krampo 5 aŭ krampo 6 aŭ krampo 7 aŭ io preter la fino, aŭ eĉ ion below-- tabelo krampo negativa 1-- ĉiuj el tiuj estas bufro superfluas. Vi tuŝis memoro en malbonaj manieroj. Demando 23. Do en ĉi tiu necesas implementar strlen. Kaj ni diras al vi ke vi povas supozi s ne estos nula, tial vi ne devas fari ajnan ĉeko nula. Kaj ekzistas multnombraj manieroj Vi povus fari tion. Ĉi tie ni nur prenu la simpla. Ni komencu per nombrilo, n. n estas rakonti cuantos karakteroj ekzistas. Do ni komencu je 0, kaj poste ni persisti super la tutan liston. Ĉu s krampo 0 egalas al la null terminator karakteron? Memoru ni serĉas la nula terminator karaktero determini kiel longe nia kordoj estas. Kiu tuj chesigi ajna rilatajn kordo. Tia estas la krampo 0 egalaj al la nula terminator? Se ĝi ne estas, tiam ni tuj rigardi s krampo 1, s krampo 2. Ni dauxre iros ĝis ni trovi la nulan finilo. Iam ni trovis ĝin, tiam n enhavas la tuta longo de la kordo, kaj ni povas nur redoni tion. Demando 24. Do tiu estas kie vi devi fari la komercon for. Do unu afero estas bona en unu vojo, sed en kia maniero estas malbona? Do jen, kunfandi speco inklinas esti pli rapida ol bobelo varo. Dirinte that-- bone, tie Estas multnombraj respondojn tie. Sed la ĉefa estas kiu bobelo speco Estas omega de n por ordo listo. Memoru ke tablo ni vidis antaŭe. Do bobelo ordigas omega de n, la plej bona kazo scenaro cxu estas kapabla simple transiru la liston unufoje, determini hey afero estas jam ordigataj kaj reveno. Kunfandi speco, negrave kio vi faras, estas omega n log n. Do por ordo listo, bobelo speco tuj estos rapida. Nun kio pri ligitaj listoj? Do ligillisto povas kreski kaj retiri por persvadi kiel multaj eroj kiel bezonataj. Dirinte that-- tiel kutime la rekta komparo tuj estos kunligita listo kun tabelo. Do kvankam arrays povas facile kreski kaj retiri por persvadi kiel multaj eroj drajvo, kunligita listo kompare al array-- oni tabelo havas hazarda aliro. Povas indekson en ajna aparta ero de la tabelo. Do por ligillisto, ni ne povas nur iri al la kvina ero, ni devos trairi la komenco ĝis ni atingos la kvina ero. Kaj tio tuj neebligos nin el fari iun kiel duuma serĉo. Parolante pri duuma serĉo, duuma serĉo inklinas esti pli rapide ol lineara serĉo. Dirinte that-- tiel, unu ebla estas ke vi ne povas fari duuma serĉu en ligitaj lertaj, vi nur povas fari ĝin sur arrays. Sed verŝajne pli grave, vi ne povas plenumi duuma serĉo sur tabelo kiu ne ordo. Upfront vi eble bezonas ordigi la tabelo, kaj nur tiam povas vi faru duuma serĉo. Do se via afero ne ordo por komenci, tiam lineara serĉo povus esti rapida. Demando 27. Do konsideru la programo sube, kiuj estos en la proksima diapozitivo. Kaj jen estas la unu kie ni estas tuj volas eksplicite deklari la valorojn de pluraj variabloj. Do, ni rigardu tion. Do linio unu. Ni havas int x estas 1. Tio estas la nura afero kiu okazis. Do en linio, ni vidas en nia tablo, y, a, b, kaj tmp estas ĉiuj nigra for. Do kio estas x? Nu, ni nur starigis lin egala al 1. Kaj tiam vicigi du, nu, Ni vidos ke y estas fiksita al 2, kaj la tablo estas jam plenigis por ni. Tiel x estas 1 kaj y estas 2. Nun, linio tri, ni estas nun ene la interŝanĝan funkcio. Kion ni pasas por interŝanĝi? Ni pasis ampersand x por a, kaj ampersand y por b. Kie la problemo antaŭe asertis, ke la adreso de x Estas 0x10, kaj la adreso de y estas 0x14. Do a kaj b estas egala al 0x10 kaj 0x14, respektive. Nun je linio tri, kio estas x kaj y? Nu, nenio ŝanĝiĝis proksimume x kaj y en tiu punkto. Kvankam ili estas ene ĉefa stako, Ili ankoraŭ havas la saman valoroj antauxe. Ni ne modifita ajnan memoron. Tiel x estas 1, y estas 2. Bone. Do nun ni diris int tmp egalaj star a. Do en linio kvar, ĉiu Estas la sama krom tmp. Ni ne ŝanĝis ajn valoroj nenion krom tmp. Ni opcio tmp egalaj star a. Kio estas stelo pli? Nu, punktoj x, do star oni tuj egala x, kiu estas 1. Do ĉio estas kopiita malsupren, kaj tmp estas fiksita al 1. Nun la sekva linio. Star a egalas stelo b. Do por linio five-- bone denove, ĉio Estas la sama krom ajn stelon a estas. Kio estas stelo pli? Nu, ni nur diris stelo a estas x. Do ni ŝanĝi x al egala stelo b. Kio estas stelo b? y. b punktoj al y. Do stelo b estas y. Do ni opcio x egalas al y, kaj ĉio alia estas sama. Do ni vidas en la sekva vico x estas nun 2, kaj la resto estas nur kopiis suben. Nun en la sekva linio, stelo b egalas tmp. Nu, ni nur diris stelo b estas y, tial ni opcio y egalas al tmp. Ĉio alia estas la sama, tial ĉiu prenas kopiitaj suben. Ni opcio y egalas al tmp, kio estas unu, kaj ĉio alia estas sama. Nun fine, la linio sep. Ni estas reen en la ĉefa funkcio. Ni post swap estas finita. Ni perdis, b, kaj tmp, sed finfine ni ne ŝanĝi ĉiujn valorojn de io ĉe tiu punkto, ni simple kopiu x kaj y suben. Kaj ni vidos ke x kaj y estas Nun 2 kaj 1 anstataŭ 1 kaj 2. La interŝanĝa sukcese ekzekutita. Demando 28. Supozu ke vi renkontas La erarmesaĝoj malsupre dum oficejo horoj sekva jaro kiel CA aŭ TF. Konsilus kiel ripari ĉiu el tiuj eraroj. Do nedefinita referencon GetString. Kial povus vi vidas tion? Nu, se studento estas uzanta GetString en sian kodon, ili adekvate Hash inkludis cs50 dot h inkludi la cs50 biblioteko. Nu, kion fari ili bezonas korekti tiun eraron? Ili bezonas fari strekon lcs50 ĉe la komandlinio kiam ili estas kompilita. Do se ili ne transiros tin haltostreko lcs50, ili estas ne tuj havos la fakta kodo kiu implementa GetString. Demando 29. Implice deklarante biblioteko funkcio strlen. Nu tiu nun, ili ne havas faris la taŭgan hash inkluzivi. En ĉi tiu aparta kazo, la kaplinio dosieron ili bezonas por inkludi estas kordoj dot h, kaj inkludante kordo dot h, hodiaŭ la student-- nun la tradukilo havas aliron al la deklaroj de strlen, kaj ĝi scias ke via kodo uzas strlen korekte. Demando 30. Pli procento konvertiĝoj ol datumoj argumentoj. Do kio estas tio? Memoru ke tiuj procentoj signs-- kiom ili estas adekvataj al printf. Do en printf ni povus percent-- ni povus presi ion kiel procento i backslash n. Aŭ ni povus presi kiel procento i, spaco, procento i, spaco, procento i. Do por ĉiu el tiuj procento signoj, ni bezonas pasi variablo fine de printf. Do se ni diras printf paren procento i backslash n proksime paren, nu, ni diru, ke ni estas tuj presi entjero, sed poste ni ne pasas printf entjero al reale presi. Do jen pli procento konvertiĝoj ol datumoj argumentoj? Tio diras, ke ni havas tutan faskon da por cent, kaj ni ne havas sufiĉe da variabloj efektive plenigi tiujn por cent. Kaj tiam definitive, por demando 31 definitive perdis 40 bitokoj en unu blokojn. Do tio estas Valgrind eraro. Tiu diras ke ie en via kodo, vi havas atribuo kiu estas 40 bajtojn grandajn tiel vi malloced 40 bajtoj, kaj vi neniam liberigita ĝin. Plej verŝajne vi nur bezonos trovi iun memoro liko, kaj trovi kie necesas liberigi tiu bloko de memoro. Kaj pridubi 32, nevalida registran de grandeco 4. Denove ĉi estas Valgrind eraro. Ĉi tio ne devas fari kun memoro fugoj nun. Tio estas, la plej likely-- Mi volas diri, estas ia nevalida memoro rajtoj. Kaj plej verŝajne tiu estas iuj ia buffer overflow. Kie vi havas tabelo, eble entjera tabelo, kaj ni diras ke estas de amplekso 5, kaj vi provu tuŝi tabelo krampo 5. Do se vi provas skribi por ke valoro, tio ne estas peco de memoro ke vi efektive havas aliron al, kaj tial vi estas iranta akiri tiun eraron, dirante nevalida registran de grandeco 4. Valgrind tuj rekonos vi provas tuŝi memoro netaŭge. Kaj tio estas por quiz0. Mi Rob Bowden, kaj ĉi tiu estas CS50.