>> [Музыка играет]
>> 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 это идти через.
>> Обратите особое внимание на раздел.
Проверьте шорты.
Читайте вопросы ваших одноклассников на Обсудить и размещать свои собственные.
>> Желаем удачи в р-набора.
И спасибо за просмотр.
Это было Жадный.
>> [Музыка играет]