Recursive Backtracking

[ChuckB]

Ok, I'm working on this program to do recursive backtracking, however
it's not working for all cases. Any help would be apprietiated. (all 4
should be true, but 168 is coming up false)

Heres the rules:
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.
The goal of the game is to end up with EXACTLY 42 bears.

Heres the code:
#include <iostream>
using namespace std;
bool bear (int);

void main( )
{
cout << bear(168) << endl;
cout << bear(250) << endl;
cout << bear(42) << endl;
cout << bear(84) << endl;
}

bool bear(int x)
{
if (x<42)
return false;
if(x==42)
return true;
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 bear(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 bear(x-42);
if(x%2==0) /* rule 1 */
return bear(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;
}

 

[KS]

bool bear(int x)

{
if (x<42)
return false;
if(x==42)
return true;
if(x%3==0 || x%4==0)
{ /* rule 2, some cases eliminates rule 1 and rule 3 */
int a = (x%10 * ((x%100)/10));

You probably want to apply rules in the order given by your
description. (You are applying rule 2 before rule 1)

 

[Christoph Flohr]

Ok, I'm working on this program to do recursive backtracking, however

it's not working for all cases. Any help would be apprietiated. (all 4
should be true, but 168 is coming up false)

Heres the rules:
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.
The goal of the game is to end up with EXACTLY 42 bears.

try:

#include <iostream>

bool bear(int x);

int main()
{ std::cout << std::boolalpha ;
std::cout << bear(168) << std::endl;
std::cout << bear(250) << std::endl;
std::cout << bear(42) << std::endl;
std::cout << bear(84) << std::endl;
return 0;
}

bool bear(int x)
{ if (x<42)
return false;

if (x==42)
return true;

if (x%2==0)
if (bear( x/2 ))
return true;

if ((x%3==0)||(x%4==0))
if ( int a =((x%10)*((x%100)/10)) )
if (bear( x - a))
return true;

if (x%5==0)
if (bear( x-42 ))
return true;

return false;

}