سلام!
این بار مسابقه الگوریتمی شماره ۴۰ رو با هدف تمرین و یادگیری بیشتر برای شما طراحی کردیم. سؤالات این مسابقه به این صورت هست که یک برنامه برای حل یک مسئله نوشته شده ولی این برنامه ایراد داره. از شما می‌خواهیم که یک مثال چاپ کنید تا خروجی برنامه به ازای این ورودی، به‌درستی کار نکنه. در واقع باید مثال نقض بزنید!
برای شرکت در این مسابقه خوبه که به این موارد توجه کنید:
- این مسابقه ۵ سؤال الگوریتمی رو شامل میشه و حل سؤالات اون روی امتیاز کوئرایی شما تأثیر نداره.
- برای فهمیدن متن سؤالات باید حداقل یکی از زبان‌های Python یا ++C یا Java رو در حد مقدماتی بلد باشید؛ اما برای ارسال پاسخ‌ها هیچ محدودیت زبانی وجود نداره.
- برای حل سؤالات، ۲ ساعت زمان کافی هست، اما شما از ساعت ۸ صبح روز سه‌شنبه تا ۸ صبح روز چهارشنبه به مدت ۲۴ ساعت زمان دارید تا پاسخ‌های خودتون رو ارسال کنید.
- امکان پشتیبانی و پرسیدن سؤال برای این مسابقه، فقط ۲ ساعت اول امکان‌پذیر هست.
ثبت‌نام این مسابقه در صفحه مسابقه الگوریتمی شماره ۴۰ انجام میشه. دقت کنید که برای ثبت‌نام فقط تا ۱۴ام اردیبهشت فرصت دارید.
منتظرتون هستیم 🙂
پی‌نوشت: راهحلها
امیدواریم که از مسابقه الگوریتمی شماره ۴۰ لذت برده باشید. در ادامه راه‌حل‌های سؤالات مسابقه توضیح داده شده‌اند.
در صورتی که متوجه راه‌حلی نشدید، می‌توانید در بخش نظرات سؤالات و ابهام‌های خود را مطرح کنید. همچنین اگر راه‌حل دیگری برای سؤالات دارید، خوشحال می‌شویم که راه‌حل خود را در بخش نظرات با ما و دوستانتان به اشتراک بگذارید.
هر رشته‌ای از حروف کوچک انگلیسی به طول n که با q شروع می‌شود، درست است؛ چون در برنامه‌ی نوشته‌شده، شرط اولِ گفته‌شده در سؤال به‌درستی در نظر گرفته نشده و یک حرف q به اول آن اضافه می‌شود. در حالی که در سؤال تاکید شده که در این حالت نباید تغییری ایجاد شود.
این سؤال راه‌حل‌های متنوعی می‌تواند داشته باشد. یکی از راهحلها این است که دنباله‌ی
n, n - 1, n - 2, \dots , 3, 2, 1
را چاپ کنید. این دنباله در الگوریتمِ گفته‌شده مرتب نمی‌شود. روش مرتب کردنِ گفته‌شده در سؤال، شبیه به «مرتب‌سازی حبابی» است، اما اشکال برنامه‌ی نوشته‌شده این است که در حلقه j، مقدار از i شروع می‌شود و تا n افزایش پیدا می‌کند. یعنی بعد از i مرحله، دیگر به سراغ i عدد اول دنباله نمی‌رود، در حالی که i عدد آخر دنباله مرتب می‌شوند.
این سؤال نیز راه‌حل‌های متنوعی دارد. اما یکی از راهحلها این است که مقدار a = b = c باشد؛ چون:
a^b \equiv c^c\equiv 0 \mod c
ولی چون اشکال برنامه این است که مقدار b را نیز با باقی‌مانده آن بر c جایگزین می‌کند، مقدار b برابر 0 خواهد شد و خروجی برنامه 1 می‌شود.
اگر تعداد مقسوم‌علیه‌های n را با d(n) نشان دهیم. تنها در صورتی ممکن است مثال نقضی برای این برنامه وجود داشته باشد که:
چون اگر مقدار m بیشتر باشد، لزوماً یکی از مقسوم‌علیه‌های n شامل سکه‌ها می‌شود و برنامه به‌درستی کار می‌کند. همچنین اگر m از ۲ کمتر باشد – یعنی برابر ۱ باشد – پس یعنی یک سکه داریم و این برنامه به‌درستی کار می‌کند و مثال نقضی وجود ندارد.
اما آیا همواره مثال نقضی با این ویژگی‌ها وجود دارد؟
اگر مقدار n بزرگتر یا مساوی ۷ باشد و همواره دو کوچک‌ترین عددی که مقسوم‌علیه n نباشند و نسبت به هم اول باشند را برداریم، این کار شدنی خواهد بود. این دو عدد را a و b بنامید. چون a و b نسبت به هم اول هستند، می‌توان تمام اعداد طبیعی را به‌صورت ax + by که x و y صحیح هستند تولید کرد و اگر a و b به اندازه کافی کوچک و n به اندازه کافی بزرگ باشد، این کار با ضرایب طبیعی نیز ممکن می‌شود.
برای اعداد کمتر یا مساوی ۶ نیز می‌توان راه‌حل را به‌صورت دستی بررسی کرد.
اگر یک رشته به طول n فقط شامل a باشد، مقدار هش (hash) آن ۰ می‌شود. حال کافی است رشته دیگری بسازیم که چنین خاصیتی داشته باشد. برای اینکار مضارب m را در مبنای b می‌نویسیم و اگر همه ارقام این مضرب بین ۰ تا ۲۵ بودند، رشته متناظر را خروجی می‌دهیم.
