Skip to content. | Skip to navigation

Personal tools

Sections
You are here: Home / Didaktik der Informatik / Muenzen

Muenzen

C source code icon muenzen.c — C source code, 1 KB

File contents

#include <stdio.h>
int w,manz,muenz[20],cache[10000];

int muenzsolv(int v)
{ int min,help,i;
  
  if (v==0)
  { 
    return 0;
  }
  if (v<0) return 10000;
  min=10000;
  if (cache[v]<10000) return cache[v];
  for (i=0;i<manz;i++)
  {
    help=muenzsolv(v-muenz[i]);
    if (help<min)
    {
      min=help;
    } 
  }
  cache[v]=min+1;
  return min+1;
  
}

int main(void)
{
  int i;
  
  for(i=0;i<10000;i++){cache[i]=10000;}
  
  
  printf("Anzahl:");
  scanf("%i",&manz);
  for (i=0;i<manz;i++) scanf("%i",&muenz[i]);
 do {
  printf("Wert 0=Ende");
  scanf("%i",&w);
     printf("%i\n",muenzsolv(w));
  }
  while (w!=0);
  return(0);
}