＜問題＞
①ある正の整数が与えられる。
例）１５
②整数は１かその数自身を除いた約数で除算ができる。
例）１５－３＝１２
③ＪｏｈｎとＢｒｕｓの２人でゲームをし、除算ができなくなった方が負け。
最初のターンはＪｏｈｎ。
④このとき、与えられた整数に対して勝つ方のプレイヤー名を返す。
＜関数＞
memset(f,0,sizeof(f));
数字を０で初期化する関数。
これも使えますが、単純に宣言での初期化をしました。
return f[n] ? "John" : "Brus";
f[n]が正の時は"John"、偽の時は"Brus"を返す。
これでもＯＫですが、if文でも。
Challengeポイント
最初はjをj<i/2としましたが、i/2は含めないといけなかったので
システムテストでfail。
安全にj<iまで最後までまわした方がよいですね。
＜考え方＞
特定の整数が与えられた際、勝ちか負けかが一意に決まる。
これを利用し１から初めて、
与えられた整数まで全ての数に対して勝ち負けの状態遷移を保存する。
1,2,3～6ぐらいまでシミュレーションしてみると、
ある整数に対し、それ未満の割り切れる整数に対し
check[i-j]が0になれば勝ちなので1とする。それ以外は0のまま。
＜コード＞
class TheNumberGameDivTwo {
public: string find(int n) {
vector<int> check(n+1,0);
FORE(i,1,n+1){
FORE(j,2,i)if(i%j==0 && check[i-j]==0)check[i]=1;
}
if(check[n]==1)return "John";
return "Brus";
}
};
①ある正の整数が与えられる。
例）１５
②整数は１かその数自身を除いた約数で除算ができる。
例）１５－３＝１２
③ＪｏｈｎとＢｒｕｓの２人でゲームをし、除算ができなくなった方が負け。
最初のターンはＪｏｈｎ。
④このとき、与えられた整数に対して勝つ方のプレイヤー名を返す。
＜関数＞
memset(f,0,sizeof(f));
数字を０で初期化する関数。
これも使えますが、単純に宣言での初期化をしました。
return f[n] ? "John" : "Brus";
f[n]が正の時は"John"、偽の時は"Brus"を返す。
これでもＯＫですが、if文でも。
Challengeポイント
最初はjをj<i/2としましたが、i/2は含めないといけなかったので
システムテストでfail。
安全にj<iまで最後までまわした方がよいですね。
＜考え方＞
特定の整数が与えられた際、勝ちか負けかが一意に決まる。
これを利用し１から初めて、
与えられた整数まで全ての数に対して勝ち負けの状態遷移を保存する。
1,2,3～6ぐらいまでシミュレーションしてみると、
ある整数に対し、それ未満の割り切れる整数に対し
check[i-j]が0になれば勝ちなので1とする。それ以外は0のまま。
＜コード＞
class TheNumberGameDivTwo {
public: string find(int n) {
vector<int> check(n+1,0);
FORE(i,1,n+1){
FORE(j,2,i)if(i%j==0 && check[i-j]==0)check[i]=1;
}
if(check[n]==1)return "John";
return "Brus";
}
};