Having trouble where to go next on this program:

1. If n is even, then you may give back exactly n/2 bears.
2. If n is divisible by 3 or 4, then you may multiply the last two digits of n and give back this many bears. By the way, the last digit of n is n%10, and the next-to-last digit is ((n%100)/10. Keep in mind that the result of these operations may be 0, in which case, you don't want to use this option.
3. If n is divisible by 5, then you may give back exactly 42 bears.

Here is what I have so far:

``````bool count(int x)
{
if(x==42){
return true;
}else if (x<42){
return false;
}else{
if(x%5==0){
return count(x-42);
}else if(x%2==0){
return count(x/2);
}else if(x%3==0 || x%4==0){
return count(x - ((x%10) * ((x%100)/10))));
}
}

int main()
{
count(250);
return 0;
}``````

<< moderator edit: added code tags: `[co[u][/u]de][/co[u][/u]de]` >>

Here is how a sample should look like:

bears.
The goal of the game is to end up with EXACTLY 42 bears.
For example, suppose that you start with 250 bears. Then you could make these moves:
• --Since 250 is divisible by 5, you may return 42 of the bears, leaving you with 208 bears.
• --Since 208 is even, you may return half of the bears, leaving you with 104 bears.
• --Since 104 is even, you may return half of the bears, leaving you with 52 bears.
• --Since 52 is divisible by 4, you may multiply the last two digits (resulting in 10) and return these 10 bears. This leaves you with 42 bears.
• --You have reached the goal!

I am having trouble trying to backtrack when n becomes less than 42 in the if statements. ANy help would be much appreciated.

## All 6 Replies

Why are you using recursion for this? A loop would be trivial.

THe problem requires you to solve it recursively. I ended up solving the problem. Here is the code:

``````bool count(int x)
{
if(x==42)
return true;
if (x<42)
return false;
if(x%3==0 || x%4==0)
{ /* rule 2, some cases eliminates rule 1 and rule 3 */
int a = (x%10 * ((x%100)/10));
if(a!=0)
return count(x-a);
/* if the last two digits give 0 we don't want to use that
* So what should we do ??
* The scenario for this is:
*     a) 0x
*       - gets caught by rule 1, 50% of the time and rule 3, 10% of the time
*     b) x0
*       - gets caught by rule 3 100% of the time
*/
}
if(x%5==0) /* rule 3 and in some cases eliminates rule 1 */
return count(x-42);
if(x%2==0) /* rule 1 */
return count(x/2);
/* what should we do if nothing matches (like 59) ??
* Since we got no rule to catch that, we better return false
*/
return false;
}``````

>THe problem requires you to solve it recursively.
Naturally. I wonder when teachers will start giving good assignments for learning recursion instead of contriving silly stuff that could more easily be solved with a loop. :rolleyes:

I've been thinking/saying that for a long time... It's actually why I struggle at times... because I can do the problem, but it's hard to "dumb down" myself to do the problem the way they want it.

Actually doesn't work all the time... try inputting 168

If you have 168, is' even, divide it in 1/2 you can return n/2 bears
168/2 = 84

84 is even so divide it by 2 and walla... 42

Your code is saying it's false. just an FYI

Just FYI, this thread is over a year old.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.