>> [MUSIQUE JEU]
>> ZAMYLA CHAN: Maintenant nous allons aborder Greedy.
Dites que vous êtes un caissier, et vous besoin de donner à vos clients une
certaine quantité de changement.
Eh bien, si vous étiez un caissier gourmand, vous voudriez garder tous
les pièces de monnaie à vous-même.
Donc vous donneriez le client leur changement en utilisant le moins de pièces que possible.
>> Votre tâche pour cette p-ensemble est de mettre en œuvre Gourmand, un programme qui
calcule le nombre minimum des pièces utilisées pour faire des
une quantité donnée de changement.
Avant de plonger dans la programmation concepts et la syntaxe C pour Greedy,
Parlons d'abord à travers le Greedy programme, et voir si nous
peut identifier un algorithme.
Rappelez-vous que d'un algorithme est juste un ensemble de
instructions pour résoudre les problèmes.
Un algorithme de Greedy ne serait qu'un un ensemble de règles et étapes logiques
nous pouvons suivre.
Et ils seront toujours donner le minimum nombre de pièces nécessaires.
>> La première chose que vous devez savoir, c'est combien le changement
est due à la clientèle.
Pour cet exemple, disons $ 0,32.
Il existe de nombreuses façons de récupérer $ 0,32.
Vous pouvez utiliser, par exemple, 32 centimes.
Ou si, vous étiez un peu plus gourmand en le choix de vos pièces, vous pouvez utiliser
cinq pièces de monnaie au lieu de 32 en donnant le client trois dimes -
$ 0,10 chacune - et deux sous - $ 0,01 chacune.
>> Mais pouvons-nous faire mieux que cinq pièces de monnaie?
Pouvons-nous être encore plus gourmande?
Très probablement.
>> Continuons à marcher à travers le programme avide, et voir.
Si votre objectif final est d'utiliser quelques pièces de monnaie que possible, il serait plus
prudent d'utiliser la plus grande pièces possibles.
Vous préférez donnez un quart sauvegarder - $ 0,25 chacun -
de cinq cents -
$ 0,05 chacune.
Alors peut-être notre règle de régie Greedy peut être de toujours utiliser le
plus grande pièce possible.
En rupture de quartiers, dimes, nickels, et pièces de monnaie, notre
plus grande pièce est le trimestre.
Nous allons donc essayer de les utiliser en premier.
>> Retour à notre $ 0,32.
Pouvons-nous utiliser un quart de donner le client $ 0,32?
Oui.
Cela nous laisse avec $ 0,07 gauche.
>> Peut-on utiliser un autre trimestre?
Non, parce que 25 est supérieur à sept ans.
Nous ne voulons pas donner au client pas plus que nous leur devons.
>> Très bien.
Maintenant que nous avons épuisé nos quartiers, Passons à la deuxième plus grande
pièce de monnaie, le sou.
Pouvons-nous utiliser un sou à donner à la client leur $ 0,07 dos?
N, puisque 10 est plus grande que sept.
>> Alors la prochaine plus grande pièce accessible pour nous, c'est nickel.
Pouvons-nous utiliser un nickel?
Oui.
Et puis nous aurions $ 0,02 reste.
>> Nous ne pouvons pas utiliser un nickel pour retourner $ 0,02.
Alors nous sommes la dernière pièce à notre disposition - le sou.
Et après l'utilisation de deux cents, nous serions gauche avec zéro cent, ce qui signifie que
nous avons payé avec succès retour à l'utilisateur son changement devait
en utilisant seulement quatre pièces -
quart, nickel, et deux sous.
>> Vous pouvez exécuter la solution de personnel pour voir si notre règle et le processus d'administration a donné
nous la bonne réponse.
Pour la plupart des ensembles de problèmes, vous serez en mesure pour exécuter la solution de personnel pour voir comment
votre propre programme devrait fonctionner.
Et des instructions spécifiques seront dans le problème définit les spécifications.
>> Une fois que nous courons la solution du personnel, il nous invite à quel point le changement est dû
noter qu'il demande le Montant en dollars.
Nous entrée $ 0,32, 0,32.
Il nous dit que quatre pièces sont dues, compatible avec notre réponse.
Fantastique.
>> Alors maintenant, nous allons commencer la recherche à la mise en œuvre
de l'algorithme glouton.
Nous savons quelques choses.
Un, que nous devons demander à l' l'utilisateur pour une quantité de changement.
>> Deux, que nous voulons suivre notre régissant règle de toujours utiliser le
plus grande pièce possible.
Et trois, que nous avons besoin de garder une trace de combien de pièces que nous utilisons.
Parce que, enfin, nous devons imprimer le nombre de pièces que nous.
>> Tout d'abord, demander à l'utilisateur pour une quantité de changement.
Si vous travaillez dans l'entrée d'utilisateur, assurez- assurer que vous pensez de l'ensemble des
exigences de l'entrée, et seulement accepter l'entrée qui répond à ceux qui
exigences.
Dans ce cas, nous voulons faire face à une valeur monétaire en dollars.
>> Les fonctions GetFloat et getInt assurer que l'entrée est numérique.
Mais l'utilisateur est en mesure d'entrée des valeurs numériques négatives.
Alors, n'oubliez pas d'utiliser uniquement non-négatif entrées, ce qui inclut tous négatifs
chiffres et zéro.
>> Dans ce cas, l'entrée devrait être un flotteur.
En d'autres termes, un nombre décimal.
Parce que le jeu de problème spécification exige vous demandez entrée en dollars.
>> Mais en C, les valeurs à virgule flottante ne peut pas être représentés avec précision.
Parce qu'il existe un nombre fini de bits avec lequel
représenter des valeurs infinies.
Prenez le nombre 0,1.
Si je devais vous demander d'écrire par 0,1 la main à la décimale centième,
vous pouvez écrire un 1, suivi par 99 zéros.
Nous nous attendons à ce que notre ordinateur serait imprimer exactement la même chose
si nous avons demandé à.
>> Voyons donc ce qu'il fait.
Je vais passer en revue les valeurs d'impression vers la fin de cette promenade à travers.
Pour l'instant, voyons ici que f% est un espace réservé pour un point flottant.
Mais nous précisons au préalable que nous voulons 100 décimales affichées, puis une nouvelle
ligne pour la mise en forme plus agréable.
>> Après la chaîne, nous choisissons 0,1 comme le flottons que nous voulons imprimer.
Et le résultat, une une, suivie par des zéros, mais un
le groupe entier de nombres.
Certainement pas comme prévu.
>> Virgule flottante imprécision peut introduire erreurs d'arrondi dans votre
calculs que vous voulez veulent absolument éviter.
Si vous voulez voir plus d'exemples, vous peuvent télécharger imprecision.ce de la
marcher dans le code, qui est un simple programme qui demande à flotter et imprime
Retour à la décimale centième.
Bien sûr, si vous voulez montrer plus ou moins décimales
vous pouvez modifier vous-même.
>> Comme vous le verrez, bien que la différence entre les deux est faible, quand vous obtenez
pour multiplier et additionner les flotteurs, qui différence peut éventuellement ajouter.
Retour à Greedy.
Nous voulons éviter les erreurs d'arrondi en traitant avec des nombres entiers.
Donc, après que nous obtenions entrée valide de l'utilisateur, nous allons convertir ce
valeur du dollar pour cents.
>> Mentalement, nous faisons cela en multipliant la valeur du dollar par 100.
Mais rappelez-vous, en raison de virgule flottante imprécision, nous voulons faire
vous que nous utilisons la bonne valeur.
En multipliant par 100 sera essentiellement déplacer la décimale deux espaces à
la droite, coupant ou en tronquant rien après.
>> Si vous jouez avec un peu plus de exemples, vous verrez que vous ne serez pas
toujours eu le bon nombre si vous utiliser cette méthode de troncature.
Par exemple, 12,59 imprimé à 100 décimales, qui vous donne
12,5899, et cetera.
Vous obtiendrez 12.58 si vous tronquées, pas 12.59, comme vous avez besoin.
>> Au lieu de cela, il est préférable d'arrondir le premier numéro.
Heureusement, C est livré avec la fonction appelée Round.
C'est dans la bibliothèque de mathématiques.
>> Si vous voulez savoir comment utiliser ronde, alors vous pouvez afficher le manuel ou
page de manuel de cette fonction.
Vous faites cela en tapant man, court pour manuel, puis la fonction que vous
envie de regarder vers le haut.
Donc, écrire homme rond dans le terminal ligne de commande fera apparaître le manuel.
>> Il pourrait être un peu difficile à déchiffrer, mais vous finirez
obtenir le coup de lui.
Les pages de manuel vous montrent ce que la fonction fait, et puis certains
utilisations possibles de l'informatique.
Je vous laisse à explorer la page de manuel pour la série.
Mais sachez que vous pouvez l'utiliser pour arrondir la valeur au cours de votre conversion de
dollars pour cents.
>> Round vous redonner un certain nombre du type de données double.
Et vous pouvez convertir ou fonte à un int après.
Grand.
A présent, nous avons incité les utilisateurs pour un montant monétaire, et
converti en cents.
Maintenant, nous pouvons mettre en œuvre un algorithme qui utilise toujours le
grandes pièces disponibles.
>> Gardez à l'esprit qu'il existe plusieurs moyens à mettre en œuvre Greedy, comme
Il ya plusieurs façons d'aborder tous les problèmes de la science informatique.
Trouver le moyen le plus élégant, c'est la partie amusante.
Tout au long de ces p-ensembles, si votre programme ne correspond pas exactement à mon
explication dans les procédures pas à pas, c'est OK.
Mais assurez-vous juste qu'il passe consultez 50, satisfait toutes les
exigences constituent les spécifications, et que vous considérez que votre
approche a une bonne conception.
>> En d'autres termes, comment efficace est-il?
Par exemple, avez-vous tapez répétitif des lignes de code, au lieu d'utiliser une boucle?
L'écriture de code avec une meilleure conception sera venir faire l'expérience que vous progressez
dans le cours.
>> Pour cette promenade à travers, je vais aller sur Deux méthodes peuvent être utilisées pour
compléter Greedy.
La première méthode est une méthode utilisant boucles et soustraction.
Plus tôt, lorsque nous avons parlé à travers le Processus gourmand, nous en continu
vérifié si nous pouvions utiliser un quart, et utilisé un quart jusqu'à ce que le
valeur résiduelle était inférieure à 0,25 $.
>> Cela se traduit bien à un tandis que la structure de boucle.
Alors que nous pouvons toujours utiliser un quart, utiliser un.
Qui boucle while doit exécuter tant que la valeur restante est supérieure à
ou égale à la valeur de cent d'un trimestre.
Cela signifie que vous aurez également besoin de garder une trace de l'argent qui reste
valeur, et mettre à jour tous les fois que vous utilisez une pièce de monnaie.
>> Rappelez-vous aussi que, à la fin, votre sortie est le nombre de pièces utilisées.
Donc, une autre chose à garder une trace de est le nombre de pièces que vous utilisez.
Vous pouvez suivre les utilisant variables bien nommé.
Et dans le corps de la boucle serait une mise à jour de ces variables.
Une fois la boucle de trimestre se termine, vous peut utiliser un semblable pour dimes,
et ainsi de suite et ainsi de suite, jusqu'à ce que vous avez retourné toutes les espèces.
>> J'ai écrit quelques pseudo-code ici à vous aider à visualiser à quel point la
processus, nous avons discuté pourrait se traduire par C. Comme vous le voyez ici, je suis toujours à l'aide
Mots anglais.
Il n'est pas encore C.
Mais j'ai commencé à les choses tiret.
J'ai mis des conditions à l'intérieur mes parenthèses.
Il commence à regarder un peu peu comme le code de programmation.
>> Pseudo-code est un excellent moyen à vous procurer commencé.
Visualisez votre code avant vous regardez la syntaxe.
Parce que souvent la partie la plus difficile sur un problème est vraiment comprendre ce
exactement que vous devez faire.
Une fois que vous écrivez que vers le bas, alors c'est une beaucoup plus facile de voir les fonctions
et la syntaxe spécifique à votre ligne de pseudo-code
>> Gardez à l'esprit que ce ne serait pas identique à la forme de squelette de
votre code que vous écrivez.
Il ya toujours des optimisations à réaliser.
Et surtout dans mon pseudo-code ici, voyez si vous pouvez repérer.
>> Mais l'essentiel du processus et la façon de penser
est juste que nous avons discuté.
La première ligne nous dit d'obtenir un certain montant en dollars.
Et le second nous dit de convertir en cents.
>> Et puis, tout en quarts peuvent être utilisés, nous vouloir augmenter le nombre de pièces et
diminuer le montant de trésorerie.
Idem pour dimes, nickels, et pièces de monnaie.
Et enfin, nous disons l'utilisateur le nombre de pièces que nous avons utilisé.
>> Grand.
Alors que conclut la méthode de la boucle.
Maintenant, nous allons parler de la méthode modulaire, qui ressemble plus à la division.
>> Nous sommes tous familiers avec le plus, moins, multiplier et diviser des opérateurs
à notre disposition.
C a tous les quatre de ceux-ci, mais a aussi l'opérateur modulo, représenté par un
signe pour cent.
Modulo est vraiment bien.
Il vous donne le reste de la division de deux nombres.
>> Rappelez-vous le message de division longue quand vous divisez, par exemple, 74 par trois?
A partir de la position des dizaines, vous savent que 3 va dans sept
deux fois pour une durée de six à reste un.
Vous écririez deux en haut, puis soustraire 6 de sept, portant sur
le reste de 14 à répéter le processus.
>> Trois va en 14 quatre fois à faire 12, avec le reste deux.
Et deux ne portent pas sur plus.
Donc deux serait laissé à la bas que le reste.
>> Et c'est ce qui donne modulo, vous ce nombre en bas.
Donc 74 modulo trois donneriez-vous deux.
Et 10 modulo deux, bien que donnerait de vous concentrer.
Parce qu'il n'y a pas de reste quand on divise 10 par deux.
>> Six modulo cinq, bien cinq passe en six fois.
Et puis il a un reste.
Donc six modulo cinq est un.
>> Alors si vous avez sept modulo neuf, vous obtiendrez sept.
Parce que neuf est plus grand que sept ans.
Donc, il ne divise pas le tout dans sept, laissant sept comme votre réponse.
>> Si vous pensez modulo un peu plus, n'oubliez pas que c'est vous le donne
reste après vous divisez quelque chose.
Pensez à comment vous pourriez être capable de l'utiliser dans Greedy.
Disons que l'utilisateur demande $ 400,11.
Qu'est-ce que c'est une façon de savoir combien de trimestres dont vous avez besoin sans avoir à
compter chacun?
>> Une fois que vous avez compris combien quarts vous pouvez utiliser pour faire $ 400,11, combien
changer restes?
Peut-être une combinaison entre ici modulo et la division viendraient
pratique pour vous donner un endroit frais, élégant aborder le problème Greedy.
Mais n'oubliez pas que la gouvernance règle s'applique toujours.
Toujours utiliser la plus grande pièce possible.
>> Une fois que vous avez fait le calcul de la façon dont de pièces à utiliser, la dernière étape
est d'imprimer le nombre de pièces que vous avez calculé.
Jusqu'à présent, nous avons utilisé le printf fonctionner uniquement pour les chaînes.
Mais lorsque vous souhaitez imprimer un In, ou n'importe quel type de données qui est stocké
dans une variable, vous devez indiquer que l'utilisation d'un espace réservé.
>> Ici, j'ai inclus que quelques conseils sur la façon d'imprimer des valeurs.
Si vous avez un nombre entier, vous le feriez écrire votre chaîne en utilisant% d comme un
espace réservé.
Après la cotation de fermeture marque, entrez une virgule.
Et puis mettre dans l'entier qui sera prendre la place de% d fois imprimée.
>> Donc, après l'affichage du numéro des pièces utilisées, vous êtes
fini avec Greedy.
Assurez-vous de vérifier tous les cas de coin, ranger votre style un peu, et vous êtes
le tout de se soumettre.
A la fin de cette série de problèmes, vous allez être plus familier avec le CS50
appareil, le terminal, et la boucle et les variables dans les structures C.
>> Vous êtes bien sur votre chemin.
La courbe d'apprentissage peut sembler difficile.
Donc prendre étape par étape.
Assurez-vous que vous écrivez pseudo-code avant de plonger trop profondément
en syntaxe inconnu.
>> Faire une liste à faire, et briser la affectation en plus petit, plus
tâches gérables.
Explorez toutes les ressources de CS50.
En plus de la conférence, rewatch cette promenade à travers.
>> Portez une attention particulière à la section.
Découvrez les shorts.
Lisez les questions de vos camarades de classe Discutez sur, et poster le vôtre.
>> Bonne chance avec le p-ensemble.
Et merci pour regarder.
Ce fut avide.
>> [MUSIQUE JEU]