une meilleure façon de mettre en œuvre ce

Je surfais sur Internet quand je suis tombé sur cet algorithme (modification) et l’ai implémenté comme ci-dessous … mais existe-t-il encore un moyen efficace de le faire … aussi comment puis-je trouver la complexité du même programme à partir de celui que j’ai implémenté …

1> algorithme est comme suit

makechange(c[],n) //c will contain the coins which we can take as our soln choice and 'n' is the amount we want change for soln<-NULL//set that will hold solution sum=0 while(sum!=n) { x<-largest item in c such that sum+x<=n if(there is no such item) return not found soln here is what i have sortinged #include #include void main() { int c[]= {100,50,20,10,5,1},soln[6]; int num,i,j,sum=0,x,k,flag=0; clrscr(); printf("\nEnter amount to make change:"); scanf("%d",&num); for(i=0;i<6;i++) { soln[i]=NULL; } j=0; while(sum!=num) { for(i=0;i<6;i++) { if(sum+c[i]<=num) { x=c[i]; break; } } sum=sum+x; for(k=0;k<6;k++) { if(soln[k]==x) { flag=1; } } if(flag!=1) soln[j]=x; j++; } printf("\nsoln contains coins below:"); j=0; while(soln[j]!=NULL) { printf("%d ",soln[j]); j++; } getch(); } 

toute aide serait appréciée … merci …

Pour le plaisir, voici une version de constexpr !

 template  static constexpr auto change(int amount) -> decltype(make_tuple(denomination...)) { typedef decltype(make_tuple(denomination...)) R; return R { [&]() { auto fill=amount/denomination; amount-=denomination*fill; return fill;}()... }; } 

Démo: Live On Coliru

 #include  #include  using boost::tuple; using boost::make_tuple; template  static constexpr auto change(int amount) -> decltype(make_tuple(denomination...)) { typedef decltype(make_tuple(denomination...)) R; return R { [&]() { auto fill=amount/denomination; amount-=denomination*fill; return fill;}()... }; } int main() { auto coins = change<100,50,20,10,5,1>(367); std::cout << coins; } 

Sortie:

 (3 1 0 1 1 2) 

Version sans boost: http://liveworkspace.org/code/3uU2AS$0

Pour génial, c'est le désassemblage de la version non boost compilée par clang avec -O2. http://paste.ubuntu.com/5632315/

Remarquez le motif 3 1 0 1 1 2?

 400826: be 03 00 00 00 mov $0x3,%esi ... 400847: be 01 00 00 00 mov $0x1,%esi ... 400868: 31 f6 xor %esi,%esi ... 400886: be 01 00 00 00 mov $0x1,%esi ... 4008a7: be 01 00 00 00 mov $0x1,%esi ... 4008c8: be 02 00 00 00 mov $0x2,%esi 

C'était complètement comstacktime évalué!

L’autre approche consiste à examiner les options de pièces, en commençant par les plus grandes, et en en prenant le plus possible sans devenir négatif, puis en passant à la suivante, et ainsi de suite:

 #define RESULT_EXACT 1 #define RESULT_INEXACT 0 int i; int result_exact = RESULT_EXACT; for (i=0; i<6; i++) { soln[i] = n/c[i]; // How many of this value do we need n -= soln[i]*c[i]; // We've now given that amount away } if (n!=0) result_exact = RESULT_INEXACT; 

Évidemment (j'espère), cela nécessite que c stocke les valeurs des pièces du plus grand au plus petit et nécessite un contrôle sur result_exact pour savoir si le changement est exactement correct.