任何更好的方法来实现这一点

Question

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

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 <- soln U {a coin of value x}
    sum=sum+x
    return soln
}

2>here is what i have tried

#include<stdio.h>
#include<conio.h>

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

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

Answer 1

为了好玩,这是一个constexpr版本!

template <int... denomination>
    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 <boost/tuple/tuple_io.hpp>
#include <iostream>

using boost::tuple;
using boost::make_tuple;

template <int... denomination>
    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

这是完全编译时评估的!