(۲۸ آذر ۱۳۹۵ ۱۲:۳۳ ق.ظ)Behnam‌ نوشته شده توسط:  

(14 آذر ۱۳۹۵ ۰۵:۰۲ ب.ظ)shamim1395 نوشته شده توسط:  در صفحات آخر فصل اول درس طراحی الگوریتم مدرسان یک سری مسائلی آورده است که جواب آن ها به صورت یک رابطه بازگشتی حل می شود من این مسئله که به پیوست کرده ام دو سوال دارم

۱- نحوه ی شمارش ناحیه ها اشتباه نیست مثلا اونجا که در شکل من علامت زده ام را جز ناحیه ها به حساب نیاورده است؟

۲- روش بدست اوردن رابطه که اصلا چیزی متوجه نشدم

توضیحاتش جامع بود پس فکر نمیکنم نیازی به توضیح راه حلش باشه، اما در مورد سوالایی که پرسیدید

۱- درست شمرده. از اون محلی که شما علامت نشون دادید میشه اومد به جایی که نوشته ناحیه‌ی ۱ بدون اینکه از خطی رد بشید. پس اینا یه ناحیه هستند
۲- با توضیحاتش نشون داد که هر خط شکسته، معادل با دو خط راست هست ولی دو تا کمتر ناحیه ایجاد میکنه. اون $T'$ فرمول تعداد ناحیه‌های خط راست هست. T هم فرمول تعداد ناحیه‌های خط شکسته. پس تعداد ناحیه‌هایی که n خط شکسته میسازن یعنی $T(n)$ برابر هست با تعداد ناحیه‌هایی که ۲n خط راست میسازن یعنی $T'(2n)$ ولی این وسط هر خط شکسته، دو ناحیه کمتر میسازه، پس به ازای هر کدوم از n خط، باید دو تا کم کنیم که میشه ۲n. یعنی $T'(2n)-2n$. فرمول خطوط راست رو هم که داشت، جاگذاری کرده.