[Музика грає] 

ZAMYLA Чан: Тепер давайте візьмемося Жадібний. Скажи, що ти касир, і ви повинні дати вашому клієнтові Певних змін. Ну, якщо б ви були жадібними касир, ви хотіли б зберегти всі монети до себе. Таким чином, ви б дати клієнтові їх зміну використовуючи як кілька монет, наскільки це можливо. 

Ваше завдання в цьому р-набору полягає в реалізації Жадібний, програма, яка обчислює мінімальну кількість монет, що використовуються, щоб зробити будь враховуючи кількість змін. Перед зануренням у програмуванні поняття і C синтаксис Жадібний, давайте спочатку поговоримо через Жадібний Програма, і подивитися, якщо ми може визначити алгоритм. Пам'ятайте, що алгоритм це просто набір інструкції щодо вирішення проблем. Алгоритм Жадібний буде просто набір логічних правил і заходів, які ми можемо слідувати. І вони завжди дадуть мінімум кількість монет, необхідних. 

Перше, що ви повинні були б знати, як багато змін є зобов'язанням щодо клієнта. Для цього прикладу, скажімо, $ 0.32. Є багато способів, щоб отримати назад $ 0.32. Можна використовувати, наприклад, 32 копійки. Або, якщо ви були трохи жадібними в виборі монет, ви можете використовувати п'ять монет замість 32, даючи Клієнт три десять центів - Кожен $ 0.10 - і дві копійки - $ 0.01 кожен. 

Але ми можемо зробити краще, ніж п'ять монет? Чи можемо ми бути навіть більш жадібними? Цілком можливо. 

Давайте продовжимо ходити через Жадібний програма, і подивитися. Якщо ваш кінцева мета полягає у використанні кілька монет як це можливо, то це було б найбільш розумно використовувати найбільшим можливі монети. Ви б краще дати однієї чверті назад - $ 0.25 кожна - ніж за п'ять нікель - $ 0.05 кожен. Так що, можливо наш керівний правило для Жадібний може бути, щоб завжди використовувати максимально можливе монета. З кварталів, десять центів, нікель, і пенні, наш Найбільший монета є квартал. Таким чином, ми постараємося використовувати їх в першу чергу. 

Повернемося до нашого $ 0.32. Чи можемо ми використовувати чверть, щоб дати клієнт $ 0.32? Так. Це залишило б нас з $ 0,07 залишили. 

Чи можемо ми використовувати ще чверть? Ні, тому що 25 більше, ніж сім. Ми не хочемо, щоб дати клієнтові більше, ніж ми повинні. 

Добре. Тепер, коли ми вичерпали наші квартали, давайте перейдемо до наступного за величиною монета, копійки. Чи можемо ми використовувати ні копійки, щоб дати клієнт їх $ 0,07 назад? Ні, оскільки 10 більше, ніж сім. 

Так то наступний за величиною монета доступні для нас є нікель. Чи можемо ми використовувати нікель? Так. І тоді ми повинні були б $ 0,02 в запасі. 

Ми не можемо використовувати нікель повернутися $ 0.02. Таким чином, ми переїхали останню монету в в нашому розпорядженні - копійки. А після використання двох копійки, ми були б залишилося з нульовими центів, а це означає, що ми успішно повернуті користувач їх зміну заборгував використовуючи тільки чотири монети - одна чверть, одна нікель, і дві копійки. 

Ви можете запустити рішення персоналу, щоб переконатися, наше правило керівний та процес дав нам правильну відповідь. Для більшості проблемних наборів, ви зможете щоб запустити рішення персоналу, щоб побачити, як свій власний програма повинна працювати. І конкретні інструкції буде бути в задачі встановлює специфікації. 

Як тільки ми запустити рішення на персонал, при спонукає нас за скільки зміна прочитується зверніть увагу, що він просить складе в доларах. Ми вхід $ 0.32, 0.32. Це говорить нам, що чотири монети заборгували, узгоджується з нашою відповіддю. Фантастика. 

