有n个人围成一圈等待处决。计数从圆圈中的某个点开始，沿着圆圈的固定方向进行。在每一步中，都会跳过一定数量的人，然后执行下一个人。清除过程围绕着圆圈进行（随着被处决的人被清除，圆圈变得越来越小），直到只剩下最后一个人，他才获得自由。给定总人数n和一个数字k，该数字表示跳过k-1人，并在圆圈中杀死第k人。任务是在最初的循环中选择一个地方，这样你就剩下最后一个，这样你就可以存活下来。（基于0的索引）。 例如：
null
Input : Length of circle : n = 4 Count to choose next : k = 2Output : 0Input : n = 5 k = 3Output : 3
我们已经讨论了这个问题的不同解决方案( 在这里 , 在这里 和 在这里 在本文中，胡先生讨论了一个使用列表容器的基于C++的STL解决方案，它使用循环列表的思想。
C++
// CPP program to find last man standing #include <bits/stdc++.h> using namespace std; int josephusCircle( int n, int k){ list< int >l; //creates a doubly linked list using stl container// for ( int i=0;i<n;i++) l.push_back(i); //pushes i to the end of the doubly linked list// auto it = l.begin(); while (l.size()>1){ for ( int i=1;i<k;i++){ it++; if (it==l.end()){ //if iterator reaches the end,then we change it to begin of the list// it = l.begin(); } } it = l.erase(it); if (it==l.end()){ //if iterator reaches the end,then we change it to begin of the list// it = l.begin(); } } return l.front(); //returns front element of the list// } /* Driver program to test above functions */ int main() { int n=14,k=2; cout<<josephusCircle(n,k)<< "" ; return 0; } |
JAVA
// Java Code to find the last man Standing public class GFG { // Node class to store data static class Node { public int data ; public Node next; public Node( int data ) { this .data = data; } } /* Function to find the only person left after one in every m-th node is killed in a circle of n nodes */ static void getJosephusPosition( int m, int n) { // Create a circular linked list of // size N. Node head = new Node( 1 ); Node prev = head; for ( int i = 2 ; i <= n; i++) { prev.next = new Node(i); prev = prev.next; } // Connect last node to first prev.next = head; /* while only one node is left in the linked list*/ Node ptr1 = head, ptr2 = head; while (ptr1.next != ptr1) { // Find m-th node int count = 1 ; while (count != m) { ptr2 = ptr1; ptr1 = ptr1.next; count++; } /* Remove the m-th node */ ptr2.next = ptr1.next; ptr1 = ptr2.next; } System.out.println ( "Last person left standing " + "(Josephus Position) is " + ptr1.data); } /* Driver program to test above functions */ public static void main(String args[]) { int n = 14 , m = 2 ; getJosephusPosition(m, n); } } |
Python3
# Python3 program to find last man standing # /* structure for a node in circular # linked list */ class Node: def __init__( self , x): self .data = x self . next = None # /* Function to find the only person left # after one in every m-th node is killed # in a circle of n nodes */ def getJosephusPosition(m, n): # Create a circular linked list of # size N. head = Node( 1 ) prev = head for i in range ( 2 , n + 1 ): prev. next = Node(i) prev = prev. next prev. next = head # Connect last #node to first #/* while only one node is left in the #linked list*/ ptr1 = head ptr2 = head while (ptr1. next ! = ptr1): # Find m-th node count = 1 while (count ! = m): ptr2 = ptr1 ptr1 = ptr1. next count + = 1 # /* Remove the m-th node */ ptr2. next = ptr1. next # free(ptr1) ptr1 = ptr2. next print ( "Last person left standing (Josephus Position) is " , ptr1.data) # /* Driver program to test above functions */ if __name__ = = '__main__' : n = 14 m = 2 getJosephusPosition(m, n) # This code is contributed by mohit kumar 29 |
C#
// C# Code to find the last man Standing using System; public class GFG { // Node class to store data class Node { public int data ; public Node next; public Node( int data ) { this .data = data; } } /* Function to find the only person left after one in every m-th node is killed in a circle of n nodes */ static void getJosephusPosition( int m, int n) { // Create a circular linked list of // size N. Node head = new Node(1); Node prev = head; for ( int i = 2; i <= n; i++) { prev.next = new Node(i); prev = prev.next; } // Connect last node to first prev.next = head; /* while only one node is left in the linked list*/ Node ptr1 = head, ptr2 = head; while (ptr1.next != ptr1) { // Find m-th node int count = 1; while (count != m) { ptr2 = ptr1; ptr1 = ptr1.next; count++; } /* Remove the m-th node */ ptr2.next = ptr1.next; ptr1 = ptr2.next; } Console.WriteLine ( "Last person left standing " + "(Josephus Position) is " + ptr1.data); } /* Driver program to test above functions */ static public void Main(String []args) { int n = 14, m = 2; getJosephusPosition(m, n); } } //contributed by Arnab Kundu |
Javascript
<script> // javascript Code to find the last man Standing // Node class to store data class Node { constructor(val) { this .data = val; this .next = null ; } } /* * Function to find the only person left after one in every m-th node is killed * in a circle of n nodes */ function getJosephusPosition(m , n) { // Create a circular linked list of // size N. var head = new Node(1); var prev = head; for (i = 2; i <= n; i++) { prev.next = new Node(i); prev = prev.next; } // Connect last node to first prev.next = head; /* * while only one node is left in the linked list */ var ptr1 = head, ptr2 = head; while (ptr1.next != ptr1) { // Find m-th node var count = 1; while (count != m) { ptr2 = ptr1; ptr1 = ptr1.next; count++; } /* Remove the m-th node */ ptr2.next = ptr1.next; ptr1 = ptr2.next; } document.write( "Last person left standing " + "(Josephus Position) is " + ptr1.data); } /* Driver program to test above functions */ var n = 14, m = 2; getJosephusPosition(m, n); // This code is contributed by umadevi9616 </script> |
输出
12
输出：
Last person left standing (Josephus Position) is 12 ( 0 based indexing )
时间复杂性： O（k*n） 本文的改进是 机械化 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
