....ol comp....

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

....ol comp....

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

....ol comp....
طبقه بندی موضوعی
بایگانی
آخرین مطالب
پربیننده ترین مطالب
نویسندگان
پیوندها

سوال ۱۰ . «برنامه نویسی»

چهارشنبه, ۸ آذر ۱۳۹۱، ۱۰:۵۳ ب.ظ

دنباله ای از با حروف a ٬ b ٬ c ٬ d به طول حد اکثر ۱۰۴ در ورودی داده میشود . در خروجی دنباله ای با همان طول و متشکل از همین ۴ حزف چاپ کنید که با دنباله ورودی کوتاه ترین زیر دنباله مشترک را داشته باشد.

 * زیر دنباله از حذف تعدادی از اعضای یک دنباله ایجاد می شود.

راهنمایی هم نداره ٬ فکر کنید چشمک

  • Hamro

نظرات  (۱)

  • ۲۳ آبان ۹۲ ، ۲۱:۴۳
  • amirkasra
    • سلام !
    فرض کنید رشته ی ورودی یا Rرشته ای به طول n است که  A تا a  و B تا b و C تا c و D تا d دارد و مثلا C از همه کمتر است.
    ادعا میکنم رشته ی مطلوب n تا c است.
    فرض کنید رشته ای دیگر داریم به اسم RR و  بزرگترین زیررشته ی مشترک آن با R کمتر از  C حرف دارد. RR از AA تا a و BB تا b و CC تا c و DD تا d تشکیل شده. 
    حداقل یکی از AA یا BB یا CC یا DD از همتای خود در R بیشتر است (فرض کنید ‌‌BB از ‌‌B بیشتر است) چراکه اگر همه از همتایانشان در R کمتر باشند طول RR هم کمتر از R میشود که خلاف فرض است. در اینصورت بزرگترین زیر رشته ی مشترک R و RR طولی بیش‌‌ از ‌‌‌‌‌B دارد.(یک زیر رشته ی مشترک به طول B وجود دارد و آن هم تمام b های R است و تمام b های RR.) 
    از آنجایی که طبق فرض C کوچکتر مساوی B است رشته ای که معرفی شد(n تا c) رشته ای با بزرگترین ریر رسته ی مشترک کوچکتری با R است و از هر رشته ای بزرگنرین زیر رشته ی مشترک کوچکتری با R دارد.

    لطفا درستی یا نادرستی جوابم را در ایمیل برایم بفرستید. با تشکر!

    ارسال نظر

    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی
    ساخت وبلاگ در بلاگ بیان، رسانه متخصصان و اهل قلم