Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۲:سوال ۵

سوال ۵

می‌خواهیم n ماتریس M1 تا Mn را در هم ضرب کنیم (M=M1×M2××Mn). فرض کنید ابعاد ماتریس‌ها به گونه‌ای هستند که حاصلضرب هر دو ماتریس مجاور امکان‌پذیر است می‌خواهیم تعداد ترتیب‌های مختلف برای انجام این ضرب را به دست آوریم. این ترتیب‌ها را می‌توان با استفاده از پرانتز نشان داد. فرض کنید Tn تعداد حالات پرانتزگذاری این ضرب باشد. مثلا T4=5 و ترتیب‌های مورد نظر بقرار زیرند:

M1×((M2×(M3×M4))M1×((M2×M3)×M4)(M1×M2)×(M3×M4)(M1×(M2×M3))×M4((M1×M2)×M3)×M4

الف) فرمولی برای Tn بر حسب Ti ها (i<n)‌ بنویسید و آن را اثبات کنید.

ب) برنامه‌ای بنویسید تا با دریافت n،‌ Tn را در خروجی چاپ نماید.


ابزار صفحه