谜题|球芽甘蓝游戏-yiteyi-C++库

给定n个位置和两名球员。玩家需要连接任意两个点而不与任何一条线相交，不能移动的玩家将失败。确定谁将赢得player1或player2。

null

例如：

Input : n = 2
Output : player 2

Input : n = 3
Output : player 1

说明： 图片[1]-谜题|球芽甘蓝游戏-yiteyi-C++库

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法： 这个游戏的赢家并不取决于玩家选择的动作，而是取决于n。这个问题可以通过使用欧拉特性 .

根据欧拉特征：对于每个曲面S，都存在一个整数 $\chi(S)$ 这样，每当一个带有V顶点和E边的图G嵌入到S中，从而有F个面（被图分割的区域），那么：

$V - E + F = \chi(S)$

对于平面图 $\chi(S) = 2$ .

考虑最后的图片（即最后一次移动后的情况）。图片[5]-谜题|球芽甘蓝游戏-yiteyi-C++库

使用欧拉特征的解决方法： 1.在最后一张图片中，我们可以将每个交叉点作为一个顶点。 2.连接这些交叉点的每条线可被视为一条边和一条线 3.每个区域（包括外部区域）都可以被视为图形的一个面。

设，特定n的可能移动次数为m。要解决这个问题，必须找到m的值。

观察： 1.最初有n个交叉点（即n个顶点）。每一步创造一个新的十字架。因此，最终将有总V=（n+m）交叉点（顶点）。 2.在每一步中，当玩家用一条线连接两个自由端，并在该线中做一个新的十字（创建一个新的顶点），下一个玩家将用两条新边连接三个顶点（旧的2，新的1）。因此，在m次移动之后，图中会有E=2*m条边。 3.可以看出，每个面内只有一个自由端。因此，面数等于自由端的总数。同样，在每一步中，玩家连接两个自由端（失去两个自由端）并创建两个新的自由端（通过创建一个新的交叉点）。因此，自由端的总数保持不变。所以，自由端的总数最初=面数，F=4*n。

现在，它可以写成：V–E+F=2 i、 e.（n+m）–2*m+4*n=2。解这个方程，m=（5*n–2）

现在，如果m是奇数，玩家1将获胜，如果m是偶数，玩家2将获胜。

C++

                         // C++ code to find out winner                       
                         // of Brussels Sprouts game.                       
                         #include <iostream>                       
                         using                                     namespace                                     std;                       
                                   
                         // Function to find out winner of                       
                         // the game.                       
                         void                                     winner(                                     int                                     n)                       
                         {                       
                                   
                                                 // Total number of moves m.                       
                                                 int                                     m = 5 * n - 2;                       
                                   
                                                 // If m is odd Player 1 is winner                       
                                                 // If m is even Player 2 is winner.                       
                                                 if                                     (m % 2 == 1)                       
                                                 cout <<                                     "Player 1"                                     << endl;                       
                                                 else                       
                                                 cout <<                                     "Player 2"                                     << endl;                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 // Test case 1                       
                                                 int                                     n1 = 2;                       
                                                 winner(n1);                       
                                   
                                                 // Test case 2                       
                                                 int                                     n2 = 3;                       
                                                 winner(n2);                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to find out winner                       
                         // of Brussels Sprouts game.                       
                                   
                         import                                     java.io.*;                       
                                   
                         class                                     GFG {                       
                                   
                                                 // Function to find out winner of                       
                                                 // the game.                       
                                                 static                                     void                                     winner(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // Total number of moves m.                       
                                                 int                                     m =                                     5                                     * n -                                     2                                     ;                       
                                   
                                                 // If m is odd Player 1 is winner                       
                                                 // If m is even Player 2 is winner.                       
                                                 if                                     (m %                                     2                                     ==                                     1                                     )                       
                                                 System.out.println(                                     "Player 1"                                     );                       
                                                 else                       
                                                 System.out.println(                                     "Player 2"                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                   
                                                 // Test case 1                       
                                                 int                                     n1 =                                     2                                     ;                       
                                                 winner(n1);                       
                                   
                                                 // Test case 2                       
                                                 int                                     n2 =                                     3                                     ;                       
                                                 winner(n2);                       
                                                 }                       
                         }                       
                                   
                         // This code is contributed by vt_m.                       

输出：

Player 2
Player 1

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

THE END

技术文章