سلام دوستان . پوزش بابت تاخیر در شروع این قسمت از عیدانه .. انشاءالله این قسمت رو فردا صبح به پایان میبریم و بعدازظهر قسمت آخر رو تقدیم شما خواهیم کرد ..
با ما همراه باشید🌹🌹
با ما همراه باشید🌹🌹
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
تکنیک برنامه ریزی پویا تا حدی شبیه روش تقسیم و حل هست . چون میاد یک نمونه از مسئله رو به نمونه های کوچک تر تبدیل میکنه .. ولی توی این روش ، اول از همه نمونه های کوچیک رو حل میکنیم و سپس نتایج اونهارو ذخیره می کنیم و به این ترتیب در صورت نیاز به اونها در مراحل بعدی ، از اونها استفاده میکنیم . در برنامه ریزی پویا ، حل یک مسئله به صورت پایین به بالا هست در صورتی که در روش تقسیم و حل ، مسائل به صورت بالا به پایین بررسی می شدند . پس ما در برنامه ریزی پویا باید یک ویژگی بازگشتی در نمونه ی مسئله پیدا کنیم و سپس با استفاده از اون و به روش پایین به بالا کل مسئله رو حل کنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
برای اینکه بهتر با این روش آشنا بشیم ، میریم سراغ یک الگوریتم کاربردی .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
این الگوریتم ضریب دو جمله ای هست . ضریب دو جمله ای به صورت زیر هست :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
C(n,k)= n!/k!(n-k)! 0<= k =< n
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
البته این تعریف نسبتا خوبی از ضریب دو جمله ای هست ولی خب اگه n و k خیلی بزرگ باشن ، شاید خیلی سخت بشه از این فرمول استفاده کرد . برای همین میتونیم از روابط دیگری هم استفاده کنیم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
این رابطه ی بالا ، اساس الگوریتم بازگشتی برای محاسبه ی ضریب دو جمله ای هست . این الگوریتم جزء روش تقسیم و حل محسوب میشه :
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
کارایی این الگوریتم بسیار کم هست .. دقیقا شبیه الگوریتم بازگشتی برای محاسبه ی جمله ی n ام دنباله ی فیبوناچی که دارای پیچیدگی زمانی نامناسبی بود . مشکل هم تا حدی مشابه هست . توی چنین الگوریتم هایی ممکنه یک نمونه چندین بار به طور جداگانه محاسبه بشه . و همین امر میتونه باعث کاهش شدید کارایی الگوریتم بشه .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
اما حالا همین رو میخوایم با استفاده از برنامه ریزی پویا توضیح بدیم . ایده ی ما تقریبا مثل الگوریتم بازگشتی هست ولی سعی میکنیم ماتریسی تعریف کنیم مثل M به طوریکه M[i][j] حاوی C(i,j) باشه .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
پس اول یک ویژگی بازگشتی تعریف می کنیم . دقیقا همون ویژگی که در الگوریتم بازگشتی دیده شد .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
حالا کافیه ماتریس رو به شیوه ی پایین به بالا پر کنیم . یعنی با شروع از سطر صفرم . اگر دقت کنیم در این ماتریس میبینم که مثلت خیام _پاسکال در حال شکل گیری هست . هرکدوم از سطر ها هم از روی سطر قبلیشون در حال ساخته شدن هستن . اگر ماتریس خودمون رو nXk در نظر بگیریم ، عنصر M[n][k] همون C(n,k) خواهد بود . برای اینکه این موضوع رو متوجه بشیم یک مثال میگیم و بعد میریم سراغ الگوریتمش .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
مثلا فرض کنید که بخوایم C(3,2) رو حساب کنیم . خب میایم شروع میکنیم به دست آوردن درایه های ماتریس از سطر صفرم .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
M[0][0]= 1
M[1][0]=1
M[1][1]=1
M[2][0]=1
M[2][1]=M[1][0]+M[1][1]=1+1=2
M[2][2]=1
M[3][0]=1
M[3][1]=M[2][0]+M[2][1]=1+2=3
M[3][2]=M[2][1]+M[2][2]=2+1=3
M[1][0]=1
M[1][1]=1
M[2][0]=1
M[2][1]=M[1][0]+M[1][1]=1+1=2
M[2][2]=1
M[3][0]=1
M[3][1]=M[2][0]+M[2][1]=1+2=3
M[3][2]=M[2][1]+M[2][2]=2+1=3
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
پس جواب برابر با 3 هست .
Forwarded from آموزش برنامه نویسی - از مبتدی تا حرفه ای
⚡️البته دو نکته رو باید گفت: