📢📢📢 انجمن علمی علوم کامپیوتر برگزار می کند...📢📢📢

کارگاه یک روزه ی "برنامه نویسی اندروید "

زیرِ نظرِ علیرضـــــاپیر

در سال های اخیر استفاده از گوشی های هوشمند به سرعت در میان مردم رواج پیدا کرده است، در این میان گوشی های مبتنی بر سیستم عامل اندرویدی در بین مردم ایران از جایگاه بسیار ویژه تری برخوردار اند و میتوان گفت اکثریت قاطع گوشی های هوشمند در ایران را شامل می شوند.

این یک موقعیت بسیار عالی برای برنامه نویسان و حتی افراد علاقه مند است تا با ساخت نرم افزار و بازی های اندرویدی، و با توجه به مخاطب ملیونی، درآمد خوبی کسب کنند.

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

زمانِ برگزاری کارگاه به زودی اعلام خواهد شد.

سلام دوستان . پوزش بابت تاخیر در شروع این قسمت از عیدانه .. انشاءالله این قسمت رو فردا صبح به پایان میبریم و بعدازظهر قسمت آخر رو تقدیم شما خواهیم کرد ..
با ما همراه باشید🌹🌹

📝 قسمت پنجم آموزش الگوریتم 📝


🌴🌱🌿☘🍀🍃🌷🌼🌸💐🌳🌲🎄🌵

تکنیک برنامه ریزی پویا تا حدی شبیه روش تقسیم و حل هست . چون میاد یک نمونه از مسئله رو به نمونه های کوچک تر تبدیل میکنه .. ولی توی این روش ، اول از همه نمونه های کوچیک رو حل میکنیم و سپس نتایج اونهارو ذخیره می کنیم و به این ترتیب در صورت نیاز به اونها در مراحل بعدی ، از اونها استفاده میکنیم . در برنامه ریزی پویا ، حل یک مسئله به صورت پایین به بالا هست در صورتی که در روش تقسیم و حل ، مسائل به صورت بالا به پایین بررسی می شدند . پس ما در برنامه ریزی پویا باید یک ویژگی بازگشتی در نمونه ی مسئله پیدا کنیم و سپس با استفاده از اون و به روش پایین به بالا کل مسئله رو حل کنیم .

برای اینکه بهتر با این روش آشنا بشیم ، میریم سراغ یک الگوریتم کاربردی .

این الگوریتم ضریب دو جمله ای هست . ضریب دو جمله ای به صورت زیر هست :

C(n,k)= n!/k!(n-k)! 0<= k =< n

البته این تعریف نسبتا خوبی از ضریب دو جمله ای هست ولی خب اگه n و k خیلی بزرگ باشن ، شاید خیلی سخت بشه از این فرمول استفاده کرد . برای همین میتونیم از روابط دیگری هم استفاده کنیم .

این رابطه ی بالا ، اساس الگوریتم بازگشتی برای محاسبه ی ضریب دو جمله ای هست . این الگوریتم جزء روش تقسیم و حل محسوب میشه :

کارایی این الگوریتم بسیار کم هست .. دقیقا شبیه الگوریتم بازگشتی برای محاسبه ی جمله ی n ام دنباله ی فیبوناچی که دارای پیچیدگی زمانی نامناسبی بود . مشکل هم تا حدی مشابه هست . توی چنین الگوریتم هایی ممکنه یک نمونه چندین بار به طور جداگانه محاسبه بشه . و همین امر میتونه باعث کاهش شدید کارایی الگوریتم بشه .

اما حالا همین رو میخوایم با استفاده از برنامه ریزی پویا توضیح بدیم . ایده ی ما تقریبا مثل الگوریتم بازگشتی هست ولی سعی میکنیم ماتریسی تعریف کنیم مثل M به طوریکه M[i][j] حاوی C(i,j) باشه .

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

حالا کافیه ماتریس رو به شیوه ی پایین به بالا پر کنیم . یعنی با شروع از سطر صفرم . اگر دقت کنیم در این ماتریس میبینم که مثلت خیام _پاسکال در حال شکل گیری هست . هرکدوم از سطر ها هم از روی سطر قبلیشون در حال ساخته شدن هستن . اگر ماتریس خودمون رو nXk در نظر بگیریم ، عنصر M[n][k] همون C(n,k) خواهد بود . برای اینکه این موضوع رو متوجه بشیم یک مثال میگیم و بعد میریم سراغ الگوریتمش .

مثلا فرض کنید که بخوایم C(3,2) رو حساب کنیم . خب میایم شروع میکنیم به دست آوردن درایه های ماتریس از سطر صفرم .

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

پس جواب برابر با 3 هست .