Advertisement
Python253

josephus_problem

May 23rd, 2024
540
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.87 KB | None | 0 0
  1. #!/usr/bin/env python
  2. # -*- coding: utf-8 -*-
  3. # Filename: josephus_problem.py
  4. # Version: 1.0.0
  5. # Author: Jeoi Reqi
  6.  
  7. """
  8.  
  9. Description:
  10.    - This script simulates the Josephus problem, where a group of people
  11.      stand in a circle and are sequentially eliminated based on a fixed counting
  12.      rule until only one person remains.
  13.  
  14. Requirements:
  15.    - Python 3.x
  16.  
  17. Functions:
  18.    - find_last_person(n):
  19.        Simulates the elimination process in the Josephus problem and returns
  20.        the index of the last remaining person.
  21.    
  22. Usage:
  23.    - Run the script and input the number of people when prompted. The script
  24.      will then find and print the index of the last remaining person. To exit,
  25.      type '0' when prompted for input.
  26.  
  27. Additional Notes:
  28.    - The Josephus problem has a mathematical solution, but this script
  29.      simulates the elimination process for demonstration purposes.
  30.  
  31. """
  32.  
  33. def find_last_person(n):
  34.     """
  35.    Simulates the elimination process in the Josephus problem and returns
  36.    the index of the last remaining person.
  37.    
  38.    Args:
  39.        n (int): The number of people in the circle.
  40.        
  41.    Returns:
  42.        int: The index of the last remaining person.
  43.    """
  44.     circle = list(range(1, n + 1))  # Represent the circle of people with indices starting from 1
  45.     p = 0  # Pointer to the current person
  46.  
  47.     # Simulating the elimination process
  48.     while len(circle) > 1:
  49.         # Each person counts twice per round
  50.         p = (p + 2) % len(circle)
  51.         # Eliminate the person at the current index
  52.         circle.pop(p - 1 if p > 0 else len(circle) - 1)
  53.         # Adjust pointer if needed
  54.         p = p - 1 if p > 0 else len(circle)
  55.  
  56.     # Return the index of the last remaining person
  57.     return circle[0]
  58.  
  59. def main():
  60.     """
  61.    Main function to interact with the user and find the last remaining person.
  62.    """
  63.     while True:
  64.         print("""
  65.      _                           _                
  66.     | |                         | |                
  67.     | |  ___   ___   ___  _ __  | |__   _   _  ___
  68. _   | | / _ \ / __| / _ \| '_ \ | '_ \ | | | |/ __|
  69. | |__| || (_) |\__ \|  __/| |_) || | | || |_| |\__ \\
  70. \____/  \___/ |___/ \___|| .__/ |_| |_| \__,_||___/
  71.                          | |                      
  72.                          |_|
  73. """)
  74.         # Input the number of people
  75.         n = input("\nEnter the number of people (or type '0' to exit): ")
  76.        
  77.         if n == '0':
  78.             print("\nExiting Program... GoodBye!\n")
  79.             break
  80.        
  81.         n = int(n)
  82.        
  83.         # Find and print the index of the last remaining person
  84.         print("\nThe index of the last remaining person is:", find_last_person(n))
  85.        
  86.         # Prompt the user to hit enter to continue
  87.         input("\nPress Enter to continue...")
  88.  
  89. if __name__ == "__main__":
  90.     main()
  91.  
  92.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement