Dev Faq
-1
votes

Déterminez le nombre minimum de pièces de monnaie requises pour donner un changement à l'aide de l'approche gourmande

Comme une affectation pour mon cours sur la conception et l'analyse des algorithmes, on m'a demandé de déterminer le nombre minimum de pièces de monnaie nécessaires à la modification, à l'aide d'une approche gourmande. J'ai proposé cette approche intuitive: 

#include<stdio.h>
#include<stdlib.h>

int main(){
  int hundreds=0,tens=0,ones=0,sum=0;

  printf("Enter a sum of money in range 1 to 999\n");
  scanf("%d",&sum);
  while(sum!=0) {
    if (sum<10&&sum>=1){
      ones=sum/1;
      sum-=ones;
    }
    else if(sum>=10&&sum<100){
      tens=sum/10;
      sum-=tens*10;
    }
    else if(sum>=100&&sum<=999){
      hundreds=sum/100;
      sum-=hundreds*100;
    }
    else{
      printf("Error");
      exit(0);
    }
  }

  printf("%d $100, %d $10, %d $1",hundreds,tens,ones);
  return 0;
}

7 commentaires

Qui vous a dit d'utiliser une approche gourmande? L'avez-vous demandé ce qu'ils entendent par «une approche gourmande»?

Cela peut être résolu sans boucle; Dans chaque itération, exactement 1 des cas sera vrai et ne sera jamais vrai dans aucune itération future.

Alors que le compilateur ne se soucie pas des espaces, des lignes vides, une indentation ou des commentaires, ces choses sont très importantes pour les humains qui tentent de lire et de comprendre votre code.

Par "une approche gourmande", je veux dire un algorithme gourmand. Ce programme utilise donc un algorithme gourmand? Comment puis-je le prouver?

@Divyanshuvarma Il n'y a pas de limite sur le gourmand car il est possible d'ajouter tout calcul inutile, mais il est facilement possible de faire plus de gourmand, regarde ma réponse

Depuis la question concerne le nombre minimum de pièces de monnaie. Discutons-nous des livres anglaises ou des pièces américaines ou autre chose?

OT: Concernant: scanf ("% d", et somme); Vérifiez toujours la valeur renvoyée (pas les valeurs de paramètre) pour assurer que l'opération a été réussie

3 Réponses :

1
votes

Votre code n'est pas suffisant gourmand car cela peut être pire: xxx pré>

compilation et exécution: p> xxx pré>

Comment puis-je prouver que le programme est correct p> blockQuote>

A (gourmand) pour prouver que le code est correct est d'utiliser la force brutale pour vérifier le résultat de 1 à 999: P> 

pi@raspberrypi:/tmp $ gcc -pedantic -Wextra g.c
pi@raspberrypi:/tmp $ ./a.out
all ok

2 commentaires

Comment ces questions répondent-elles?

@Jeffuk Réponse corrigé pour faire plus gourmand ...

4
votes

Ceci est vraiment une approche gourmande, mais vous devez inverser l'ordre de si, alors, autre. En général, gourmand signifie consommer au moment actuel la plus grande quantité que vous pouvez consommer.

Vous devez vérifier d'abord pour la plus grande pièce de monnaie. Il n'y a pas besoin de boucle. xxx

0 commentaires
0
votes

Le code proposé suivant:

  1. compile parfaitement
  2. n'inclut pas les fichiers d'en-tête Ces contenus ne sont pas utilisés
  3. suit l'axiome: une seule déclaration par ligne et (au plus) une déclaration variable par déclaration.
  4. effectue la fonctionnalité souhaitée
  5. Effectue une vérification des erreurs appropriées
  6. effectue un algorithme "gourmand" de consommer autant que possible "l'argent" que possible, en utilisant le moins de "factures"

    et maintenant, le code proposé: xxx

    Le code proposé ignore les factures (américaines) 50 $, 20 $, 5 $, 5 $ et 2 $

0 commentaires

Articles qui pourrait vous intéresser :

Que puis-je utiliser pour la conversion d'entrée au lieu de scanf?
Comment puis-je calculer a * b / c lorsque a et b sont tous deux plus petits que c, mais que a * b déborde?
Comment vérifier si un pointeur void (void *) est l'un des deux types de données?
L'écran LCD affiche des caractères aléatoires (MPLAB)