تمرین کنید که سوزن ذهنتان روی یک نقطه قفل نکند

فهرست مطالب

در حل برخی مسایل راه حل درست نسبت به ایده ای که اول به ذهنتان می رسد بسیار متفاوت است. بنابر این ذهن خود را برای ایده های جدید باز بگذارید.

پرسش: برنامه ای بنویسید که ترتیب کلمات درون یک رشته را بالعکس می کند.

پاسخ: کار را با چند مثال شروع می کنیم. اگر رشته ورودی "Hello world" باشد آنگاه برنامه باید مقدار "world Hello" را برگرداند.

با کمی فکر کردن متوجه می شویم که اگر یک لیست از کلمات متوالی درون رشته بسازیم و لیست را برعکس کنیم آنگاه ترتیب مطلوب کلمات در لیست بدست می آید. با وصل کردن کلمات درون لیست می توانیم رشته مورد نظر را بسازیم. قطعه کد زیر این کار را انجام می دهد.

اما مصاحبه کننده از ما می خواهد که رشته ورودی "Hello      World" را روی تست کنیم. با دنبال کردن برنامه با داده ورودی، خروجی"World Hello" تولید می شود که پاسخ مطلوب نیست زیرا چندین کاراکتر فاصله بین دو کلمه از بین رفته اند. این اتفاق به دلیل نحوه کار تابع split رخ می دهد که رشته را از نقطه فاصله می شکند ولی فاصله ها را در حاصل دخیل نمی کند.

اگر بخواهیم این الگوریتم را تصحیح کنیم باید از روشی برای جداکردن کلمات استفاده نماییم که برخلاف split، فاصله ها را نیز در لیست خروجی در اختیار بگذارد. خوشبختانه راه حلی برای این کار وجود دارد و آن استفاده از تابع split درون کتابخانه عبارات باقاعده (regular expression) برای جداکردن رشته در نقاط فاصله است. این روش به ازای هر فاصله های یک رشته خالی در لیست حاصل ایجاد می کند. ممکن است در زمان پاسخگویی نحوه استفاده از عبارات باقاعده را ندانیم اما مطرح کردن این گزینه ،حتی اگر نتوانیم آن را پیاده کنیم، برای مصاحبه کننده نشان دهنده آن است که شما ذهنی باز دارید و گزینه های مختلف برای حل مساله را در نظر می گیرید. این یکی از مهمترین خصوصیات یک برنامه نویس خوب است.

اگر هم که حضور ذهن برای نوشتن عبارات باقاعده داشته باشیم می توانیم جواب درست زیر را پیاده کنیم.

اما اگر ایده استفاده از عبارت با قاعده به ذهنمان نرسید یا مصاحبه کننده از ما بخواهد که از این امکان استفاده نکنیم، باید یک ایده دیگر بزنیم و مساله را به روش دیگری حل کنیم.

با دقت در ورودی و خروجی مثال متوجه می شویم که خروجی در واقع معادل با رشته ایست که نسبت به رشته اول برعکس شده و هر کلمه نیز پس از آن برعکس شده است. مثلا با عکس کردن رشته "Hello      World" به رشته "dlroW      olleH" می رسیم. سپس با برعکس کردن هریک از کلمات در جای خود به رشته نهایی "World Hello" دست خواهیم یافت. بنابر این الگوریتم درست کار می کند.

با اندکی تامل بیشتر متوجه می شویم که برعکس کردن رشته عملی است که در هر دو مرحله الگوریتم انجام می شود. بنابر این در حل برنامه تابعی بنویسیم که بتواند یک رشته را برعکس کند. برای اینکه بتوانیم عمل برعکس کردن را روی کلمه ها هم انجام دهیم باید تابع را بصورتی بنویسیم که بتواند هر زیر رشته دلخواه بین اندیس های داده شده از یک رشته را در محل برعکس کند.

با این ذهنیت شروع به نوشتن برنامه می کنیم. همانطور که برنامه را می نویسیم خطوط برنامه را برای مصاحبه کننده توضیح می دهیم. ابتدا نام مناسبی برای تابع در نظر می گیریم. این تابع یک رشته را به عنوان ورودی می گیرد. در ادامه ابتدا رشته را به لیستی از کاراکتر ها تبدیل می کنیم (خط 2). این کار را به این دلیل انجام می دهیم که در زبان پایتون رشته یک ساختمان داده تغییر ناپذیر (immutable) می باشد. در ادامه یک تابع کمکی می نویسیم که اندیس چپ و راست یک زیر لیست را می گیرد و همه عناصر لیست در آن بازه را برعکس می کند (خطوط 4 تا 7). از این تابع هم برای برعکس کردن کل رشته (خط 9) و هم برعکس کردن کلمات (خطوط 10 تا 15) استفاده می کنیم. در انتها کاراکترهای لیست را به هم متصل می کنیم تا رشته را بسازیم.

تحلیل سرعت برنامه: این برنامه عملا یکبار رشته را می پیماید تا آن را برعکس می کند و سپس کلمات درون رشته را با یکبار پیمایش آنها برعکس می کند. بنابر این پیچیدگی محاسباتی این الگوریتم(O(n می باشد.