网站平台管理,培训网站建设课程,wordpress写表格,做网站月入1000输入#xff1a;一个正整数N 输出#xff1a;Alice赢#xff0c;返回true#xff0c;否则false 规则#xff1a;黑板上给出一个数字N#xff0c;ALice先选择。Bob后选择。他们可以选择一个数字 X#xff0c;0XN并且N%X0。一个人选择X以后#xff0c;黑板上的数…输入一个正整数N 输出Alice赢返回true否则false 规则黑板上给出一个数字NALice先选择。Bob后选择。他们可以选择一个数字 X0XN并且N%X0。一个人选择X以后黑板上的数字变为N-X。 当一个人没有可以选择的数字的 时候就输了。假设Alice和 Bob水平相同状态相同。 分析假设N5。 Alice选择1黑板数字 变为4。 Bob选择2或者1. Bob选择2黑板 数字变为2。 Alice选择1黑板数字变为1。 Bob没有可以选的Alice赢。 Bob选择1黑板数字变为3 Alice选择黑板数字变为。 Bob选择1黑板数字变为1。 Alice没有可以选的Alice输。
Bob有两种选择会导致Alice可能赢也可能输。那结果应该是什么呢题目中有一个条件是Alice和 Bob水平相同状态相同。他们应该会分析怎么选择才能让自己赢。我觉得这可能是题目的难点。我们使用归纳法总结一下。 从上面的分析看到谁遇到数字谁会输。谁遇到数字谁就会赢。谁遇到数字谁会输。 那遇到数字只要让对方遇到数字自己就赢了。 那遇到遇到数字呢要让对方遇到数字或者自己能赢但是不等于不等于所以只能选择对方遇到数字对方赢。 我们需要一个dp,dp[i]true表示Alice遇到数字i会赢dp[i]false表示Alice遇到数字i会输。 public boolean divisorGame(int N) {boolean[] target new boolean[N1];target[1] false; if(N1) return false;target[2] true;for(int x 3;xN;x){for(int y1;yx/2;y){if(x%y0 target[x-y]false){target[x]true;break;}}}return target[N];}分析2使用数学归纳法。 N1输 N2赢 N3输 N4赢 假设 N奇数输N偶数赢。 那么当Nn1时如果n是偶数N一定是奇数。如果想要赢我们一定要选一个偶数留给对方一个奇数。但是N是奇数N的约数只有1我们只能选择1剩下一个偶数给对方。所以我们一定会输。 如果n是奇数N一定是偶数。如果想要赢我们一定要留给对方一个奇数那我们可以选择一个奇数可以直接选择1留一个奇数给对方。我们一定会赢。 假设成立。 public boolean divisorGame(int N) {return N%20;}
