任何更好的方式来实现这个

当我遇到这个算法(进行更改)并在下面实现它时,我正在网上冲浪…但仍然有任何有效的方法来做到这一点……我怎样才能从我执行的程序中找到相同的复杂性…

1>算法如下

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 tried #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(); } 

任何帮助将不胜感激…谢谢……

为了好玩,这是一个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;}()... }; } 

演示: 住在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; } 

输出:

 (3 1 0 1 1 2) 

版本没有提升: http : //liveworkspace.org/code/3uU2AS$0

对于绝对令人敬畏的,这是clang与-O2编译的非boost版本的反汇编。 http://paste.ubuntu.com/5632315/

注意模式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 

这是完全编译时评估的!

另一种方法是通过硬币选项,盯着最大的硬币,并尽可能多地使用硬币,而不是消极,然后再到下一个最大,等等:

 #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; 

显然(我希望)这要求c存储从最大到最小的硬币值,并需要检查result_exact以了解更改是否完全正确。