recursive backtracking

[skeet123]

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:
• --Start with 250 bears.
• --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.

[Narue]

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

[skeet123]

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;
}

[Narue]

>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:

[DeadDrunk]

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.

[DeadDrunk]

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

[Narue]

Just FYI, this thread is over a year old.