-1

I tried to solve project euler 31:

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

with this code:

#define to2(x) ((x)/2+1)

int to5(x)
{
    int acc=1;
    for(;x>0;x-=5)
        acc+=to2(x);
    return acc;
}

int to10(x)
{
    int acc=1;
    for(;x>0;x-=10)
        acc+=to5(x);
    return acc;
}

int to20(x)
{
    int acc=1;
    for(;x>0;x-=20)
        acc+=to10(x);
    return acc;
}

int to50(x)
{
    int acc=1;
    for(;x>0;x-=50)
        acc+=to20(x);
    return acc;
}

int to100(x)
{
    int acc=1;
    for(;x>0;x-=100)
        acc+=to50(x);
    return acc;
}

int main()
{
    int test = to100(200)+1;
    printf("%d",test);
    return 0;
}

But the code gives 73685, not 73682 but I don't know why, could someone help me plz?

2
  • 1
    And what should it compute? The question should make sense on its own, not just after looking at assignments from other sites.
    – jpalecek
    Feb 6, 2012 at 15:30
  • 3
    If at all appropriate, not everybody knows project Euler 31. What are you trying to solve?
    – Bart
    Feb 6, 2012 at 15:31

2 Answers 2

6

Why do you initialize acc to 1? (It makes sense when x is a multiple of the number of the function, but only then.) change it to 0, and change the loop condition to x>=0. (If I understood your code).

1
1

This problem does not need C code to solve, it is a problem of set selections. You need to solve number of ways to select n coins where n > 0 and sum = 2£, you should look up Set theory.
This should help you find a linear equation to compute the number.

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.