(۳۰ دى ۱۳۹۲ ۰۲:۵۷ ق.ظ)msalehi1991 نوشته شده توسط:  سلام دوستان
دو تا سوال مشابه یکی از آی تی ۹۲ و یکی از هوش ۸۹,
جواب صحیح هوش ۸۹ گزینه ۱ میشه یعنی با استفاده از الگوریتم یافتن بزرگترین زیر دنباله مشترک میتوان مساله را حل کرد.
حال در ای تی ۹۲جواب گزینه ۴ میشه یعنی در زمان O(n) میتوان مساله را حل کرد!!!!!!!
خو اگه پاسخ هوش ۸۹ رو صحیح بگیریم مرتبه زمانی حل مساله O(n^2 میشه.

به نظرتون الگوریتم ای تی ۹۲ چیه؟!

تشکر

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

توی سوال ای تی فکر کنم این محدودیت وجود داره که اون دنباله اندیس هاشون پشت سر هم باشه که اینو میشه توی n حل کرد.
اینجا دوتا ابهام هست یکی کدومش substring میخواد و کدومش subsequence ! که بین این دو فرق هستش.

(۳۰ دى ۱۳۹۲ ۰۹:۳۷ ب.ظ)Riemann نوشته شده توسط:  

(30 دى ۱۳۹۲ ۰۲:۵۷ ق.ظ)msalehi1991 نوشته شده توسط:  سلام دوستان
دو تا سوال مشابه یکی از آی تی ۹۲ و یکی از هوش ۸۹,
جواب صحیح هوش ۸۹ گزینه ۱ میشه یعنی با استفاده از الگوریتم یافتن بزرگترین زیر دنباله مشترک میتوان مساله را حل کرد.
حال در ای تی ۹۲جواب گزینه ۴ میشه یعنی در زمان O(n) میتوان مساله را حل کرد!!!!!!!
خو اگه پاسخ هوش ۸۹ رو صحیح بگیریم مرتبه زمانی حل مساله O(n^2 میشه.

به نظرتون الگوریتم ای تی ۹۲ چیه؟!

تشکر

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

توی سوال ای تی فکر کنم این محدودیت وجود داره که اون دنباله اندیس هاشون پشت سر هم باشه که اینو میشه توی n حل کرد.
اینجا دوتا ابهام هست یکی کدومش substring میخواد و کدومش subsequence ! که بین این دو فرق هستش.

درسته o(n) هس تو ۶۰۰ مسئله یک سوال شبیه این هست که با پویا حل کرده

کسی می دونه این مساله راه حل حریصانه داره؟ در چه زمانی ؟؟

و LCS چه مرتبه ای داره؟ کتاب من مقسمیه اینو نگفته!