[Powered by Google Translate] [Avsnitt 4] [mindre bekväm]
[Nate Hardison] [Harvard University]
[Detta är CS50.] [CS50.TV]
>> Okej, välkommen tillbaka till avsnitt.
I denna veckas avsnitt ska vi göra ett par saker.
Vi kommer till det första återblick problembild 2,
vilket är Caesar och Vigenère problembild.
Och sedan ska vi dyka in Quiz 0 omdöme
och spendera lite tid regummering vad vi har pratat om
i varje föreläsningarna hittills, och vi kommer också att göra några problem
från föregående års frågesporter.
På så sätt ni har ett bra sätt att förbereda sig för detta.
>> Till att börja, jag startat upp ett par bra lösningar
för föregående problemet inställd, ställ Problem 2, i detta utrymme.
Om ni träffa alla här länken,
och om du klickar på mitt namn och klicka på min första översyn
ser du caesar.c, vilket är exakt vad jag tittar på.
Låt oss tala om det här verkligen snabbt.
Detta är bara en provlösning.
Detta är inte nödvändigtvis den perfekta lösningen.
Det finns många olika sätt att skriva detta,
men det finns några saker som jag ville lyfta fram
som jag såg när jag klassificering, vanliga misstag som jag tror
denna lösning gör ett mycket bra jobb med hantering.
>> Den första är att ha någon form av header kommentar längst upp.
På linjerna 1 till 7 du ser detaljer,
exakt vad detta program gör.
En god praxis när du skriver C-kod
oavsett om ditt program finns i en enda fil eller
oavsett om det är delad över flera filer är att ha någon form av
orientera kommentaren överst.
Det är också för människor som går ut och skriva kod i den verkliga världen.
Det är där de sätter copyrightinformation.
Nedan är # omfattar.
På rad 16 finns det # define, som vi ska återkomma till i bara lite.
Och sedan när funktionen startar när stora starter,
eftersom detta program har alla i en enda funktion
den allra första som händer, och detta är mycket idiomatisk och typiskt för ett C-program
som tar i kommandoraden argument, är att det omedelbart kontrollerar
>> för argumentet räkna, argc.
Just här ser vi att detta program väntar 2 argument exakt.
Kom ihåg att det är det första argumentet som är det speciella en
det är alltid namnet på det program som är körs,
Namnet på den körbara filen.
Och så vad detta innebär är det förhindrar användaren från att köra programmet
med fler eller färre argument.
Anledningen till att vi vill kontrollera detta direkt beror
Vi kan faktiskt inte komma åt denna argv array här tillförlitligt
tills vi har kontrollerat att se hur stort det är.
>> En av de vanligaste felen jag såg var människor omedelbart skulle gå i
och grab argv [1].
De skulle ta nyckeln argumentet ur matrisen och gör en till jag kolla på det,
och då de skulle göra testet för argc samt nästa test,
huruvida eller inte den första argumentet verkligen var ett heltal på samma gång,
och det inte fungerar eftersom det i fall att det inte finns några medföljande argument
du kommer att ta tag ett argument som inte finns eller försöker ta en som inte finns.
>> Den andra stora sak som du kommer att märka är att
du alltid vill skriva ut någon form av hjälp felmeddelande
till användaren att orientera dem.
Jag är säker på att du har alla köra program där plötsligt kraschar,
och du får denna löjliga lilla dialogrutan som dyker upp och säger
något fruktansvärt kryptiska och kanske ger dig en felkod eller något liknande
som är meningslöst.
Det är där du verkligen vill ge något till hjälp
och riktade till användaren så att när de kör det de går "Åh," ansikte palm.
"Jag vet precis vad jag ska göra. Jag vet hur man fixar det här."
>> Om du inte skriver ut ett meddelande, då du hamna faktiskt
lämnar användaren att gå undersöka din källkod
att räkna ut vad som gick fel.
Det finns också några gånger som du använder olika felkoder.
Här har vi använt bara en för att säga att det var ett misstag,
Det uppstod ett fel, det var ett fel.
Större program, ofta program som anropas av andra program,
kommer tillbaka någon form av särskilda felkoder i olika scenarier
att programmässigt kommunicera vad du annars skulle
bara använda en trevlig engelsk meddelande för.
Cool.
Eftersom vi arbetar ner, kan du se att vi drar nyckeln ut.
Vi testar för att se om nyckeln passar.
Vi får ett meddelande från användaren.
Anledningen till att vi gör det i den här göra medan loop-och detta är något som vi kommer att täcka
i lite-men det visar sig att om du skriver kontroll D
när du får den GetString snabbt på terminalen
vad det faktiskt gör det skickar en speciell karaktär
till programmet.
Det kallas ELF eller slutet av filen karaktär.
Och i så fall kommer vårt budskap sträng vara null,
så detta var inte något vi kontrollerat i problemet satt.
>> Men när vi går vidare, nu när vi har börjat prata om pekare
och dynamisk minnesallokering på högen,
kontroll av null när du har en funktion som skulle kunna
returnera null som ett värde är något som du kommer att vilja få en vana att göra.
Detta är här främst för illustration.
Men när du ser GetString i framtiden,
så från problembild 4 på, men du vill ha detta i åtanke.
Återigen, detta är inte en fråga för problembild 3 antingen eftersom vi inte hade täckt det ännu.
Slutligen får vi till denna del där vi får den huvudsakliga kryptering slingan,
och det finns ett par saker som pågår här.
Först iterera vi över hela meddelandet strängen själv.
Här har vi hållit strlen samtalet i tillståndet,
som flera av er har påpekat är inte ett bra sätt att gå.
Det visar sig i det här fallet är det inte heller bra,
dels för att vi ändrar innehållet i själva meddelandet
innanför for-slingan, så om vi har ett budskap som är 10 tecken långa,
första gången vi startar att för slingan strlen kommer tillbaka vad?
10.
>> Men om vi sedan ändra budskap, säger vi ändra sitt 5:e karaktär,
och vi slänger i en \ 0 tecken i den 5: e positionen,
på en senare upprepning strlen (meddelande) inte kommer att återvända vad det gjorde
första gången vi upprepade,
men det kommer i stället tillbaka 5 eftersom vi kastade i den null terminator,
och strängens längd definieras
av läget för att \ 0.
I det här fallet, är detta ett bra sätt att gå eftersom vi ändrar den på plats.
Men du märker att detta är faktiskt förvånansvärt enkelt att kryptera
om du kan få matten korrekt.
Allt som krävs är att kontrollera huruvida det brev som du tittar på
är versaler eller gemener.
>> Anledningen till att vi bara behöver kontrollera det och vi behöver inte kontrollera
det är alfa fallet beror
Om ett tecken är versaler eller om det är gemener
då är det definitivt en bokstav,
eftersom vi inte har stora och små siffror.
Den andra saken som vi gör-och det är lite knepigt,
är att vi har ändrat standard Caesar chiffer formel
att vi gav i problemet inställda specifikationen.
Vad är annorlunda här är att vi subtraheras
i versaler fall kapital A, och sedan vi lagt kapital A
tillbaka i slutet.
>> Jag känner några av er har gjort detta i din kod.
Har någon av er gör detta i era synpunkter?
Du gjorde det här. Kan du förklara vad detta innebär, Sahb?
Genom att subtrahera det, eftersom du gjorde en mod direkt efter det,
du måste ta ut, så på det sättet får du [hosta] läge.
Och sedan genom att lägga tillbaka senare du skiftat över den du ville ha.
Ja, exakt.
Vad Sahb sade var att när vi vill lägga
vårt budskap och vår nyckel tillsammans
och sedan mod att mod att genom NUM_LETTERS,
om vi inte skala vårt budskap i rätt 0 till 25 intervall först,
då kan vi i slutändan får en riktigt konstig nummer
eftersom de värderingar som vi tittar på när vi tittar på meddelande [i],
när vi tittar på den i: te karaktär vår vanlig textmeddelande,
är ett värde någonstans i detta 65 till 122 intervall
baserat på ASCII-värden för versaler A genom gemener z..
Och så när vi mod det med 26 eller NUM_LETTERS,
eftersom det var vår # define längst upp till höger här uppe,
det kommer att ge oss ett värde som är i 0 till 25 intervall,
och vi behöver ett sätt att sedan skala som backup
och få den i rätt ASCII området.
Det enklaste sättet att göra det är att bara skala ned allt
i 0 till 25 intervall till att börja med,
och sedan flytta tillbaka allt i slutet.
>> Ett annat vanligt fel som jag såg människor stöter är att
om du inte verkligen göra detta skalning direkt
och du lägger och skriv tillsammans och du lägger till dem, säg,
till en röding variabel problemet med att
är sedan meddelande [i] är en relativt stort antal att börja med,
kom ihåg det är minst 65, om det är en versal tecken-
om du har en stor nyckel, säg, något som 100,
och du lägger dem 2 ihop till en undertecknad röding du kommer att få ett överflöd.
Du kommer att få ett värde som är större än 127,
vilket är det största värdet som en CHAR-variabel kan hålla.
Återigen, det är därför du skulle vilja göra sånt till att börja med.
Vissa människor fick runt det fallet genom att göra en om annat och testa
för att se om det skulle svämma över innan du gör det,
men detta sätt får runt det.
Och sedan i denna lösning vi skrivs ut hela strängen i slutet.
Andra människor skrivs ut ett tecken i taget. Båda är fantastisk.
Vid denna punkt, gör ni har några frågor, några kommentarer om detta?
Saker du gillar, saker du inte gillar?
>> Jag hade en fråga.
Jag kanske missade det under din förklaring, men hur går det här programmet
hoppa över utrymmena för anslutning av nyckeln till textens längd?
Detta är bara Caesar chiffer. >> Förlåt, ja.
Ja, vi ser det.
I Caesar chiffer vi fick runt att eftersom
Vi vände bara tecken.
Vi roterade bara dem om de var stora eller små bokstäver.
Ni känner ganska bra om det här?
Kopiera gärna detta hem, ta det,
jämför det med vad ni skrev.
Definitivt gärna skicka frågor om det också.
Och återigen, inser att målet här med ditt problem sätter
är inte att få er att skriva perfekt kod för ditt problem uppsättningar.
Det är en lärorik erfarenhet. Ja.
>> Tillbaka till DO WHILE loop, om det är lika med noll,
så null betyder bara någonting, slog de bara in?
Null är en speciell pekare värde,
och vi använder noll när vi vill säga
Vi har en pekare variabel som pekar på ingenting.
Och så typiskt att det innebär att denna variabel, detta meddelande variabel
är tom, och här, eftersom vi använder CS50 speciell sträng typ,
vad är det CS50 sträng typ?
Har du sett vad det är när David drog tillbaka huven i föreläsningen?
Det är en funky, det är en pekare, eller hur?
Okej, ja. >> Det är en char *.
Och så verkligen att vi kunde ersätta denna
här med char * meddelande
och så GetString funktionen, om det inte lyckas få en sträng från användaren,
det kan inte tolka en sträng, och ett fall där det inte kan tolka en sträng
är om användaren skriver änden av fil karaktär, kontroll D,
vilket inte är något man normalt gör, men om det händer
då funktionen returnerar denna nollvärde som ett sätt att säga
"Hej, jag fick inte en sträng".
Vad skulle hända om vi inte sätter meddelande = null,
vilket är något som vi inte har gjort ännu?
Varför skulle det vara ett problem här?
Eftersom jag vet att vi pratade lite i föreläsning om minnesläckor.
Ja, låt oss göra det, och låt oss se vad som händer.
>> Basil fråga var vad som händer om vi inte faktiskt har
detta meddelande = null test?
Låt oss bläddra upp till toppen.
Ni kan kommentera detta.
Egentligen, jag sparar det i en revision.
Detta kommer att vara Revision 3.
Vad du måste göra för att köra det här programmet är att du måste klicka på denna kugghjulsikonen här uppe,
och du måste lägga till ett argument till det.
Du måste ge den nyckeln argument eftersom vi vill gå på en kommandorad argument.
Här kommer jag att ge den siffran 3. Jag gillar 3.
Nu zoomar ut igen, kör programmet.
Den körs, sammanställa, bygga.
Nu kör vi. Det väntar på att bli tillfrågad.
Om jag skriver in något i stil med Hello-där gick det?
Åh, tog mitt program för lång tid att köra. Jag jawing för länge.
Här går.
Nu har jag skriver i hej.
Vi ser att det krypterar korrekt.
Nu vad händer om vi gör snabb GetString att returnera null?
Kom ihåg, jag sa att vi gjorde det genom att trycka på kontrollen D samtidigt.
Jag bläddrar upp här. Vi kör det igen.
Byggnad. Där det går.
Nu när jag slog kontroll D
Jag fick denna linje som säger opt/sandbox50/bin/run.sh, segmenteringsfel.
Har ni sett det förut?
>> [Student] Varför finns det ingen->> Ursäkta?
[Student] Varför finns det ingen core dump i detta fall?
Kärnan dump är-frågan är varför finns det ingen core dump här?
Frågan är att det kan finnas, men kärnan dumpa är en fil
som får lagras på hårddisken.
I det här fallet har vi inaktiverat minnesdumpar
på flykt servern så att vi inte har människor seg förkastningar
och bygga upp massor av centrala soptippar.
Men du kan få en.
Minnesdumpar är det slags saker som du kan ofta inaktivera,
och ibland gör.
Den segmenteringsfel, att svara på din fråga, basilika,
säger att vi försökte få tillgång till en pekare
som inte var inställd att peka på något.
Tänk Binky i videon när Binky försöker
gå åt en pekare som inte är att peka på något?
I det här fallet antar jag tekniskt pekaren pekar på något.
Det pekar på null, vilket är tekniskt 0,
men som är definierad att vara i ett segment som inte är tillgänglig
av ditt program, så att du får ett segmenteringsfel
eftersom du inte tillgång till minne som är i en giltig segment
som heap segmentet eller stapeln segmentet eller datasegmentet.
Cool.
Några fler frågor om Caesar?
>> Låt oss gå vidare. Låt oss titta på Revision 2 riktigt snabbt.
Det är Vigenère.
Här i Vigenère
Vi kommer att gå igenom detta en ganska snabbt eftersom, återigen,
Vigenère och Caesar är ganska lika.
Header kommentar är innan,
# Define är före att undvika att använda dessa magiska nummer.
Det fina är att säga att vi ville flytta till
ett annat alfabet eller något liknande.
Hellre än att behöva gå manuellt ändra alla 26-talet i koden
Vi kan ändra det till 27 eller släppa ner
om vi använde olika alfabet, olika språk.
Återigen, vi har denna kontroll av argumentet räkna,
och verkligen kan du nästan ta detta som en mall.
Ganska mycket alla program du skriver ska ha,
om det tar kommandoradsargument-vissa sekvens av linjer
som lyder så här i början.
Det är en av de första sanity tester du vill göra.
>> Här är vad vi gjorde var att vi såg till att
nyckelordet var giltig, och det var den andra kontrollen som vi gjorde.
Notera igen att vi separerade det från argc och 2.
Notera att i detta fall en sak som vi hade att göra var istället
att använda en till jag vi ville att validera hela strängen,
och för att göra det du faktiskt måste gå tecken för tecken
över strängen.
Det finns inget bra sätt att kalla något på det
eftersom även, till exempel, en till jag återkommer 0
om det inte kan tolka ett heltal, så att inte ens fungerar.
Återigen, trevlig meddelande om att användaren exakt vad som hände.
Då här, igen, hanterar vi även fallet när
användaren skriver i en kontroll D slumpmässig karaktär.
>> Och sedan Charlotte hade en fråga tidigare om hur vi lyckas hoppa utrymmen
i vår sträng här.
Detta var typ av liknar vad vi gjorde med Myspace programmet
som vi gjorde i snitt och hur detta fungerat
är att vi spårade antalet bokstäver som vi hade sett.
När vi gick över meddelandet strängen, som vi gick över tecken för tecken,
Vi spårade index som en del av vår for-slinga, och sedan vi också spåras
antalet bokstäver, så icke-specialtecken, icke-siffror, icke-vita rymden
att vi hade sett i separat variabel.
Och därefter denna lösning ändrar nyckeln
att få en verklig nyckel heltal, och det gör att i farten,
precis innan det går då att kryptera själva meddelandet karaktär.
Det finns några lösningar som var helt bra också
som skulle ändra uppåt när man testar för nyckeln giltighet.
Förutom att se till att karaktär och sökordet
var en bokstav visade det sig också att till ett heltal
i 0 till 25 intervall för att sedan hoppa behöva göra det senare i detta for-slinga.
Återigen ser du här detta är verkligen exakt samma kod
som vi använde i Caesar vid denna punkt.
Du gör exakt samma sak, så det verkliga tricket är att räkna ut
hur du aktiverar sökordet till ett heltal.
>> En sak som vi gjorde här som är lite tät
är vi upprepade denna fras, antar jag att du kan kalla det,
3 separata gånger på ledningarna 58, 59, och 61.
Kan någon förklara vad exakt denna fras gör?
Det öppna en karaktär, som du sa.
Ja, det är [ohörbart] ett tecken i sökordet,
och så det är många sett bokstäver eftersom du bara rör sig längs
nyckelordet när du har sett brevet,
så det kommer att effektivt hoppa utrymmen och sånt.
Ja, exakt.
Och sedan när du har sett sökordet tomt du bara mod så du flyttar tillbaka runt.
Exakt. Det är en perfekt förklaring.
Vad Kevin sa att vi vill indexera i sökordet.
Vi vill få num_letters_seen karaktär, om du vill,
men om num_letters_seen överskrider längden på sökordet,
hur vi får tillbaka i rätt område är vi använder mod operatören
att effektivt linda runt.
Till exempel, som i korthet är vår sökord bacon,
och det är 5 bokstäver långa.
Men vi har sett 6 bokstäver i vår klartext på denna punkt
och krypterade 6.
Vi kommer att hamna tillgång till num_letters_seen,
vilket är 6, mod längden av nyckelordet, 5,
så vi får 1, och så vad vi ska göra är att vi ska
tillgång till första tecknet på insidan av vår sökord på den punkten.
>> Okej, alla frågor om Vigenère
innan vi går vidare?
Ni känner ganska bra om det här?
Cool, bra.
Jag vill vara säker på att ni får chansen att se kod
som vi tror ser bra ut och har chansen att lära av det.
Detta kommer att bli det sista vi kommer att använda utrymmen för närvarande,
och vi kommer att övergången nu, och jag ska gå till cs50.net/lectures
så att vi kan göra lite frågesport översyn.
Det bästa sättet tror jag att börja göra frågesport recension
är att komma till denna Föreläsningar sidan, cs50.net/lectures,
och under varje vecka rubriker, så om jag ser här vid vecka 0,
Jag ser att vi har en lista över ämnen som vi täckt i vecka 0.
>> Om någon av dessa frågor verkar obekant för dig
du definitivt vill gå tillbaka och skura föreläsningsanteckningar och eventuellt
även skumma igenom föreläsningar, titta på dem igen om du vill
att få en känsla för vad som händer med vart och ett av ämnena.
Jag kommer att säga ytterligare i år en av de coola resurser vi har fått
är dessa shorts som vi har skapat, och om man tittar på vecka 0,
vi har inte alla de ämnen som behandlas, men vi har en hel del av dem,
några av de knepigaste sådana, så titta på dessa shorts igen
är ett bra sätt att få dig upp till hastigheten.
I synnerhet kommer jag att sätta i en plugg för 3 på botten, eftersom jag gjorde dem.
Men om du kämpar med binära, bitar, hex, den sortens saker,
binär är ett bra ställe att börja.
ASCII är en annan som är bra att visa också.
Du kan även titta på mig på 1.5x hastighet om jag går för långsamt för dig.
Eftersom det är recension, gärna göra det.
>> Bara att börja riktigt snabbt, kommer vi att gå igenom ett par av dessa frågesport problem
bara för att snabbt pressa igenom dessa.
Till exempel, låt oss titta på problemet 16 att jag har rätt här uppe på bordet.
Vi har denna följande beräkning i binär,
och vi vill visa något arbete.
Okej, jag ska ge detta en chans.
Ni borde följa med papper,
och vi ska göra det riktigt snabbt.
Vi vill utföra följande beräkning i binär.
Jag har 00.110.010.
Och jag kommer att lägga till den 00.110.010.
För matte genier följer med hemma,
Detta är i praktiken multipliceras med 2.
Låt oss börja.
Vi kommer att följa samma tillägg algoritm som vi gör
när vi lägger decimaltal tillsammans.
Verkligen den enda skillnaden här är att vi slinga tillbaka runt
när vi har 1 + 1 istället för när vi kommer till 10.
>> Om vi ​​börjar från höger, riktigt snabbt, är det den första siffran?
[Student] 0. >> [Nate H] 0.
Stora, den andra siffran?
[Student] 1.
[Nate H] Är det en 1? 1 + 1 är?
[Student] 10.
[Nate H] Exakt, så vad är den siffra som jag skriver rakt nedanför 2 ettor lagts ihop?
[Student] 1, 0 eller 0 och sedan bära 1.
[Nate H] 0 och bär en 1, exakt.
Nästa upp, basilika, du upp.
Vad är den tredje? >> [Basil] 1.
[Nate H] 1, perfekt. Kevin?
[Kevin] 0. >> [Nate H] 0, Charlotte?
[Charlotte] 0. >> [Nate H] Ja, och vad ska jag göra?
[Student] Den 1.
[Nate H] Och vad ska jag göra? Och då jag bär 1.
Perfekt, Sahb? >> [Sahb] Nu har du 1.
[Nate H] Och gör jag något här?
[Sahb] Sedan för nästa har du 1 för att du som överförts 1.
[Nate H] Bra, så här kan vi avsluta det.
Cool.
[Student] Har 0 + 0 = 0?
0 + 0 = 0.
1 + 1, som du sa, är 10, eller 1, 0, snarare.
10 är en missvisande eftersom för mig 10 innebär att antalet 10,
och det är sarkasm hur vi representerar det när vi skriver det.
Vi representerar siffran 2 med 1, 0, och antalet 10 är något annorlunda.
>> Vad är typ av trevligt om binär är att det verkligen inte finns så många
fall måste du lära dig.
Det finns 0 + 0 = 0, 0 + 1 = 1,
1 + 1 är 0, och sedan bära en 1,
och sedan kan du se här på den tredje kolumnen från höger
vi hade detta 1, 1 och 1.
Och 1 + 1 + 1 är en 1,
och du bär en annan 1.
När du gör binär addition, ganska enkelt.
Jag skulle göra ett par fler av dessa vårt förstånd kontrollera er
innan du går in för det här är
förmodligen något som vi får se på testet.
Nu ska vi göra det här nästa också.
Låt oss göra problemet 17.
Vi kommer att omvandla följande binära tal till decimal.
Jag har 10100111001.
Tänk på det binära videon som jag gjorde
Jag gick igenom ett par exempel, och jag visade hur
allt fungerar när du gör det i decimalform.
När du arbetar i decimal representation jag tror att vi är
vid denna punkt i våra liv så flytande i det som
Det är ganska lätt att släta över mekaniken i hur det faktiskt fungerar.
>> Men för att göra en snabb resumé, om jag har numret 137
Detta betyder, och verkligen igen, detta är i decimal representation,
numret 137 i decimalform innebär att jag har 1 x 100 + 3 x 10 + 7 x 1.
Detta är allt som vistas på skärmen.
Och sedan om man tittar på dessa siffror här,
100, 10 och 1, ser du att de är faktiskt alla befogenheter 10.
Jag har 10 ^, 10 ^, och 10 till noll.
Vi har en liknande saker i binär,
förutom att vår bas, som vi kallar det, är 2 istället för 10.
Dessa 10s som jag skrev här nere på botten,
detta 10 m², 10 ¹, 10 till noll, 10 är vår bas,
och exponenten, 0, 1, eller 2,
antyds av läget för siffran i antalet som vi skriver.
1, om vi ser på det, är detta 1 i 2: a plats.
Den 3 är i den 1: a positionen, och 7 är i 0:e läge.
Det är så vi får olika exponenter nedan för våra baser.
>> Efter allt detta we'll-faktiskt, vet du vad?
Vi gör-vart tog min ångra knapp vägen?
Där det går.
Jag älskar det här ångra sak.
Efter detta tror jag för mig åtminstone
Det enklaste sättet att börja konvertera ett binärt tal
eller ett hexadecimalt tal där basen är 16
och inte 10 eller 2 är att gå vidare och skriva ut
grunderna och exponenter för alla nummer i min binärt tal i toppen.
Om vi ​​börjar från vänster till höger igen,
som är typ av bakvända,
Jag kommer att ändra tillbaka till svart här, har vi 2 till 0. Läget,
och sedan har vi 2 ¹, 2 ²,
och sedan 2 till 3, 2 till 4, 2 till 5, 6,
7, 8, 9, och 10.
Dessa siffror har jag skrivit ut är alla exponenter.
Jag skrev bara baserna här i första 3 bara för rymden.
>> På denna punkt kommer jag att gå vidare och jag faktiskt kommer att radera
de saker som vi gjorde i decimal, om det är okej.
Ni har alla fått det.
De av er tittar på nätet är jag säker på kommer att kunna spola tillbaka mig om du vill.
Växla tillbaka till pennan.
Nu, vad vi kan göra, om ni inte är helt upp till hastigheten på dina befogenheter 2,
Det är helt cool.
Det händer. Jag förstår.
Jag hade en gång en anställningsintervju där jag fick höra att jag borde känna till alla befogenheter 2
upp genom 2 till den 30.
Det var inte ett jobb jag fick.
Hur som helst, kan ni gå vidare och göra matten här,
men med binär det inte verkligen göra mening,
och inte heller det vettigt med decimal eller hexadecimal heller,
att göra matten reda på var du har nollor.
Du kan se har jag 0 här, en 0 här, 0 här, 0 här, 0 här, 0 här.
Varför kan det inte meningsfullt att göra själva matten
att beräkna lämplig effekt av 2 för den positionen?
Exakt, precis Charlotte sa blir det 0.
Kan lika gärna spara själv tid om beräkning befogenheter 2 inte är din starka sida.
I det här fallet behöver vi bara beräkna det för 2 till 0, som är-?
[Student] 1.
[Nate H] 1, 2 till 3 som är-?
[Student] 8. >> [Nate H] 8.
2 till 4?
[Student] 2. Jag är ledsen, 1.
[Nate H] 2 ​​till 4 är 16, exakt.
2 till 5, Kevin? >> 32.
[Nate H] 32, 2 till 8?
[Student] 32 x 8, 256.
[Nate H] Perfekt.
Och 2 till 10?
[Student] 1024.
[Nate H] Ja, 1024.
>> När vi har fått dessa siffror kan vi summera dem alla.
Och det är där det är verkligen viktigt att göra ett par saker.
En är att gå sakta och kontrollera ditt arbete.
Du kan säga att det finns en 1 i slutet av detta nummer,
så jag borde definitivt få ett udda antal som min resultat,
eftersom alla de andra kommer att bli ännu tal
tanke på att det är ett binärt tal.
Den andra sak att göra är om du kommer till denna punkt på prov
och du har skrivit ut så här långt
och du ont om tid
titta på antalet poäng att detta problem är värt.
Detta problem, som ni kan se, om jag vänder tillbaka till min laptop verkligen snabbt,
detta problem är värt 2 poäng, så det är inte den typ av tillägg
du bör gå igenom om du verkligen ont om tid.
Men vi ska växla tillbaka till iPad, och vi ska gå igenom det riktigt snabbt.
>> Jag gillar att göra de små siffrorna 1.
eftersom jag tycker att lättare.
Jag gillar 32 och 8 eftersom de går ihop ganska enkelt, och vi får 50.
16 och 1 får 17.
Där får vi 57,
och då kan vi göra resten av detta, så att vi kan göra 57, 156.
Kom igen.
Människan, ja, låt oss se.
Vi hade 57, 256 och 1024.
Vid denna punkt, skulle jag hellre bara gå igenom.
Jag har ingen aning. Jag behöver helt klart läsa upp detta.
7, 6 och 4, får du 17.
1, 5, 5, 2, 13.
Då får vi 3, och sedan får vi 1.
1337.
Påskägg, någon?
Någon känner igen detta nummer?
Chris känner igen numret. Vad betyder det, Chris?
[Chris] Leet.
Leet, så om du tittar på det här, det ser ut som Leet.
Hacker grejer. Se upp för den typen av saker på halva tiden eller testet, snarare.
Om du ser den typen av grejer och du undrar "Va,"
som faktiskt kan betyda något.
Jag vet inte. David gillar att sätta den i.
Det är ett bra sätt att förnuft kontrollera det.
Liksom okej, jag kan se vad som händer.
>> Det är vecka 0/Week 1 grejer.
Om vi ​​växlar tillbaka till våra bärbara nu,
zooma ut, och ett par andra saker.
Det finns ASCII, vilket vi har gjort en hel del med problemet uppsättningar.
Detta begrepp av kapital A. Vad är det egentligen?
Att veta att det är det decimala heltal.
65 är vad det är mappat till i ASCII tabellen,
och det är därför hur datorn skriver det,
och det är hur vi har komma undan med faktiskt skriva
tecknet kapital A och karaktären gemener en
i några av dessa lösningar och sätter problem som du har gjort.
Ett par andra saker.
Vi har uttalanden, booleska uttryck, villkor, slingor, variabler och trådar.
>> De alla verkar vettigt för det mesta?
En del av denna terminologi är lite funky ibland.
Jag tycker om att ett uttalande som för det mesta något som avslutas med ett semikolon.
Uttalanden som x = 7, som sätter en variabel,
förmodligen kallas x = 7.
Förmodligen X är också en typ som kan lagra numret 7,
så det är en int eller möjligen en flottör eller en kort eller en röding,
något liknande.
Ett booleskt uttryck använder dessa dubbel lika
och bang är lika eller inte lika, mindre än, större än,
mindre än eller lika med alla såna saker.
Förutsättningarna är då om else uttalanden.
Jag skulle komma ihåg att du inte kan ha en annan utan motsvarande om.
På samma sätt kan du inte ett annat om utan motsvarande om.
Loopar, minns 3 sorters loopar vi har hammering in dig
för de senaste avsnitten och sätter problem.
Använda gör medan när du får indata,
användning medan slingor tills ett visst villkor är sant,
och sedan använda dem för loopar om du behöver
veta vilken iteration av slingan närvarande är du på är hur jag tänker på det.
Eller om du gör en för varje tecken i en sträng jag vill göra något,
för varje element i en array jag vill göra något för att det elementet.
>> Trådar och evenemang.
Dessa vi har inte täckt så uttryckligen i C,
men kom ihåg detta från grunden.
Detta är begreppet har olika skript.
Detta är också denna uppfattning att sända ett evenemang.
Vissa människor använde inte sändningar i sina projekt från början,
vilket är helt cool,
men dessa är 2 olika sätt att hantera denna större fråga kallas samtidighet,
vilket är hur får man program för att utföra
eller till synes exekvera samtidigt?
Olika uppgifter körs medan andra uppgifter också igång.
Detta är hur operativsystemet verkar fungera.
Det är därför även, till exempel,
Jag har min webbläsare igång kan jag vända också på Spotify och spela upp en låt.
Det är mer av en konceptuell sak att förstå.
Jag skulle ta en titt på gängorna korta
Om du vill veta mer om det.
>> Låt oss se, tror jag att det kan ha varit
ett problem på detta i en av dessa.
Återigen, jag tror trådar och händelser är inte något som vi kommer att täcka i C
bara för att det är betydligt svårare än i Scratch.
Du ska inte bry dig om det där, men definitivt förstå begreppen,
förstå vad som händer.
Innan vi går vidare, några frågor om vecka 0 material?
Alla mår ganska bra?
Förstå variabler och vad en variabel är?
>> Går vidare. Vecka 1.
Ett par saker här som inte var särskilt omfattas
i frågesporten översyn nödvändighet och också är mer konceptuella saker att tänka på.
Den första är denna föreställning om vad källkoden, kompilatorer och objektkod är.
Någon? Basilika.
Är objektkod-jag menar källkod är vad du lägger i klang,
och objektkod är vad klang lägger ut så att datorn kan läsa programmet.
Exakt.
Källkod är C-kod som du faktiskt skriva upp.
Objektkod är vad du får ut av klang.
Det är 0 och 1 i den binärt format.
Vad som händer är när du har en massa objektfiler,
säga att du sammanställa ett projekt eller ett program som använder flera källkodsfiler,
som konventionellt ges. c. filändelsen.
Det är därför vi har caesar.c, vigenère.c.
Om du skriver Java-program du ger dem en förlängning. Java.
Python-program har filtillägget. Py ofta.
>> När du har flera. C-filer, kompilera du dem.
Klang spottar ut allt detta binära skräp.
Sedan för att du vill endast 1 program
har du länken länken alla dessa objektfiler tillsammans
i 1 körbar fil.
Detta är också vad som händer när du använder CS50 biblioteket, till exempel.
Den CS50 bibliotek är både att. H. huvudfil
att du läser, det # includecs50.h.
Och då är det också en speciell binär biblioteksfil
som har varit sammanställts som är 0 och 1,
och att-Jag flaggan, så om vi går tillbaka till våra utrymmen och vi ser verkligen snabbt
på vad som händer här när vi ser på vår klang kommando,
vad vi har är att detta är vår källkod fil här.
Dessa är ett gäng kompilator flaggor.
Och sedan i slutet, dessa-l flaggor länken i
de faktiska binära filer för dessa 2 bibliotek, CS50 bibliotek och sedan matematik bibliotek.
>> Förstå varje typ av filer "syftet
i sammanställningen processen är något du vill kunna
ger åtminstone en hög nivå översikt över.
Källkod kommer in Objektkod kommer ut.
Objekt kodfiler knyta ihop, och du får en vacker, körbar fil.
Cool.
Det är också där du kan få fel på flera punkter
i sammanställningen processen.
Det är där, till exempel, om du tar det här länka flagga,
den CS50 flaggan och du utelämnar det i utrymmen eller när du kör din kod,
det är där du får ett fel i länkningen fasen,
och länken kommer att säga, "Hej, kallat er en funktion GetString
det är i CS50 biblioteket. "
"Du sa att det var i CS50 biblioteket och jag kan inte hitta koden för det."
Det är där du måste länka det, och det är separata
från ett kompileringsfel eftersom kompilatorn tittar på syntax och sånt.
Det är bra att veta vad som händer när.
>> Andra saker att känna till.
Jag skulle säga att du absolut vill ta en titt på den korta på typecasting görs av Jordanien
att förstå vad ints är under huven,
vilka tecken är under huven.
När vi talar om ASCII och vi faktiskt tittar på ASCII tabellen,
vad det gör är att ge oss en under huven ser
på hur datorn faktiskt representerar kapitalet A och siffran 7
och ett kommatecken och ett frågetecken.
Datorn har också speciella sätt att representera
numret 7 som ett heltal.
Den har ett speciellt sätt att representera nummer 7 som ett flyttal,
och de är mycket olika.
Typecasting är hur du säger datorn "Hej, jag vill att du ska konvertera
från en representation till en annan representation. "
Varför inte vi ta en titt på det.
>> Jag vill också ta en titt på den korta på biblioteken och den korta på kompilatorer.
De talar om processen för sammanställning,
vad ett bibliotek är och gå igenom några av dessa frågor som du kan få frågade.
Frågor om Vecka 1-material?
Finns det några ämnen i här som verkar skrämmande du vill täcka?
Jag försöker blåsa igenom de flesta av dessa tidigare frågor så att vi kan få till
pekare och göra lite av rekursion.
Tankar?
Allt för att täcka?
Dags för lite choklad kanske?
Ni arbetar genom den.
Jag kommer att fortsätta smuttar på mitt kaffe.
Vecka 2.
Bra samtal, bra samtal.
I vecka 2 pratade vi lite mer om funktioner.
>> Under de första problemet set vi inte riktigt skriva några funktioner alls
annat än vilken funktion?
[Student] Main. >> Main, exakt.
Och så har vi sett de olika kostymer som främsta bär.
Där är en som tar inga argument,
och vi säger bara tomrum mellan parenteserna,
och sedan finns det andra där vi vill ta kommandoradsargument,
och som vi såg, det är där du har int argc och sträng argv array
eller nu när vi har faktiskt utsatt sträng att vara den char * att det är
vi kommer att börja skriva det som char * argv och konsoler.
I problembild 3, såg ni ett gäng funktioner,
och du genomfört ett gäng funktioner, rita, titta upp, scramble.
Prototyperna var alla skrivna där för dig.
>> Vad jag ville prata om här med funktioner riktigt snabbt
är att det finns 3 delar till dem när du skriver en funktion.
Du måste ange en returtyp för funktionen.
Du måste ange ett namn för funktionen och då måste man ange
argumentlistan eller parameterlistan.
Till exempel, om jag skulle skriva en funktion för att summera ett gäng heltal
och sedan tillbaka till mig den summa vad som skulle vara min återkomst typ
om jag ville summera heltal och sedan tillbaka summan?
Sedan namnet på funktionen.
Om jag går vidare och skriver i grönt, är denna del av returtyp.
Denna del är namnet.
Och sedan mellan parentes
är där jag ger argumenten,
ofta förkortat args, ibland kallade params för parametrar.
Och om du har en, anger du bara en.
Om du har flera du dela var och en med ett kommatecken.
Och för varje argument du ger den 2 saker som är-Kevin?
[Kevin] Du måste ge den typ och sedan namnet.
Och sedan namnet och namnet är det namn som du kommer att använda
att hänvisa till det argumentet inom ramen för summan funktion,
inom den funktion som du för närvarande skriver.
>> Du behöver inte, till exempel om jag ska sammanfatta,
säga, en rad av heltal-Vi gör int array,
och jag ska ge mig några klammerparenteser där-
sedan när jag passerar en array till funktionen SUMMA
Jag låta det gå i den första positionen av argumentet listan.
Men array som jag passerar på inte behöver ha namnet arr.
Arr kommer att vara hur jag hänvisar till det argumentet i själva funktionen.
Den andra saken som vi måste ta hänsyn till,
och detta är något annorlunda funktioner, men jag tycker det är en viktig punkt,
är att i C när jag skriver en funktion som denna
hur vet jag hur många element är i denna array?
Detta är något av en kuggfråga.
Vi pratade om detta lite i förra veckans avsnitt.
Hur vet jag hur många element inuti en array i C?
Finns det något sätt?
>> Det visar sig att det finns inget sätt att veta.
Du måste låta det gå i separat.
Det finns ett trick som du kan göra
om du är i samma funktion som arrayen har förklarats,
och du arbetar med en stack array.
Men det fungerar bara om du är i samma funktion.
När du passerar en rad till en annan funktion eller om du har deklarerat en matris
och du sätter den arrayen på högen, har du använt malloc
och sånt, så alla satsningar är avstängd.
Då har du faktiskt gå runt
en speciell argument eller annan parameter
berätta hur stor gruppen är.
I det här fallet skulle jag vilja använda en komma-Jag är ledsen, det kommer upp på skärmen här-
och jag skulle passera i ett annat argument
och kallar det int len ​​för längden.
>> En sak som kan komma upp på frågesport
ber dig att skriva eller genomföra en viss funktion som heter något.
Om vi ​​inte ger dig prototypen, så hela den här saken här,
hela den här röran kallas funktionen deklarationen eller funktionen prototyp,
Detta är en av de första saker som du kommer att vilja spika ner om den inte har gett
till dig direkt på testet.
Den andra knep som jag har lärt mig är att
säger att vi gör ger dig en prototyp för en funktion, och vi säger: "Hej, har du att skriva det."
Inuti klammerparenteser som du har på testet
om du märker att det finns en returtyp och du märker att avkastningen typen
är något annat än tomrum, vilket innebär att funktionen inte returnera någonting,
då en sak som du definitivt vill göra är att skriva
någon form av return i slutet av funktionen.
Avkastning, och i detta fall kommer vi sätta en tom eftersom vi vill fylla i de tomma.
Men detta får dig att tänka på rätt sätt om hur ska jag närma sig detta problem?
Och det påminner dig att du kommer att få tillbaka ett värde
till anroparen av funktionen.
>> Ja. >> [Student] Har stil gälla när vi skriver kod på testet?
Såsom indrag och sånt? >> [Student] Ja.
Nej, inte så mycket.
Jag tror att många av-detta är något vi kommer att klargöra om testet på dagen för,
men typiskt oroa omfattar # och sånt, det är typ av utanför.
[Student] Behöver du kommentera din handskrivna kod?
Behöver du kommentera din handskrivna kod?
Kommentarer är alltid bra om du är orolig för partiell kredit
eller om du vill kommunicera din avsikt att grader.
Men jag, återigen, att klargöra om testet själv och den frågesport dag,
men jag tror inte att du kommer att krävas för att skriva kommentarer, nej.
Vanligtvis inte, men det är definitivt den typ av sak där
Du kan kommunicera din avsikt, som "Hej, det är här jag ska med det."
Och ibland som kan hjälpa till med partiell kredit.
Cool.
>> Basilika.
[Basil] Vad är skillnaden mellan att förklara, säger, int Lang
i argument eller parametrar kontra förklara en variabel i funktionen?
Wow, gick kaffe ner luftstrupen.
[Basil] Som vilka saker vi vill sätta i argument.
Ja, det är en bra fråga.
Hur väljer du vilka saker du vill sätta i argumenten
kontra vad saker du bör göra inne i funktion?
I detta fall har vi inkluderat båda dessa som argument
eftersom de är något som den som ska använda funktionen SUMMA
måste ange dessa saker.
>> Summan funktionen som vi talade om, har ingen möjlighet att veta
hur stor gruppen är den får från sin uppringaren eller den som använder funktionen SUMMA.
Den har ingen möjlighet att veta hur stor den gruppen är.
Anledningen till att vi passerar i denna längd här som ett argument
är för att det är något som vi i grund och botten säger till den som ringer av funktionen,
vem ska använda funktionen SUMMA, "Hej, inte bara att du måste ge oss en rad
av Ints, måste du också berätta hur stor den array som du har gett oss är. "
[Basil] De kommer båda att vara kommandoradsargument?
Nej, det är faktiskt argument som du skulle passera till funktionen.
>> Låt mig göra en ny sida här.
[Basil] Som namnet skulle passera-
[Nate H] Om jag har int main (void),
och jag kommer att sätta i min återkomst 0 här nere på botten,
och säger att jag vill ringa summan funktionen.
Jag vill säga int x = summa ();
För att använda funktionen SUMMA jag måste passera både den array som jag vill sammanfatta
och längden av uppsättningen, så det är där
förutsatt att jag hade en rad Ints,
säga att jag hade int numbaz [] = 1, 2, 3,
typ av användning som hackat upp syntax där,
vad jag skulle göra i summa jag skulle vilja gå i
både numbaz och antalet 3
att berätta summan funktionen "Okej, här matrisen jag vill att du ska summera."
"Här är dess storlek."
Verkar det vettigt? Besvarar det din fråga?
>> På många sätt den gör parallella vad vi gör med största
när vi har kommandoradsargumenten.
Ett program som Caesar chiffer, till exempel, behövs det
kommandoradsargument skulle inte kunna göra någonting.
Det skulle inte vet hur man krypterar om du inte tala om vad för att använda
eller om du inte tala om vad sträng du vill kryptera.
Uppmaning för inmatning, det är där vi har 2 olika mekanismer
för att ta in in från användaren, för att ta information från användaren.
För problembild 1 såg vi denna getInt, GetString, getFloat sätt
att förmå för inmatning, och det kallas med standard in strömmen.
Det är något annorlunda.
Det är något som du kan göra på en gång i stället för
När du startar programmet, när du startar programmet körs.
De kommandoradsargument alla anges när du startar programmet igång.
Vi har blanda två av dem.
När vi använder argument till en funktion, det är mycket som kommandoradsargument till huvud.
Det är när du anropar funktionen måste du berätta det
exakt vad den behöver för att utföra sina uppgifter.
En annan bra sak att titta på, och jag ska låta dig titta på det på fritiden,
och det var täckt i frågesporten-var denna föreställning om omfattningen
och lokala variabler kontra globala variabler.
Vill uppmärksamma det.
>> Nu när vi får in på denna andra grejer,
i vecka 3 började vi prata om sökning och sortering.
Sökning och sortering, åtminstone i CS50,
är mycket en introduktion till några av de mer teoretiska delarna av datavetenskap.
Problemet med sökning, problemet med sortering
är stora, kanoniska problem.
Hur hittar man ett visst antal i en rad miljarder heltal?
Hur hittar man ett visst namn i en telefonbok
som lagras på din bärbara dator?
Och så presenterar vi den här begreppet asymptotiska körtider
att verkligen mäta hur länge, hur hårt dessa problem är,
hur lång tid de tar att lösa.
I, tror jag, 2011 s frågesport det finns ett problem som jag tycker förtjänar
täcker mycket snabbt, vilket är en, problemet 12.
O nej, det är Omega.
>> Här pratar vi om snabbast möjliga körtid
för en viss algoritm och sedan den långsammaste möjliga körtid.
Detta Omega och O är egentligen bara genvägar.
De är notationer genvägar för att säga
hur snabbt på bästa möjliga fallet kommer vår algoritm springa,
och hur långsamt i värsta möjliga fall kommer vår algoritm körs?
Låt oss göra ett par av dessa, och dessa också omfattas
på kort på asymptotisk notation, som jag rekommenderar.
Jackson gjorde ett riktigt bra jobb.
Med binär sökning, talar vi om binärsökning som en algoritm,
och vi brukar tala om det i termer av dess stora O.
Vad är den stora O?
Vad är den långsammaste möjliga drifttid för binär sökning?
[Student] N ^?
Nära, jag antar liknar.
Det är mycket snabbare än så.
[Student] Binary? >> Ja, binär sökning.
[Student] Det är log n.
Log n, så vad gör log n menar?
Det halverar det varje iteration.
Exakt, så i den långsammaste möjliga fallet,
säga om du har en sorterad array
miljon heltal och antalet du söker
är antingen den första elementet i matrisen eller den sista elementet i gruppen.
Kom ihåg, fungerar den binära sökalgoritmen genom att titta på den mellersta elementet,
se om det är matchen som du letar efter.
Om det är så stor, du hittade det.
>> På bästa möjliga fallet, hur snabbt rinner binär sökning?
[Studenter] 1.
1, är det konstant tid, stora O i 1. Ja.
[Student] Jag har en fråga. När du säger loggar n, menar du när det gäller bas 2, eller hur?
Ja, det är så att den andra saken.
Vi säger log n, och jag antar att när jag var i gymnasiet
Jag antog alltid att stocken var basen 10.
Ja, så ja, logga bas 2 normalt är vad vi använder.
Återigen, gå tillbaka till binär sökning, om du söker efter något
elementet i slutet eller elementet i början,
eftersom du startar i mitten och sedan kassera
beroende halv uppfyller inte de kriterier som du letar efter,
och du går vidare till nästa halv och nästa halv och nästa halv.
Om jag söker efter den största elementet i miljon heltalsmatris
Jag ska halvera den som mest logg på 1 miljon gånger
innan jag testar slutligen och se att elementet jag söker
är i den största eller i den högsta indexet i matrisen,
och som kommer att ta logg av n, logga på 1 miljon gånger.
>> Bubbla sortera.
Minns ni algoritmen bubblan slag?
Kevin, kan du ge mig en snabb resumé av vad som hände i bubblan Sortera algoritmen?
[Kevin] I grunden går igenom allt i listan.
Det ser på de två första.
Om den första är större än den andra den swappar dem.
Sedan jämförs andra och tredje, samma sak, swappar,
tredje och fjärde, hela vägen ner.
Större siffror kommer att följa upp till slutet.
Och efter hur många loopar du är klar.
Exakt, så vad Kevin sa att vi ska titta större antal
bubbla upp till slutet av arrayen.
Till exempel har något emot dig gå oss genom det här exemplet, om detta är vår matris?
[Kevin] Du tar 2 och 3.
3 är större än 2, så att du byta dem.
[Nate H] Rätt, så vi byter dessa, och så får vi 2, 3, 6, 4, och 9.
[Kevin] Sedan jämföra 3 och 6.
3 är mindre än 6, så att du lämnar dem,
och 6 och 4, skulle du byta dem eftersom 4 är mindre än 6.
[Nate H] Rätt, så jag får 2, 3, 4, 6, 9.
[Kevin] och 9 är större än 6, så att du lämnar den.
Och du skulle gå tillbaka genom det igen.
>> [Nate H] Är jag gjort i detta läge? >> [Kevin] Nej
Och varför är jag inte gjort på denna punkt?
Eftersom det ser ut som min grupp sorteras. Jag tittar på det.
[Kevin] Gå igenom den igen och se till att det inte finns fler swappar
innan du kan helt sluta.
Exakt, så du måste hålla gå igenom och se till att det inte finns några swappar
att du kan göra på denna punkt.
Det var egentligen bara tur, som du sa, att vi hamnade
bara behöva göra 1 passerar genom och vi är sorterade.
Men för att göra detta i det allmänna fallet kommer vi faktiskt måste göra detta om och om igen.
Och i själva verket var detta ett exempel på bästa möjliga fallet,
som vi såg i problemet.
Vi såg att det bästa möjliga fallet n.
Vi gick igenom arrayen 1 gång.
Vad är det värsta möjliga fallet för denna algoritm?
[Kevin] N ^.
Och vad tycker det utseendet? Vad skulle en array ser ut som skulle ta n ^ tid?
[Kevin] [ohörbart] sorteras.
Exakt, så om jag hade matrisen 9, 7, 6, 5, 2,
först 9 skulle bubbla hela vägen upp.
Efter 1 iteration skulle vi ha 7, 6, 5, 2, 9.
Sedan 7 skulle bubbla upp, 6, 5, 2, 7, 9, och så vidare och så vidare.
>> Vi skulle behöva gå igenom hela matrisen n gånger,
och du kan faktiskt få något mer exakt än detta
eftersom när vi har flyttat 9 hela vägen upp till sitt sista möjliga läge
Vi vet att vi aldrig behöver jämföra mot det elementet igen.
När vi börjar bubblar 7 upp
Vi vet att vi kan stoppa när 7 är rätt innan 9
eftersom vi redan jämförde 9 till det.
Om du gör detta på ett smart sätt är det inte riktigt, antar jag, så mycket tid.
Du kommer inte att jämföra alla möjliga [ohörbara] kombinationer
varje gång du går igenom varje iteration.
Men ändå, när vi talar om denna övre gräns säger vi att
du tittar på N ^ jämförelser hela vägen igenom.
>> Låt oss gå tillbaka, och eftersom vi börjar få lite ont om tid
Jag skulle säga att du definitivt bör gå igenom resten av denna tabell,
fylla ut allt.
Tänk exempel. Tänk på konkreta exempel.
Det är verkligen praktiskt och bra att göra.
Dra ut.
Detta är den typ av tabell som när du går igenom i datavetenskap
du borde verkligen börja känna dem utantill.
Det är den typ av frågor som du får i intervjuer.
Det är massa saker som är bra att veta,
och tänka på de kant fallen verkligen räkna ut hur att tänka på
att veta att för Bubble sortera den sämsta matrisen
att sortera med det är en som är i omvänd ordning.
>> Pekare. Låt oss tala lite om pekare.
Under de sista minuterna som vi har här
Jag vet att detta är något tillsammans med I / O-det är ganska nytt.
När vi talar om pekare anledningen till att vi vill tala om pekare
beror en, när vi arbetar i C
Vi är verkligen på en relativt låg nivå jämfört med de flesta moderna programmeringsspråk.
Vi är faktiskt kan manipulera variabler i minnet,
räkna ut var de är faktiskt belägna inom vårt RAM.
När du har gått på att ta klasser operativsystem du ser
att det är, återigen, typ av en abstraktion.
Det är faktiskt inte fallet.
Vi har virtuellt minne som döljer dessa uppgifter från oss.
>> Men nu kan du räkna med att när du har ett program,
till exempel när du börjar köra din Caesar chiffer program-
Jag växla tillbaka till min iPad verkligen snabbt,
att i början ditt program, om du har, säg,
4 gigabyte RAM-minne på din bärbara dator,
du får avsatt denna bit, och vi kommer att kalla detta RAM.
Och det börjar på en plats vi kommer att ringa 0,
och det slutar på en plats som vi kallar 4 gigabyte.
Jag kan verkligen inte skriva. Människan, är att hacka.
När programmet körs
operativsystemet skär upp RAM,
och det anges olika segment för olika delar av ditt program att leva i.
Här nere detta område är typ av en ingenmansland.
När du går upp lite längre här
du har faktiskt den plats där
koden för ditt program liv.
Att den faktiska binär kod, faktiskt att körbar fil får laddas in i minnet
När du kör ett program, och den lever i kodsegmentet.
Och som ditt program exekverar processorn ser på detta kodsegment
att räkna ut vad som är nästa instruktion?
Vad är nästa kodrad behöver jag köra?
>> Det finns också en datasegment, och det är där de strängkonstanter
får lagras som du har använt.
Och sedan längre upp finns denna plats som kallas högen.
Vi åt minnet där med malloc,
och sedan mot den absoluta toppen av ditt program
Det finns stacken,
och det är där vi har spelat under större delen av början.
Detta är inte att skala eller något.
Mycket av detta är mycket maskin beroende,
operativsystemet beroende, men det är relativt hur saker och ting blir chunked upp.
När du kör ett program och du deklarerar en variabel som heter X-
Jag ska rita en annan låda nere, och det kommer att bli RAM också.
Och jag kommer att se ut.
Vi kommer dra taggiga linjer för att indikera detta är bara en liten del av RAM-minne
och inte alla av det som vi drar på toppen.
>> Om jag deklarerar en heltalsvariabel kallad x,
vad jag faktiskt får är en kartläggning
som lagras i symboltabellen i mitt program
som ansluter namnet X till denna region av minne som jag har ritat
här mellan de vertikala staplarna.
Om jag har en kodrad i mitt program som säger x = 7
processorn vet "Åh, okej, jag vet att x bor på denna plats i minnet."
"Jag ska gå vidare och skriva en 7 där."
Hur vet den vilken plats detta är i minne?
Tja, det är allt gjort vid kompileringen.
Kompilatorn tar hand om fördelningen där varje variabel kommer att gå
och skapa en speciell kartläggning eller snarare ansluta prickar
mellan en symbol och där det går, en variabel namn
och där det kommer att leva i minnet.
Men det visar sig att vi faktiskt kan komma åt den i våra program också.
Detta blir viktigt när vi börjar prata om några av de datastrukturer,
vilket är ett begrepp som vi kommer att införa senare.
>> Men nu, vad du kan veta är att jag kan skapa en pekare till denna plats, x.
Till exempel kan jag skapa en pekare variabel.
När vi skapar en pekare variabel använder vi stjärnan notation.
I det här fallet säger det jag ska skapa en pekare till en int.
Det är en typ precis som alla andra.
Vi ger det en variabel som y,
och då vi satt det lika med adressen till en adress.
I detta fall, kan vi ställa y peka till x
genom att ta adressen av x, som vi gör med denna et-tecken,
och sedan sätter vi y att peka på den.
Vad detta i huvudsak innebär är om vi ser på vår RAM
detta skapar en separat variabel.
Det kommer att kalla det y,
och när denna rad med kod körs
det faktiskt kommer att skapa en liten pekare som vi vanligtvis dra som en pil,
och det sätter y att peka på x.
Ja.
[Student] Om x är redan en pekare, skulle du göra just
int * y = x i stället för et-tecknet?
Ja.
Om x är redan en pekare, kan du ställa in 2 pekare lika med varandra,
i vilket fall Y inte skulle peka på x,
men det skulle peka på vad X pekar på.
Tyvärr kan vi för sent.
>> Vad jag vill säga i det här läget kan vi prata om det här offline
men jag skulle säga börja arbeta igenom problemet, # 14.
Du kan se det redan lite fyllas i för dig här.
Du kan se att när vi deklarerar 2 pekare, int * x och * y,
och konstaterar att peka * bredvid variabeln var något som gjordes förra året.
Det visar sig att detta liknar vad vi gör i år.
Det spelar ingen roll var du skriver * när du förklara pekaren.
Men vi har skrivit * bredvid den typ
eftersom det gör det mycket tydligt att du förklara en pekare variabel.
Du kan se att förklara de 2 pekarna ger oss 2 lådor.
Här när vi satt x lika med malloc
vad detta säger avsätter minne i högen.
Denna lilla ruta här, denna cirkel, ligger på högen.
X pekar på det.
Observera att y fortfarande inte pekar på något.
För att få minnes-för att lagra numret 42 till X
Vi skulle använda vad notation?
[Student] * x = 42.
Exakt, * x = 42.
Det innebär att följa pilen och kasta 42 där.
Här där vi satt y och x har vi y pekar på x.
Återigen är så här precis vad Kevin sa där vi satt y lika med x.
Y inte pekar på x.
Snarare är det att peka på vad x pekar på också.
>> Och slutligen i denna sista ruta finns 2 möjliga saker som vi kan göra.
En är att vi kan säga * x = 13.
Den andra saken är att vi kan säga-Alex, vet du vad vi kan göra här?
Man kan säga * x = 13 eller-
[Student] Du kan säga int vad som helst.
[Nate H] Om detta skulle kallas en int variabel som vi kunde göra det.
Vi skulle också kunna säga * y = 13 eftersom de är båda pekar på samma plats,
så att vi kunde använda antingen variabel för att komma dit.
Ja. >> [Student] Hur skulle det se ut om vi bara säga int x är 13?
Det skulle vara att förklara en ny variabel som heter X, som inte skulle fungera.
Vi skulle ha en kollision eftersom vi förklarade x för att vara en pekare upp här.
[Student] Om vi ​​bara hade detta påstående i sig vad skulle det se ut i termer av cirkeln?
Om vi ​​hade x = 13 då vi skulle ha en låda, och snarare än att ha en pil
kommer ut ur lådan vi skulle dra det som bara en 13.
[Student] i rutan. Okej.
>> Tack för att titta, och lycka till på Quiz 0.
[CS50.TV]