کمک در حل یک مسئله بازگشتی

[armiya]

ممکنه یکی بگه این سوال چطوری حل میشه ؟؟؟ یعنی تکنیک حلش رو می خوام

رابطه بازگشتی زیر را در نظر بگیرید

f(x,0)=f(x+1,0)+f(x+1,1) ,if x<n

f(x,1)=2f(x+1,0)+f(x+1,1), if x<n

f(n,0)=1

f(n,1)=0

 

 

اگر ازین رابطه بخواهیم مقدار( f(1,1 را بصورت کارا حساب کنیم به چند عمل +(همان + در رابطه فوق) را باید انجام دهیم

البته گزینه هم داره می گذارم برای راحتی حل ولی اصولا چه تکنیکی برای حل اینطور
مسا ئل تو داده هستش

o(2^n)
o(n^2)
o(n)
o(2^n-1)

روش حلش رو می خوام

-------------------------------------------------------------------------
با تشکر

[qwerty11]

سلام،

یحتمل باید گزینه ی 3 درست باشه

اگر قرار دهیم :

F(x)=f(x,0)

G(x)=g(x,1)

آنگاه :

F(x)=F(x+1)+G(x+1)

G(x)=2F(x+1)+G(x+1)

اگر ما مقدار F(x) رو داشته باشیم اونوقت ما مطمئنیم که تمام مقادیر F(x+1) , F(x+2) , ... , F(n) رو داریم ! و در ضمن مطمئنیم که تمام مقادیر G(x+1) , G(x+2) , ... , G(n) رو نیز داریم ! در واقع این اعداد رو داخل آرایه نگهداری میکنیم ! (خودت برای یک x و n فرضی مثال بزنی منظورمو میفهمی). پس ما مقادیر G(X) رو توی زمان O(1) میتونیم به دست بیاریم و جواب O(n) میشه ...

[pesar irooni]

گزینه 4
چون به ازای هر بار فراخوانی f دوبار خودش رو فراخوانی میکنه پس میشه نمایی
اگه درختش هم بکشی معلومه
f = 2^n بار فراخوانی میشه و (s = 2^(n-1 بار جمع میکنه

[odiseh]

f(1,1 در دو معادله بازگشتي گفته شده صدق مي كنه؟

[armiya]

بله صدق میکنه صدقا و لی بهینه رو خواسته خودمم نمی فهمم که چطور حل میشه

[armiya]

در ضمن گزینه 3 جوابه ولی چطور اخه نمی دونم با چه استدلالی ؟؟؟؟؟؟؟؟؟
تو بالا که دوستمون اومده حل کرده اومده معادله رو با یه تغییر متغییر بازنویسی کرده و قبول دارم که اگر تابع f(X) را پیدا کنیو تابع دیگر رو می تونیم بنویسیم و لی باز هم با عدد اگه مثال بزنیم رو نمی فهمم ؟؟؟؟؟؟؟؟؟؟؟؟؟

[armiya]

از دوستان کسی نظری نداره ؟؟؟؟؟؟؟؟؟؟

[qwerty11]

سلام ! خوب خدا رو شکر همونطور که گفتم گزینه ی 3 مثل اینکه درسته.

دوست عزیز نمیدونم چقدر با برنامه نویسی پویا آشنایی داری. شما اگر درختش رو بکشی همه چی معلوم میشه.

این کد طریقه ی به دست آوردن مقادیر F و G به صورت کارا هستش. در ابتدا تمام مقادیر رو -1 میزاریم به این معنی که تا حالا به دست نیومدن. تست کن ببین پیچیدگیش چطوری میشه !؟

int F(int x){

    if(x==n) return 1;

    if(f[x]!=-1) return f[x];

    return f[x]=F(x+1)+G(x+1);

}



int G(int x){

    if(x==n) return 0;

    if(g[x]!=-1) return g[x];

    return g[x]=2*F(x+1)+G(x+1);

}

اگر حوصله داشتی این رو هم بخون : http://en.wikipedia.org/wiki/Memoization

[pesar irooni]

احتمالا منظورش اینه که از نتایج مراحل قبل استفاده کنی و تو یه آرایه ذخیره کنی.
همون جور که دوستمون گفت فک کنم همون برنامه نویسی پویاست
جوابش رو نوشتم ولی نمیشه آپلود کرد.
برنامه نویس این روزا داغونه

[pesar irooni]

این چیزی که فک کنم میخواسته
از یه جدول استفاده میکنی تا نتایج مراحل قبل رو به دست بیاری