[Музыка играет] 

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 это идти через. 

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

Желаем удачи в р-набора. И спасибо за просмотр. Это было Жадный. 

[Музыка играет]