1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
|
#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;
}
|