جلسه ۹۷: مسئله 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 های حلقوی و مسائلی که در مورد انها وجود دارد، آشنا شده‌اید. برای ارزیابی دانش خودتان کوییز بعدی را امتحان کنید.