ساختمان داده

[r_khan]

در مورد حل رابطه بازگشتی توضیح دهید؟

مثلا رابطه بازگشتی زیر چگونه حل می شود


T(n) =T(n/2 +5)+n

[cherchil_hra]

تابع بازگشتی باید دو تا خاصیت داشته باشه:

1. خودش را صدا بزنه
2. یک شرط جهت اتمام فراخوانی ها

البته ممکن هست که دو تا زیر برنامه، همدیگر رو صدا بزنند. مثلا a در داخل خودش b رو صدا بزنه و b هم در داخل خودش a رو.

T(n) =T(n/2 +5)+n

اما تابع شما اینجوری حل میشه:

n=5, t(5)=t(5/2+5)+5
n=7.5, t(7.5)=t(7.5/2+5)+7.5
...

قسمت اول با مقدار n=5 شروع می کنیم (یا عددی که می خوایم). تابع t در داخل خودش، خودش را صدا می زنه. پس حالا برای اینکه مقدار t(5) رو حساب کنیم باید t(7.5) رو حساب کنیم ...

مثال متداول حل فاکتوریل هست:

function fact (int n)
{
if n<1 then fact=1
else fact= n*fact(n-1)
}

مثلا برای n=4 داریم:

fact(4)=4 * fact(4-1)
fact(3)=3 * fact(3-1)
fact(2)=2 * fact(2-1)
شرط بر قرار میشه
fact(1)=1

حالا مقدار یک در تابع قبلی گذاشته میشه و الی آخر :

fact(2)=2 * 1
fact(3)=3 * 2
fact(4)=4 * 6=24

[Developer Programmer]

مثلا رابطه بازگشتی زیر چگونه حل می شود

فصل آخر کتاب طراحی الگوریتمها ترجمه جعفرنژادقمی به تفصیل روش حلش رو یاد داده... خوب بخون مطمئن باش هیچ مشکلی دیگه نخواهی داشت

[itmicro]

سلام دوست عزیز
برای حل توابع بازگشتی دو روش را بهت پیش نهاد می کنم.
1-اگر جواب هر مرحله به مرحله قبلی مربوط می باشد باید آن را به صورت فرم درختی رسم کرد تا به جواب نهایی برسیم
2-در غیر این صورت به صورت خط به خط و مرحله به مرحله جلو ببریم.
T(n) =T(n/2 +5)+n
این جور مثال ها به صورت درختی حل میشه.


(4)T
|
|
|
4+(5+2)T
|
|
|
4+(5+(1)T

امید وارم که تونسته باشم بهت کمک کنم