[Powered by Google Translate] [Rozdział 3] [mniej wygodne]
>> [Nate Hardison] [Harvard University]
>> [To jest CS50.] [CS50.TV]
>> Dobra, zaczynajmy.
Zapraszamy do tygodnia 4 z CS50.
Jeśli faceci otworzyć przeglądarkę internetową i otwórz Pset 3,
Wymieszaj z CS50, zamierzamy zacząć chodzić
przez sekcję pytań tam.
Podobnie jak w zeszłym tygodniu, będziemy pracować w CS50 Spaces
jeśli będziesz też ciągnąć, że aż tak dobrze,
i jeśli iść dalej i odwiedzić ten link, że mam tu na górze.
Nadszedł czas, aby zacząć.
Mamy naszą małą programu hi tutaj. Nic szalony.
Jedną z pierwszych rzeczy, które chcę zrobić z was jest dziś przejść kilka rozwiązań
Zestaw do problemu 1, rodzaj rozwiązań przykład
tak więc można poczuć jakie personelu kodu jest pisanie,
jakie rodzaje kodów innych studentów pisania,
i czy spojrzeć na to, bo wiem, że to dziwne,
podczas przesyłania rozwiązanie zestawu problemów i uzyskać komentarz
na własnej wersji, ale czasami jest to przydatne, aby zobaczyć jak inni to zrobili,
szczególnie te, które są ładne.
W przeważającej części, byłem naprawdę pod wrażeniem rozwiązań wy produkowane.
Jeszcze nie zaczął patrząc na 2s Set problem, ale jeśli są one coś jak pierwszy,
oznacza to, że tylko dobre rzeczy.
>> Jeśli spojrzeć na moich zmian, zacznijmy w dół w wersji 1,
i zamierzamy podjąć szybkie spojrzenie na rozwiązania Mario.
Jeśli ciągnąć ten fakt, te programy, które mamy zamiar przedstawić są prawidłowe.
Nie było zagadnienia poprawności tych problemów, ale raczej
chcemy rozmawiać trochę o różnych zagadnień projektowych
, które były tutaj stosowane.
Jedną z rzeczy, które były ciekawe rozwiązania
jest to, że użył tego nowego konstruktu nazwie pound zdefiniować,
czasami określane jako określenie mieszania.
Pozwól mi powiększyć tutaj.
# Define pozwala na nadanie nazwy tych liczb w programie.
W tym przypadku, maksymalna wysokość w Mario piramidy
był 23 i zamiast przedstawić 23 w moim kodu-
patrz my że ciężko kodowania 23 -
Zamiast tego daje MAX_HEIGHT nazwisko do tego numeru,
tak, że tu, w moim do-while
rzeczywiście można odnieść się do MAX_HEIGHT
zamiast uczynić numer 23 w.
[Student] Co to jest zaletą robi?
To jest dobre pytanie.
Jednym z nich jest czytelność.
Zaletą korzystania z tego # define jest czytelność.
Kiedy czytam ten kod, widzę, co się dzieje.
>> Widzę w tym stanie tutaj testujemy
na wysokość jest <0, co może się również zdefiniowane
się minimalną wysokość lub wysokość minimalna.
Inną zaletą jest to, że można to przeczytać resztę linii aby
także, że mamy do sprawdzenia, czy wysokość jest większa od maksymalnej wysokości,
bo będziemy kontynuować a wysokość jest większa od maksymalnej wysokości.
Inną korzyścią jest to, gdybym pomniejszyć trochę tu
jeśli uruchomić ten program i uruchomić go, powiedzmy, 23 już teraz,
zostanie wydrukowane wszystkie 23 wierszy po prostu.
Ale powiedzieć, że chciał zmienić wysokość max,
i teraz chcę, aby ograniczyć maksymalną wysokość piramid
być tylko powiedzieć-man, który był funky.
# Include, # define MAX_HEIGHT,
i powiedzmy, że chcemy, aby ustawić go w wysokości 10.
Teraz w tym momencie wszystko, co musiałem zrobić, to zmienić go w tym jednym miejscu.
Można ponownie skompilować kod, a teraz, gdy próbuję i wpisz 12,
poprosi mnie ponownie.
W tym przypadku mamy tylko za pomocą MAX_HEIGHT raz.
To nie jest, że duże z kłopotów, aby przejść
i zmienić go w pętli, jeśli trzeba.
Ale w programach, w których jesteś odwołującego samą liczbę magiczną
w kółko, to # define mechanizm jest naprawdę przydatne
bo po prostu zmienić go raz na górze file-to zazwyczaj, gdzie je-
Zmiana i przenika przez części pliku.
>> Inne rzeczy, które chciałem zwrócić uwagę w tym zadaniu, że myślałem, wyglądało naprawdę miło,
jeden był nazewnictwa zmiennych.
Widać tutaj, że mamy całkowitą zmienne zwane wiersz i wysokość tzw.
Spaces, asocjacyjne, pomaga uczynić kod trochę bardziej czytelne,
sprawia, że ​​trochę bardziej zrozumiała, co się rzeczywiście dzieje.
Jest to w przeciwieństwie do używania, na przykład, litery losowych
lub po prostu bełkot całkowicie.
Ostatnią rzeczą będę wskazać, że w pętli,
często te zmienne iteracyjnej, te liczniki, które używasz w pętli,
to średnia i konwencjonalnych je uruchomić zarówno z I, a następnie a następnie j k
i będzie stamtąd jeśli potrzebujesz więcej zmiennych,
i jest to tylko konwencja.
Istnieje wiele konwencji.
To zależy od języka programowania używasz.
Ale w C, zazwyczaj zaczynają się i.
To nie ma sensu używać, powiedzmy, lub b
się w zależności od sytuacji.
To jest to na ten jeden.
Jeśli teraz podciągnąć Revision 2, zobaczysz kolejny Mario,
a ten jest podobny do drugiego tak, że piły,
ale ma coś w rodzaju super.
Jeśli przyjrzymy się tej części tutaj wewnątrz wewnętrznej pętli for
oni używają jakiś szalony składni szuka tutaj właśnie w tej linii.
Nazywa się to operator trójskładnikowych.
Jest jeśli else skondensowane w jednej linii.
Warunkiem jest ta część w nawiasach.
Jest to równoznaczne z powiedzeniem, jeśli j <wysokości - i - 1.
I co wtedy zawartość, że jeśli blok byłby to przestrzeń
i zawartość, co będzie jeszcze są to #.
To zasadniczo przypisywania miejsca do tej zmiennej.
To oddanie miejsca w treści zmiennej bloku
Jeśli warunek ten jest spełniony, a jeśli warunek nie jest spełniony,
wtedy zmienna blok dostaje to #.
, A następnie, w trakcie, zamiast budowania cały ciąg
i drukowania wszystko na końcu Roztwór ten wypisuje jeden znak czasu.
Całkiem fajne.
>> Inną parę rzeczy do obejrzenia. Przeniesiemy się do chciwy.
Teraz, jeśli spojrzymy na chciwy, to pierwsze rozwiązanie
używa tych # definiuje całkiem sporo.
Mamy jeden stałą zdefiniowany dla każdego z różnych numerów w tym programie.
Mamy jeden dla centów za dolara, jeden dla kwartałach dimes, monet i grosze,
i teraz, jeśli przewinąć i przeczytać kodu,
widzimy standardowy-while wszystko drukowania LOOP OUT.
Kind of sedna tego problemu było uświadomienie sobie, że
potrzebne do konwersji pływaka, który odczytuje od użytkownika do liczby całkowitej
dokładnie do matematyki, a to dlatego,
z liczb zmiennoprzecinkowych, jak rozmawialiśmy o tym w wykładzie krótko
nie jest możliwe, aby dokładnie reprezentować każdą wartość na osi liczbowej
ponieważ jest nieskończenie wiele wartości między 3 i, powiedzmy, 3,1 nawet.
Możesz mieć 3,01 i 3,001 i 3,0001, i można iść dalej.
Okazuje się, gdy użytkownik pracuje z pieniędzmi, często chcesz przekonwertować
na liczbę całkowitą tak, że nie tracimy groszy i tego typu rzeczy.
Robi to i zaokrąglenie było kluczem.
To rozwiązanie stosowane idealnie prosty, dobry algorytm,
których zmniejszona liczbę centów pozostałych najpierw kwartałach
następnie dimes, następnie monet, potem grosze,
i dodawanie do liczby monet każdorazowo.
>> Innym rozwiązaniem, które zobaczymy, jak to pomniejszyć i przejdź do Rewizji 4,
miał bardzo podobny początek, ale zamiast używanego div i mod
tuż nad tutaj aby obliczyć liczbę centów.
To czwarte liczba jest równa liczbie centów podzielonych przez 25,
i powód to działa, ponieważ robimy całkowitą podział,
dlatego odrzucając jakiekolwiek reszta.
[Student] Czy musimy skomentować wyszukiwanie?
To naprawdę zależy.
[Student] Masz więcej niż komentowanie kodu tutaj.
Tak, a więc istnieje kilka różnych filozofii na ten temat.
Moja osobista filozofia jest taka, że ​​Twój kod jest rzeczywiście prawdą,
jak twój kod jest co faktycznie wykonywany na komputerze,
a więc kod powinien być czytelny, jak to możliwe, aby nie wymagało tyle komentarzy.
Powiedział, że gdy robisz rzeczy, które są swego rodzaju skomplikowane matematycznie
lub algorytmicznie, to dobrze, żeby komentować te, tak aby można
dodać dodatkowy wymiar, dodatkowy poziom do tego, kto jest czytanie kodu.
W tych rozwiązaniach, często są bardziej intensywnie komentuje tylko dlatego
chcemy być w stanie dystrybuować je i ludzie je odebrać
i przeczytać je dość łatwo.
Ale na pewno, zgadzam się, że to jest ciężkie.
[Student] Jednak w przypadku wątpliwości, przejdź cięższy?
W przypadku wątpliwości, przejdź cięższe.
Niektórzy ludzie czasami mówią 0 zwrotny czy coś takiego.
Myślę, że to śmieszne komentarz.
Oczywiście, że to co się dzieje.
Nie muszę polski mi powiedzieć, że.
Czasami ludzie będą pisać takie rzeczy "kthxbai!"
To trochę słodkie, ale także nie-
to nie robi różnicy między punktami komentowania czy nie.
Tego typu komentarze są po prostu ha, ha.
Cool.
>> W tym momencie, zacznijmy pracuje nad tym problemem Zestaw 3 części pytania.
Jeśli faceci ciągnąć ten ponownie,
jak w zeszłym tygodniu, że nie będziemy oglądać spodenki w tej sekcji.
Damy wam robić w swoim wolnym czasie i porozmawiać o pytania.
Ale teraz, w tej części mamy zamiar spędzić trochę więcej czasu
mówić o mniej podstaw kodowania
tak jak my w zeszłym tygodniu, a zamiast tego, mamy zamiar skupić się na
nieco więcej teorii, więc mówić o binarnym wyszukiwanie i sortowanie.
Od tych z Was, którzy śledzą razem z wykładem,
może ktoś mi dać podsumowaniem jaka jest różnica
pomiędzy wyszukiwania binarnego i poszukiwanie liniowego?
Co się dzieje? Jasne.
Liniowe szukane przeglądać każdego elementu w posortowanej liście
jeden po drugim, przez jeden przez jeden po drugim,
i wyszukiwanie binarne dzieli listę na 2 grupy,
Sprawdza, czy wartości kluczy, że szukacie jest większa lub mniejsza od wartości punktu środkowego
że po prostu znaleźć, a jeśli jest to mniejsza, to idzie z listy dolnej
i dzieli to jeszcze raz, nie sama funkcja
w dół, aż znajdzie środkowy być równa wartości samej.
Racja.
>> Dlaczego nas to obchodzi?
Dlaczego mówimy o binarnym wyszukiwanie kontra liniowy wyszukiwania?
Tak.
Binarny jest dużo szybciej, więc jeśli dwukrotnie rozmiar problemu
to ma jeszcze jeden krok, a nie dwa razy więcej.
Dokładnie.
To świetna odpowiedź.
Liniowe przeszukiwanie jest bardzo sprawdzając jeden element na raz,
a jak zobaczyłem na pierwszy dzień wykładu
Kiedy Dawid przeszedł przez jego przykład książki telefonicznej
i wyrwał jedną stronę książki telefonicznej w czasie
i przechowywane robić w kółko i od nowa,
to zajmie mu naprawdę dużo czasu, aby znaleźć kogoś w książce telefonicznej,
o ile, oczywiście, że szuka kogoś, na samym początku alfabetu.
Z wyszukiwaniem binarnym, można przejść o wiele szybciej,
i to nie tylko dwa razy szybciej i 3 razy szybciej lub 4 razy szybciej.
Ale problem staje się coraz mniejszy i mniejszy o wiele szybciej.
Aby to zilustrować, zaczniemy mówić o tym, co się dzieje
kiedy piszemy wyszukiwania binarnego.
Problemem jest to, że w zasięgu ręki, jeśli mam tablicę liczb,
powiedzmy, 1, 2, 3, 5, 7, 23, 45, 78, 12323,
a 9 z tonę 0s po nim,
chcemy być w stanie dowiedzieć się bardzo szybko, co jest w
ta tablica liczb.
Wiem, że to wydaje się trochę głupie i mało pomysłowo
ponieważ teraz jest.
Mamy tablicę, która nie ma bardzo wiele elementów w nim,
i jeśli mogę zapytać jednego z was, aby dowiedzieć się, czy
23 jest w tablicy, można to zrobić bardzo szybko
po prostu patrząc na to i mówi mi tak lub nie.
Analogowy do rozważenia jest sobie wyobrazić, jeśli to było, powiedzmy,
Arkusz kalkulacyjny Excel z 10.000 wierszy, 20.000 wierszy.
Oczywiście, można zrobić F polecenia lub sterowania F i poszukaj coś.
Można również użyć filtrów i rzeczy wyszukiwarki
ale gdybyś miał zajrzyj do tego pliku linia po linii po linii,
zajmie Ci dużo czasu, aby go znaleźć.
To trochę tak jak w przykładzie z książki telefonicznej, zbyt, gdzie
nikt nie patrzy przez książkę telefoniczną stronie jeden na raz.
Zwykle są one nie otworzyć w środku
lub w przypadku wielu książek telefonicznych i słowników gdzie
trzeba rzeczywiście to wprowadzisz pierwszą literę,
można przerzucić do tej pierwszej litery i otworzyć i rozpocząć przechodzi tam.
>> Przypomnij mi swojego imienia. >> Sam.
Sam.
Jak Sam powiedział, że liniowy proces wyszukiwania będzie bardzo powolny,
i zamiast z wyszukiwania binarnego, sposób działa to jest to, że
za każdym razem przejść przez iteracji naszego algorytmu przeszukiwania,
mamy zamiar podzielić listę na pół, w istocie,
na dwa mniejsze list.
A następnie na następnej iteracji, będziemy dzielić ją ponownie
do innych mniejszych list.
Jak widać, problem staje się coraz mniejszy i mniejszy
ponieważ zachowujemy pół odrzut listy za każdym razem.
Jak to działa discard?
Tylko jako przypomnienie, co będziemy robić, gdy byliśmy komputer
a my, powiedzmy, szukając numeru 5 na tej liście
jest to, że możemy wybrać numer w środku.
W środku tej liście, ponieważ jest 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 numerów,
dalszy wybrać na numer albo 4 pozycji lub w 5 pozycji,
a my nazywamy to środek naszej liście.
Wybierz numer w środku.
Następnie, podobnie jak Sam powiedział, będziemy sprawdzać, czy liczba ta jest równa
do numeru, który chcemy uzyskać lub naszego numeru żądanego.
Jeśli jest równe, to znaleźliśmy go. Wygramy.
Jeśli to nie jest równe, to istnieje kilka przypadków.
Dwa przypadki są albo liczba musi być większa od liczby patrzymy,
lub jest mniejsza niż.
Jeśli jest większa, możemy przenieść się w prawo.
A jeśli jest to mniej, ruszamy w lewo.
A potem powtórz cały proces jeszcze raz
albo na pół prawej lub lewej części listy.
>> Pierwszym problemem w dzisiejszej części jest dowiedzieć
jak możemy zacząć wyrażać to w kodzie C.
Mamy Pseudokod tutaj.
Co zaczniemy robić to ja wyciągnij zupełnie nową przestrzeń,
zapisać zmiany tak, że mamy te notatki na później,
my usunąć to wszystko, a następnie skopiować i wkleić ze zbioru problemowego
te informacje do naszych pomieszczeń, a miejmy nadzieję, że w ten sposób nie złamać.
Perfect.
Jeśli faceci wszystko zrobić, skopiuj i wklej ten kod do nowego miejsca,
do pustego jeden.
Spróbujmy Daniela. Jeśli skompilować i uruchomić ten program, to działa?
>> No Co on mówi?
Mówi sterowanie osiągnie koniec funkcji non-void.
Tak, więc pozwól mi spróbować uruchomić go.
Czy widzieliście tego wcześniej? Czy wiesz, co to oznacza?
Dobra, wnikliwie ten trochę.
To powiedzenie w file.c na linii 9, kolumna 1 mamy błąd, tak jak pan powiedział,
i mówi, że to wynikające z błędu i ostrzeżenia ostrzeżenia typu powrotnego.
To wygląda jak coś, co się dzieje z zwracanego typu, która ma sens.
Mamy funkcję non-void, co oznacza, że ​​mamy funkcję
że nie powróci pustkę.
Funkcja void jest jeden, który wygląda tak:
void foo (), i to jest nieważne, ponieważ typ zwracany jest nieważna,
co oznacza, że ​​jeśli coś się tutaj
jak powrót 1, to otrzymamy błąd kompilatora dla tego.
Jednakże, mamy non-void funkcja.
Nasze non-void funkcja jest w tym przypadku nasza funkcja wyszukiwania
ponieważ ma zwracanie typu BOOL.
Kiedy mówi, że sterowanie osiągnie koniec funkcja nie pustego,
to dlatego, że wyszukiwarka nie ma instrukcji return.
To nie jest powrót niczego typu BOOL.
>> Możemy to naprawić, a co myślicie
Wyszukiwarka powinna powrócić domyślnie?
Jaka powinna być zwracana wartość domyślna wyszukiwania?
Bo to, co możemy umieścić na końcu.
Charlotte, masz wszelkie-?
Prawda czy fałsz? >> Prawda czy fałsz.
Który?
False. Nie wiem.
Fałsz? Spróbujmy.
Dlaczego chcesz powiedzieć return false? To świetna intuicja.
[Charlotte] I nie wiem.
Będziemy return false w tym przypadku, ponieważ to będzie nasz domyślny
jeśli z jakiegoś powodu lista jest pusta lub igła
że szukasz, nie istnieje.
Następnie na samym końcu, jeśli nie zwróci true wcześniej w tej funkcji,
zawsze wiemy, że funkcja ta nie powie nope, to nie jest w tablicy.
To nie jest w stogu siana.
Jeśli teraz skompilować i uruchomić go-pozwól mi zapisać to tak, możemy wyciągnąć go.
Jeśli teraz skompilować i uruchomić nasz program, buduje.
Mamy naszą małą monitu.
Gdybym uderzył 4-uh-oh.
Nie drukuje nic. Wygląda na to, że wszystko skończyło dobrze.
Musimy wypełnić to w.
Rozmawialiśmy o algorytmie w Pseudokod trochę temu.
Pozwól mi zobaczyć, zapisać to,
i będę ciągnąć ten algorytm z powrotem ponownie.
Miejmy hit tego faceta. Nope.
Jest.
W jaki sposób możemy to zrobić?
Jaki byłby dobry strategia ruszania ten kod?
Musisz wybrać liczbę w środku.
Jak mamy wybrać numer w środku tablicy?
Jakieś sugestie?
[Student] strlen podzielone przez 2.
Strlen podzielić przez 2. To jest wielki.
Strlen działa ze szczególnych rodzajów tablic.
Jakie rodzaje tablic?
Tablice String, tablice znaków.
To ten sam rodzaj pojęcia, że ​​chcemy zastosować,
ale nie możemy używać strlen ponieważ nie mamy tablicę znaków.
Mamy tablicę liczb całkowitych.
Ale co strlen uzyskać dla nas?
Czy wiesz, co robi dla nas?
[Student] strlen dostaje nam długości.
Dokładnie, to robi się nam długość.
Strlen dostaje długość tablicy dla nas.
>> Jak dostaniemy się, że w naszym programie wyszukiwania binarnego?
Jak można uzyskać długość tablicy?
[Student] strlen?
Można dostać się na długość odpowiednio sformatowanej tablicy c łańcuch z strlen.
Problemem jest jednak to, że nie mamy tablicę ciągów.
Jeśli spojrzymy na ten kod, mamy tę tablicę liczb całkowitych.
Skąd wiemy, jak długo to jest?
[Student] Czy istnieje odpowiednik jeden dla punktu końcowego, jak int l, czy coś?
Okazuje się, że w rzeczywistości nie jest, a więc w pewnym sensie, jest to
jedna z tych rzeczy, które po prostu warto wiedzieć o C,
, że nie ma sposobu, aby długości tablicy
jeśli wszystko ci dać to tablica.
Powód to działa z ciągów, powodem strlen prace,
dlatego, jeśli ciąg jest poprawnie sformatowany,
będzie miał ten szczególny znak \ 0 na samym końcu.
>> Można też sobie wyobrazić, jeśli masz źle sformatowany tekst
i nie ma \ 0 znak tam, wtedy cała sprawa nie działa.
[Student] można dodać \ 0?
Możemy w tym przypadku.
Moglibyśmy dodać jakąś \ 0
lub jakaś wyraźna postać, a następnie użyć.
Ale to nie jest całkiem zadziała
ponieważ 0 \ dla char typu
i tutaj mamy wskazówki.
Inna sprawa, czy byliśmy użyć specjalnej wartości
jak -1 aby zaznaczyć koniec tablicy
potem nie mogliśmy zapisać -1 w naszych całkowitych tablic.
Chcemy być zatrzymany.
Okazuje się, że jedynym sposobem, aby uzyskać długość
z tablicy w języku C jest faktycznie pamiętam
gdy go skonfigurować, a następnie przekazać ją wokół z tablicy
tak, że gdy mam funkcji, która ma zamiar popracować
na tablicy liczb całkowitych lub pływaków lub podwaja czy co tam jeszcze,
Również trzeba dać funkcję tablicy na długość,
i to jest dokładnie to, co zrobiliśmy tutaj w funkcji wyszukiwania.
Jeśli spojrzeć, co zrobiliśmy, gdy przechodzimy w naszej tablicy tutaj
również przekazać w długości, rozmiaru.
To po prostu zdarza się, że nazwaliśmy tę zmienną tutaj
ten parametr lub argument.
Jest to tak zwana funkcja w listę argumentów lub listę parametrów,
i te nazywane są również argumenty lub parametry.
Ludzie używają różnych terminów w różnych czasach.
Czasem zamienić je sobie.
Tak się składa, że ​​to zmienna o nazwie podobnie
do tego # define tutaj.
Ale to nie to samo.
Kapitalizacja ma znaczenie.
>> Jeśli spojrzeć na to, co dzieje się tutaj, deklarujemy
nasz int tablica, której kiedykolwiek numerów.
Daliśmy mu nasz rozmiar, który odpowiada naszej # define się na szczycie.
To będzie 8.
A potem, kiedy wywołujemy naszą funkcję wyszukiwania na dole,
mijamy liczby chcemy wyszukać, co mamy monit,
dostał od użytkownika.
Mijamy w tablicy, te liczby,
, a następnie również zdać w wielkości tablicy
i wartość wielkości 8 zostaje zmagazynowany
lub przekazywane do tej zmiennej całkowitej o nazwie wielkości.
Mamy rozmiar tablicy.
Teraz, jeśli chcemy wrócić do tego, co mówiliśmy wcześniej,
Myślę, że Missy wychowany punkt, że to, co musieliśmy zrobić, to długość tablicy
i podzielić przez 2, a to da nam punkt środkowy.
Zobaczmy.
Czy mogę mieć ktoś napisać to i zapisać je w przestrzeni?
Jak o Leila?
Czy mogę napisać to w?
Napisz pierwszą linię, gdzie wziąć długość tablicy i dostać punkt środkowy
i zapisać go w nowej zmiennej.
Dam ci kilka sekund. Czy jesteś gotowy?
[Student niesłyszalne]
Jasne, mógłbym obliczyć punkt środkowy
macierzy haystack wewnątrz funkcji wyszukiwania
przy długości tablicy stogu siana, które jest zmienne wielkości?
Nic trudne tutaj.
[Leila] Just rozmiar / 2 i po prostu-
I zapisz go i naciśnij przycisk Zapisz się tutaj, na górze,
i będziemy ciągnąć ją.
Perfect.
Proszę bardzo. Awesome.
>> Jak jest, będzie to skompilować?
[Leila] Nie, to musi być wyższa.
[Nate] Tak, więc co trzeba zrobić?
[Leila] Podoba int środkowego czy coś.
Awesome. Tak, zróbmy to, int midpoint = rozmiar.
Będzie to skompilować?
Usuńmy ten komentarz i dostać go z drogi.
Co nie będzie kompilować na ten temat?
Nie robimy nic z liczby całkowitej,
więc trzeba go wydrukować lub coś takiego.
Tak, dokładnie.
Dostaniemy nieużywaną zmienną.
Co jeszcze nie będzie działać na ten temat?
Myślę, że powiedział coś, Sam. Średnikami.
Tak mi brakuje tych średników.
To będzie stałą rzeczą w trakcie trwania kadencji.
Ostatnią rzeczą zrobię to włożę jakiś spacje po obu stronach
tego operatora tutaj, ponieważ jest to zazwyczaj jak to robimy
zgodnie z naszym przewodniku.
Mamy punkt środkowy naszej tablicy.
Teraz, jeśli pamiętamy, z powrotem do naszego algorytmu,
co drugi krok, że mieliśmy do czynienia, gdy będziemy mieli punkt środkowy?
[Student] Jeśli jest większy [niesłyszalne].
Tak, więc musimy zrobić jakieś porównania, i co my tu porównanie?
Powiedziałeś, że jeśli jest ona większa niż. Co jest w tym zdaniu na myśli?
Numer, który pojawia się, jeśli jest to więcej niż w połowie, a następnie przejść do tablicy?
Dokładnie, więc numer, który pojawia się, gdy we-
Igła, więc jesteśmy w stosunku do igły,
i co mamy porównanie z igłą?
Ponieważ igły jest to, czego szukasz.
Mamy porównanie jej dostać się do środkowego.
>> Ale czy jest sens, aby sprawdzić,
jeśli igła = midpoint?
Czy to ma sens?
Czy ktoś się nie zgadza?
Dajmy mu spróbować, jeśli (igła == midpoint).
[Student] Czy printf go znalazłeś.
[Nate] printf ("Znaleźliśmy go \ n");
Inaczej-Jestem zamiar zacząć robić coś innego tutaj.
Mam zamiar rozpocząć wprowadzanie nawiasy klamrowe wokół if cały czas
tylko dlatego, że jeśli dodamy więcej rzeczy, a następnie
nie mamy do kompilatorów.
Tak, Sam. Masz rację.
Problem jest, że punkt środkowy reprezentuje pozycję w tablicy,
ale można je dostać do reprezentacji wartości w tej pozycji tablicy.
To świetny punkt.
Czy wszyscy usłyszeć, co powiedział Sam?
Powiedział, że jak to jest punkt środkowy
reprezentuje tylko pozycję w tablicy, ale nie jest to rzeczywisty element w tablicy.
Jeśli myślisz o kodzie jak pisemnej teraz,
jeśli przyjrzymy się tej tablicy na dół, który ma 8 elementów w nim,
co jest wartością midpoint będzie w tej funkcji?
[Student] 4.
[Nate] 4.
Jeśli spojrzymy na liczbę 4 -
i możemy po prostu uruchomić ten kod i umieścić trochę smutną twarz tutaj
dlatego, że nie uważają, że-jeśli ten kod
jak to jest teraz, przesyłając go, budynek, niech przewijać w dół,
i jeśli spojrzymy na liczbę 4,
okazało się to, ale nie dostaliśmy to printf tak.
Jednym z powodów jest to, że nie zwraca true,
ale naprawdę znaleźć numer 4?
I Sam mówi nie.
Co widzimy?
Naprawdę znaleźć punkt środkowy, który jeśli spojrzymy na tablicy na dole,
to będzie elementem o indeksie 4, że mamy do czynienia,
który jest 23.
>> Jak możemy rzeczywiście dostać ten element w połowie
i to nie tylko midpoint sama?
[Student] Chcielibyśmy wprowadzić znak, czy coś?
Co by to zrobić, po prostu z ciekawości?
Możesz rozwinąć trochę więcej?
Trzeba przekształcić pozycję w liczbie,
więc masz zrobić jakiś związek-Myślę, że to znak, ale to nie może być.
Tak, to dobry punkt.
Robiliśmy dużo tego stanowiska do konwersji znaków, znaki te,
W dwóch pierwszych problemów.
Okazuje się, że tutaj jest to podobne do prawie
dostępu do Ith charakter w ciągu, jeśli to ma sens.
Tutaj chcemy uzyskać dostęp do elementu środkowego.
W jaki sposób możemy to zrobić?
Kevin, masz jakieś propozycje w jaki sposób możemy to zrobić?
Można zrobić stóg, open bracket, mid, zamknięty nawias.
Można napisać, że dla nas?
Zapisz go w tutaj, i będziemy ciągnąć tę górę.
Patrzymy na tej linii 9,
i mamy świadomość, że nie chcemy, aby porównać igłę do punktu środkowego,
, ale zamiast tego, chcemy porównać igłę
do elementu, w środkowym położeniu w naszej tablicy stogu siana.
Cool.
Proszę bardzo.
Tak, to wygląda całkiem nieźle, jeśli (igła == stóg [midpoint]).
Znaleźliśmy ją.
Jeśli teraz uruchomić kod we'll plecy się trochę-
kompiluje, uruchamia, a teraz, jeśli spojrzymy na 4,
nie znaleźliśmy, bo teraz jesteśmy rzeczywiście coraz numer 23.
Dostajemy wartość za 23, i to, co mamy w stosunku do naszej igły.
Ale to dobrze. To krok w dobrym kierunku.
>> To, co staramy się robić.
Nie chcemy, aby porównać igłę przed pozycji w tablicy
ale raczej w stosunku do rzeczywistych elementów w tablicy.
Jeśli spojrzymy ponownie teraz na kolejny krok w naszym algorytmie,
jaki jest następny krok?
Leila już wspomniano krótko.
[Student] Sprawdź, czy jest większa lub mniejsza niż, a następnie zdecydować, w którą stronę się ruszyć.
[Nate] Tak, tak, w jaki sposób to zrobić?
Czy można umieścić w jakimś-Będę zapisać zmiany,
, a następnie, jeśli umieścić w niektórych liniach, że tego nie zrobi.
Tak, Charlotte. >> Mam pytanie.
Czy nie powinno być midpoint - 1, ponieważ pierwszą rzeczą jest
to 0 indeksowane, więc jeśli do 4, to nie jest faktycznie charakter szukamy?
Tak, drugi problem, że jest,
że to świetny chwyt, bo to, co się dzieje do końca się dzieje ewentualnie
jeśli będziemy w ruchu, a my nie zawsze dostosować początkowo?
Chyba to, co możemy w końcu robić próbuje uzyskać dostęp do
Element na 8. pozycji tablicy
która w tym przypadku nie istnieje.
My chcemy zrobić jakieś księgowania fakt
że mamy pewne zera indeksowanie.
[Charlotte] Przepraszam, miałem na myśli środkowy - 1 w nawiasach kwadratowych.
Możemy to zrobić.
Wrócimy do tej kwestii za chwilę.
Kiedy zaczynają się do rzeczywistej zapętlenia,
wtedy będziemy naprawdę zobaczyć to wchodzą w grę.
W chwili obecnej, możemy to zrobić, ale jesteś całkowicie w porządku.
Że zero indeksowanie będzie miał wpływ, że musimy uwzględnić.
Zobaczmy.
>> Jak jest powyżej i poniżej,?
[Student] mam jak zrobić powyżej i poniżej części.
Po prostu nie byłem pewien, co do drukowania, jeśli okaże się, że jest to mniej niż w połowie stogu siana lub większa.
Tutaj można zapisać co I've-
[Nate] Tak, jeśli zapiszesz, co masz, i będziemy ciągnąć ją.
Proszę bardzo.
[Student] I umieścić znaki zapytania na to, czego nie wiem.
[Nate] To wygląda świetnie.
Tutaj mamy znaki zapytania, bo jeszcze nie wiem
co będziemy robić jeszcze dość.
Co mielibyśmy zrobić-ups, mamy kilka szelki wszystko funkowe na nas.
Będziemy skorygować te szelki.
Proszę bardzo.
A więc co chcemy robić, zgodnie z naszym algorytmie,
jeśli nie możemy znaleźć igłę?
Powiedzieć w przypadku, że igła jest mniej niż to, co mamy do czynienia. Kevin.
Patrzeć tylko na lewej połowie.
Prawo, tak więc możemy umieścić komentarz w tutaj, że mówi: "spójrz na lewej połowie."
A jeśli igła jest większa niż stogu siana w połowie, co chcemy zrobić?
[Student] Następnie spojrzeć na prawej połowie.
Spójrz na prawej połowie, "spojrzeć na prawej połowie."
Nie zbyt brudny.
Ok, więc w tym momencie, sprawy wyglądają całkiem nieźle.
Problem z kodem, jak pisemnej jest co?
[Student] Nie masz punkty końcowe dla połowy.
Racja, nie mamy punkty końcowe dla połowy.
Również tylko będzie przejść przez to raz.
My tylko będzie wyglądać w jednym punkcie środkowym.
Albo element jest tam, czy to nie jest.
W celu uzupełnienia tego, musimy zrobić jakieś powtarzanie.
Musimy powtarzać, aż okaże się, że
albo element jest tam bo mamy zawężony i wreszcie znalazłem,
czy to nie jest tam, bo szukałem przez wszystkie rzeczy,
w odpowiednich połówek tablicy i znaleziono, że nie ma tam.
>> Ilekroć mamy to powtórzenie dzieje, co będziemy w użyciu?
[Student] pętla.
Jakiś rodzaj pętli. Tak.
[Student] możemy zrobić do-while i go zrobić, a następnie przy
Igła nie nie równa-Jestem pewien, gdzie idę z tym.
Ale tak jakby zrobić dopóki nie jest równa wartości, że dane wejściowe.
Tak, więc zobaczymy, jak można to napisać sam?
Mówiłeś, użyjmy do-while.
Gdzie zrobić początek?
[Student] Zaraz po wielkości / 2.
[Nate] Dobra, i co my teraz zrobimy?
Będziemy wypełnić chwilę później.
Co my teraz zrobimy?
[Student] Nie chcemy robić wszystkie rzeczy mamy w razie części?
[Nate] Czy to wszystko, to świetnie.
Kopiuj i wklej.
Oh, man.
Zobaczmy, czy to działa, jeśli możemy to ponad tab.
Beautiful.
Okay, a my zapisać to tak, macie to.
Dobra, i mamy zamiar to zrobić, gdy-
co było warunkiem, gdy byłeś po?
[Student] Podczas gdy igła nie równa, tak jak wykrzyknikiem.
Ale nie jestem pewien, co to dokładnie jest jeszcze.
[Nate] Tak, to jest jeden sposób, aby to zrobić.
Sam, masz komentarz?
[Sam] Pamiętam, kiedy patrzyłem na filmy,
Zrobiłem zrzut ekranu z jednej, jak wtedy, gdy robiliśmy Pseudokod dla niego,
był jakiś związek między max i min.
Myślę, że to było coś jakby max jest zawsze mniej niż min.
Rozumiem.
[Sam] Albo jak jeśli max jest nie mniejsza niż min lub coś takiego,
bo to znaczy, że został przeszukany wszystko.
>> Tak, i co to brzmi max i min były na myśli?
[Sam] Wartości że-liczby całkowite, że się zmieni
w stosunku do których możemy umieścić punkt środkowy.
Dokładnie.
[Sam] W tym momencie, to będzie [niesłyszalne] obliczyć max i min.
Punkt środkowy jest to max i pomysł min.
Czy to ma sens do ludzi?
Jeżeli mielibyśmy zacząć patrzeć na jaki mamy zamiar to zrobić iteracji,
masz całkowitą rację, że chcemy użyć jakiegoś-while pętli.
Ale myślę, że jeśli będziemy pamiętać, co dzieje się w miejscu, z tej tablicy
i to, co faktycznie dzieje się-Jestem zamiar napisać tutaj-
w pierwszej iteracji binarnego wyszukiwania, mamy-
Zamierzam użyć B i E do oznaczenia początku.
A potem koniec naszej tablicy.
Wiemy, że na początku jest na 4 prawa tutaj,
i wiemy, że koniec jest na 108.
Powiedzieć, że jesteśmy wyszukanie numeru 15.
Pierwszy raz to zrobić, jak widzieliśmy wcześniej,
midpoint jest albo będzie 16 lub 23
w zależności od sposobu obliczania rzeczy.
Ponieważ dzieląc równo w połowie da nam tę przestrzeń
między 16 i 23, nie można równo podzielić
lub podzielić go i dostać w prawdziwego środkowego.
Przyjrzymy 16.
My sobie sprawę, "Hej, 16> 15, że szukamy".
Aby następnie spójrz na lewej połowie tablicy
co będziemy w końcu robić to odrzucając
cała górna część
i mówi: "Dobra, teraz nasz końcowy będzie tutaj".
Następna iteracja naszej pętli, jesteśmy teraz patrząc na tej tablicy
faktycznie po wyrzucić tę część, bo teraz
jeśli bierzemy punkt środkowy jako różnica pomiędzy początkiem i końcem,
odnajdujemy nasz midpoint być 8,
które możemy następnie przetestować 8 aby zobaczyć, gdzie to jest w stosunku do liczby szukamy,
15, okaże się, że 15 jest większa,
więc musimy przenieść się do prawej części listy,
co wiemy, bo jesteśmy ludźmi i możemy go zobaczyć.
Wiemy, że prawa część będzie gdzie go znaleźć,
ale komputer nie wie, że to co będziemy robić to faktycznie dowiemy
za to w górę, a teraz początek i koniec
są tym samym miejscu, to staje się punkt środkowy tylko numer na liście w tym momencie,
który jest 15, a my już ją znalazł.
Czy to rzucić trochę światła na którym cała ta notacja min max i będzie,
śledzenie końców tablicy, aby dowiedzieć się,
jak zawęzić rzeczy w dół?
>> Co by się stało, gdyby to nie była równa 15 teraz?
Co zrobić, jeśli szukaliśmy 15 i zamiast tego numeru były również 16?
Chcemy powiedzieć: "Och, to jest większa.
Chcemy wrócić do lewej ".
I chcemy przenieść nasze e prawo,
W tym momencie mamy punkt końcowy, które byłoby sprzeczne.
Nie będzie w stanie znaleźć wszystkie inne elementy
bo teraz mamy punkt końcowy i nasz punkt początkowy,
nasz max i nasz min, teraz odwrócony.
Mamy przeszukiwać całej tablicy. Nie możemy niczego znaleźć.
To jest punkt, w którym chcielibyśmy powiedzieć: "Dobra, mamy zamiar zatrzymać tego algorytmu.
Nie znaleziono niczego. Wiemy, że nie jest tutaj. "
Jak to się dzieje?
[Student] Jak dokładnie działa komputer przełączyć koniec?
Jak koniec skończyć przed początkiem?
End kończy się przed rozpoczęciem
ze względu na matematyce, że będziemy robić za każdym razem to zrobić.
Sposób wymiany jest, jeśli spojrzeć na po raz pierwszy robimy to swapa
gdzie mamy początek na 4 i koniec
w dół na 108 i nasz punkt środkowy, powiedzmy, w 16 -
Mam zamiar przywrócić to z powrotem do 15-jeśli patrzymy na 15,
wiedzieliśmy, że to, co zrobiliśmy, gdy zameldowaliśmy się 16 i zobaczyłem, że był większy
i chciał odrzucić całą prawą część listy,
widzieliśmy, że to, co chcieliśmy zrobić, to przenieść ten e tutaj.
Skutecznie, e zostaliśmy przeniesieni do jednego przed środkowego.
Podobnie, gdy zrobiliśmy to iteracji algorytmu
i był na 8 punkt środkowy,
okazało się, że 8 <15, więc chcieliśmy, aby przenieść b.
jeden obok środkowego.
Teraz, początek i koniec są zarówno razem w tym 15.
>> Gdybyśmy dzieje szukać jakiejś innej wartości, a nie 15,
lub, jeśli zamiast 15 było już 16,
nie stwierdzono, że e chcemy przenieść jeden przed środkowym.
E teraz odwrócony będzie nie mniej niż w B.
Przejdźmy przez jak faktycznie kończy się ten algorytm kodowania.
Wiemy, że chcemy mieć to obliczenie środkowego.
Wiemy również, że chcemy śledzić początek i koniec tablicy
naszej aktualnej tablicy, dzięki czemu możemy dowiedzieć się
w przypadku gdy lewa połowa liście i gdzie prawa połowa jest na liście.
Robimy to albo z rozpoczęcia i zakończenia,
lub możemy nazwać ich min i max.
Użyję rozpoczyna i kończy się tym razem.
Kiedy zaczynamy, jeśli spojrzymy na nasz przykład tu,
nasz początek był ustawiony na początku tablicy, jako naturalne.
Co indeks to było? Jakie powinny być nasze zaczynają być?
Daniel.
[Daniel] Haystack [0].
[Nate] Tak, więc możemy ustawić go równa stogu [0].
Problem jest jednak to, że nie daje nam położenie pierwszego elementu.
To daje wskaźnik pierwszego elementu lub wartości rzeczywistej w tym pierwszym położeniu.
[Student] To będzie konwersja do 0.20?
[Nate] Co to będzie zrobić, to, no cóż, to nie będzie żadnych konwersji.
Co to będzie zrobić, to będzie przechowywać 4 w początek,
i to będzie trudne do porównań przed rozpoczęciem
bo begin zorganizuje wartość 4,
która jest początkiem naszej tablicy,
ale chcemy śledzić indeksy w tablicy
w przeciwieństwie do wartości.
Będziemy faktycznie użyć 0, tak.
Do końca tablicy-Charlotte przyniósł to się trochę wcześniej.
To jest, gdy weźmiemy pod uwagę zerowy indeksowanie.
>> Charlotte, co koniec tablicy?
Co to jest indeks na końcu?
[Charlotte] Rozmiar - 1.
Tak, i jaki rozmiar powinniśmy użyć?
Powinniśmy wykorzystać wielkości kapitału lub małą wielkość?
Wielkość kapitału.
W tym przypadku, może używamy wielkość kapitału.
Jeśli chcieliśmy funkcja być przenośne
i korzystać z tej funkcji w innych programach,
faktycznie możemy wykorzystać małą wielkość.
To jest w porządku.
Ale Charlotte jest całkowicie słuszne, że chcemy mieć rozmiar - 1.
W tym momencie,
[Student] Jak to jest, że można używać wielkiej rozmiaru?
Jak to jest, że możemy korzystać z wielkiej rozmiaru?
Okazuje się, że te # definiuje są naprawdę,
pod maską, tekst jak znaleźć i wymienić, jeśli to ma sens.
Podczas kompilowania kodu, faza przerób
z kompilatora przechodzi pliku,
i wygląda na to, że na całym świecie napisałeś wielkość kapitału,
i zastępuje ten tekst dosłownie z 8, tak po prostu.
W tym sensie, to jest bardzo różni się od zmiennej.
Nie zajmuje miejsca w pamięci.
Jest to prosta sztuczka replace text.
W tym przypadku, mamy zamiar wykorzystać rozmiar.
Stąd chcę zrobić jakieś powtórzenie,
i jesteśmy na dobrej drodze z naszym do-while.
Chcemy coś zrobić, dopóki stan nie utrzymuje już,
i jak widzieliśmy wcześniej, widzieliśmy, że warunek
było rzeczywiście, że nie chcemy się do końca
powinna być mniejsza niż rozpocząć.
>> To jest nasz stan zatrzymania.
Jeśli to nastąpi, chcemy się zatrzymać i jak deklaruje, "Hej, nie znalazłem nic."
Aby wyrazić to, chcemy użyć jakiejś pętli.
W tym przypadku, to byłoby do-while, do pętli, pętla?
Mamy do-while tutaj.
Czy faceci lubią tego podejścia?
Czy uważasz, że powinniśmy spróbować innego podejścia?
Kevin, jakieś przemyślenia?
Moglibyśmy mieć pętlę while, ponieważ wiemy, maksymalnie
będzie większa od min w tak czy inaczej startu.
Tak, więc nie ma inicjalizacji, który musi się zdarzyć.
Te-while Pętle są świetne, kiedy masz coś do zainicjowania
wcześniej badania, podczas gdy tutaj
wiemy, że nie będziemy trzymać reinitializing zarówno początek i koniec
każda runda pętli.
Wiemy, że chcemy zainicjować je, a następnie sprawdzić naszą kondycję.
W tym przypadku, ja rzeczywiście iść z prostego pętli.
Okazuje się, że do-while stosowane są pętle dość rzadko.
Wiele miejsc nawet nie nauczy nie pętle while.
Są dobre do obsługi danych wejściowych użytkownika, więc widzieliśmy wiele z nich do tej pory.
Ale normalne, a gdy pętle są dużo bardziej powszechne.
Okazuje się, że warunek ten, jak napisane
nie będzie nam naprawdę wiele dobrego, a to dlaczego?
Przykro mi, nie wiem, jak się nazywasz.
Jestem Jerry. >> Przepraszam?
To B-O-R-I-U.
Oh, w porządku.
Nie widzę Cię na mojej liście.
Oh, to dlatego, oh, to ma sens.
Czy masz jakiś pomysł, dlaczego ta pętla może nie działać zgodnie z przeznaczeniem,
jak napisane z warunkiem?
[Jerry] To znaczy, jak chcesz wszystkie rzeczy po nim do-?
Tak, tak, że jest jedna.
Możemy umieścić wszystkie z tych rzeczy do pętli while, która jest całkowicie prawdziwe.
Inna sprawa, że ​​to trochę bardziej problematyczne jest jednak to, że warunek ten nie działa.
[Student] Musisz przerzucić go.
Dobra, więc ten warunek nie będzie nigdy prawdziwym początkowo sposób rozmawialiśmy o tym.
Chcemy coś zrobić, dopóki <koniec rozpocząć,
ale my chcemy zrobić coś, podczas
rozpocząć koniec ≤.
>> Jest, że odwrócenie logiki tam.
Jestem popełnia te błędy cały czas.
[Student] Dlaczego to musi być mniejsza lub równa?
Ponieważ Pamiętasz sprawę, że mamy do
gdzie był tylko jeden element, a my w dół,
i szukaliśmy na tylko 15 w naszej tablicy?
A nasz początek i nasz koniec był taki sam element.
Chcemy się upewnić, że załatwiamy tę sprawę.
Jeśli nie bezpośrednio poniżej,
chcemy być w stanie dostać się do 2-elementu tablicy.
Kiedy dostaliśmy się do tego ostatniego elementu, jeśli to nasz element, że nigdy nie znajdziesz.
Teraz tutaj, możemy zrobić dokładnie tak, jak mówisz.
Możemy zacząć plopping rzeczy prawo w środku naszej pętli.
Możemy plop naszego środkowego.
Możemy podjąć wszystkie te instrukcje if,
wyciągnąć ich z tego do-while,
plop je,
czyste rzeczy się trochę,
a ja pójdę dalej i zapisać zmiany.
I w tym momencie jesteśmy już całkiem blisko.
Sam.
Myślę, że trzeba też mieć int półmetku size = - 1/2.
Masz to, rozmiar - 1/2.
Czy coś jeszcze trzeba zmienić w tym wierszu?
To był dobry chwyt.
>> Jakie rozmiar zrobić? Czy kiedykolwiek zmiany rozmiaru?
W celu zachowania linii tak, musimy zmienić rozmiar.
Musimy zmienić rozmiar każdym razem gdy pojedziemy wokół pętli for.
Ale pamiętam, kiedy szliśmy przez naszego przykładu tylko trochę wcześniej,
i mieliśmy początek na 4
i koniec wszystkie sposób w temperaturze 108?
Jak obliczyć punkt środkowy?
Gdybyśmy na podstawie rozmiaru?
Lub używaliśmy rozpocząć i zakończyć w zamian?
Jest to różnica pomiędzy końcem i początkiem.
Dokładnie, i jak dokładnie należy napisać, że Charlotte?
Tylko koniec - zaczyna.
Nie musisz zrobić - 1
ponieważ - 1 został w końcu i zacząć już.
[Nate] Świetnie, jesteś całkowicie w porządku.
Nie mamy zrobić - 1, ponieważ - 1 został ujęty
i stanowiły kiedy zainicjować zmienną zakończenia.
>> Czy jest jeszcze coś, co należy zrobić, aby składniowo ta linia ma sens?
[Student] Plus zaczyna. >> Plus zacząć?
[Student] Pod koniec.
Bo to jedynie liczone pół długości.
Musisz dodać rozpocząć.
[Nate] Co by to obliczyć dla nas?
Jeśli myślimy o końcu tej pierwszej iteracji,
end będzie w indeksie pozycji 7.
Zaczyna się w pozycji 0.
Pamiętaj, że szukamy albo
pozycji 3 lub 4 pozycji.
Jeśli przyjrzymy się tej matmy, żeby zrobić to trochę bardziej namacalna,
umieścić kilka numerów tutaj, mamy 7, 0,
tak 7 - 0, i / 2
3 w jest liczbą całkowitą podziału, która jest.
Wtedy nie musimy dodaj ponownie nasz zacząć?
My nie w tym przypadku.
W pierwszej iteracji, to będzie w porządku, bo begin jest 0.
Ale jak postęp, mamy naprawdę wszystko, tylko trzeba
end - rozpocząć / 2.
Jest jeszcze jedna sztuczka, tutaj, i to mianowicie jedna z pierwszeństwa.
[Student] Czy musimy nawiasów?
[Nate] Dokładnie, a to dlatego, że jeśli nie umieścić te nawiasy,
to ta linia będzie interpretować zamiast
as (end) - (początek / 2), która na pewno nie chcesz.
Uważaj na tych reguł priorytetowych.
[Student] Dlaczego nie jest to skończy + zacząć?
Dlaczego nie jest to skończy + zacząć?
[Student] Dlaczego nie jest to?
Dlaczego miałby to być +?
Myślę, że masz rację.
[Student] Bo to jest średnia?
[Nate] Koniec + zacząć, masz całkowitą rację.
Wow, ja całkowicie goofed. Masz rację.
Jeśli robimy znak minus, to chcemy dodać rozpocząć widok
W tym przypadku, że jesteś bardzo dobrze, że chcemy wziąć średnią z dwóch,
więc chcesz je dodać, a nie odjąć im.
[Student] Będzie również działać, jeśli nie koniec - rozpoczyna / 2 + zacząć.
Byłoby jeśli robimy-Wierzę, że tak.
>> Na przykład, jeśli zostały patrząc rozpoczęciem
i przesunął go tutaj
do 15.
Teraz zaczyna się w pozycji 2 jest.
Koniec jest w pozycji 7.
Jeśli odejmiemy je dostajemy 5.
Podzielić, że przez 2, otrzymujemy 2.
A następnie dodajemy 2 z powrotem,
i że ma nas na 4. pozycji,
który jest tutaj, co jest midpoint.
[Student] Czy trzeba dbać o opakowaniu?
W jakim sensie musimy dbać owijania?
Jeśli suma lub różnica pomiędzy
w zależności od tego, jak to zrobić, nawet nie jest liczbą.
Następnie komputer się pogubi, czy kiedy to 2,5;
Ci przejść w lewo lub w prawo, aby określić, który jest środkiem boku?
Rozumiem.
Okazuje się, że z całkowitej podziału,
nie zawsze dostać tych liczb zmiennoprzecinkowych.
Nigdy nie dostać po przecinku.
Jest całkowicie odrzucone.
Jeśli masz komputer dzielą dwa int zmienne,
i jeden 7, a drugi jest 2,
nie dostaniesz 3,5 wyniku.
Będzie się 3.
Pozostała część zostanie odrzucona, więc jest skutecznie zaokrąglania
nie okrągły, lecz piętro, jeśli faceci znają, że w matematyce,
gdzie można całkowicie odrzucić przecinku,
i tak jesteś w zasadzie obcinania go w dół do najbliższej
Cała pozycja, do najbliższej liczby całkowitej.
[Student] Ale to jest to problematyczne, ponieważ jeśli masz tablicę 7 elementów
wtedy automatycznie wykona 3-ej z punktu środkowego, a nie 4..
Jak możemy sobie z tym poradzić?
Jest to problematyczne, ponieważ jeśli mielibyśmy tablicy 7,
to pick 3-ci zamiast 4th.
Czy mógłbyś wyjaśnić nieco więcej?
[Student] Bo jeśli masz 7 elementów następnie 4-ej
będzie midpoint, prawda?
Zapamiętaj swój komentarz o zerowej indeksowane, choć.
[Student] Tak, tak, w pozycji 3. To byłoby midpoint.
Tak.
Oh, w porządku. Rozumiem, co masz na myśli.
To trochę dziwne, jak przyzwyczaisz się do tej całej koncepcji
pozbycie przecinku.
To świetny punkt.
Skończmy to.
Mamy obliczyć nasz środkowy.
>> Testujemy czy igła jest naszą równa średniej wartości.
Jesteśmy drukowania, że ​​znaleźliśmy go, ale tak naprawdę, co chcemy zrobić w tej sytuacji?
Znaleźliśmy go, więc chcemy dać rozmówcy wiedzą, że ją znalazł.
Mamy funkcję, która jest logiczna wpisywanych funkcji.
Sposób, w jaki sygnał do wywołującego naszej funkcji, że jesteśmy gotowi do
jest powiedzieć: "Hej, to jest prawda."
W jaki sposób to zrobić, Kevin?
Jesteś kiwając głową. >> [Kevin] Dodaj return true.
[Nate] Dokładnie, zwróci true.
Teraz, jeśli nie jest równa, w jaki sposób patrzymy na lewej połowie?
Jakieś pomysły?
Stella, jakieś pomysły?
Musisz ustawić nową pozycję końca.
Tak.
Tak więc mamy do czynienia pozycji środkowego - końcowy.
Great.
Musimy ustawić nową pozycję na koniec
spojrzeć na lewej połowie.
Było to o czym rozmawialiśmy przed gdzie
I wracamy do tego przykładu.
I zaczyna się tutaj, a następnie do końca mam całą drogę tutaj.
>> Ponownie, jeśli szukamy 15, a nasz punkt środkowy przypada na 16,
i zdajemy sobie sprawę, "Oops, 16 jest większa.
Chcemy, aby przejść do lewej połowie. "
Mielibyśmy wtedy przesunąć koniec do 15,
i robimy to, że biorąc jeden z dala od punktu środkowego
i ustawienie, że naszym nowym końca.
Podobnie, jeśli chcemy, aby spojrzeć na prawej połowie, w jaki sposób to zrobić?
Czy masz jakiś pomysł?
[Student] Wystarczy ustawić zacząć półmetku + 1.
[Nate] Great.
I teraz w przypadku, że nie znajdziemy niczego,
zgadza się, że dostać się pod opieką dla nas?
Daniel, to ma się pod opieką dla nas?
[Daniel] L.
[Nate] Jeśli robimy to przez cały zespół i nie znajdziemy niczego,
gdzie by to być pod opieką, czy powinniśmy się tym zająć?
[Daniel] warunek while.
[Nate] Tak, warunkiem natomiast, dokładnie.
Będzie dbać, przechodząc przez całą tablicę, jeśli nie znalazł niczego.
Ta pętla będzie końca.
Nigdy nie spotkałem tego warunku,
i możemy powrócić false.
Możemy też zostawić to, czy tu tak
bo jeśli to, jeśli stwierdzenie jest prawdziwe,
i nasza funkcja powróci,
i tak będzie w istocie abort ta funkcja w tym punkcie
kiedy wrócimy prawda.
Ale co się dzieje z tym struktury tutaj?
To będzie działać w całości, czy też istnieje jakiś logiczny błąd w tam?
>> Istnieje pewna logiczna wada tam z sposób to skonfigurować.
Co to może być?
[Student] Dlaczego musisz - i + 1s?
Który wyznacza naszą tablicę do być nasz nowy lewy i prawy pół pół.
[Student] Ale dlaczego nie można tego zrobić bez - 1s i + 1s?
[Nate] Możemy ustawić go równa połowie?
, Co może być problematyczne, o tym?
[Student] Myślę, że to nieskuteczne, ponieważ jesteś sprawdzanie wartości, które już zostało zaznaczone.
[Nate] Dokładnie, więc Sam jest całkowicie w porządku.
Jeśli ustawisz się do końca i zacząć równa połowie
zamiast - 1 + 1 i refleksyjnie,
w pewnym momencie w przyszłości będziemy skończyć sprawdzając środkowy ponownie.
[Student] zacząłem PSET, a potem miałem coś podobnego
gdzie Zapomniałem + 1, i utknął w nieskończonej pętli.
Racja, bo w pewnym momencie, że nigdy nie będziemy się zaczynać i kończyć
faktycznie pokrywają.
Cool.
Jest jeszcze jedna logiczna wada, i że jest to, że z całą pewnością należy
else if.
Jaka może być tego przyczyna?
>> Powodem jest to, jeśli to nie jest inny, jeśli-to widziałaś, Kevin?
[Kevin] Tak, bo jesteś zmieniających punkt końcowy.
[Nate] Dokładnie.
Mamy zmianę punktu końcowego,
i jeśli jest napisane jak to zrobić-we'll przestrzenie między-
będzie sprawdzić tę sprawę.
W takim przypadku, jeśli się powiedzie, zostanie przerwana z funkcji.
Wtedy będzie sprawdzić to kolejny przypadek,
a jeśli to się uda, będzie to ustawić punkt końcowy,
a następnie będzie dalej i sprawdzić tę sprawę.
Ale w tym momencie, że nie chcemy go kontynuować sprawdzanie.
Na szczęście nie mamy zresetować środkowy tutaj
i wiemy, że ta sprawa nie uda.
Ale na pewno chcesz umieścić if tam
mimo że może w tym przypadku
ponieważ nie jesteśmy dostosowując środkowy, czy to coś zmienia?
Nie, ponieważ te sprawy są ekskluzywne.
Znowu, mój błąd.
Nie, myślę, że trzeba ten else if.
Możemy spróbować i uruchom go i zobacz co się dzieje.
Budynek, wystąpił błąd.
To pewnie dlatego, że zostawili te B i E jest tutaj.
Mam nic więcej z tych się na szczycie?
To nie wygląda na to.
Mamy pomniejszyć, budować,
tam to idzie, więc teraz, gdy szukamy 15,
Tak.
Pozwól mi powiększyć
15, tak. Możemy uruchomić go ponownie.
Wgrywanie kod źródłowy, budowę, uruchomienie.
Możemy poszukać coś jak 13,
i nie mamy nic drukowania, więc to nie jest stwierdzenie, że dla nas.
To świetnie, bo to nie jest na naszej liście.
>> Jesteśmy teraz czasu.
Że będzie to w tym tygodniu.
Dziękujemy za przyłączenie się i do zobaczenia później.
>> [CS50.TV]