پایتون
جلسه ۹۷: مسئله Josephus در پایتون

در این درس شما یاد خواهید گرفت که چگونه مسئله
Josephus
را در پایتون به کمک linked list
های حلقوی پیادهسازی کنید.مقدمه
کودکان برخی اوقات یک بازی شمارش معکوس انجام میدهند تا با خواندن یک شعر، به طور تصادفی یک نفر را از گروه انتخاب کنند. هدف انتخاب یک فرد است، چه به عنوان یک فرد برنده و چه به عنوان یک فردی که از بازی حذف بشود.مسئلهJosephus
به این مفاهیم مربوط است. در این مسئله، مردم دور یک دایره ایستادهاند و منتظر هستند. نکات این مسئله به صورت زیر است:- شمارش معکوس از یک نقطه مشخص در یک دایره آغاز میشود و دور دایره در یک جهت ثابت ادامه پیدا میکند.
- در هر مرحله تعداد مشخصی از افراد به ترتیب رد میشوند و نفر بعدی خارج میگردد.
n
نفر داشته باشیم، و تعداد k-1
نفر در هر زمان عبور داده میشوند. این یعنی اینکه نفر k
ام حذف میگردد. درنتیجه k
همان step-size
است.اکنون با یک مثال مسئله Josephus
را با تصاویر زیر نشان میدهیم:
بعد از اینکه به تصویر بالا نگاه کردید، شما احتمالا با مفهوم مسئله Josephus
آشنا شدهاید. برای این درس، ما باید نودها را در linked list
یکی یکی بشماریم، البته بر اساس step-size
تا اینکه فقط به یک نود برسیم. برای حل این مسئله، از متد remove
که در درس های قبلی یادگرفتهایم، استفاده میکنیم. ورودی این متد را همان نود مدنظر قرار میدهیم. برای اینکه در این کار گیج نشوید، کدهای remove
را کپی کرده و آن ها را در یک متد جدید به نام remove_node
قرار میدهیم ومقداری آن را نیز تغییر میدهیم.مکان هایی که تغییر پیدا کرده اند بدین صورت هستند:عبارت if self.head.data == key:
به عبارت زیر تبدیل شده است:if self.head == node:
و عبارتif cur.data == key:
به عبارت زیر تبدیل شده است: if cur == node:
همانطور که میبینید، در عوض اینکه دیتای node
ها مقایسه بشود، کل خود نود مقایسه میگردد.در کد زیر هم، در خطوط مشخص شده، تغییرات اعمال شده است:def remove_node(self, node):
if self.head == node:
cur = self.head
while cur.next != self.head:
cur = cur.next
if self.head == self.head.next:
self.head = None
else:
cur.next = self.head.next
self.head = self.head.next
else:
cur = self.head
prev = None
while cur.next != self.head:
prev = cur
cur = cur.next
if cur == node:
prev.next = cur.next
cur = cur.next
پیادهسازی
اکنون کارمان در مورد متدremove_node
به اتمام رسیدهاست. در ادامه به راه حل مسئله Josephus
میپردازیم:def josephus_circle(self, step):
cur = self.head
length = len(self)
while length > 1:
count = 1
while count != step:
cur = cur.next
count += 1
print("KILL:" + str(cur.data))
self.remove_node(cur)
cur = cur.next
length -= 1
توضیحات
در متدJosephus_circle
یکی از آرگومان ها step
است. در خط ۲، ما مقدار cur
را self.head
و یک حلقه while
در خط ۵ تعریف کردهایم که تا زمانی که، مقدار طول linked list
یک بشود این حلقه اجرا میشود. مقدار متغیر count
را هم ۱ قرار دادهایم(خط ۶). بعد ما نیاز به یک حلقه تودرتو while
دیگر در خط ۷ نیاز داریم که تا وقتی مقدار count
برابر step
نباشد ادامه پیدا میکند. در while
دوم ما، نود به نود بر اساس آپدیت کردن مقدار cur
به cur.next
درخط هشت، حرکت میکنیم. در هر تکرار این حلقه یکی به مقدار count
اضافه میکنیم. در زمانی که مقدار count
برابر step
بشود، حلقه while
دوم، به اتمام میرسد و برنامه به خط شماره ۱۰ میرود. در خط ۱۰ نودی که در آن قرار داریم را پرینت میکنیم که با این کار میتوانید متوجه بشوید که کدام نود ها حذف میشوند. در خط بعدی نود cur
را که حلقه، روی آن متوقف شده است را حذف میکنیم. در خط ۱۲، مقدار cur
را به cur.next
نسبت میدهیم تا این عملیات دوباره ادامه پیدا کند، البته تا زمانی که فقط یک نود باقی بماند. که در در اینصورت حلقه while
به کمک دستور break
به اتمام میرسد.بله، راه حل به سادگیای بود که ملاحظه کردید. شما میتوانید کد های زیر را ببینید تا بیشتر متوجه این راه حل بشوید. این کدها شامل همه کدهایی است که در این بخش ما یاد گرفتهایم.class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def prepend(self, data):
new_node = Node(data)
cur = self.head
new_node.next = self.head
if not self.head:
new_node.next = new_node
else:
while cur.next != self.head:
cur = cur.next
cur.next = new_node
self.head = new_node
def append(self, data):
if not self.head:
self.head = Node(data)
self.head.next = self.head
else:
new_node = Node(data)
cur = self.head
while cur.next != self.head:
cur = cur.next
cur.next = new_node
new_node.next = self.head
def print_list(self):
cur = self.head
while cur:
print(cur.data)
cur = cur.next
if cur == self.head:
break
def __len__(self):
cur = self.head
count = 0
while cur:
count += 1
cur = cur.next
if cur == self.head:
break
return count
def split_list(self):
size = len(self)
if size == 0:
return None
if size == 1:
return self.head
mid = size//2
count = 0
prev = None
cur = self.head
while cur and count < mid: count += 1 prev = cur cur = cur.next prev.next = self.head split_cllist = CircularLinkedList() while cur.next != self.head: split_cllist.append(cur.data) cur = cur.next split_cllist.append(cur.data) self.print_list() print("\n") split_cllist.print_list() def remove(self, key): if self.head: if self.head.data == key: cur = self.head while cur.next != self.head: cur = cur.next if self.head == self.head.next: self.head = None else: cur.next = self.head.next self.head = self.head.next else: cur = self.head prev = None while cur.next != self.head: prev = cur cur = cur.next if cur.data == key: prev.next = cur.next cur = cur.next def remove_node(self, node): if self.head: if self.head == node: cur = self.head while cur.next != self.head: cur = cur.next if self.head == self.head.next: self.head = None else: cur.next = self.head.next self.head = self.head.next else: cur = self.head prev = None while cur.next != self.head: prev = cur cur = cur.next if cur == node: prev.next = cur.next cur = cur.next def josephus_circle(self, step): cur = self.head length = len(self) while length > 1:
count = 1
while count != step:
cur = cur.next
count += 1
print("KILL:" + str(cur.data))
self.remove_node(cur)
cur = cur.next
length -= 1
cllist = CircularLinkedList()
cllist.append(1)
cllist.append(2)
cllist.append(3)
cllist.append(4)
cllist.josephus_circle(2)
cllist.print_list()
اکنون، شما با linked list
های حلقوی و مسائلی که در مورد انها وجود دارد، آشنا شدهاید. برای ارزیابی دانش خودتان کوییز بعدی را امتحان کنید.