مقدمه
هوا عالی است، اما دلتان نمیخواهد یک ساعت را در کلاس درس بگذرانید. با دلخوری وارد کلاس میشوید و روی تختهسیاه شکل مثلثی میبینید که بهطرز عجیبی رضایتبخش است. وقتی منتظر آمدن معلم ریاضی هستید، متوجه الگوهایی در مثلث میشوید: مقادیر بیرونی همه یک هستند، هر سطر بعدی یک مقدار بیشتر از سطر قبلی دارد و مثلث متقارن است. عجیب است!
کمی بعد از اینکه مینشینید، معلم وارد کلاس میشود و توضیح میدهد که این مثلث همان مثلث پاسکال معروف است.
در طول یک ساعت بعد، معلمتان موارد شگفتانگیزی را که در این مثلث پنهان است برایتان آشکار میکند:
- میتوان از آن استفاده کرد تا محاسبه کنید به چند روش میتوان
K عنصر را از میان N مقدار انتخاب کرد.
- دنبالهی فیبوناچی را در خود دارد.
- اگر اعداد فرد و زوج را با رنگهای متفاوت رنگ کنید، الگوی زیبایی به دست میآورید که مثلث سیهرپینسکی نام دارد.
معلم با اصرار از شما و همکلاسیهایتان میخواهد که کاربردهای دیگری را جستوجو کنید و اطمینان میدهد که خیلی بیشتر از اینها وجود دارد!
در همان لحظه، زنگ مدرسه به صدا درمیآید.
متوجه میشوید که در یک ساعت گذشته، کاملاً غرق یادگیری دربارهی مثلث پاسکال بودهاید.
سریع لپتاپتان را از کیفتان برمیدارید و به بیرون میروید تا هم از نور آفتاب و هم از شگفتیهای مثلث پاسکال لذت ببرید.
دستورالعملها
وظیفهی شما این است که N سطر اول مثلث پاسکال را خروجی بدهید.
مثلث پاسکال یک آرایهی مثلثی از اعداد صحیح مثبت است.
در مثلث پاسکال، تعداد مقادیر هر سطر با شمارهی آن سطر برابر است (که از ۱ شروع میشود).
بنابراین سطر اول یک مقدار دارد، سطر دوم دو مقدار دارد و به همین ترتیب.
سطر اول (بالاترین سطر) یک مقدار دارد: 1.
مقادیر سطرهای بعدی با جمع کردن اعدادی محاسبه میشود که در سطر قبلی دقیقاً در سمت راست و چپ موقعیت فعلی قرار دارند.
اگر سطر قبلی در سمت چپ یا راست موقعیت فعلی مقداری نداشته باشد (که فقط برای چپترین و راستترین موقعیتها پیش میآید)، مقدار آن موقعیت را صفر در نظر بگیرید (به این معنا که در جمع آن را نادیده میگیرید).
مثال
بیایید به ۵ سطر اول مثلث پاسکال نگاه کنیم:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
بالاترین سطر یک مقدار دارد که 1 است.
چپترین و راستترین مقادیر فقط یک موقعیت قبلی برای در نظر گرفتن دارند: به ترتیب موقعیت سمت راست یا سمت چپ آن.
چون مقدار بالاترین موقعیت 1 است، نتیجه میشود که همهی مقادیر چپترین و راستترین موقعیتها هم 1 هستند.
مقادیر دیگر همه دو موقعیت برای در نظر گرفتن دارند.
برای مثال، مقدار میانی سطر پنجم (1 4 6 4 1) برابر 6 است، چون مقادیر سمت چپ و راست آن در سطر قبلی 3 و 3 هستند:
نحوهی پیادهسازی این تمرین در Python: بازگشت
این تمرین طوری طراحی شده است که بهجای حلقهها، با recursion حل شود.
تابع بازگشتی تابعی است که خودش را فراخوانی میکند و برای حل مسائلی مفید است که بر اساس خودشان تعریف میشوند.
برای پرهیز از بازگشت بیپایان (یا بهطور دقیقتر، برای پرهیز از سرریز شدن پشته)، از چیزی به اسم «حالت پایه» استفاده میشود.
وقتی به حالت پایه میرسیم، مقداری غیربازگشتی برگردانده میشود؛ همین باعث میشود فراخوانی قبلی تابع حل شود و مقدارش را برگرداند و به همین ترتیب مثل موج در پشته به عقب برگردد تا اینکه اولین فراخوانی تابع پاسخ را برگرداند.
میتوانیم یک تابع بازگشتی بنویسیم تا پاسخ ۵! (یعنی ۵ * ۴ * ۳ * ۲ * ۱) را پیدا کنیم:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
در پایان باید اشاره کرد که Python تعداد دفعاتی را که میتوان فراخوانیهای بازگشتی انجام داد محدود میکند (بهطور پیشفرض ۱۰۰۰ بار) و برای بازگشت پایانی بهینهسازی نمیکند.
پیامهای استثنا
گاهی لازم است استثنا ایجاد کنید.
وقتی این کار را میکنید، همیشه باید یک پیام خطای معنیدار بگنجانید تا نشان دهید منشأ خطا چیست.
این کار کد شما را خواندنیتر میکند و بهشکل چشمگیری به دیباگ کمک میکند.
در موقعیتهایی که میدانید منشأ خطا نوع خاصی خواهد بود، میتوانید یکی از انواع خطای توکار را ایجاد کنید، اما باز هم باید پیامی معنیدار همراه آن بگنجانید.
این تمرین بهطور خاص میخواهد که اگر عددی منفی به تابع rows() داده شود، با دستور raise چندین ValueErrors را «پرتاب» کنید.
تستها فقط زمانی قبول میشوند که هم exception را raise کنید و هم پیامی همراه آن بگنجانید.
برای اینکه یک ValueError همراه با پیام ایجاد کنید، پیام را بهعنوان آرگومان به نوع exception بدهید:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
