[معمای پرش قورباغه روی چند ضلعی منتظم]
عرض کنم که آقای پروفسور قدسی رو که همگان میشناسند! ایشون یک جورایی پدر المپیاد کامپیوتر و ACM ایران هستن! و خیلی افتخارت و سوابق دیگه که جای بحثش نیست اینجا...
از نوابغ علوم کامپیوتر ایران.. خیلی خیلی سال پیش(1356) که کسی نمیدونست کامپیوتر چیه، بعد از لیسانس برق شریف، برای ارشد میرن دانشگاه برکلی ... دکتراشونو هم فک میکنم حدودای سال 63 میرن دوباره همونور پیگیر میشن...
حالا این بایو گرافی! به کنار.. افسانه ی مشهوری هست در مورد اینکه ایشون یا خودشون سوالای ساختمان داده و طراحی الگوریتم رو طرح میکنن... یا کسایی که سوال طرح میکنن، لاجرم تاثیر پذیرفته از ایشون هستن!!!!! :دی
البته شنیدم که آقای دکتر حقیقت سر کلاساشون گفته اند که آقای دکتر دهقان(دانشگاه امیر کبیر) مسئول انتخاب یا طرح سوالای ساختمان داده هستن...
(این داستان ها البته هیچ ربطی به تلاش و زحمت ما نداره... کسی که دنبال موفقیت تو کنکور باشه بالاخره راهشو پیدا میکنه و مطالبو یاد میگیره... حالا هرکی میخواد طراح یا سلکتور سوالا باشه! هدف اصلی این پست حل یه سوال بازگشتی جالب هست..)
اما این بار من دنبال ساختمان داده و طراحی الگوریتم نیستم.... بلکه ردپایی از این کتاب "داده ساختار ها و مبانی الگوریتم ها" ی دکتر قدسی در سوالات گسسته آی تی 94 یافته ام!
و البته در پایان این پست، حل تشریحی خوبی از یه مثال حل شده!!(
) از کتاب دکتر قدسی که توی کنکور 94 به عنوان سوال گسسته اومد رو میذارم که امروز 3 ساعت وقت منو گرفت!!!.
امروز اومدم سراغ روابط بازگشتی ساختمان گسسته... بعد یادم افتاد توی ساختمان داده و طراحی الگوریتم هم داریم بخشی به اسم حل روابط بازگشتی و اینا...
بعد رفتم سراغ کتاب "داده ساختار ها و مبانی الگوریتم ها" ی دکتر قدسی که مرجع درس ساختمان داده ها هستن یه جورایی...
بعد رفتم سراغ بخش روابط باز گشتی...
همیطو ورق میزدن رسیدم آخرین مثالش... ناگهان دیدم ای دل غافل! این که همون سوال ریاضی گسسته کنکور 94 هست!!!! (با یه اپسیلون تغییر!) که من کلی سر جلسه بش فک کرده بودم!!
و این بار ردپای دکتر قدسی رو در درس ریاضی گسسته یافتم (:دی)...
خلاصه فهمیدم ایشون رو باید پس خیییییییلی کتابشون رو دریابم!
این به کنار!
من یه بار دیگه سوالو خوندم و باز گیر کردم توش! از طرفی حل سوال پایینش نوشته شده توی کتاب! دیگه وسوسه شدم بخونمش... حل سوالو خوندم... ساعت 8 و خورده ای بود...
یه چیزایی فهمیدم ازش... یه چیزایی هم نفهمیدم!
خلاصه حالا کلنجار برو، کی کلنجار برو! من بکش! دکتر قدسی بکش!
دیدم نع! مثکه اونقدرا هم که فک میکردم باهوش نیستم! سوال حل شده رو هم حلشو نمیفهمم(یا درواقع نمیتونم تحلیل کنم!)... منگ بودم و گیج!
ساعت تقریبا شده بود 10(دو ساعت یک سوال!!!)
هرچی حساب میکردم میدیدم اشتبا حل کرده!!!! از طرفی با خودم میگفتم شرم بر تو!! چطو ممکنه قدسی اشتباه نوشته باشه!!!
ناگهان دقت کردم دیدم زیرنویس زده روی سواله... بعد پایین نوشته: این یکی از مساله های بیست و یکمین المپیاد جهانی ریاضی بود!!!
گفتم ای جانم! الان میرم دس به دامن گوگل میشم!!! بینم جریان چیه! شاید سوال غلط چاپی داره... شاید حلش گیر بیاد تو نت حالا فارسی اینگلیسی مهم نیست.. گیر من یه جاشه فقط..(21 امین المپیاد جهانی ریاضی سال 1979 بوده!!!! همون سال 1357 خودمون :دی یعنی به عبارتی 37 سال پیش).
عرض کنم که پس از کلی جست و جو چیزی تحت عنوان پاسخ یا سوال المپیاد ریاضی 37 سال پیش نیافتم!! (شایدم کم گشتم)
ولی وسط گشت و گذار... به جای سرچ فارسی و انگلیسی "سوال و پاسخ بیست و یکمین المپیاد جهانی ریاضی"، سرچ کردم "مساله بازگشتی پرش قورباغه روی هشت ضلعی"!!!، ناگهان یه جا دیدم این سوالو حل کرده بود!! دانلود کردم (داخل پی دی افی درمورد روابط بازگشتی بود... سایت رشد)حلشو با اشتیاق خوندم!... دیدم بله! همونطوری که فک میکرم یک غلط چاپی! 3 ساعت منو درگیر کرده بود!!!
خلاصه... بران شدم اصل سوال کتاب دکتر قدسی رو با حل تشریحی کاملی بذارم اینجا... سوال گسسته کنکور 94 هم دقیقا همینه با کمی تغییر عدد مسئله! اینه که مال کنکور 94 الان حل نشه بهتره! باشه برا وقتی که میخوایم از خودمون آزمون بگیریم! الان اینو حل کنیم(به کمک دکتر قدسی البته! با کمی پیاز داغ خودم بعلاوه اصلاح غلط چاپی که منو 3 ساعت معطل کرده بود!!!)
این صورت سوال المپیاد بیست و یکم:
فرض کنید A و E دوراس روبروی یک 8 ضلعی منتظم ABCDEFGH هستند. قورباغه ای از راس A شروع به جهیدن میکند و هر بار به راس مجاور می پرد. ولی وقتی به راس E رسید، همانجا متوقف می شود. (a(n را تعداد مسیرهایی بگیرید که قورباغه با n جهش از طریق آنها از A به E برسد.
ثابت کنید(عکس زیر):
و امّا راه حل(که از همون یک کیلومتری میگه با بازگشتی حل کن!):
خب... برای ساخت رابطه بازگشتی چه باید کرد؟...
کلا روابط بازگشتی همونطور که باهاشون آشنایی داریم، داره میگه یه جمله، وابسته به جملات قبلشه!! حالا یا مجموعی از یه سری جملات قبل یا ضرب یا ترکیبی از اینا!
ولی چیزی که ثابته، اینه که برای ساخت رابطه ی بازگشتی منتسب به یک مسئله! باید یک سری از اعمال اولیه توضیح داده شده توی اون مسئله رو انجام بدیم ببینیم بعدیاش چه شکلی میشن!
اینجا هم همینه!
اول یه توضیح شکلی بدیم از خود سوال.
یه قورباغه، روی یه راس از یه هشت ضلعی... قراره با یه سری جست و خیز(طول هر پرش، حد اکثر یک! یعنی به راس همسایش!) خودشو برسونه به راس روبروش (اینجا از A به E).
و مسئله چی رو میخواد؟؟!
اینکه الان از A میخواد بره به E (شکل زیر)، با همون شرط پرش به همسایه... چن تا مسیر داره تا خودشو برسونه به E ؟؟
خب طبیعتا یکیش اینه که مثل آدم از A بره به B بعدش بپره به C بعدش جهش کنه به D آخرش هم مثل بچه آدم بره تو E !! یعنی این مسیر: ABCDE
اما از اونجایی که قورباغه هست و آدم نیست! ممکنه از A بپره به B بعدش دوباره از B بپره تو A ! خلاصه هزار بار اینو هی تکرار کنه! بعد از خر شیطون بیاد پایین تو پرش هزار و یکم بعد از B بره تو C! حالا دوباره هزار بار از C بره به B بعدم A بعد دوباره بره تا C !!
خلاصه اینکه هرنوع جهشی! عقبگرد و جلوگرد! :دی
پس مسیر هایی مثل: ABCD...C...DE ، ABCD...C...FE ، ABAH...G...FE و ... همه قبولن؛ تعداد همه ی این مسیرها که باید با n تا جهش انجام بشن هر کدوم ، میشه an و مسئله نهایتا a2n رو خواسته!!
پس این از فهم مساله!
خب... ما دنبال اینیم که بدونیم در هر حال چی میشه این تعداد!
روشمون بازگشتیه پس تعدادی از اعمال رو انجام میدیم، بعد میبینیم بقیه ی مسیر چه ربطی با حل درخواست مساله داره!
خب.. میایم میگیم اگر بخواد دو تا جهش کنه، چه حالتایی براش پیش میاد و به کجاها میتونه بره!(یه جهش اطلاعات خاصی بهمون نمیده!)
خب، 4 حالت پیش میاد!! و اون چیه؟
1- از A بره به B و از B بره به C
یا
2- از A بره به H و از H بره به G
یا
3- از A بره به B و دوباره از B برگرده به A
یا
4- از A بره به H و دوباره از H برگرده به A
خب، تا الان دو تا از جهشاشو انجام داده! میمونه n-2 جهش دیگه!... حالا با این جهشای باقی مونده، میخوایم ببینیم بقیه جهشهاش رو (از کل n جهش) از اینجای جدیدی که بعد از دو جهش اومده قرار گرفته، چطوری باید انجام بده تا برسه به E...
در مورد دو حالت آخر که دوباره برمیگشت به A ، بقیه جهشاش دقیقا همونه که صورت سوال گفته!! یعنی میخواد از A بره به E ، منتهی این دفه با دوتا جهش کمتر نسبت به شروع پس میشه: 2an-2
درمورد دو حالت اول، مورد کمی فرق داره... اولا تعداد مسیر های جفتشون (از C به E یا از G به E)، به اندازه هم هستن چون شکل منتظمه... پس اسم تعداد مسیرها با n جهش از C به E رو میذاریم bn، پس تعداد مسیرها با n جهش از A به E رابطه بازگشتیش میشه این (فعلا!):
اما برای حلش باید bn-2 فومول بالایی رو به شکل an بنویسیم!... برای این کار، مجبوریم همین سناریوی قبلی رو برای bn هم پیاده کنیم و براش یه رابطه بازگشتی بنویسیم و بذاریمش تو بالایی و خلاصه نهایتا رابطه بشه به شکل یه رابطه بازگشتی همگن و د برو که رفتی!!
خب bn چی بود؟ تعداد مسیرها از C به E با n جهش(که برابر با تعداد مسیر از G به E با همون n جهش هست)، که اگر برای اینم دوتا جهش کنیم، این 3 حالت پیش میاد:
1- بره به D بعد دوباره برگرده به خودش یعنی C
یا
2- بره به H بعد دوباره برگرده به خودش یعنی C
یا
3- دوتا برگرده به عقب!! یعنی بره به B بعدم به A (خونه اول!)
دقت کنید با دو جهش بریم به E که دیگه رسیدیم و متوقف میشه!! و ما چون میخوایم همه حالتا رو به صورت بازگشتی بدست بیاریم، دیگه اونجا رو نمیریم. در واقع وقتی داریم همه حالتای رفتن از C به E رو به طور بازگشتی به دست میاریم، شامل CDE هم میشه!
و باز مثل توضیح an، رابطه بازگشتی برای bn هم طبق این سه حالت میشه این:
خب... حالا برای bn هم یه رابطه بازگشتی بدست آوردیم که شده این بالایی... برای an هم که توش bn-2 داشتیم... پس این دوتا فورمول رو از هم کم میکنیم، داریم:
(تفریق دو رابطه فوق):
an - bn = an-2 ==> bn = an-an-2
پس برای bn-2 داریم:
و در نهایت با جا گذاری در فورمول اول:
خب تا همینجا میشه این رابطه بازگشتی همگن رو حل کرد و خلاص شد!!
ولی نکته ای که وجود داره اینه که چون بین A و E، تعداد چهار تا جهش فاصله هست و هر جهش رفت و برگشتی هم خودش میشه زوج نهایتا، پس در هر حال برای رسیدن از A به E باید تعداد زوجی جهش انجام بشه!!!
یعنی در هر حال داریم: a2n-1 = 0
پس کافیه اون رابطه بازگشتی رو برای تعداد زوج جهش حل کنیم، یرای این منظور تعریف میکنیم: cn=a2n
پس رابطه جدیدمون که باید نهایتا حلش کنیم میشه این:
اینجا دیگه خعلی راحت! با یه معادله بازگشتی همگن خطی درجه دو مواجهیم! که با حل معادله مشخصه و توجه به اینکه c1=0 و c2=2 (با دو جفت جهش میشه از دو مسیر مختلف از A برسی به E یکی ABCDE و یکی هم AHGFE)، که جواب نهایی این رابطه بازگشتی میشه این:
همین میشه جواب سوال... منتهی اگر به رابطه بالایی دقت کنید، چون حاصل 2 منهای رادیکال2 کمتر از یک میشه و به توان n هم رسیده، پس میتونیم از خیرش بگذریم یه جورایی(برای n های بزرگ) و این رابطه رو هم داشته باشیم:
منابع:
1-کتاب "داده ساختارها و مبانی الگوریتم ها" نوشته محمد قدسی انتشارات فاطمی چاپ چهارم صفحات 114 و 115 مثال 3-21
2- http://olympiad.roshd.ir/computer/content/pdf/0049.pdf
والسلام، نامه شد تمام ;)
پ.ن1: اشکال جاپی کتاب دکتر قدسی این بود که نوشته شده بود bn رو میگیریم تعداد مسیرهای ممکن با n پرش از A به E !! و من گیچ بودم که این فرقش پس با خود an چیه؟! :)) خلاصه میگفتم بابا اشتب نوشته باس بگه از C... باز میگفتم نه بابا شاید نکته ای چیزی داشته باشه!!
پ.ن2: اگر این سه ساعت خودم زور میزدم، حلش کرده بودم راحت و اشکالشو خودم میفهمیدم :))) و این آفت سوال حل شده هست!
پ.ن3:با خودم میگفتم: "این که حل شد رفت پی کارش!! ولی چرا باید سوال المپیاد ریاضی رو بدن تو کنکور؟!!! برای المپیاد ریاضی این سوال چن دقیقه وقت داشته؟ برای کنکور چن دقیقه؟؟؟
بعد تنها توجیهی که براش پیدا کردم(به هدف تطهیر مولفان سوالات کنکور!) این بود که چون این سوال، از مسایل حل شده ی کتاب ساختمان داده دکتر قدسی بوده.. دیگه گفتن دانشجو اینو باس خونده باشه!"
که ناگهان با چک کردن سوال کنکور فهمیدم که!: بله! سوال داره میگه که شایان ذکر است! که عین همین سوال نیومد تو کنکور بلکه تعداد اضلاع چن ضلعی عوض شده بود(6) و در پایان هم جواب عددی سوال رو به ازای n=13 خواسته بود! که روش حل همینه قاعدتا!(مگر راه میانبری باشه که ما ندونیم:دی) خب... راه حل این سوال چی میتونه باشه! طبیعتا وقت گیره سر جلسه با همین روشی که گفتیم اینجا... هرقدر سریع! با فرض اینکه قبلا کسی اینو دیده باشه تو کتاب دکتر قدسی!
عرض کنم که من اولش اشتباها اینجا نوشته بودم که چون n=13 روخواسته و فرده، پس جوابش میشه صفر!! ولی دقت نکرده بودم که اینجا تو سوال کنکور تعداد اضلاع شیش تا هست و از A تا D به طور مستقیم 3 تا جهش فاصله هست! پس این ممکنه مسیر به طول فرد(با تعداد جهش فرد) هم داشته باشه!(بر خلاف هشت ضلعی که حل کردیم و تعداد جهش مستقیم از مبدا به مقصد 4 تا بود که خودش زوج بود... و از این نتیجه گرفتیم که مسیر به طول فرد نمیتونه وجود داشته باشه!!)... خب ینی باس حل کنیم؟.. شاید راه میانبری وجود داشته باشه هنوز!!
این کنکور لعنتی! به جای راه حل اصولی...گاهی میشه رد گزینه هم کرد!!...یعنی در واقع گاهی به نظر میرسه که طراح سوال خودش جوری سوال داده که منظورش این بوده داوطلب مخشو کار بندازه و با رد گزینه حلش کنه!!! یه گزینه که صفر داده بودن که میره کنار(میشه تو ذهن هم یه مسیر با 13 جهش پیدا کرد و اینو سریع زد کنار)... سه تا دیگه موند. نکته اینه که چون از دو طرف میشه از A برسی به D و دقیقا قرینه هم هستن، پس هر مسیر با شروع از A که خاتمش CD باشه، دقیقا مشابهش اونطرف هم وجود داره که خاتمش ED باشه!! پس دو برابر تعداد مسیر هایی که خاتمش بشه CD میشه جوابمون (یعنی جواب در هر حال زوج هست!! برای هر تعداد جهش!)... و گزینه ها فقط یکیش زوجه! پس این مثکه با دید کنکوری!! اصلا حل نمیخواسته!!! فقط یه کمی میخواسته آدم مخشو کار بندازه!(که من پارسال به کار ننداختم:دی) پس خیلی هم آدمای بدی نیستن بندگان خدا طراحان کنکور! این سوال تو کنکور پارسال، اصلا حل نمیخواسته!!! (حالا فکرشو کنید بعدا دوباره بدن این سوالو منتهی این بار تعداد اضلاع چند ضلعی منتظمه فرد باشه!!! با تعداد فرد جهش هم بشه برسی به مقصد!، گزینه ها هم همه جوره از صفر گرفته تا فرد و زوج داشته باشه! اونم بزرگ! یا مثلا خود فورمول نهایی رو بخوان... اونوقت دیگه میشه راستی راستی رحمت بفرستی بهشون!) ولی در هر حال کسی که کتاب آقای دکتر قدسی رو خونده بوده به نظرم با سوال آشنا بوده و یکباره به فکر اینکه سوال غریب و نامانوسیه خودشو سر جلسه نبازه و سوالو بندازه دور درجا!!! چون بعضی سوالا هست که باید داوطلب زود بتونه تشخیص بده که نمیتونه حل کنه و باس بره تو ریسایکلبین!
پ.ن4: سه ساعت خود سوال درگیرم کرد! حدود یک ساعت و نیم هم نوشتن این مطلب :))) ولی روحم آرامش پیدا کرد در عوض!، اینم از آفات وبلاگ داری ;)
بعد از یه مدت طولانی، پست طولانی هم لازمه
پ.ن5: تشکر از کابر محتر "علی" جان که نظرشون هست پایین مطلب و تذکر دادن که سوال کنکور 94 یه نکته ریز دیگه هم داشته و من اولش توجه نکرده بودم و بعدا با تذکر ایشون اصلاحش کردم
علی
