问题
null
这个问题是以反对罗马人的犹太历史学家弗拉维乌斯·约瑟夫命名的。根据约瑟夫斯的说法，他和他的犹太士兵被困在一个山洞里，被罗马人包围，他们选择在投降和俘虏中谋杀和自杀。他们决定所有的士兵都坐成一个圆圈，从坐在第一个位置的士兵开始，每个士兵都会按顺序杀死士兵。所以如果有5名士兵坐在一个圆圈里，位置编号为1，2，3，4，5。士兵1杀了2个，然后3杀了4个，然后5杀了1个，然后3杀了5个，因为3是唯一剩下的，所以3自杀了。 现在约瑟夫不想被谋杀或自杀。他宁愿被罗马人俘虏，也面临一个问题。他必须弄清楚自己应该在哪个位置坐成一个圆圈（前提是总共有n个人，坐在第一个位置的人有第一次杀人的机会），这样他才是最后一个站着的人，而不是自杀，他将向罗马人投降。
模式
如果你对不同的n值进行计算，你会发现一个模式。如果n是2的真幂，那么答案总是1。每n大于2的幂，答案就增加2。
| n士兵 | 2. A. +l | 幸存者W（n）=2l+1 |
|---|---|---|
| 1. | 1 + 0 | 2 * 0 + 1 = 1 |
| 2. | 2 + 0 | 2 * 0 + 1 = 1 |
| 3. | 2 + 1 | 2 * 1 + 1 = 3 |
| 4. | 4 + 0 | 2 * 0 + 1 = 1 |
| 5. | 4 + 1 | 2 * 1 + 1 = 3 |
| 6. | 4 + 2 | 2 * 2 + 1 = 5 |
| 7. | 4 + 3 | 2 * 3 + 1 = 7 |
| 8. | 8 + 0 | 2 * 0 + 1 = 1 |
| 9 | 8 + 1 | 2 * 1 + 1 = 3 |
| 10 | 8 + 2 | 2 * 2 + 1 = 5 |
| 11 | 8 + 3 | 2 * 3 + 1 = 7 |
| 12 | 8 + 4 | 2 * 4 + 1 = 9 |
现在，对于每n，约瑟夫的正确位置可以通过从数字中扣除最大可能的2次方得到答案（前提是n的值不是2的纯幂，否则答案是1）
N=2 A. +什么
式中a=最大可能功率
诀窍 每当有人谈论2的力量时，脑海中浮现的第一个词就是“二进制”。这个问题的解决方法在二进制中比在十进制中简单得多，也短得多。这其中有一个诀窍。因为我们需要在二进制中扣除最大可能的幂，所以这个数字是最高有效位。在最初的约瑟夫斯问题中，有40名士兵和约瑟夫斯一起，这使得 n=41 二进制中的.41是101001。如果我们把最左边的1移到最右边，我们得到010011，它是19（十进制），这就是答案。这适用于所有情况。这可以通过位操作轻松完成。
C++
// C++ program for josephus problem #include <bits/stdc++.h> using namespace std; // function to find the position of the Most // Significant Bit int msbPos( int n) { int pos = 0; while (n != 0) { pos++; // keeps shifting bits to the right // until we are left with 0 n = n >> 1; } return pos; } // function to return at which place Josephus // should sit to avoid being killed int josephify( int n) { /* Getting the position of the Most Significant Bit(MSB). The leftmost '1'. If the number is '41' then its binary is '101001'. So msbPos(41) = 6 */ int position = msbPos(n); /* 'j' stores the number with which to XOR the number 'n'. Since we need '100000' We will do 1<<6-1 to get '100000' */ int j = 1 << (position - 1); /* Toggling the Most Significant Bit. Changing the leftmost '1' to '0'. 101001 ^ 100000 = 001001 (9) */ n = n ^ j; /* Left-shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 (18) */ n = n << 1; /* Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place. 010010 | 1 = 010011 (19) */ n = n | 1; return n; } // hard coded driver main function to run the program int main() { int n = 41; cout <<josephify(n); return 0; } // This code is contributed by Mukul singh. |
C
// C program for josephus problem #include <stdio.h> // function to find the position of the Most // Significant Bit int msbPos( int n) { int pos = 0; while (n != 0) { pos++; // keeps shifting bits to the right // until we are left with 0 n = n >> 1; } return pos; } // function to return at which place Josephus // should sit to avoid being killed int josephify( int n) { /* Getting the position of the Most Significant Bit(MSB). The leftmost '1'. If the number is '41' then its binary is '101001'. So msbPos(41) = 6 */ int position = msbPos(n); /* 'j' stores the number with which to XOR the number 'n'. Since we need '100000' We will do 1<<6-1 to get '100000' */ int j = 1 << (position - 1); /* Toggling the Most Significant Bit. Changing the leftmost '1' to '0'. 101001 ^ 100000 = 001001 (9) */ n = n ^ j; /* Left-shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 (18) */ n = n << 1; /* Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place. 010010 | 1 = 010011 (19) */ n = n | 1; return n; } // hard coded driver main function to run the program int main() { int n = 41; printf ( "%d" , josephify(n)); return 0; } |
JAVA
// Java program for josephus problem public class GFG { // method to find the position of the Most // Significant Bit static int msbPos( int n) { int pos = 0 ; while (n != 0 ) { pos++; // keeps shifting bits to the right // until we are left with 0 n = n >> 1 ; } return pos; } // method to return at which place Josephus // should sit to avoid being killed static int josephify( int n) { /* Getting the position of the Most Significant Bit(MSB). The leftmost '1'. If the number is '41' then its binary is '101001'. So msbPos(41) = 6 */ int position = msbPos(n); /* 'j' stores the number with which to XOR the number 'n'. Since we need '100000' We will do 1<<6-1 to get '100000' */ int j = 1 << (position - 1 ); /* Toggling the Most Significant Bit. Changing the leftmost '1' to '0'. 101001 ^ 100000 = 001001 (9) */ n = n ^ j; /* Left-shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 (18) */ n = n << 1 ; /* Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place. 010010 | 1 = 010011 (19) */ n = n | 1 ; return n; } // Driver Method public static void main(String[] args) { int n = 41 ; System.out.println(josephify(n)); } } |
Python3
# Python3 program for josephus problem # Function to find the position # of the Most Significant Bit def msbPos(n): pos = 0 while n ! = 0 : pos + = 1 n = n >> 1 return pos # Function to return at which # place Josephus should sit to # avoid being killed def josephify(n): # Getting the position of the Most # Significant Bit(MSB). The leftmost '1'. # If the number is '41' then its binary # is '101001'. So msbPos(41) = 6 position = msbPos(n) # 'j' stores the number with which to XOR # the number 'n'. Since we need '100000' # We will do 1<<6-1 to get '100000' j = 1 << (position - 1 ) # Toggling the Most Significant Bit. # Changing the leftmost '1' to '0'. # 101001 ^ 100000 = 001001 (9) n = n ^ j # Left-shifting once to add an extra '0' # to the right end of the binary number # 001001 = 010010 (18) n = n << 1 # Toggling the '0' at the end to '1' # which is essentially the same as # putting the MSB at the rightmost # place. 010010 | 1 = 010011 (19) n = n | 1 return n # Driver Code n = 41 print (josephify(n)) # This code is contributed by Shreyanshi Arun. |
C#
// C# program for Josephus Problem using System; public class GFG { // Method to find the position // of the Most Significant Bit static int msbPos( int n) { int pos = 0; while (n != 0) { pos++; // keeps shifting bits to the right // until we are left with 0 n = n >> 1; } return pos; } // method to return at which place Josephus // should sit to avoid being killed static int josephify( int n) { // Getting the position of the Most Significant // Bit(MSB). The leftmost '1'. If the number is // '41' then its binary is '101001'. // So msbPos(41) = 6 int position = msbPos(n); // 'j' stores the number with which to XOR // the number 'n'. Since we need '100000' // We will do 1<<6-1 to get '100000' int j = 1 << (position - 1); // Toggling the Most Significant Bit. // Changing the leftmost '1' to '0'. // 101001 ^ 100000 = 001001 (9) n = n ^ j; // Left-shifting once to add an extra '0' // to the right end of the binary number // 001001 = 010010 (18) n = n << 1; // Toggling the '0' at the end to '1' which // is essentially the same as putting the // MSB at the rightmost place. 010010 | 1 // = 010011 (19) n = n | 1; return n; } // Driver code public static void Main() { int n = 41; Console.WriteLine(josephify(n)); } } // This code is contributed by vt_m . |
PHP
<?php // PHP program for josephus problem // function to find the position of // the Most Significant Bit function msbPos( $n ) { $pos = 0; while ( $n != 0) { $pos ++; // keeps shifting bits to the right // until we are left with 0 $n = $n >> 1; } return $pos ; } // function to return at which place Josephus // should sit to avoid being killed function josephify( $n ) { /* Getting the position of the Most Significant Bit(MSB). The leftmost '1'. If the number is '41' then its binary is '101001'. So msbPos(41) = 6 */ $position = msbPos( $n ); /* 'j' stores the number with which to XOR the number 'n'. Since we need '100000'. We will do 1<<6-1 to get '100000' */ $j = 1 << ( $position - 1); /* Toggling the Most Significant Bit. Changing the leftmost '1' to '0'. 101001 ^ 100000 = 001001 (9) */ $n = $n ^ $j ; /* Left-shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 (18) */ $n = $n << 1; /* Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place. 010010 | 1 = 010011 (19) */ $n = $n | 1; return $n ; } // Driver Code $n = 41; print (josephify( $n )); // This code is contributed by mits ?> |
Javascript
<script> // javascript program for josephus problem // method to find the position of the Most // Significant Bit function msbPos(n) { var pos = 0; while (n != 0) { pos++; // keeps shifting bits to the right // until we are left with 0 n = n >> 1; } return pos; } // method to return at which place Josephus // should sit to avoid being killed function josephify(n) { /* Getting the position of the Most Significant Bit(MSB). The leftmost '1'. If the number is '41' then its binary is '101001'. So msbPos(41) = 6 */ var position = msbPos(n); /* 'j' stores the number with which to XOR the number 'n'. Since we need '100000' We will do 1<<6-1 to get '100000' */ var j = 1 << (position - 1); /* Toggling the Most Significant Bit. Changing the leftmost '1' to '0'. 101001 ^ 100000 = 001001 (9) */ n = n ^ j; /* Left-shifting once to add an extra '0' to the right end of the binary number 001001 = 010010 (18) */ n = n << 1; /* Toggling the '0' at the end to '1' which is essentially the same as putting the MSB at the rightmost place. 010010 | 1 = 010011 (19) */ n = n | 1; return n; } // Driver Method var n = 41; document.write(josephify(n)); // This code is contributed by Amit Katiyar </script> |
输出：
19
以前关于同一主题的文章：
本文由 帕拉什尼甘酒店 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
