This Python program solves the Josephus Problem using a circular linked list. The Josephus Problem is a theoretical problem related to a certain counting-out game, where people stand in a circle, and every nth person is eliminated until only one person remains.
The Josephus Problem is a famous theoretical problem related to a certain elimination game. In this problem, a group of people stand in a circle, and at each step, a certain number of people are skipped and the next person is eliminated. This process continues until only one person remains. The challenge is to determine the position of the last remaining person.
Problem Statement
Given the total number of people in the circle and the number of people to be skipped in each step, write a Python program to find the position of the last remaining person in the circle.
Python Program to Solve Josephus Problem using Linked List
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
self.head.next = self.head
else:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = new_node
new_node.next = self.head
def remove_node(self, node):
if self.head == node:
temp = self.head
while temp.next != self.head:
temp = temp.next
temp.next = self.head.next
self.head = self.head.next
else:
temp = self.head
prev = None
while temp.next != self.head:
prev = temp
temp = temp.next
if temp == node:
prev.next = temp.next
break
def josephus(self, step):
temp = self.head
while len(self) > 1:
count = 1
while count < step:
temp = temp.next
count += 1
self.remove_node(temp)
temp = temp.next
def __len__(self):
count = 0
temp = self.head
while temp:
count += 1
temp = temp.next
if temp == self.head:
break
return count
def get_survivor(self):
return self.head.data
def solve_josephus(n, k):
cll = CircularLinkedList()
for i in range(1, n + 1):
cll.add_node(i)
cll.josephus(k)
return cll.get_survivor()
# Input
total_people = int(input("Enter the total number of people: "))
skip_count = int(input("Enter the number of people to be skipped: "))
# Output
survivor_position = solve_josephus(total_people, skip_count)
print(f"The survivor is at position: {survivor_position}")
How It Works
The program defines a Node class and a CircularLinkedList class to handle the circular linked list data structure. The josephus method simulates the elimination process according to the given step, and the solve_josephus function orchestrates the entire process and returns the position of the survivor.
Input/Output
