سلام. یادم میاد که تو صف نون لواش بودم و ماشا الله حسابی شلوغ بود و فکر کنم حدود ۲۰ نفر تو صف بودن آفتاب هم که کوتاه نمیومد که دقیقا رو من نشونه رفته بود. همه چیز به خوبی پیش می رفت که ناگهان یک نفر از صف بدون هماهنگی خارج شد و اینجوری بود که شاهد صحنه ی درگیری تن به تن افراد بودم روی حق تقدم نون لواش! حقم داشتن بنده خدا ها! زمان لازم برای آماده سازی و پخت یک قرص نان لواش اونم با دستگاه های تماما اتوماتیک حدود ۶ ثانیه هست که در تعداد بالا فاجعه هست و زمان انتظار گاها به ساعت ها میرسه.
خلاصه اینکه داشتم به این فکر میکردم که چطور میشه به این معظل فائق اومد؟ بدون اینکه صف به هم بریزه؟
توی خونه مسئله رو اینطوری طرح کردم(حتما بعضیا میگن دوباره شروع کرد!):
فرض کنین ۹ نفر انسان خوشحال که هرکدوم به ترتیب از ۱ تا ۹ شماره بندی شدن توی صف هستن (صف نون لواش، سبزی!، مرغ!!، ...) که ناگهان یک نفر از صف خارج میشه و ترتیب شماره ها به هم میخوره (درصورتی که افراد رندوم بیشتر در صف های طولانی تر از صف خارج بشن مشکل بزرگ تر میشه) حالا بر اثر سوء تفاهمات بسیار برای مرتب کردن صف قرار نیست که اعلام جنگ کنیم!.برای حل این مشکل اینکار رو می کنیم:
فرد قبل از خروجش شماره خودش رو به بغلی میده (بغلی بگیر!) و بغلی هم به بغل دستیش و این کار تا ته صف انجام میشه در نهایت نفر آخر(تو این مثال دهمین نفر) شماره خودش رو به نانوا میده و اینطوری صف مرتب میشه. برای درک بهتر به شکل زیر توجه بنمایید!
حالا فرض کنیم که چند نفر از صف اونم رندوم میخوان خارج بشن. اینبار از یه الگوریتم ساده استفاده می کنیم که برای هر حالتی که پیش بیاد جواب داره (دیگه نیاین تو کامنتا بگین اگر از ۱۰۰ نفر یکی موند اونوقت چی؟ - خب دیگه طرف مگه دیوانست؟! نونش رو میگیره میره دنبال زندگیش دیگه!??)
الگوریتم:
شماره اولین نفر خارج شده از صف را با 'خ' مشخص می کنیم سپس اولین همسایه اش(فرد داخل صف)میدهیم و شماره آن فرد و افراد باقی صف را نادیده می گیریم. فقط به تعداد افراد موجود در صف، یکی یکی به شماره ی خ اضافه می کنیم و به افراد در صف می دهیم. صف مرتب خواهد شد.
شاید این کار خیلی خفن یا خیلی عملی نباشه (بخصوص برای نونوایی ها!) ولی از دو جهت به نظرم ارزش داره:
۱ - اینجوری فکر کردن به مسائل پیش پا افتاده مقدمه حل مسائل پیچیده تره.
۲ - شاید بشه در مرتب سازی لیست (آرایه) های بزرگ در کامپیوتر استفادش کرد.
پی نوشت : سعی کردم به بهترین شکل ممکن منظورم رو برسونم امیدوارم که لذت برده باشین:)