А тепер давайте почати шукати на реалізацію жодного алгоритму. Ми знаємо, пару речей. Один з них, що нам потрібно, щоб спонукати Користувач на суму зміни. 

Два, що ми будемо хотіти слідувати нашій керівним правило завжди використовувати максимально можливе монета. І три, що ми повинні стежити від того, скільки монет ми використовуємо. Тому що, нарешті, ми повинні надрукувати кількість монет, які ми. 

По-перше, пропонуючи користувачеві на суму змін. Всякий раз, коли ви маєте справу з користувальницької введення, щоб Переконайтеся, що ви думаєте про все Вимоги вході, і тільки приймати введення, який відповідає тим вимоги. У цьому випадку, ми хочемо мати справу з грошова вартість у доларах. 

Функції GetFloat і GetInt забезпечення що вхід є числовий. Але користувач може вводити негативні числові значення. Так що не забудьте використовувати тільки невід'ємне входів, яка включає в себе весь негатив числа і нуля. 

У цьому випадку вхідний повинен бути поплавок. Іншими словами, десяткове число. Тому що проблема набір специфікації вимагається Вам задати для введення в доларах. 

Але в C, значення з плаваючою точкою не може бути представлені точно. Тому що є кінцеве число бітів, з яким представляють нескінченні значення. Візьміть номер 0.1. Якби мені довелося попросити вас написати 0,1 по рука, щоб в сотий знака після коми, Ви б написати 1, а потім на 99 нулями. Ми очікуємо, що наш комп'ютер буде друкувати один і той же якщо ми запитали його. 

Отже, давайте подивимося, що він робить. Я розгляну висновок значень до в кінці цього йти через. В даний час, бачимо, що е% є Місце для плаваючою крапкою. Але ми вказуємо заздалегідь, що ми хочемо 100 десяткові відображається, а потім новий лінія для більш гарного форматування. 

Після рядка, ми вибираємо 0,1, як плавати, що ми хочемо, щоб роздрукувати. І результат, один, а потім деякими нулів, але потім ціла купа цифр. Звичайно, не як очікувалося. 

Плаваючою точкою неточність можна ввести помилок округлення у ваше розрахунки, що ви будете безумовно хочете уникнути. Якщо ви хочете побачити більше прикладів, можете завантажити imprecision.ce від пройти через код, який представляє собою простий програма, яка просить плавати і друкує його назад в сотий знака після коми. Звичайно, якщо ви хочете показати більш-менш знаків після коми Ви можете змінити себе. 

Як ви побачите, хоча різниця між ними невелика, коли ви отримуєте множенню і додавання поплавці, що Розбіжність в кінцевому підсумку може скласти. Назад до Жадібний. Ми хочемо уникнути помилок округлення , Маючи справу з цілими числами. Таким чином, після ми отримуємо дійсний введення з користувач, давайте перетворити це вартість долара до центів. 

Подумки ми робимо це шляхом множення доларова вартість на 100. Але пам'ятайте, через плаваючою точкою неточність, ми хочемо зробити упевнений, що ми використовуємо правильне значення. Множачи на 100 істотно рухатися після коми два простори в право, відрубування або усічення нічого після цього. 

Якщо ви пограти з деякими більш приклади, ви побачите, що у вас не буде завжди є правильний номер, якщо ви використовувати цей метод усікання. Наприклад, 12.59 надруковані до 100 знаків після коми, що дає вам 12,5899, і так далі. Ви б отримати 12,58, якщо ви усічений, НЕ 12.59, як вам потрібно. 

Замість цього краще закруглити кількість в першу чергу. На щастя, C поставляється з Функція називається Круглий. Це в математичній бібліотеки. 

Якщо Ви хочете знати, як використовувати раунд, то ви можете вивести на керівництво чи Людина сторінки для цієї функції. Це можна зробити, набравши людини, скорочення Керівництво, а потім функція, що ви хочу подивитися. Так, набравши людина раунд в термінал командного рядка з'явиться керівництво. 

Це може бути трохи важко розшифрувати, але в кінці кінців ви будете отримати вид його. Довідкові сторінки показати вам, що функції робить, а потім деякі з можливі застосування нього. Я залишу вас, щоб дослідити сторінка керівництва за раунду. Але знайте, що ви можете використовувати його, щоб закруглити значення під час вашого переходу від доларів, щоб центів. 

Круглий дасть вам назад ряд типу даних Double. І ви можете конвертувати або литі це до міжнар згодом. Великий. В даний час ми спонукало користувача для грошова сума, і перетворили його на центів. Тепер ми можемо реалізувати алгоритм що завжди використовує Найбільші монети доступні. 

Майте на увазі, що є кілька способів реалізації Жадібний, як Є кілька способів вирішити кожна проблема науки комп'ютер. Пошук найбільш елегантний спосіб, що найцікавіше. Протягом усіх цих р-наборів, якщо ваша програма неточно відповідати моїм пояснення в покрокових посібників, це нормально. Але просто переконайтеся, що вона проходить перевірити 50, задовольняє всім вимоги утворюють специфікації, і що ви вважаєте ваш підхід має хороший дизайн. 

Іншими словами, наскільки ефективно це таке? Наприклад, чи знаєте ви вводите повторювані рядків коду, замість використання петлю? Написання коду з найкращим дизайном буде приходять досвід, як ви прогрес через курс. 

Для цього йти через, я піду за два способи, які можна використовувати, щоб завершити Жадібний. Перший спосіб являє собою спосіб з використанням петлі і віднімання. Раніше, коли ми говорили через Жадібний процес, ми постійно перевірили, чи можна використовувати в квартал, і використовували чверть до залишкова вартість була менше, ніж $ 0.25. 

Це призводить також до в той час як структура циклу. У той час як ми все ще можемо використовувати чверть, використовуйте один. Це в той час як цикл повинен виконати доти, як залишилася значення більше або дорівнює значенню центів кварталу. Це означає, що ви також хочете, щоб відслідковувати всю готівку, що залишилася значення, і оновлювати його кожен раз, коли ви використовуєте монету. 

Також пам'ятайте, що врешті-решт, ваш Вихід кількість монет, використовуваних. Так ще одна річ, щоб відстежувати це кількість монет, які ви використовуєте. Ви можете слідкувати за ним за допомогою добре названий змінні. І в тілі вашого циклу буде бути собою оновлення цих змінних. Після того як петля для чверті закінчується, вам може використовувати подібний один для п'ятаків, і так далі і так далі, поки ви не повернувся всю готівку. 

Я написав кілька псевдо-код тут, щоб допомогти вам уявити, наскільки Процес, який ми обговорювали, можливо перевести на С. Як ви бачите тут, я все ще з допомогою Англійські слова. Це не C ще. Але я почав відступу речей. Я поклав умови всередині мої дужки. Це починає виглядати трохи трохи схоже програмного коду. 

Псевдо-код є відмінним способом щоб самі почали. Візуалізація код перед ви подивіться вгору синтаксис. Бо часто найскладніше в Проблема насправді зрозуміти, що точно що вам потрібно зробити. Після того, як ви пишете, що вниз, то це набагато легше перегляду функції і синтаксис, характерні для даної лінія псевдо-код 

Майте на увазі, що це не може бути ідентична виду каркаса ваш код, що ви пишете. Є завжди оптимізації повинні бути зроблені. І особливо в моїй псевдо-код тут, подивитися, якщо ви можете визначити його. 

Але по суті процес і спосіб мислення так само, як ми обговорювали. Перший рядок говорить нам, щоб отримати певну кількість в доларах. І другий говорить нам перетворити його в центів. 

І потім, в той час чверті можуть бути використані, ми хочете збільшити кількість монет і зменшити кількість готівки. Те ж саме стосується Dimes, нікель, і пенні. І, нарешті, ми говоримо користувачу скільки монет ми використали. 

