>> [MUZYKA GRA]
>> ZAMYLA Chandler: Teraz możemy zająć chciwy.
Powiedzmy, że jesteś kasjerka, a trzeba dać Klient
pewna ilość zmian.
Cóż, jeśli jesteś chciwy kasjer, że chcesz zachować wszystkie
monety do siebie.
Więc chcesz dać klientowi ich zmianę stosując jako kilka monet, jak to możliwe.
>> Twoim zadaniem w tym p-set jest wdrożenie Chciwy, program
obliczy minimalną liczbę monet używanych do dowolnego
biorąc pod uwagę ilość zmian.
Przed nurkowaniem w programowaniu koncepcje i C składnia chciwy,
niech najpierw rozmowa przez Sknerus Program, i zobaczyć, czy
Można zidentyfikować algorytmu.
Pamiętaj, że algorytm jest tylko zestaw
instrukcje rozwiązywania problemów.
Algorytm chciwy będzie tylko zestaw logicznych zasad i kroków, które
możemy podążać.
I będą zawsze uzyskując minimum liczba monet potrzebnych.
>> Pierwszą rzeczą, którą trzeba się wiedzieć, jak dużo zmian
jest należne do klienta.
W tym przykładzie, powiedzmy, 0,32 dolarów.
Istnieje wiele sposobów, aby uzyskać z powrotem 0,32 dolarów.
Można użyć, na przykład, 32 groszy.
Lub jeśli jesteś nieco greedier w Wybierając swoje monety, można użyć
pięć monet zamiast 32, dając klientów - trzy dimes
Każdy 0,10 dolarów - i dwa grosze - 0,01 dolarów każda.
>> Ale możemy to zrobić lepiej niż pięć monet?
Możemy być nawet greedier?
Całkiem możliwe.
>> Niech nadal chodząc Program chciwy, i zobaczyć.
Jeśli twój koniec celem jest wykorzystanie kilku monet jest to możliwe, to byłoby najbardziej
rozsądne, aby korzystać największym możliwe monety.
Wolisz dać jedną czwartą kopii - 0.25 dolarów każdy -
niż pięć monet -
0,05 dolarów każda.
Więc może nasz przepis na rządzenie Chciwy można zawsze używać
największa moneta.
Z kwartałach dimes, nickels, i grosze, nasze
Największa moneta jest czwarta.
Więc postaramy się wykorzystać je w pierwszej kolejności.
>> Z powrotem do naszego 0,32 dolarów.
Możemy użyć ćwierć dać Klient 0,32 dolarów?
Tak.
, Który pozostawia nas z 0,07 dolarów w lewo.
>> Możemy użyć kolejny kwartał?
Nie, ponieważ 25 jest większa niż siedem.
Nie chcemy, aby dać klientowi więcej niż my im winni.
>> Dobrze.
Teraz, gdy już wyczerpały nasze czwarte, przejdźmy do następnego największym
moneta, bilon.
Możemy używać ani grosza dać Klient ich 0,07 dolarów z powrotem?
Nie od 10 jest większa niż siedem.
>> Tak więc następna największa moneta dostępna dla nas jest nikiel.
Możemy użyć niklu?
Tak.
I wtedy mielibyśmy 0,02 dolarów pozostało.
>> Nie możemy użyć niklu wrócić 0,02 dolarów.
Więc przenieśliśmy się w ostatnią monetę naszej dyspozycji - grosza.
I po użyciu dwóch groszy, bylibyśmy lewo zero groszy, co oznacza, że
mamy skutecznie zwrócona Użytkownik winien ich zmiana
przy użyciu tylko cztery monety -
jedna czwarta, jedna nikiel, i dwa grosze.
>> Możesz uruchomić rozwiązanie, aby sprawdzić, czy personel Nasza zasada rządząca i proces dał
nam prawidłowa odpowiedź.
Dla większości zespołów problemowych, będziesz mógł uruchomić rozwiązanie, aby zobaczyć, jak personel
własny program powinien działać.
I szczegółowe instrukcje będą być problemu ustala specyfikacje.
>> Kiedy uruchomić rozwiązanie pracowników, to prosi nas o ile zmiana jest należne
pamiętać, że prosi o wartość w złotych.
Mamy wejście 0,32 dolarów, 0,32.
To mówi nam, że cztery monety są należne, zgodne z naszą odpowiedzią.
Fantastyczne.
>> Teraz zacznijmy patrząc w realizacji
algorytmu Greedy.
Wiemy, że kilka rzeczy.
Raz, że musimy monitować Użytkownik na kwotę zmiany.
>> Dwa, że ​​my chcemy podążać nasze regulujące zasady, aby zawsze używać
największa moneta.
I trzy, że musimy śledzić o ile monet używamy.
Bo wreszcie, musimy wydrukować liczba monet, że.
>> Po pierwsze, monitowania użytkownika na kwotę zmiany.
Zawsze, gdy masz do czynienia z danych wprowadzonych przez użytkownika, należy Upewnij się, że myślę o wszystkich
wymagania i tylko wejście akceptuje wejście, które spełnia te
wymagania.
W tym przypadku, możemy mieć do czynienia z wartość pieniężna w dolarach.
>> Funkcje GetFloat i GetInt zapewnienia że wejście jest numeryczna.
Ale użytkownik może wprowadzić ujemne wartości liczbowe.
Więc pamiętać, aby używać tylko nieujemna wejścia, które obejmuje wszystkie negatywne
liczby i zera.
>> W tym przypadku wejścia powinien być pływak.
Innymi słowy, liczba dziesiętna.
Ponieważ specyfikacja wymaga zestawu problemem można prosić o wejście w dolarach.
>> Ale w C, wartości zmiennoprzecinkowe nie może być reprezentowane dokładnie.
Ponieważ istnieje skończona liczba bitów o jakim
reprezentują wartości nieskończone.
Weź numer 0.1.
Gdybym miał zapytać napisać 0,1 przez Ręka do setnej miejsca po przecinku,
byś dodać 1, a następnie przez 99 zer.
Należałoby oczekiwać, że nasz komputer by wydrukować dokładnie to samo
gdy zapytaliśmy go.
>> Zobaczmy więc, co robi.
Ja przeglądu wartości drukowania do koniec tego przejść.
Teraz, patrz tutaj, że f% jest zastępczy zmiennoprzecinkowych.
Ale określić wcześniej, że chcemy Wyświetlona 100 dziesiętne, a następnie nowy
linia do ładniejszy formatowania.
>> Po ciągu wybieramy 0,1 jako pływak, który chcemy wydrukować.
I wynik, jeden, a następnie od około zera, a następnie
cała masa liczb.
Na pewno nie jak oczekiwano.
>> Zmiennoprzecinkowe brak precyzji może wprowadzić błędów zaokrąglania do swojej
Obliczenia, które będzie zdecydowanie chcą uniknąć.
Jeśli chcesz zobaczyć więcej przykładów, można Możesz pobrać imprecision.ce od
przejść przez kod, który jest prosty Program, który prosi go pływak i drukuje
Powrót do setnej miejsca po przecinku.
Oczywiście, jeśli chcesz, aby pokazać mniej lub więcej miejsc po przecinku
można zmienić siebie.
>> Jak zobaczysz, choć różnica między nimi jest niewielka, gdy pojawi się
do mnożenia i dodawania pływaków, że rozbieżność może w końcu dodać.
Kopię do chciwy.
My chcemy, aby uniknąć błędów zaokrąglania przez czynienia z liczbami.
Więc po otrzymaniu prawidłowych wejście od użytkownika, to niech konwersji
Wartość dolara centów.
>> Psychicznie, robimy to poprzez pomnożenie Wartość dolara przez 100.
Ale pamiętaj, ze względu zmiennoprzecinkowe brak precyzji, chcemy, aby
upewnić się, że używamy właściwej wartości.
Mnożąc przez 100, będzie zasadniczo przenieść miejsca po przecinku dwa miejsca do
Dobrze, odcięcie lub obcinania coś później.
>> Jeśli bawić się kilka przykłady, przekonasz się, że nie będzie
zawsze ma odpowiedni numer, jeśli korzystają z tej metody obcinania.
Przykładowo, 12,59 drukowane 100. miejsc po przecinku, która daje
12,5899, et cetera.
Można dostać 12,58 jeśli obcięte, nie 12.59, jak trzeba.
>> Zamiast tego, lepiej zaokrąglić Numer pierwszy.
Na szczęście, C jest wyposażony Funkcja o nazwie Okrągły.
Jest w bibliotece matematycznej.
>> Jeśli chcesz wiedzieć, jak korzystać rundy, następnie można wywołać instrukcję lub
Strona man dla tej funkcji.
Można to zrobić, wpisując krótki dla człowieka, ręczny, a następnie, że funkcja
chcę patrzeć.
Tak wpisując cały człowiek w terminalu linia poleceń spowoduje instrukcję.
>> To może być trochę trudne do odczytania, ale w końcu będziesz
się zawiesić go.
Strony man pokazać, co funkcję nie, a nawet
Możliwości wykorzystania tego.
Zostawię cię zbadać Strona man dla rundy.
Ale wiem, że można go używać do rundy wartość podczas konwersji
dolarów centów.
>> Okrągły daje powrotem numer danych typu double.
I można konwertować lub odlewane go do int później.
Świetnie.
Teraz mamy monit użytkownikowi na kwotę pieniężną, a
zamieniona centów.
Teraz możemy realizować algorytm że zawsze używa
Największe monety dostępne.
>> Należy pamiętać, że istnieje wiele sposobów realizacji chciwy, jak
istnieje wiele sposobów podejścia każdy komputer Problem nauki.
Znalezienie najbardziej elegancki sposób, to jest część zabawy.
Przez te P-set, jeśli program nie dokładnie odpowiadają mojemu
wyjaśnienie w solucje, to jest OK.
Ale upewnij się, że przechodzi sprawdzić 50, spełnia wszystkie
Formularz specyfikacji wymagań, i rozważyć, czy Twój
podejście ma dobry projekt.
>> Innymi słowy, jak skuteczne jest?
Na przykład, czy wpiszesz powtarzalne linie kodu, zamiast za pomocą pętli?
Pisania kodu z lepszego projektu będzie się doświadczeniem w miarę postępów
przez tor.
>> Za to przejść przez, pójdę na dwie metody, które mogą być stosowane do
zakończyć chciwy.
Pierwszą metodą jest metoda z użyciem pętle i odejmowanie.
Wcześniej, kiedy rozmawialiśmy przez Proces chciwy, nieustannie
sprawdzić, czy możemy skorzystać na kwartał, i wykorzystywane aż jedną czwartą
wartość pozostała było mniej niż $ 0,25.
>> To przekłada się także na natomiast struktura pętli.
Chociaż możemy nadal korzystać kwartału, użyć jednego.
Że należy wykonać podczas pętli tak długo jak pozostała wartość jest większa niż
lub równa wartości cent kwartalną.
Oznacza to, że będziesz także chcą śledzić pozostałą gotówkę
wartość i aktualizować go co czas, aby użyć monety.
>> Należy również pamiętać, że na koniec, twój Wyjście to liczba monet stosowane.
Tak więc kolejna rzecz do śledzenia jest liczba monet, które są używane.
Możesz śledzić je za pomocą dobrze nazwane zmienne.
A w ciele swojej pętli byłoby będzie aktualizacja do tych zmiennych.
Po zakończeniu pętli na kwartał, ci Można użyć podobną do grosze,
i tak dalej i tak dalej, dopóki nie zwrócone wszystkie gotówce.
>> Pisałem jakiś pseudo-kod, żeby pomóc w wizualizacji, jak
Proces dyskutowaliśmy może przełożyć się C. Jak widać tutaj, jestem wciąż przy
Angielskie słowa.
To nie jest jeszcze C.
Ale zacząłem tiret rzeczy.
Wrzuciłem warunki wewnątrz moje nawiasy.
To zaczyna wyglądać trochę trochę jak kod programowania.
>> Pseudo-kod jest doskonałym sposobem aby dostać się zaczęło.
Wizualizację kodu przed patrzysz się składni.
Ponieważ często najtrudniejsze Problem jest naprawdę zrozumieć, co
dokładnie trzeba zrobić.
Raz piszesz, że w dół, to jest to dużo łatwiej zajrzeć do funkcji
i specyficzne dla składni linii kodu pseudo-
>> Należy pamiętać, że to może nie być identyczna rodzaju szkieletu
Twój kod, który piszesz.
Nie zawsze są optymalizacje być wykonane.
A zwłaszcza w moim pseudo-kodzie tu, czy można go dostrzec.
>> Ale zasadniczo proces i sposób myślenia
to tak jak mówiliśmy.
Pierwsza linia mówi nam uzyskać pewną kwotę w dolarach.
I mówi do drugiego przekonwertować go do centa.
>> A następnie, podczas gdy czwarte mogą być stosowane, ale chce zwiększyć liczbę monet i
zmniejszyć ilość gotówki.
Samo dimes, monet, i grosze.
I wreszcie powiemy użytkownika ile monet użyliśmy.
>> Świetnie.
Tak, że dochodzi do wniosku, metody pętli.
Teraz porozmawiajmy o metody modułowej, który jest bardziej jak podział.
>> Wszyscy jesteśmy zaznajomieni z plus, minus, mnożenie i dzielenie podmiotów
dla nas dostępne.
C ma wszystkie cztery z nich, a także zawiera Operator modulo, reprezentowana przez
znak procent.
Modulo jest naprawdę fajnie.
To daje resztę z dzielenia dwóch liczb.
>> Pamiętam długą wiadomość podczas podziału podzielić, powiedzmy, 74 przez trzy?
Począwszy od miejsca dziesiątek, byś wiem, że 3 idzie do siedmiu
dwa razy, aby dokonać sześciu z jedna pozostała.
Można by napisać dwa na górze, a następnie odjąć 6 z siedmiu, przeniesienia
Pozostała część 14 do powtórzyć proces.
>> Trzy przechodzi w 14 cztery razy do Marka 12, z pozostałej dwa.
A dwa nie przenieść więcej.
Więc dwa będzie w lewo na dno z pozostałą.
>> I to właśnie modulo daje, ty liczba ta w dolnej części.
Więc 74 modulo trzy da ci dwa.
I 10 modulo dwa, dobrze, że nie daje zero.
Ponieważ nie ma żadnych pozostała po podzieleniu 10 przez dwa.
>> Sześć modulo pięć, a pięć idzie do sześciu raz.
I to jest jeden pozostały.
Więc sześć modulo pięć jest jeden.
>> Następnie, jeśli masz siedem modulo dziewięć, można dostać siedem.
Ponieważ dziewięć jest większa niż siedem.
Więc nie podzielić to wszystko do siedmiu, pozostawiając siedem jako odpowiedź.
>> Jeśli myślisz o modulo trochę więcej, pamiętaj, że daje ci
Pozostała po podzieleniu coś.
Pomyśl o tym, jak może być w Możliwość korzystania w chciwy.
Załóżmy, że użytkownik prosi o 400,11 dolarów.
Co jest sposobem, aby dowiedzieć się, ile czwarte potrzebne, bez konieczności
Ilość każdego?
>> Po dowiedzieć się, ile czwarte można użyć do 400,11 dolarów, ile
zmienić szczątki?
Być może połączenie tutaj między Modulo i podział by się
poręczne dać fajny, elegancki podejście do Greedy problemu.
Ale pamiętaj, że rada zasada nadal obowiązuje.
Zawsze należy stosować możliwie największą monetę.
>> Po wykonaniu obliczenia, jak wiele monet w użyciu, ostatni krok
jest wydrukować liczbę Monety, które obliczone.
Do tej pory używaliśmy printf funkcjonować wyłącznie na strunach.
Ale jeśli chcesz wydrukować in, lub po prostu każdy rodzaj danych, które przechowywane
w zmiennej, trzeba podać że stosując zastępczy.
>> Tutaj podaję tylko kilka porad w jaki sposób wydrukować wartości.
Jeśli masz liczbę całkowitą, byś napisz ciąg za pomocą% d jako
zastępczy.
Po cudzysłowu znak, oddziel.
, A następnie umieścić w całkowitej, która będzie zająć miejsce% d, gdy wydrukowane.
>> Więc po wyświetleniu numeru używane monety, jesteś
wykończone chciwy.
Upewnij się, aby sprawdzić wszystkie przypadki, narożne, posprzątać swój styl trochę, a ty jesteś
Wszystko gotowe do złożenia.
Pod koniec tego zestawu problemów, które będziesz być bardziej zaznajomieni z CS50
Urządzenie, terminal, a pętla struktury i zmienne w C
>> Jesteś na dobrej drodze.
Krzywa uczenia się może wydawać trudne.
Więc weź to krok po kroku.
Upewnij się, że pisać pseudo-kod przed zbyt głębokie nurkowanie
w składni nieznanym.
>> Dodać do zrobienia, i zerwać zadanie na mniejsze, bardziej
zarządzaniu zadania.
Poznaj wszystkich zasobów CS50.
Oprócz wykładu, rewatch to przejść.
>> Zwróć szczególną uwagę na części.
Sprawdź szorty.
Czytaj pytania kolegami " na Omów i dodawać własne.
>> Powodzenia z p-set.
I dzięki za oglądanie.
To był chciwy.
>> [MUZYKA GRA]