زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۲:۰۲ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

بزرگترین زیر دنباله مشترک

ارسال:
  

kamal3401 پرسیده:

بزرگترین زیر دنباله مشترک

چطور میشه بزرگترین زیر دنباله مشترک بین این رشته هارو پیدا کرد مثلا
با روش پویا احتمالا باید حل بشه ولی ممنون میشم راهنمایی کنید
الگوریتم خاصی داره؟

۲,۱۱,۳,۱۰,۸,۶,۷,۹,۱,۴,۵
۱,۲,۳,۴,۵,۶,۷,۸,۹,۱۰,۱۱
مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

Behnam‌ پاسخ داده:

RE: بزرگترین زیر دنباله مشترک

(۱۷ خرداد ۱۳۹۵ ۱۱:۴۲ ب.ظ)kamal3401 نوشته شده توسط:  چطور میشه بزرگترین زیر دنباله مشترک بین این رشته هارو پیدا کرد مثلا
با روش پویا احتمالا باید حل بشه ولی ممنون میشم راهنمایی کنید
الگوریتم خاصی داره؟

۲,۱۱,۳,۱۰,۸,۶,۷,۹,۱,۴,۵
۱,۲,۳,۴,۵,۶,۷,۸,۹,۱۰,۱۱

آره داینامیک میخواد.
فرض کن [tex]a=(a_1,\: a_2,\: ...,\: a_n)[/tex] یک رشته، و یکی دیگه [tex]b=(b_1,\: b_2,\: ...,\: b_m)[/tex] باشه
اگه دو تای سمت راست باهم برابر باشند، قطعاً در زیردنباله باید باشند (و الا زیردنباله ماکزیمم نیست).
پس در [tex]a=(a_1,\: a_2,\: ...,\: a_{n-1})[/tex] و [tex]b=(b_1,\: b_2,\: ...,\: b_{m-1})[/tex] دنبال مابقی بگردیم.
ولی اگر برابر نباشند یا در [tex]a=(a_1,\: a_2,\: ...,\: a_{n-1})[/tex], [tex]b=(b_1,\: b_2,\: ...,\: b_{m})[/tex] و یا در [tex]a=(a_1,\: a_2,\: ...,\: a_{n})[/tex], [tex]b=(b_1,\: b_2,\: ...,\: b_{m-1})[/tex] هست.
ضمنا نمیتونیم هر دو کاراکتر آخری رو حذف کنیم چون ممکن هست یکی توو زیردنباله‌ی مشترک باشه (یعنی اینکه کاراکترهای آخر با هم برابر نیستند معنی این رو نمیده که هیچ کدوم در زیردنباله نیستند، به این معنی هست که "هر دو با هم نیستند" و ممکن هست یکی باشه).
لذا


نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  بزرگترین ضریب ss311 ۰ ۱,۲۵۷ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۵۷ ب.ظ
آخرین ارسال: ss311
  سوالی از دنباله ها و قوانین سیگما fendi ۱ ۲,۷۳۳ ۰۶ اردیبهشت ۱۳۹۸ ۰۲:۱۱ ق.ظ
آخرین ارسال: Saman
Question مشکل با درک توابع دنباله دار و مولد ؟؟؟؟ radar ۰ ۲,۴۸۶ ۱۶ دى ۱۳۹۷ ۰۴:۳۶ ب.ظ
آخرین ارسال: radar
  بهترین زمان بهینه برای مساله بزرگترین زیر دنباله صعودی(LIS) امیدوار ۳ ۴,۱۲۶ ۱۲ خرداد ۱۳۹۷ ۰۵:۴۳ ق.ظ
آخرین ارسال: Mr.R3ZA
  پنجمین ازمون استخدام مشترک فراگیر دستگاه های اجرایی کشور naghmeh70 ۷ ۷,۰۴۳ ۳۱ اردیبهشت ۱۳۹۷ ۱۱:۳۵ ب.ظ
آخرین ارسال: αɾια
  بزرگترین تجربه زندگی mengan ۱۱ ۸,۵۳۱ ۱۱ دى ۱۳۹۶ ۱۲:۰۵ ب.ظ
آخرین ارسال: csun
  نتایج چهارمین آزمون استخدامی مشترک فراگیر دستگاه‌های اجرایی کشور (شهریورماه سال ۹۶) edward71 ۲۵ ۱۷,۱۷۲ ۰۳ آبان ۱۳۹۶ ۰۸:۱۵ ب.ظ
آخرین ارسال: edward71
  درخواست زیر انجمن برای نتایج نهایی سال ۹۶ TRon ۴ ۲,۸۴۱ ۱۷ شهریور ۱۳۹۶ ۰۱:۰۴ ب.ظ
آخرین ارسال: TRon
  درخواست زیر انجمن سال ۹۶ TRon ۰ ۱,۳۸۵ ۱۱ شهریور ۱۳۹۶ ۰۶:۰۲ ب.ظ
آخرین ارسال: TRon
  یک شنبه های عکاسی: نمای زیر پل areldecor ۰ ۹ ۰۸ مرداد ۱۳۹۶ ۱۲:۴۵ ب.ظ
آخرین ارسال: areldecor

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close