مقدمه
هوا عالی است، اما دلتان نمیخواهد یک ساعت را در کلاس درس بگذرانید. با دلخوری وارد کلاس میشوید و روی تختهسیاه شکل مثلثی میبینید که بهطرز عجیبی رضایتبخش است. وقتی منتظر آمدن معلم ریاضی هستید، متوجه الگوهایی در مثلث میشوید: مقادیر بیرونی همه یک هستند، هر سطر بعدی یک مقدار بیشتر از سطر قبلی دارد و مثلث متقارن است. عجیب است!
کمی بعد از اینکه مینشینید، معلم وارد کلاس میشود و توضیح میدهد که این مثلث همان مثلث پاسکال معروف است.
در طول یک ساعت بعد، معلمتان موارد شگفتانگیزی را که در این مثلث پنهان است برایتان آشکار میکند:
- میتوان از آن استفاده کرد تا محاسبه کنید به چند روش میتوان
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 هستند:
