约瑟夫问题|集2（k=2时的简单解）-yiteyi-C++库

有n个人围成一圈等待处决。计数从圆圈中的某个点开始，沿着圆圈的固定方向进行。在每一步中，都会跳过一定数量的人，然后执行下一个人。清除过程围绕着圆圈进行（随着被处决的人被清除，圆圈变得越来越小），直到只剩下最后一个人，他才获得自由。给定总人数n和一个数字k，该数字表示跳过k-1人，循环中第k人被杀。任务是在最初的循环中选择一个地方，这样你就剩下最后一个，这样你就可以存活下来。我们在下面的集合1中讨论了一个广义解。 Josephus问题|集1（O（n）解）在这篇文章中，我们将讨论一个特殊的案例 k=2

null

例如：

Input  : n = 5Output : The person at position 3 survivesExplanation : Firstly, the person at position 2 is killed, then at 4, then at 1 is killed. Finally, the person at position 5 is killed. So the person at position 3 survives.Input  : n = 14Output : The person at position 13 survives

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

以下是一些有趣的事实。

在第一轮中，所有处于同一位置的人都被杀。
第二轮出现两个案例
1. 如果n是偶数： 例如n=8。在第一轮中，前两名被杀，然后是4名，然后是6名，然后是8名。在第二轮比赛中，我们在第一、第二、第三和第四的位置分别有1、3、5和7。
2. 如果n是奇数： 例如n=7。在第一轮中，前两名被杀，然后是4名，然后是6名。在第二轮比赛中，我们在第一、第二和第三位分别有3、5、7位。

如果n是即使一个人在本轮比赛中处于x位，然后他在上一轮比赛中处于2x-1位。如果n是 古怪的 一个人在本轮中处于x位置，然后他在上一轮中处于2x+1位置。根据以上事实，我们可以递归地定义寻找幸存者位置的公式。

Let f(n) be position of survivor for input n, the value of f(n) can be recursively written as below.If n is even   f(n) = 2f(n/2) - 1Else   f(n) = 2f((n-1)/2) + 1

解决上述问题的方法是

f(n) = 2(n - 2^floor(Log_²ⁿ⁾ + 1     = 2n - 2^{1 + floor(Log}_²ⁿ⁾ + 1

下面是查找上述公式值的实现。

C++

                         // C/C++ program to find solution of Josephus                       
                         // problem when size of step is 2.                       
                         #include <stdio.h>                       
           
                         // Returns position of survivor among a circle                       
                         // of n persons and every second person being                       
                         // killed                       
                         int                                     josephus(                                     int                                     n)                       
                         {                       
                                                 // Find value of 2 ^ (1 + floor(Log n))                       
                                                 // which is a power of 2 whose value                       
                                                 // is just above n.                       
                                                 int                                     p = 1;                       
                                                 while                                     (p <= n)                       
                                                 p *= 2;                       
           
                                                 // Return 2n - 2^(1+floor(Logn)) + 1                       
                                                 return                                     (2 * n) - p + 1;                       
                         }                       
           
                         // Driver Program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 16;                       
                                                 printf                                     (                                     "The chosen place is %d"                                     , josephus(n));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find solution of Josephus                       
                         // problem when size of step is 2.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // Returns position of survivor among                       
                                                 // a circle of n persons and every                       
                                                 // second person being killed                       
                                                 static                                     int                                     josephus(                                     int                                     n)                       
                                                 {                       
           
                                                 // Find value of 2 ^ (1 + floor(Log n))                       
                                                 // which is a power of 2 whose value                       
                                                 // is just above n.                       
                                                 int                                     p =                                     1                                     ;                       
                                                 while                                     (p <= n)                       
                                                 p *=                                     2                                     ;                       
           
                                                 // Return 2n - 2^(1+floor(Logn)) + 1                       
                                                 return                                     (                                     2                                     * n) - p +                                     1                                     ;                       
                                                 }                       
           
                                                 // Driver Program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     16                                     ;                       
           
                                                 System.out.println(                                     "The chosen place is "                       
                                                 + josephus(n));                       
                                                 }                       
                         }                       
           
                         // This Code is Contributed by Anuj_67                       

Python3

                         # Python3 program to find solution of                       
                         # Josephus problem when size of step is 2.                       
           
                         # Returns position of survivor among a                       
                         # circle of n persons and every second                       
                         # person being killed                       
                         def                                     josephus(n):                       
                                   
                                                 # Find value of 2 ^ (1 + floor(Log n))                       
                                                 # which is a power of 2 whose value                       
                                                 # is just above n.                       
                                                 p                                     =                                     1                       
                                                 while                                     p <                                     =                                     n:                       
                                                 p                                     *                                     =                                     2                       
           
                                                 # Return 2n - 2^(1 + floor(Logn)) + 1                       
                                                 return                                     (                                     2                                     *                                     n)                                     -                                     p                                     +                                     1                       
           
                         # Driver Code                       
                         n                                     =                                     16                       
                         print                                     (                                     "The chosen place is"                                     , josephus(n))                       
           
                         # This code is contributed by Shreyanshi Arun.                       

C#

                         // C# program to find solution of Josephus                       
                         // problem when size of step is 2.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Returns position of survivor among                       
                                                 // a circle of n persons and every                       
                                                 // second person being killed                       
                                                 static                                     int                                     josephus(                                     int                                     n)                       
                                                 {                       
           
                                                 // Find value of 2 ^ (1 + floor(Log n))                       
                                                 // which is a power of 2 whose value                       
                                                 // is just above n.                       
                                                 int                                     p = 1;                       
                                                 while                                     (p <= n)                       
                                                 p *= 2;                       
           
                                                 // Return 2n - 2^(1+floor(Logn)) + 1                       
                                                 return                                     (2 * n) - p + 1;                       
                                                 }                       
           
                                                 // Driver Program to test above function                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 16;                       
           
                                                 Console.Write(                                     "The chosen place is "                       
                                                 + josephus(n));                       
                                                 }                       
                         }                       
           
                         // This Code is Contributed by Anuj_67                       

PHP

                         <?php                       
                         // PHP program to find solution                       
                         // of Josephus problem when                       
                         // size of step is 2.                       
           
                         // Returns position of survivor                       
                         // among a circle of n persons                       
                         // and every second person being                       
                         // killed                       
                         function                                     josephus(                                     $n                                     )                       
                         {                       
                                                 // Find value of 2 ^ (1 + floor(Log n))                       
                                                 // which is a power of 2 whose value                       
                                                 // is just above n.                       
                                                 $p                                     = 1;                       
                                                 while                                     (                                     $p                                     <=                                     $n                                     )                       
                                                 $p                                     *= 2;                       
           
                                                 // Return 2n - 2^(1+floor(Logn)) + 1                       
                                                 return                                     (2 *                                     $n                                     ) -                                     $p                                     + 1;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 16;                       
                         echo                                     "The chosen place is "                                     , josephus(                                     $n                                     );                       
           
                         // This code is contributed by ajit.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find solution of Josephus                       
                         // problem when size of step is 2.                       
           
                         // Returns position of survivor among                       
                         // a circle of n persons and every                       
                         // second person being killed                       
                         function                                     josephus(n)                       
                         {                       
                                   
                                                 // Find value of 2 ^ (1 + floor(Log n))                       
                                                 // which is a power of 2 whose value                       
                                                 // is just above n.                       
                                                 let p = 1;                       
                                   
                                                 while                                     (p <= n)                       
                                                 p *= 2;                       
           
                                                 // Return 2n - 2^(1+floor(Logn)) + 1                       
                                                 return                                     (2 * n) - p + 1;                       
                         }                       
           
                         // Driver code                       
                         let n = 16;                       
           
                         document.write(                                     "The chosen place is "                                     +                       
                                                 josephus(n));                       
                                   
                         // This code is contributed by susmitakundugoaldanga                       
           
                         </script>                       

输出：

The chosen place is 1

上述解的时间复杂度为O（logn）。本文由 分析师拉胡尔贾殷 .

另一个有趣的解决方案是，当k=2时，可以根据观察结果给出，我们只需左旋转N的二进制表示就可以得到所需的答案。工作代码考虑到数字为64位数字，下面也提供了相同的信息。

以下是上述方法的实施情况：

C++

                         // C++ program to find solution of Josephus                       
                         // problem when size of step is 2.                       
                         #include <bits/stdc++.h>                       
           
                         using                                     namespace                                     std;                       
           
                         // Returns position of survivor among a circle                       
                         // of n persons and every second person being                       
                         // killed                       
                         int                                     josephus(                                     int                                     n)                       
                         {                       
                                                 // An interesting observation is that                       
                                                 // for every number of power of two                       
                                                 // answer is 1 always.                       
                                                 if                                     (!(n & (n - 1)) && n) {                       
                                                 return                                     1;                       
                                                 }                       
           
                                                 // The trick is just to right rotate the                       
                                                 // binary representation of n once.                       
                                                 // Find whether the number shed off                       
                                                 // during left shift is set or not                       
           
                                                 bitset<64> Arr(n);                       
           
                                                 // shifting the bitset Arr                       
                                                 // f will become true once leftmost                       
                                                 // set bit is found                       
                                                 bool                                     f =                                     false                                     ;                       
                                                 for                                     (                                     int                                     i = 63; i >= 0; --i) {                       
                                                 if                                     (Arr[i] == 1 && !f) {                       
                                                 f =                                     true                                     ;                       
                                                 Arr[i] = Arr[i - 1];                       
                                                 }                       
                                                 if                                     (f) {                       
           
                                                 // shifting bits                       
                                                 Arr[i] = Arr[i - 1];                       
                                                 }                       
                                                 }                       
           
                                                 Arr[0] = 1;                       
           
                                                 int                                     res;                       
           
                                                 // changing bitset to int                       
                                                 res = (                                     int                                     )(Arr.to_ulong());                       
                                                 return                                     res;                       
                         }                       
           
                         // Driver Program to test above function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 16;                       
                                                 printf                                     (                                     "The chosen place is %d"                                     , josephus(n));                       
                                                 return                                     0;                       
                         }                       

Python3

                         # Python 3 program to find solution of Josephus                       
                         # problem when size of step is 2.                       
           
           
                         # Returns position of survivor among a circle                       
                         # of n persons and every second person being                       
                         # killed                       
                         def                                     josephus(n):                       
                                                 # An interesting observation is that                       
                                                 # for every number of power of two                       
                                                 # answer is 1 always.                       
                                                 if                                     (~(n & (n                                     -                                     1                                     ))                                     and                                     n) :                       
                                                 return                                     1                       
                                   
           
                                                 # The trick is just to right rotate the                       
                                                 # binary representation of n once.                       
                                                 # Find whether the number shed off                       
                                                 # during left shift is set or not                       
           
                                                 Arr                                     =                                     list                                     (                                     map                                     (                                     lambda                                     x:                                     int                                     (x),                                     list                                     (                                     bin                                     (n)[                                     2                                     :])))                       
                                                 Arr                                     =                                     [                                     0                                     ]                                     *                                     (                                     64                                     -                                     len                                     (Arr))                                     +                                     Arr                       
           
                                                 # shifting the bitset Arr                       
                                                 # f will become true once leftmost                       
                                                 # set bit is found                       
                                                 f                                     =                                     False                       
                                                 for                                     i                                     in                                     range                                     (                                     63                                     ,                                     -                                     1                                     ,                                     -                                     1                                     ) :                       
                                                 if                                     (Arr[i]                                     =                                     =                                     1                                     and                                     not                                     f) :                       
                                                 f                                     =                                     True                       
                                                 Arr[i]                                     =                                     Arr[i                                     -                                     1                                     ]                       
                                   
                                                 if                                     (f) :                       
           
                                                 # shifting bits                       
                                                 Arr[i]                                     =                                     Arr[i                                     -                                     1                                     ]                       
                                   
                                   
           
                                                 Arr[                                     0                                     ]                                     =                                     1                       
           
                                                 # changing bitset to int                       
                                                 res                                     =                                     int                                     (''.join(Arr),                                     2                                     )                       
                                                 return                                     res                       
           
           
                         # Driver Program to test above function                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     16                       
                                                 print                                     (                                     "The chosen place is"                                     , josephus(n))                       

输出：

The chosen place is 1

时间复杂性： O（对数（n）） 辅助空间： O（对数（n））这个想法是由 阿努库尔·钱德 . 如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

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

THE END

技术文章