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

[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 ميتونن يه مثلث قايم الزاويه با اضلاعي ك اندازشون صحيحه رو بسازن يا اعداد ديگه اي هم وجود دارن؟