在nim游戏中找到赢家-yiteyi-C++库

您将得到一个由n个元素组成的数组A[]。有两位选手爱丽丝和鲍勃。玩家可以从数组中选择任意元素并将其移除。如果移除选定元素后，所有剩余元素的按位异或等于0，则该播放器将失败。这个问题就是尼姆：游戏。

null

注：每个玩家轮流玩游戏。如果两名球员都发挥最佳状态，找出胜利者。爱丽丝先开始比赛。在情况下，数组中的一个元素将其值视为数组的XOR。

例如：

输入：A[]={3,3,2} 输出：Winner=Bob 说明：Alice可以选择2并删除它，使数组的XOR等于零。如果Alice选择3删除，Bob可以选择2/3中的任何一个，最后Alice必须执行他的步骤。

输入：A[]={3,3} 输出：Winner=Alice 说明：由于数组的异或已经为零，Alice无法选择任何要删除的元素，因此Alice是赢家。

让我们一步一步地开始解决这个问题。我们总共有三个选择的异或阵列和这个游戏。

数组的XOR已为0： 在这种情况下，爱丽丝将无法采取行动，因此爱丽丝是赢家。
数组的异或不是零： 现在，在这种情况下，我们有两个选择，数组的大小将是奇数或偶数。
- 案例A：如果阵列大小是奇数，那么鲍勃肯定会赢得比赛。
- 案例B：如果数组大小为偶数，则Alice将赢得游戏。

通过数学归纳法可以证明上述结论。设A[]={1}即数组的大小为奇数，数组的异或为非零：在这种情况下，Alice可以选择元素1，然后[]将变为空，因此数组的XOR可以被视为零。结果鲍勃获胜。让数组的大小为偶数，数组的异或为非零。现在我们可以证明Alice总能找到一个要移除的元素，这样数组中剩余元素的XOR将不为零。

为了证明这一点，让我们从矛盾开始，即假设你应该选择剩余数组的XOR的任何元素都必须为零。所以，让a1xor a2xor…An=X，n是偶数。根据我们的矛盾假设，对于1<=i<=n，Ai Xor X=0。计算所有XOR Ai（即n个方程）的XOR，取所有n个方程的XOR后，我们得到XOR X…XOR X（n次）=0，因为n是偶数。现在，我们还有A1或A2异或。。An=0，但我们知道A1 Xor A2…Xor=X。这意味着我们在偶数大小的数组中至少有一个元素，这样在它移除非零中剩余元素的Xor之后。

让数组的大小为偶数，数组的异或为非零。 Alice不能删除元素Ai，使剩余数字的xor为零，因为这将使Bob获胜。现在，以另一种情况为例，当剩余N的xor？1是非零的数字。正如我们所知，N？1是均匀的，根据归纳假设，我们可以说，当前移动后的位置将是Bob获胜的位置。因此，这对爱丽丝来说是一个失败的位置。

int res = 0;for (int i = 1; i <= N; i++) {    res ^= a[i];}if (res == 0)    return "ALice";if (N%2 == 0)    return "Alice";else    return "Bob";

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

C++

                         // CPP to find nim-game winner                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to find winner of NIM-game                       
                         string findWinner(                                     int                                     A[],                                     int                                     n)                       
                         {                       
                                                 int                                     res = 0;                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 res ^= A[i];                       
           
                                                 // case when Alice is winner                       
                                                 if                                     (res == 0 || n % 2 == 0)                       
                                                 return                                     "Alice"                                     ;                       
           
                                                 // when Bob is winner                       
                                                 else                       
                                                 return                                     "Bob"                                     ;                       
                         }                       
           
                         // driver program                       
                         int                                     main()                       
                         {                       
                                                 int                                     A[] = { 1, 4, 3, 5 };                       
                                                 int                                     n =                                     sizeof                                     (A) /                                     sizeof                                     (A[0]);                       
                                                 cout <<                                     "Winner = "                                     << findWinner(A, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java to find nim-game winner                       
                         class                                     GFG {                       
                                   
                                                 // function to find winner of NIM-game                       
                                                 static                                     String findWinner(                                     int                                     A[],                                     int                                     n)                       
                                                 {                       
                                                 int                                     res =                                     0                                     ;                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n; i++)                       
                                                 res ^= A[i];                       
                                   
                                                 // case when Alice is winner                       
                                                 if                                     (res ==                                     0                                     || n %                                     2                                     ==                                     0                                     )                       
                                                 return                                     "Alice"                                     ;                       
                                   
                                                 // when Bob is winner                       
                                                 else                       
                                                 return                                     "Bob"                                     ;                       
                                                 }                       
                                   
                                                 //Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     A[] = {                                     1                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     };                       
                                                 int                                     n =A.length;                       
                                   
                                                 System.out.print(                                     "Winner = "                       
                                                 + findWinner(A, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to find nim-game winner                       
           
                         # Function to find winner of NIM-game                       
                         def                                     findWinner(A, n):                       
           
                                                 res                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (n):                       
                                                 res ^                                     =                                     A[i]                       
           
                                                 # case when Alice is winner                       
                                                 if                                     (res                                     =                                     =                                     0                                     or                                     n                                     %                                     2                                     =                                     =                                     0                                     ):                       
                                                 return                                     "Alice"                       
           
                                                 # when Bob is winner                       
                                                 else                                     :                       
                                                 return                                     "Bob"                       
           
                         # Driver code                       
                         A                                     =                                     [                                     1                                     ,                                     4                                     ,                                     3                                     ,                                     5                                     ]                       
                         n                                     =                                     len                                     (A)                       
                         print                                     (                                     "Winner = "                                     , findWinner(A, n))                       
           
                         # This code is contributed by Anant Agarwal.                       

C#

                         // C# to find nim-game winner                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // function to find winner of NIM-game                       
                                                 static                                     String findWinner(                                     int                                     []A,                                     int                                     n)                       
                                                 {                       
                                                 int                                     res = 0;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 res ^= A[i];                       
                                   
                                                 // case when Alice is winner                       
                                                 if                                     (res == 0 || n % 2 == 0)                       
                                                 return                                     "Alice"                                     ;                       
                                   
                                                 // when Bob is winner                       
                                                 else                       
                                                 return                                     "Bob"                                     ;                       
                                                 }                       
                                   
                                                 //Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     []A = { 1, 4, 3, 5 };                       
                                                 int                                     n =A.Length;                       
                                   
                                                 Console.WriteLine(                                     "Winner = "                       
                                                 + findWinner(A, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP to find nim-game winner                       
           
                         // function to find                       
                         // winner of NIM-game                       
                         function                                     findWinner(                                     $A                                     ,                                     $n                                     )                       
                         {                       
                                                 $res                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 $res                                     ^=                                     $A                                     [                                     $i                                     ];                       
           
                                                 // case when Alice is winner                       
                                                 if                                     (                                     $res                                     == 0                                     or                                     $n                                     % 2 == 0)                       
                                                 return                                     "Alice"                                     ;                       
           
                                                 // when Bob is winner                       
                                                 else                       
                                                 return                                     "Bob"                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $A                                     =                                     array                                     (1, 4, 3, 5 );                       
                         $n                                     =                                     count                                     (                                     $A                                     );                       
                         echo                                     "Winner = "                                     , findWinner(                                     $A                                     ,                                     $n                                     );                       
           
                         // This code is contributed by vt_m.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find nim-game winner                       
           
                                                 // function to find winner of NIM-game                       
                                                 function                                     findWinner(A, n)                       
                                                 {                       
                                                 let res = 0;                       
                                   
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 res ^= A[i];                       
                                   
                                                 // case when Alice is winner                       
                                                 if                                     (res == 0 || n % 2 == 0)                       
                                                 return                                     "Alice"                                     ;                       
                                   
                                                 // when Bob is winner                       
                                                 else                       
                                                 return                                     "Bob"                                     ;                       
                                                 }                       
           
           
                         // Driver Code                       
           
                                                 let A = [ 1, 4, 3, 5 ];                       
                                                 let n = A.length;                       
                                   
                                                 document.write(                                     "Winner = "                       
                                                 + findWinner(A, n));                       
                                   
                         </script>                       

输出：

Winner = Alice

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章