Великий. Так що висновок, метод зворотного зв'язку. Тепер давайте поговоримо про модульного методу, який більше схожий дивізії. 

Ми всі знайомі з плюсом, мінус, множити і ділити операторів в нашому розпорядженні. С має всі чотири з них, але також має оператор по модулю, в особі знак відсотка. Модулю дійсно охайно. Це дає вам залишок від ділення двох чисел. 

Пам'ятайте довге повідомлення ділення, коли ви розділите, скажімо, 74 на три? Починаючи з місця десятки, ви б знаю, що 3 переходить в семи два рази, щоб зробити шість з Решта один. Ви б написати два у верхній частині, а потім відняти 6 з семи, перенесення залишок від 14 до повторити процес. 

Три переходить в 14 в чотири рази, щоб зробити 12, із залишком два. І два не переноситься більше. Так два залишиться на нижня як залишок. 

І ось що дає модулю, ви що число внизу. Так 74 по модулю три дасть вам два. І 10 по модулю два, ну, що дасть вам зосередитися. Тому що немає ніякого залишок коли ви розділите 10 на два. 

Шість модулю п'ять, а п'ять переходить в шести разів. А потім він один в запасі. Так шість модулю п'ять є одним. 

Тоді, якщо у вас є сім модулю дев'ять, ви отримаєте сім. Тому що дев'ять більше, ніж сім. Так що не ділить все це в сім, залишивши сім, як ваша відповідь. 

Якщо ви думаєте про модулю трохи більше, пам'ятайте, що це дає вам Решта після розділити щось. Подумайте, як ви могли б бути можливість використовувати його в Жадібний. Скажімо про це попросить користувач $ 400,11. Що таке спосіб з'ясувати, скільки чверті ви повинні без необхідності розраховувати кожен? 

Після того як ви з'ясувати, скільки чверті ви можете використовувати, щоб зробити $ 400,11, скільки змінити останки? Можливо поєднання тут між модулю і ділення прийде в зручно, щоб дати вам прохолодно, елегантний підійти до Жадібні проблеми. Але пам'ятайте, що керівний правило все ще застосовується. Завжди використовуйте якомога більшу монету. 

Як тільки Ви зробили розрахунок, як багато монет у використанні, останній крок повинен роздрукувати кількість монети, які ви розраховані. До цих пір ми використовували на Printf функціонувати виключно для рядків. Але якщо ви хочете, щоб роздрукувати лист в систему, або просто будь-який тип даних, яка зберігається у змінній, ви повинні вказати що використання заповнювача. 

Тут я включив всього кілька порад про те, як роздрукувати значення. Якщо у вас є ціле, ви б написати рядок, використовуючи% D, як заповнювач. Після закриття котирування знак, кому. А потім поклав у ціле число, яке буде зайняти місце% D, коли на друк. 

Таким чином, після відображення номера з використовуватися монети, ви закінчив із Жадібний. Переконайтеся, щоб перевірити всі кутові випадки, привести в порядок ваш стиль трохи, і ти все готово уявити. Наприкінці цієї проблеми набору, ви будете бути більш знайомі з CS50 Прилад, термінал, і петля структури та змінні в С 

Ти на правильному шляху. Крива навчання може здатися жорстким. Так що беріть його крок за кроком. Переконайтеся, що ви виписати псевдо-код перед зануренням занадто глибоко в незнайомій синтаксису. 

Зробити, щоб зробити список, і розпадаються Призначення на більш дрібні, більш керовані завдання. Досліджуйте всі CS50 ресурсів. На додаток до лекції, rewatch це йти через. 

Зверніть особливу увагу на розділ. Перевірте шорти. Читайте питання ваших однокласників на Обговорити і розміщувати свої власні. 

Бажаємо удачі в р-набору. І спасибі за перегляд. Це було Жадібний. 

[Музика грає]