4

Greedy アルゴリズムと Dynamic アルゴリズムを使用して最小コイン数を計算するコードを作成しましたが、Dynamic アルゴリズム部分が正しく動作しません。配列に 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];

}

ねえ、これらは私が得ている結果です

数字を入力してください: 8
貪欲なアルゴリズムによるコイン最小: 3
動的アルゴリズム: 1

私が得ている別の答えは、私が間違っていることを理解できない

数字を入力してください : 71
貪欲なアルゴリズムによるコイン最小: 4
動的アルゴリズム : 3
4

2 に答える 2

4

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

これをしないでください。

于 2012-11-09T05:11:41.877 に答える
1 
int coinCounter(int n){
    int opt[n];
    int largest[n]; <---- Don't do this. This does not work like you expect it to.

への変更

int coinCounter(int n){
        int opt[n];
        int *largest = malloc(sizeof(int)*n);

編集：

アルゴリズムの別のバグ

変数「a」は初期化されておらず、if 条件で使用しています。

denom[i]>j 変数「a」が初期化されない場合を考えてみてください。 そのため、ガベージ値に応じて結果が異なりますバグはこちらですが、opt割り当てを変更すると表示されます。その割り当てにより条件が変更されるためです。私が言いたいのは - if (X<Y)、XとYの両方に依存します。問題はXにありますが、Yを変更すると条件が変わり、異なる結果が得られます

于 2012-11-09T05:41:53.327 に答える