simple recursion program using mathematical induction

[kesler]

Hi, I am trying to write a program that utilizes mathematical induction. Where the user enter a target greater than 8 and the program will figure out how many 3 and 5 will be needed to add up to that target. I wrote the main function already but I don't know how to write the following function using mathematical induction. Could anyone help me? Thanks.
Function prototype:
int calc( int x, int &three, int &five );
// x= target value

[NMTop40]

looks just like my stamp problem.

Yes, recursion is one versatile method to use, because you get a tree-type structure. (versatile if you want to be able to change the numbers you are using, or the number of them).

The function should return -1 if you can't reach the solution, 0 if x is 0 and otherwise the number of digits required.

In order to remove permutations of the same solution, you should only be allowed to pick them sorted. So the prototype won't be like that but will give a set of available values.

But for the most basic method you would do as follows:


int calc( int x, int &three, int &five )
{
int i5=0; i3=0;

if ( x == 0 )
{
return 0;
}
else if ( x < 3 )
{
return - 1;
}

i5 = calc( x-5, three, five );
i3 = calc( x-3, three, five );

if ( i5 == -1 )
{
if ( i3 == -1 )
{
return -1;
}
else
{
++three;
return 1 + i3;
}
}
else if ( (i3 == -1) || (i5 < i3) )
{
--five;
return 1+i5;
}
else
{
--three;
return 1+i3;
}
}




That will work but is not the optimal solution.

You can also make a table for values between 8 and 22:

struct pair35
{
int i3;
int i5;
};

const pair35 table35[] =
{
{1,1}, // 8
{0,3}, // 9
{2,0}, // 10
{1,2}, // 11
{0,4}, // 12
{2,1}, // 13
{1,3}, // 14
{3,0}, // 15
{2,2}, // 16
{1,4}, // 17
{3,1}, // 18
{2,3}, // 19
{4,0}, // 20
{3,2}, // 21
{2,4} // 22
};




Now I can solve the whole thing without recursion.

int calc( int x, int &three, int &five )
{
int y1 = x - 8;
int y2 = y1 % 15;
int y3 = y1 / 15;

five = 3 * y3 + table35[y2].i5;
three = table35[y2].i3;

return five + three;
}






The best things come to those who rate

[baheath]

Another way not using tables:


int calc( int x, int &three, int &five )
{
if(x == 1 || x == 2 || x == 4 || x == 7) // no solution for these inputs
return -1;
else if(x == 5)
{
three = 0;
five = 1;
}
else if(x == 8)
{
three = 1;
five = 1;
}
else if( (x % 3) == 0)
{
three = x / 3;
five = 0;
}
else if( (x % 3) == 1)
{
three = ((x - 1) / 3) - 3;
five = 2;
}
else // (x % 3) == 2
{
three = ((x - 2) / 3) - 1;
five = 1;
}

return five + three;
}

[NMTop40]

that wouldn't give you the optimal solution.

my solution with tables wasn't complete of course as I should have handled the cases where x is 0 to 7.

you would get the optimal solution by going through x%5 though


int calc( int x, int &three, int &five )
{
if ( x < 0 ) return -1;

switch ( x )
{
case 0:
three = 0; five = 0; return 0;
case 3:
three = 1; five = 0; return 1;
case 5:
three = 0; five = 1; return 1;
case 6:
three = 2; five = 1; return 2;
case 1: case 2: case 4: case 7:
return -1;

// could put rest into default...
}
switch ( x % 5 )
{
case 0: three = 0; break;
case 1: three = 2; break;
case 2: three = 4; break;
case 3: three = 1; break;
case 4: three = 3; break;
}
five = ( x- 3 * three) / 5;
return five + three;
}






The best things come to those who rate

[baheath]

no you would get the optimal solution using x%3:


int calc( int x, int &three, int &five )
{
if ( x < 0 ) return -1;
switch ( x )
{
case 5:
three = 0; five = 1; return 1;
case 8:
three = 1; five = 1; return 2;
case 1: case 2: case 4: case 7:
return -1;
// could put rest into default...
}
switch ( x % 3 )
{
case 0: five = 0; break; // handles x = 0, 3, 6, 9
case 1: five = 2; break;
case 2: five = 1; break;
}
three = ( x - (5 * five) ) / 3;
return five + three;
}





But both algorithms the same efficiency (using 'Big O' notation they are both O(1), assuming *, +, etc. are constant efficiency, which is the normal thing to do) so it doesn't matter that much anyway.

[NMTop40]

the optimal solution is the one with the lowest return value.

if you have 15 then it is cheaper to have 3 fives than 5 threes

I think in my solution I forgot to divide by 5.

I know some of my cases could have been solved in the "general" solution (5 and 6)

In your case, your general solution also handles 5 (as well as 3 and 6)


The best things come to those who rate

[baheath]

Oh, I thought you meant optimal algorithm (fastest) and not optimal solution (least number of fives and threes). So you are correct.

Cheers,

Brandon