Python to C algorithm

Question

I am trying to find simple recursive implementation of change-making algorithm and all i could find is this (working) algorithm in python:

def min_change(V, C):
    def min_coins(i, aC):
        if aC == 0:
            return 0
        elif i == -1 or aC < 0:
            return float('inf')
        else:
            return min(min_coins(i-1, aC), 1 + min_coins(i, aC-V[i]))
    return min_coins(len(V)-1, C)

I dont understand python so i am asking for help if anyone could rewrite this small code in C or Java so it would be understandable to me. Or if anyone know of any implementation of this in C or Java can you post link please ?

Thank you for any help

edit: I was able to do this:

int min_change(int * V, int C) {
    return min_coins(/*Length-last index*/, C)
}

int min_coins(int i, int C) {
    if (C == 0)return 0;
    else if (i == -1 || C < 0)return sizeof (int)*32;
    else return min(min_coins(i - 1, C), 1 + min_coins(i, C - V[i]));
}

It's probably easier to learn enough python to read this than it would be to re-write it. What's confusing? def defines a function. It's a little odd here that they're defining a function within another function, but that just scopes it. The rest of the syntax is very C-like, without the brackets of course. In python, the indentation defines what brackets would in C. — Collin
– Collin, Commented Dec 4, 2013 at 20:21
To expand @Collin's comment about defining the function in another function - that's a closure. Doing it that way allows min_coins to access the V variable from its parent namespace. I expect you could replace that with a third parameter to min_coins instead. — Peter DeGlopper
– Peter DeGlopper, Commented Dec 4, 2013 at 20:30
here's another recursive algorithm plus very simple (to implement) iterative one in Python. Could you describe what you do not understand about the function definition that you've provided given that you already know C? Just add int* V argument to min_coins() and pass V's length to min_change(). You could use unsigned type as a return value (number of ways is >=0), use UINT_MAX instead of float('inf') in this case. — jfs
– jfs, Commented Dec 5, 2013 at 21:58

alexgirao · Accepted Answer · 2013-12-04 21:18:22Z

1

I believe this is the correct equivalent:

    #include <stdlib.h>
    #include <stdio.h>
    #include <stdint.h>

    int min_change0(int *V, int i, int aC)
    {
      if (aC == 0) {
        return 0;
      } else if (i == -1 || aC < 0) {
        return INT32_MAX - 1;
      } else {
        int a = min_change0(V, i-1, aC);
        int b = 1 + min_change0(V, i, aC - V[i]);
        return a <= b ? a : b;
      }
    }

    int min_change(int *V, int C)
    {
      int len = 0;
      while (V[len]) len++;
      /* min_coins(len(V)-1, C) */
      return len ? min_change0(V, len-1, C) : -1;
    }

    int main(void)
    {
      int total = 123;
      int values[] = {1,5,10,25,50,0 /* sentinel */};
      printf("minimal number of coins to change %i with 1, 5, 10, 25 and 50 coins is %i\n",
             total,
             min_change(values, total)
             );
      return 0;
    }

as 2*50 + 2*10 + 3*1 is 123

answered Dec 4, 2013 at 21:18

alexgirao

9059 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Pastx Over a year ago

Is there any way i could remember coins i used ? So output would be 50,50,10,10,1,1,1 instead of just 7?

alexgirao Over a year ago

that is a very good question that I was unable to answer, though I like math and specially number theory, I'll have to defer such investigation, maybe asking in math.stackexchange.com should yield a prompt answer

Collectives™ on Stack Overflow

Python to C algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related