100个人站成一个圆圈，顺序是1到100。1号有一把剑。他杀死下一个人（即2号），并将剑交给下一个人（即3号）。所有人都这么做，直到只有一个人活下来。最后还有多少人幸存？ 从1到100有100人。 解决方案：第73条 人终将活下来
null
解释1（直观和逻辑）： 我们可以观察到，如果站在一个圆圈里的人数是2的幂，那么开始游戏的人就会活着。这是因为在每一轮杀戮之后，剩下的人数将减少2人，并且没有剩余的人，因此，下一轮将再次从最初开始游戏的同一个人开始。这将继续下去。
对于循环中的人数不是2的幂的情况，那么在第一轮中，当活着的人数变成2的幂时，持枪的人会赢，因为基本上，他是在开始一场游戏，剩下的人是2的幂。因此，对于100人来说，当64人仍然存在时，36人需要死亡，也就是说，一个比给定数字小的数字和2的幂。第36名被杀者将是第72名，因此，当活着的人数为64人时，第73名将拥有枪支。
说明2（代码）： 在这里，我们可以定义一个包含100个元素的数组，其值从1到100。
- 1号有一把剑。他杀死下一个人（即2号），并将剑交给下一个人（即3号）。 我们把数组元素作为一个人。第一个人杀死下一个人。所以，从1开始，我们将删除下一个元素，即2。
- 然后第一个人把剑交给下一个人，即3。那个人也会杀死下一个人，这一点会继续下去。也就是说，在数组中，我们需要从1开始，每隔100个元素移除一个元素。（所有偶数将被删除，我们将只剩下数组中的奇数）。
第一轮： 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99 第二轮： 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77, 81, 85, 89, 93, 97 第三轮： 1, 9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97 第四轮： 9, 25, 41, 57, 73, 89 第五轮： 9, 41, 73 第六轮： 9, 73 第七轮： 73
为避免上述手动计算，以下是通用算法： 第一步： 对于给定的N值，求出“2的幂”立即大于N。我们称之为P 第二步： 从（P-1）中减去N。我们把它叫做M，也就是说，M=（P-1）-N 第三步： 把M乘以2。i、 e M*2 第4步： 从P-1中减去M*2。我们称之为ans，即ans=（P-1）–（M*2） 所以，编号为“ans”的人会活到最后。
代码：
C++
#include <bits/stdc++.h> using namespace std; int main() { int person = 100; // Placeholder array for person vector< int > a(person); // Assign placeholders from 1 to N (total person) for ( int i = 0; i < person; i++) { a[i] = i + 1; } // Will start the game from 1st person (Which is at // placeholder 0) int pos = 0; // Game will be continued till we end up with only one // person left while (a.size() > 1) { // Current person will shoot the person next to // him/her. So incrementing the position. pos++; // As person are standing in circular manner, for // person at last place has right neighbour at // placeholder 0. So we are taking modulo to make it // circular pos %= a.size(); // Killing the person at placeholder 'pos' // To do that we simply remove that element a.erase(a.begin() + pos); // There is no need to increment the pos again to // pass the gun Because by erasing the element at // 'pos', now next person will be at 'pos'. } // Print Person that survive the game cout << a[0]; return 0; } |
JAVA
// Java program for the above approach import java.io.*; import java.util.Arrays; class GFG { // Driver code public static void main (String[] args) { int person = 100 ; // Placeholder array for person int [] a = new int [person]; // Assign placeholders from 1 to N (total person) for ( int i = 0 ; i < person; i++) { a[i] = i + 1 ; } // Will start the game from 1st person (Which is at // placeholder 0) int pos = 0 ; // Game will be continued till we end up with only one // person left while (a.length > 1 ) { // Current person will shoot the person next to // him/her. So incrementing the position. pos++; // As person are standing in circular manner, for // person at last place has right neighbour at // placeholder 0. So we are taking modulo to make it // circular pos %= a.length; // Killing the person at placeholder 'pos' // To do that we simply remove that element int [] anotherArray = new int [a.length - 1 ]; System.arraycopy(a, 0 , anotherArray, 0 , pos); System.arraycopy(a, pos + 1 , anotherArray, pos,a.length - pos - 1 ); a = anotherArray; // There is no need to increment the pos again to // pass the gun Because by erasing the element at // 'pos', now next person will be at 'pos'. } // Print Person that survive the game System.out.println(a[ 0 ]); } } // This Code is contributed by ShubhamSingh10 |
Python3
person = 100 # Placeholder array for person a = [ 0 ] * person # Assign placeholders from 1 to N (total person) for i in range (person): a[i] = i + 1 # Will start the game from 1st person (Which # is at placeholder 0) pos = 0 # Game will be continued till we end up with # only one person left while ( len (a) > 1 ): # Current person will shoot the person next # to him/her. So incrementing the position. pos + = 1 # As person are standing in circular manner, # for person at last place has right neighbour # at placeholder 0. So we are taking modulo # to make it circular pos % = len (a) # Killing the person at placeholder 'pos' # To do that we simply remove that element del a[pos] # There is no need to increment the pos again to # pass the gun Because by erasing the element at # 'pos', now next person will be at 'pos'. # Driver code # PrPerson that survive the game print (a[ 0 ]) # This code is contributed by ShubhamSingh10 |
C#
// C# program for the above approach using System; using System.Linq; public static class GFG { // Driver code static public void Main () { int person = 100; // Placeholder array for person int [] a = new int [person]; // Assign placeholders from 1 to N (total person) for ( int i = 0; i < person; i++) { a[i] = i + 1; } // Will start the game from 1st person (Which is at // placeholder 0) int pos = 0; // Game will be continued till we end up with only one // person left while (a.Length > 1) { // Current person will shoot the person next to // him/her. So incrementing the position. pos++; // As person are standing in circular manner, for // person at last place has right neighbour at // placeholder 0. So we are taking modulo to make it // circular pos %= a.Length; // Killing the person at placeholder 'pos' // To do that we simply remove that element a = a.Where((source, index) =>index != pos).ToArray(); // There is no need to increment the pos again to // pass the gun Because by erasing the element at // 'pos', now next person will be at 'pos'. } // Print Person that survive the game Console.Write(a[0]); } } // This Code is contributed by ShubhamSingh10 |
Javascript
<script> var person = 100; // Placeholder array for person var a = new Array(person); // Assign placeholders from 1 to N (total person) for ( var i = 0; i < person; i++) { a[i] = i + 1; } // Will start the game from 1st person (Which is at // placeholder 0) var pos = 0; // Game will be continued till we end up with only one // person left while (a.length > 1) { // Current person will shoot the person next to // him/her. So incrementing the position. pos++; // As person are standing in circular manner, for // person at last place has right neighbour at // placeholder 0. So we are taking modulo to make it // circular pos = pos% (a.length); // Killing the person at placeholder 'pos' // To do that we simply remove that element a.splice(pos,1) // There is no need to increment the pos again to // pass the gun Because by erasing the element at // 'pos', now next person will be at 'pos'. } // Print Person that survive the game document.write(a[0]); // This code is contributed by ShubhamSingh10 </script> |
输出
73
这个谜题是由 乔蒂 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
