در صفحات آخر فصل اول درس طراحی الگوریتم مدرسان یک سری مسائلی آورده است که جواب آن ها به صورت یک رابطه بازگشتی حل می شود من این مسئله که به پیوست کرده ام را قسمت ii اش را متوجه نمی شوم می شود بیشتر توضیح بدین؟
(۱۴ آذر ۱۳۹۵ ۰۵:۰۴ ب.ظ)shamim1395 نوشته شده توسط: در صفحات آخر فصل اول درس طراحی الگوریتم مدرسان یک سری مسائلی آورده است که جواب آن ها به صورت یک رابطه بازگشتی حل می شود من این مسئله که به پیوست کرده ام را قسمت ii اش را متوجه نمی شوم می شود بیشتر توضیح بدین؟
سلام.فرض کنید که [tex]a_n[/tex] رشته هایی بطول n بر روی الفبای a و b و c باشه که تعداد aهای آن فرد است.
حالا اگه رشته با b یا c شروع بشه،چونکه تغییری در تعداد a ها رخ نداده،پس [tex]n-1[/tex] حرف باقیمانده هم بایستی خاصیت مسئله یعنی تعداد a فرد رو داشته باشند.یعنی [tex]2a_{n-1}[/tex]
ولی اگه رشته با a شروع بشه،بایستی [tex]n-1[/tex] حرف باقیمانده دارای تعداد a زوج باشند،که با a ی اولی جمعا تعداد a ها فرد بشوند.
و واسه اینکه بگیم که [tex]n-1[/tex]حرف باقیمانده،دارای تعداد زوج a باشند،کافیه که تعداد کل رشته های بطول [tex]n-1[/tex] یعنی [tex]3^{n-1}[/tex] رو منهای تعداد رشته هایی بطول [tex]n-1[/tex] کنیم که تعداد a های آن فرد باشد یعنی ([tex]a_{n-1}[/tex]).
پس جواب برابر میشه با:[tex]a_n\: =2\: a_{n-1}\: +\: 3^{n-1}-\: a_{n-1}\: =\: a_{n-1}\: +\: 3^{n-1}[/tex]
یادآوری: [tex]a_n[/tex] یعنی رشته هایی بطول n بر روی الفبای a و b و c باشه که تعداد aهای آن فرد است.
و [tex]a_{n-1}[/tex] یعنی رشته هایی به طول [tex]n-1[/tex] بر روی الفبای a و b و c که تعداد aهای آن فرد است.