اخیرا در وبلاگ کروسان با قهوه مطلبی با عنوان یکی از وسواس‌های دوران کودکی را دیدم. در این مطلب مسئله ای مطرح شده است که من اسمش را گذاشتم " مسئله راه رفتن عادلانه ". برای اینکه با مسئله آشنا شوید می توانید به مطلب اصلی مراجعه کنید.
خلاصه مسئله این است که اگر برای برداشتن قدم از الگویی خاص پیروی کنیم، چطور می توانیم پیش بینی کنیم قدم i ام با پای چپ برداشته خواهد شد یا با پای راست.
در اینجا یک راه حل که به ذهنم رسید را ارائه می کنم. یک راه حل ساده تر و غیر بازگشتی هم در کامنت های پست اصلی بر اساس XOR عنوان شده است که می توانید آن را هم ببینید. البته پیاده سازی کامپیوتری راه حلی که در اینجا می بینید را می توانید به صورت غیر بازگشتی هم انجام دهید.
به قول معروف، بدون کاستن از کلیت مسئله، فرض کنیم قدم ها با "راست" شروع می شوند. فرمول بازگشتی زیر در تعریف می کنیم که در آن، i قدمی است که می خواهیم بفهمیم، قدم راست خواهد بود یا چپ و n هم اولین عدد به صورت توان دوی بزرگتر از i:
حال تابع f را به صورت زیر تعریف می کنیم:
این تابع با توجه به مقدار i، می گوید که قدم iام، قدم راست خواهد بود یا قدم چپ.
در زیر قطعه کد مربوط به حل مسئله را می بینید. اگر مقدار بازگشتی زوج باشد، قدم i ام، قدم راست وگرنه قدم چپ است. n هم یک توان دوی به اندازه کافی بزرگ(!) می باشد:
int step( int i, int n )
{
if( n == 0 )
return 0;
return step( i - (i/n) * n, n/2 ) + i/n;
}
اگر خروجی تابع بالا زوج باشد، قدم راست وگرنه قدم چپ خواهد بود.
