- 589 名前：デフォルトの名無しさん mailto:sage [2010/07/07(水) 00:26:32 ]
- >>583
#include<stdio.h>
#include<stdlib.h>
int gcd(int a, int b){ int c; while((c=a%b)) a=b, b=c; return b; }
int lcm(int a, int b){ return a/gcd(a, b)*b; }
void coin_func_r(int *result, int c[], int m, int n){
int i;
if(m<0 || c[0]<0 || (*result>0 && n>=*result)) return;
if(m==0){
if(*result<0 || *result>n) *result=n;
return;
}
for(i=0;c[i]>0;i++) coin_func_r(result, c+i, m-c[i], n+1);
}
int coin_func(int c[], int amount){
int i, lcm_all=1, result=-1, rest, c_max=1;
for(i=0;c[i]>0;i++){
lcm_all=lcm(lcm_all, c[i]);
if(c_max<c[i]) c_max=c[i];
}
rest=amount%lcm_all;
coin_func_r(&result, c, rest, 0);
return result+(amount-rest)/c_max;
}
int main(int argc, char *argv[]){
int c[]={15, 10, 8, 5, 1, -1}, x=100, result=-1;
if(argc==2) x=atoi(argv[1]);
result=coin_func(c, x);
printf("%d\n", result);
return 0;
}
|
 |
