روزنوشته

سلام یکی از مهمترین مباحث الگوریتم و برنامه نویسی داینامیک هستش و کلا چیز مهمیه به قول یکی از اساتید المپیاد کامپیوتر دانش آموزی دانشگاه جورجیا تک آمریکا "داینامیک آنقدر برای طراح اونجا مهم بوده از 8 تا سوال برنامه نویسی 6 تا داینامیک بوده کلا عاشق داینامیک بوده!! ".

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

اگر تشخیص دادید که یه مسئله دینامیک هست (کار ساده ای نیست) باید سه مرحله رو بگزرانید تا مسئله رو حل کنید:

1 .DP state رو حدس بزنید در واقع بیایید اون آرایه ای که می خواهید در اون اعضای دنباله ی بازگشتی رو ذخیره کنید رو تعریف کنید. مثلا بعضی وقتا یک بعدیه بعضا دو بعدی و ...

2 . حالت پایه رو بدست آورید یعنی جواب سوال رو برای 0 یا 1 و ...

3 . ضابطه ی دنباله ی بازگشتی رو بدست آورید کار سختیه اما با تمرین زیاد سختیش میاد پایین ولی هیچ وقت راحت نمیشه!

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

تو این سوال می خوام 10 تا سوال !! مطرح کنم که شامل سوالات معروف و .. داینامیک هستند:

1 . n امین عدد دنباله ی فیبوناچی را بدست آورید (خیلی خیلی ساده)

2 . n را از ورودی بگیر و تعداد راهای نوشتن آن با اعداد 1 و 3 و4 را بدست آورید (ساده) مثلا عدد 5 را می توان به 5 روش نوشت.

3 . دنباله ای داریم از n عدد صحیح (مثبت و منفی) بزرگترین زیر آرایه متوالی با بیشرترین مجموع را بیابید.(ساده و معروف)

4 . دنباله ای داریم از n عدد صحیح (مثبت و منفی) طول بزگترین زیر دنباله ی صعودی را بیابیید.(ساده و معروف)

5 . فردی دارای n نوع سکه است و می خواهد اسکناس k تومانی خود را با این سکه ها خرد کند. کمترین تعداد سکه های لازم را بیابیید. ابتدا n را دریافت کرده و سپس n نوع سکه را دریافت کرده و k را دریافت کنید.(ساده و معروف)

6 . تعداد راهای پوشاندن یک جدول در 3 را با دومینو را بیابیید .(POJ 2663 ) (متوسط ) یک حالت برای n=12

7 . مسئله ی کوله پشتی : n شئ داریم با وزن های متفاوت و با ارزش های متفاوت و یک کیف که دارای ظرفیت k کیلو است می خواهیم تعدادی از این اشیا را ورداریم که وزن آن از ظرفیت کیف بیشتر نشود و مجموع ارزش بیشینه شود.(متوسط و معروف)

8 . مثلثی مانند شکل زیر داریم که دارای n لایه است می خواهیم مسیری از قله ی مثلث تا پایین انتخاب کنیم که مجموع اعداد آن بیشینه شود آن عدد را چاپ کنید.(شکل) هر عدد می تواند به دو عدد مجاور خود برود.ابتدا n را دریافت و مثلث را دریافت کنید.(شبیه به سوال 3 مرحله 3 دوره ی 23 روز دوم که 40 امتیازی از 100 امتیاز رو تشکیل می داد)(متوسط)

9 . مجموعه ای داریم از n عضو تعداد زیر مجموعه های از آن که مجموع اعضای آن برابر با c باشدرا بیابیید.(متوسط به بالا)

10 . در یک کشور که دارای 2n شهر است و دارای یک رود می باشد متاسفانه این رود از وسط کشور رد شده است به گونه ای که n شهر در یک طرف و n شهر دیگر در طرف دیگر قرارگرفته است به همین دلیل رئیس جمهور آن کشور تصمیم گرفته که بین مجموعه ی A , B از شهرها پل احداث کنیم . هر شهر فقط می تواند با شهری پل داشته باشد که با آن هم جمعیت باشد . هر شهر می تواند با شهر دیگر پل داشته اگر با پلی دیگر برخورد نکند. حداکثر این کشور چند پل می تواند داشته باشد.ابتدا n را دریافت کن سپس دو دنباله ی n عضوی از جمعیت شهر های A و B دریافت کن که جمعیت شهرهای A و B را به ترتیب در آن دو دنباله دارد.نکته : میدانیم هر شهر در پایین با یک شهر با بالا هم جمعیت است.حداکثر چند پل می تواند احداث شود.(متوسط)