Question

سلام یکی از مهمترین مباحث الگوریتم و برنامه نویسی داینامیک هستش و کلا چیز مهمیه به قول یکی از اساتید المپیاد کامپیوتر دانش آموزی دانشگاه جورجیا تک آمریکا "داینامیک آنقدر برای طراح اونجا مهم بوده از 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 image description

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

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

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

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

Answer 1

دیدم بچه ها میگن سوالا همه کلاسیکه،،،

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

فرض کنید جدولی 100*100 داریم که کپل در ابتدا در خانه ی پایین و سمت چپ یعنی خانه ی 1 و 1 قرار دارد و میخواهد به خانه ی سمت راست و بالا یعنی 100 و 100 برود.در هر مرحله اگه در خانه ی x , y قرار داشته باشد چنانکه x+y مضرب 5 بوده به یکی از خانه های x+1 , y+1 or x+2 , y or x , y+2 می رود.

و در غیر این صورت به یکی از خانه های x+1 , y or x , y+1 خواهد رفت.

باقی مانده ی تعداد راه های رسیدن به مقصد بر عدد 13921392 را به دست آورید.

در ابتدا در خانه پایین و راست یا پایین و چپ؟
2015-05-15 06:40:57 -0600 روبیک
ممنون که گفتید،،،،،تصحیح شد
2015-05-15 06:42:35 -0600 کنکوری
راستی شما میدونید چرا جاج irprogramming بسته شده؟
2015-05-15 06:44:10 -0600 روبیک
متاسفانه الان جواب ندارم!!!!
2015-05-15 06:45:24 -0600 کنکوری

Answer 2

برای 9 ضابطه $$dp[i][x]= dp[i-1][x]+dp[i-1][x-c_i]$$ که $dp[i][x]$ تعداد زیرمجموعه هایی از $i$ عضو اوله که مجموع $x$ دارند.

کد سوال 9(چون اعضا میتوانند بزرگ باشند از map استفاده شده و الگوریتم از $ O(N^2 lgN)$ است.)

کد سوال 6. $O(N)$

کد سوال 10.مثل LCS عمل میکنه. $O(N^2)$

منم یه سوال داینامیک خوب سراغ دارم. راه اصلیش داینامیک بود ولی من خودم یه جوردیگه با داینامیک حل کردم(مطمئن هم نیستم درست باشه ولی خب ظاهرا که هست!).اگه خواستید شما هم روش فکر کنید بعد جوابامونو مقایسه کنیم.الان جوابو نمیزارم.سوال اینه:

مجموعه ی اعداد طبیعی ۱ تا ۸ را در نظر بگیرید. میخواهیم مجموعه ای (شاید تهی!) از زیرمجموعه های این مجمـوعه را انتخـاب کنیـم، طوری که به ازای هر دو زیرمجموعه ی انتخاب شده، یکی زیرمجموعه ی دیگری باشد.

مثلن میتوانیم { {۱,۲} , {۱}} را انتخاب کنیم ولی نمیتوانیم {{۳} , {۲}} را انتخاب کنیم.

چند انتخاب مختلف داریم؟ (توجه کنید که ترتیب زیرمجموع ‌ههای انتخاب شده مهم نیست.)

منبع سوال : alefi17.mihanblog.com

پ.ن.: راه من:

میایم $dp[i][j]$ رو تعداد دنباله های زیرمجموعه ای با i عضو اول که j تا زیرمجمموعه دارن تعریف میکنیم.برای $dp[i][j]$ :

یا اصلا عضو i ام توشون نیومده که میرسیم به $dp[i-1][j] $.

یا عضو i ام هم اومده. یکی از جواب هارو در نظربگیرید.اول میایم همه زیرمجموعه هایی که توش اومدن رو بر حسب تعداد اعضا و به صورت نزولی مرتب میکنیم.واضحه که هرکدوم از زیرمجموعه ها باید زیرمجموعه همه قبلیاش باشه و هر عضوی که یه زیرمجموعه داره همه قبلیاش هم باید اونو داشته باشن. ودرواقع عضو i باید توی زیر مجموعه های 1,2,...,x اومده باشه که x میتونه از 1 تا j باشه.(درواقع نباید gap بیفته).به مثال زیرتوجه کنید:

                                   {} , {4} , {1,2,4} , {1,2,3,4}

همونطور که میبینید 4 توی زیرمجموعه های اول تا سوم اومده ، 3 فقط توی اولی اومده ، و 1 و 2 توی اولی و دومی اومدن.

حالا باز 2 حالت داریم:

با حذف عضو i از همه زیرمجموعه ها هیچ مشکلی پیش نمیاد که میرسیم به $j*dp[i-1][j]$
با حذف عضو i دوتا زیرمجموعه برابر به وجود میاد پس باید دو تا زیرمجموعه متوالی داشته باشیم که فقط توی عضو i با هم اختلاف داشته باشن.حالا عضو i رو حذف میکنیم و اون دوتا زیرمجموعه رو یکی درنطر میگیریم.باتوجه به مکان عضو iام میرسیم به $(j-1)*dp[i-1][j-1]$

اینم کد.که جواب میده :2183340 !!

39,830,292....درسته آیا؟؟
2015-05-15 02:58:04 -0600 کنکوری
اگه بود بگید کدمو بزارم
2015-05-15 03:07:11 -0600 کنکوری
میگم این سوالتون با ترکیبیات خالی حل نمیشه؟؟؟
2015-05-15 03:21:19 -0600 حمیدرضاه
جواب رو به عدد میشه بگین؟؟؟
2015-05-15 03:21:30 -0600 حمیدرضاه
ببخشید اشتباه کردم من :) یه سری حالات رو در نظر نگرفتم
2015-05-15 05:30:58 -0600 حمیدرضاه

آمار پرسش:

پرسش‌های مشابه:

نکاتی در مورد نوشتن پاسخ:

استفاده از ویرایشگر:

علائم ریاضی:

برنامه نویسی پویا چیست و مسائل مهم آن کدامند؟ (قسمت اول)

2 پاسخ

پاسخ شما

پیش‌نمایش: