PDA

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



armiya
جمعه 11 تیر 1389, 13:00 عصر
ممکنه یکی بگه این سوال چطوری حل میشه ؟؟؟ یعنی تکنیک حلش رو می خوام

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


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
جمعه 11 تیر 1389, 17:01 عصر
سلام،

یحتمل باید گزینه ی 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
چهارشنبه 16 تیر 1389, 12:42 عصر
گزینه 4
چون به ازای هر بار فراخوانی f دوبار خودش رو فراخوانی میکنه پس میشه نمایی
اگه درختش هم بکشی معلومه
f = 2^n بار فراخوانی میشه و (s = 2^(n-1 بار جمع میکنه

odiseh
چهارشنبه 23 تیر 1389, 14:44 عصر
f(1,1 در دو معادله بازگشتي گفته شده صدق مي كنه؟

armiya
چهارشنبه 23 تیر 1389, 23:55 عصر
بله صدق میکنه صدقا و لی بهینه رو خواسته خودمم نمی فهمم که چطور حل میشه

armiya
پنج شنبه 24 تیر 1389, 14:34 عصر
در ضمن گزینه 3 جوابه ولی چطور اخه نمی دونم با چه استدلالی ؟؟؟؟؟؟؟؟؟
تو بالا که دوستمون اومده حل کرده اومده معادله رو با یه تغییر متغییر بازنویسی کرده و قبول دارم که اگر تابع f(X) را پیدا کنیو تابع دیگر رو می تونیم بنویسیم و لی باز هم با عدد اگه مثال بزنیم رو نمی فهمم ؟؟؟؟؟؟؟؟؟؟؟؟؟

armiya
یک شنبه 27 تیر 1389, 16:09 عصر
از دوستان کسی نظری نداره ؟؟؟؟؟؟؟؟؟؟

qwerty11
یک شنبه 27 تیر 1389, 18:32 عصر
سلام ! خوب خدا رو شکر همونطور که گفتم گزینه ی 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
پنج شنبه 31 تیر 1389, 19:06 عصر
احتمالا منظورش اینه که از نتایج مراحل قبل استفاده کنی و تو یه آرایه ذخیره کنی.
همون جور که دوستمون گفت فک کنم همون برنامه نویسی پویاست
جوابش رو نوشتم ولی نمیشه آپلود کرد.
برنامه نویس این روزا داغونه

pesar irooni
سه شنبه 05 مرداد 1389, 02:15 صبح
این چیزی که فک کنم میخواسته
از یه جدول استفاده میکنی تا نتایج مراحل قبل رو به دست بیاری