Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger

المپیاد کامپیوتر , الگوریتم , برنامه نویسی , ترکیبیات , گراف , ....

Challenger
طبقه بندی موضوعی
پیوندهای روزانه

۲ مطلب در بهمن ۱۳۹۰ ثبت شده است

۱۶بهمن

Longest common subsequence

شرح مساله(ویکی پدیا) :

دو رشته زیر را در نظر بگیرید:


S_{1}=ACCGGTCGAGTGCGCGGAGCCGGCCGAA\,\!


S_{2}=GTCGTTCGGAATGCCGTTGCTCTGTAAA\,\!

هدف مقایسه این دو رشته و پیدا کردن شباهت بین آنها است. بزرگترین زیردنباله مشترک این طور تعریف می‌شود که دنباله‌ای مانند S_{3} است به طوری که حروف موجود در S_{3} با حفظ ترتیب در S_{1} و S_{2} موجود باشد. اما مطلقاً لزومی ندارد که متوالی باشد. از طرفی S_{3} باید بزرگترین دنباله ممکن با خواص بالا باشد. به طور کلی اگر دو رشته X=\langle x_{1},x_{2},... ,x_{n}\rangle و Y=\langle y_{1},y_{2},... ,y_{n}\rangle را در نظر بگیریم٫ یک بلندترین زیر دنباله مشترک را می‌توان با استفاده از برنامه نویسی پویا پیدا کرد.

محمد مهدی جهان آرا
۱۶بهمن
صورت اصلی سوال : http://projecteuler.net/problem=31
ترجمه :
در انگلستان واحد پول بر پایه پند و پنس است .
(£1=100p)
در کل هشت نوع سکه وجود دارد : 1p, 2p, 5p, 10p, 20p, 50p, £1-100p and £2-200p
برای مثال می تونیم دو پند رو به شکل زیر درست کنیم :
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

چند راه متفاوت برای ساختن 2 پند وجود به طوری از هر سکه به تعدادی نا محدود در اختیار داشته باشیم ؟

___________________________________________

شرح راه حل : مسئله را با بهره گیری از برنامه ریزی پویا حل می کنیم ...
کد راه حل : http://snipt.net/JahanaraCo/project-euler-problem-31
محمد مهدی جهان آرا