[A or B win] using recursion

[c2252011]

Hi
There is a question asking A or B to take turns to take coins out off the pool. assume that there are n coins, A always takes first. they are only allow to take 2,3,5,7,11 coin. if some one cannot take any coins in the pool then that one is lost.[remember they are only allowed to take 2,3,5,7,11 but not 1 or 0]
so given n, find A can win or not.


Here is my code, however, it gave the wrong answer. :( so what are the errors?



#include <iostream>

using namespace std;

bool test(int n, bool evaluated[], bool result[]){
if (n==0 || n==1)
return false; // no more tokens can be taken

if (evaluated[n])
return result[n];//has been evaluated then return the result of previous evaluation

if (n>1){
if (test(n-2,evaluated, result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;//record that test(n) has been evaluated and result is true;
return true;
}

if (test(n-3,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;
return true;}

if (test(n-5,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if (test(n-7,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if (test(n-11,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if ((test(n-2,evaluated,result))
&&(test(n-3,evaluated,result))
&&(test(n-5,evaluated,result))
&&(test(n-3,evaluated,result))
&&(test(n-11,evaluated,result))){ // if A cannot win by taking either 2,3,5,7 or 11 tokens, then A must lose.
evaluated[n]=1;
result[n]=0;
return false;}

else {
evaluated[n]=1;
result[n]=1;
return true;}
}

else {
evaluated[n]=1; //record that test(n) has been evaluated and result is false;
//return false;
result[n]=0;
return false;}

}

int main(){
int n;
cin >> n;

bool *evaluated= new bool[n+1];
bool *result = new bool[n+1];

for (int n=1;n<100;n++)
if (test(n,evaluated,result))
cout << n << "Adam can win" << endl;

else
cout << n <<"Adam cannot win" << endl;

system ("pause");
return 0;

}

[ascii]

How does one "win."

[Ben Duncan]

OH MY FREAKING BAJESUS! PUT THE CODE TAGS IN!

#include <iostream>

using namespace std;

bool test(int n, bool evaluated[], bool result[]){ 
if (n==0 || n==1)
return false; // no more tokens can be taken

if (evaluated[n])
return result[n];//has been evaluated then return the result of previous evaluation

if (n>1){ 
if (test(n-2,evaluated, result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;//record that test(n) has been evaluated and result is true;
return true;
}

if (test(n-3,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;
return true;}

if (test(n-5,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if (test(n-7,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if (test(n-11,evaluated,result)){
evaluated[n]=1;// B cannot win after 2 tokens being taken then
result[n]=1;// B cannot win after 2 tokens being taken then
return true;}

if ((test(n-2,evaluated,result))
&&(test(n-3,evaluated,result))
&&(test(n-5,evaluated,result))
&&(test(n-3,evaluated,result))
&&(test(n-11,evaluated,result))){ // if A cannot win by taking either 2,3,5,7 or 11 tokens, then A must lose.
evaluated[n]=1;
result[n]=0;
return false;}

else {
evaluated[n]=1;
result[n]=1;
return true;}
}

else {
evaluated[n]=1; //record that test(n) has been evaluated and result is false;
//return false;
result[n]=0;
return false;}

}

int main(){
int n;
cin >> n;

bool *evaluated= new bool[n+1];
bool *result = new bool[n+1];

for (int n=1;n<100;n++)
if (test(n,evaluated,result))
cout << n << "Adam can win" << endl;

else
cout << n <<"Adam cannot win" << endl;

system ("pause");
return 0;

}

[c2252011]

if there is 1 or 0 left when some one is about to take, then that some one is lost

[cire]

Just looking at:

int main(){
	int n;
	cin >> n;

	bool *evaluated= new bool[n+1];
	bool *result = new bool[n+1];

	for (int n=1;n<100;n++)
	{ // braces added by cire for clarity.
		if (test(n,evaluated,result))
			cout << n << "Adam can win" << endl;
		else
			cout << n <<"Adam cannot win" << endl;
	}

	return 0;
}

First, you have two separate ns defined in main. It may be that you are entering a large enough number initially that you aren't accessing memory that doesn't belong to you, but why are you using user input at all given what the for loop does?

You're off track with the whole evaluated and result thing.

I would suggest starting over with bool test(int num_coins) as your test function. Don't forget you need to account for player B's moves!