المپیاد سوالات الگوریتم

[علــی[میم]]

پاسخ : سوالات الگوریتم

خوب پیشنهاد خوبیه ولی ما نمی تونیم رو برنامه نویسی کار کنیم به صورتی که دستمون باز باشه
می تونیم اسم تاپیک رو بکنیم "رفع اشکال الگوریتمی"
نظرتون چیه؟

خوبس دیه این بهتره

 

[mahtab.f]

پاسخ : سوالات الگوریتم

اسم تاپیک تغییر کرد
از این به بعد پس اشکالات الگوریتمی تون رو اینجا بپرسید !

 

[fateme.n]

پاسخ : سوالات الگوریتم

توی dynamic ما باید چجوری پیش بریم؟
راستش استادمون درس داده سوالم حل کرده ولی من هنوز دستم نیومده و همه رو قاطی کردم

 

[عمو ژپتو]

پاسخ : سوالات الگوریتم

توی dynamic ما باید چجوری پیش بریم؟
راستش استادمون درس داده سوالم حل کرده ولی من هنوز دستم نیومده و همه رو قاطی کردم

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

 

[مهسا.ق]

پاسخ : سوالات الگوریتم

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

می شه بیشتر توضیح بدی ما هم یاد بگیریم؟

 

[kia.celever]

پاسخ : سوالات الگوریتم

توی dynamic ما باید چجوری پیش بریم؟
راستش استادمون درس داده سوالم حل کرده ولی من هنوز دستم نیومده و همه رو قاطی کردم

من شهود خودمو میگم!
تو روش تقسیم و حل میایم مسئله رو به زیرمسئله های کوچیکتر تقسیم می کنیم و اول اونارو حل می کنیم ... بعد با استفاده از جواب های اون زیرمسئله ها جواب مسئله بزرگه رو بدست میاریم!
ولی برای بعضی سؤالا تعداد زیرمسئله های تکراری زیاد می شه! و هربار حساب کردنشون زمان زیادی رو الکی تلف می کنه ...
پس برای جلوگیری از این تکرار ها، میایم جواب زیرمسئله ها رو تو یه جدول نگه می داریم! اینطوری دفه بعدی که بهش نیاز داشتیم لازم نیست از اول حسابش بکنیم و میریم از اون جدوله می خونیمش!
کلیتش اینه!
فقط برعکس بازگشتی، باید اول کوچیکترین زیرمسئله رو حل کنید! منظورم اینه که توی بازگشتی از قسمت های بزرگ می رسید به قسمت های کوچیک ... ولی اینجا اول زیرمسئله های کوچیکو حل می کنیم بعد تو هر مرحله یه کم بزرگ می کنیم مسئله رو!

 

[informatic]

پاسخ : سوالات الگوریتم

کلـاً داینامیک چیز ِ خوبیــه !!!! معروف‌ترین مسئلــه ــَش هم میشــه گفت مسئلــه‌ی "کولــه پُشتی" ـــه ...

برای شروع میتونید حلِ این مسئلــه رو بخونید کــه دستتون بیاد موضوع از چــه قراره ... !!!

حرفــای دوستان هم کاملا درست بود ...


برای اینکــه راه بیُفتید می‌تونید کد چند تا سوال رُ بزنید کــه بـا این روش حل میشن ... !!! (برای تمرین میتونید سوال 104 ـــه SGU رو بزنید ... اگــه هم هنوز کد زدنُ شروع نکردید ، میتونید تئوریشُ حل کنید فعلاً ...)

 

[عمو ژپتو]

پاسخ : سوالات الگوریتم

حسام خدارو شکر تو معلم نشدی دانش آموزات پیر مشدن
توضیحات خودم کامل تر بود
فقط این قسمت چهارمش چی بود؟

 

[fateme.n]

پاسخ : سوالات الگوریتم

الگوریتم دنباله فیبوناچی با همینه دیگه؟
میشه یکی پیدا کردن بزرگترین دنباله در اعداد 1تاNرو بگه؟فک کنم LISبود اگه اشتباه نکنم؟
کیارش ممنون توضیحات کامل بود و واقعا خیلیا با بازگشتی قاطی میکنند.

 

[عمو ژپتو]

پاسخ : سوالات الگوریتم

الگوریتم دنباله فیبوناچی با همینه دیگه؟ آره اگه نخوای بازگشتی حل کنی
میشه یکی پیدا کردن بزرگترین دنباله در اعداد 1تاNرو بگه؟فک کنم LISبود اگه اشتباه نکنم؟
کیارش ممنون توضیحات کامل بود و واقعا خیلیا با بازگشتی قاطی میکنند.

من هرچی فکر میکنم میبینم سوالو بد توضیح دادیدا
من با دوسه تا سوال شبیه این قاظی کردم

 

[fateme.n]

پاسخ : سوالات الگوریتم

من هرچی فکر میکنم میبینم سوالو بد توضیح دادیدا
من با دوسه تا سوال شبیه این قاظی کردم

عصر درستش میکنم

 

[kia.celever]

پاسخ : سوالات الگوریتم

