MOJAB 24

الگوریتم محاسبه تابع F(n) با روابط زیر تعریف می‌شود: F(n) = n اگر n ≤ 3 باشد؛ F(n) = 2 · n · n + F(n – 1) اگر n یک عدد زوج بزرگتر از 3 باشد؛ F(n) = n · n · n + n + F(n – 1) اگر n یک عدد فرد بزرگتر از 3 باشد؛ تعداد مقادیر طبیعی n را که در آن‌ها F(n) کمتر از 107 باشد، تعیین کنید.

برای حل این سوال، می‌توانیم از روش بازگشتی استفاده کنیم و تابع F(n) را به صورت بازگشتی محاسبه کنیم. ابتدا اعضای اولیه‌ی تابع F(n) را محاسبه می‌کنیم:

F(1) = 1 · 1 · 1 + 1 + F(0) = 1 + 1 + F(0) F(2) = 2 · 2 + F(1) = 4 + F(1) F(3) = 3 · 3 + F(2) = 9 + F(2)

حال از روابط داده شده برای محاسبه اعضای بعدی استفاده می‌کنیم:

F(4) = 2 · 4 · 4 + F(3) = 32 + F(3) F(5) = 5 · 5 · 5 + 5 + F(4) = 125 + 5 + F(4) F(6) = 2 · 6 · 6 + F(5) = 72 + F(5) F(7) = 7 · 7 · 7 + 7 + F(6) = 343 + 7 + F(6) و به همین ترتیب ادامه می‌دهیم تا زمانی که مقدار F(n) بیشتر از 107 شود. در این صورت تعداد مقادیر n که F(n) کمتر از 107 است را محاسبه می‌کنیم.

با انجام محاسبات، مقادیر n که باعث می‌شوند F(n) کمتر از 107 باشد به صورت زیر است: n = 1, 2, 3, 4, 5, 6

پس تعداد مقادیر n که F(n) کمتر از 107 باشد، برابر با 6 است.