我写了一个代码来计算使用贪心算法和动态算法的最小硬币数,但是动态算法部分不能正常工作。数组中有一个 Null 值,我找不到它。请帮我。我需要尽快得到答复。
#include <stdio.h>
int n;
int denom[]={1,2,4,5,20,25};
int coinCounter(int n);
int main(){
printf("Please Enter a Number : ");
scanf("%d",&n);
int coinmin,orin,i;
orin=n;
i=coinmin=0;
for(i=(sizeof(denom)/4)-1;i>=0;i--){
coinmin =coinmin+n/denom[i];
n=n%denom[i];
}
printf("Coin Min By Greedy Algorithm : %d\n",coinmin);
printf("Dynamic Algorithm : %d\n",coinCounter(orin));
return 0;
}
int coinCounter(int n){
int opt[n];
int largest[n];
int i,j,a;
i=j=0;
for(j=1;j<=n;j++){
opt[j]=10000;
//printf("xxn");
for(i=(sizeof(denom)/4)-1;i>=0;i--){
if(denom[i]==j){
opt[j]=1;
largest[j]=j;
}
else if(denom[i]<j){
a=opt[j-denom[i]]+1;
}
if(a<opt[j]){
opt[j]=a;
largest[j]=denom[i];
}
}
}
return opt[n];
}
我按如下方式编辑了代码,但没有得到答案
int coinCounter(int n){
int opt[n];
int largest[n];
int i,j,a;
i=j=0;
for(j=1;j<n;j++){
opt[j]=10000;
printf("xxn");
for(i=(sizeof(denom)/4)-1;i>=0;i--){
if(denom[i]==j){
opt[j]=1;
largest[j]=j;
}
else if(denom[i]<j){
a=opt[j-denom[i]]+1;
}
if(a<opt[j]){
opt[j]=a;
largest[j]=denom[i];
}
}
}
return opt[n-1];
}
嘿,这些是我得到的结果
Please Enter a Number : 8 Coin Min By Greedy Algorithm : 3 Dynamic Algorithm : 1
我得到的另一个答案我不知道我做错了什么
Please Enter a Number : 71 Coin Min By Greedy Algorithm : 4 Dynamic Algorithm : 3
最佳答案
1
int opt[n]; // not the right way to do dynamic allocation. Use malloc/calloc
int largest[n];
2
for(j=1;j<=n;j++){
^ array is indexed from 0...n-1, index-n is outside array bounds
不要这样做。
关于C程序空解析,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13302412/