فکر کنم منظورتون بزرگترین زیردنباله مشترک بین 2 تا دنباله از اعداد 1 تا n باشه. اسمشم LCS ـه!
الگوریتمشو بگم؟ روش فکر کنید با هم بریم جلو ...

 

[fateme.n]

پاسخ : سوالات الگوریتم

سوال درست:
n تا عدد داریم بزرگترین زیر دنباله صعودی یا همونLIS چقدر است؟
شما روش بگید اشکالامون رو ازش بپرسیم یا با هم؟هرطور راحتید

 

[عمو ژپتو]

پاسخ : سوالات الگوریتم

سوال درست:
n تا عدد داریم بزرگترین زیر دنباله صعودی یا همونLIS چقدر است؟
شما روش بگید اشکالامون رو ازش بپرسیم یا با هم؟هرطور راحتید

به نظرم 4 تا راه داره که 4 تاشون nبه توان 2 اند
توضیحات کامل رو کیانوش جان بگن

 

[kia.celever]

پاسخ : سوالات الگوریتم

به نظرم 4 تا راه داره که 4 تاشون nبه توان 2 اند
توضیحات کامل رو کیانوش جان بگن

من گفتم LCS رو بلدم نه LIS! به خاطر همین می گم با هم بریم جلو ...
در ضمن من کیارشم!!

 

[عمو ژپتو]

پاسخ : سوالات الگوریتم

خوب یه راه حلش اینه که بیایم برای هر عدد بزرگترین زیر دنباله صعودی رو که بهش ختم میشرو حساب کنیم
دینامیک میشه
حالت پایه : اولین عدد
زیر مسئله: خونه i میشه طول بزرگترین دنباله صعودی که به iختم میشه
آپ دیت: از i به عقب میریم تا به یه عدد کوچیک تر برسیم بعد خونه i
اینجاش یادم نمیاد

 

[علــی[میم]]

پاسخ : سوالات الگوریتم

خب من دو تا راهش رو میگم

1 . خب بزرگترین و کوچکترین عدد دنباله روپیدا کنیم بعد یه دنباله بسازیم از مینیمم تا ماکسیمم بعد بین دنباله جدید و دنباله اولیه LCS بگیریم

این اُردرن میشه همون اردر LCS که n^2 هستش که فقط یه پیدا کردن مینیمم و ماکسیمم مهمه که با lg(n ) پیدا میشه و میشه ازش صرف نظر کرد

ولی این یه مشکل داره که میتونه بزرگترین دنباله اکیدا صعودی رو پیدا کنه ولی اگه دنباله اصلی رو مرتب کنیم و LCS بگیریم میشه زیردنباله صعودی

فلن رو این بحث کنین اون یکی توضیحش سخته والا

 

[kia.celever]

پاسخ : سوالات الگوریتم

1 . خب بزرگترین و کوچکترین عدد دنباله روپیدا کنیم بعد یه دنباله بسازیم از مینیمم تا ماکسیمم بعد بین دنباله جدید و دنباله اولیه LCS بگیریم

منظور اینه که سورتش کنیم؟

ولی این یه مشکل داره که میتونه بزرگترین دنباله اکیدا صعودی رو پیدا کنه ولی اگه دنباله اصلی رو مرتب کنیم و LCS بگیریم میشه زیردنباله صعودی

این بزرگترین دنباله صعودی رو پیدا می کنه! اگه بخایم اکیداً صعودی باشه کافیه بعد از مرتب کردن دنباله دوم، عدد های تکراریش رو حذف کنیم ... با (O(n

 

[علــی[میم]]

پاسخ : سوالات الگوریتم

منظور اینه که سورتش کنیم؟
این بزرگترین دنباله صعودی رو پیدا می کنه! اگه بخایم اکیداً صعودی باشه کافیه بعد از مرتب کردن دنباله دوم، عدد های تکراریش رو حذف کنیم ... با (O(n

هممممم خب بعله دیه

حالا راه بعدیشم من یه جور توضیح میدم شاید افتاد چم

2.
فرض کنیم طول بزرگترین زیر دنباله صعودی m باشه بعد ما میایم تمام زیر دنباله های 1 تا m عضوی رو پیدا میکنیم اینجوری که تو هر مرحله زیر دنباله ای که پیدا شده بهینه باشه یعنی عنصر آخرش مینیمم باشه و دنباله i عضوی بهینمونو از روی دنباله i - 1 عضویمون بسازیم
خب راستش هرچی فک میکنم میشه میشه همون راه حل داینامیکی که امیر میخواس بگه فقط یکمی گریدی هم توش داره

اینو با دو تا اُردر n^2 و nlgn میشه پیادش کرد.

 

[zahra.k]

پاسخ : سوالات الگوریتم

جاي الگوريتم خيلي خالي بود
هر كس اشكالي داشت درباره الگوريتم يه برنامه ميتونه اينجا مطرح كنه.

در سوال 9 projecteuler
فقط مضارب 3 و 4 و 5 ميتونن يه مثلث قايم الزاويه با اضلاعي ك اندازشون صحيحه رو بسازن يا اعداد ديگه اي هم وجود دارن؟