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

یک سئوال در ترکیب با روش پویا و تقسیم و غلبه

ارسال:
  

rend4rend پرسیده:

یک سئوال در ترکیب با روش پویا و تقسیم و غلبه

سلام بچه ها
یه سوالی که ذهنمو مشغول کرده و ره آورد جزوه‌ی استاد ابراهیمی مقدم بوده اینه:
می دانیم تعداد اعمال جمع در پیاده سازی ترکیب در تقسیم و غلبه برابر C(n,m)-1 است که C همان ترکیب است. این مقدار برای الگوریتم پویای آن که از روش مثلث خیام بهره می گیرد
برابر (m(n-1)/2 + m(n-m خواهد بود که در صورتی که m=n باشد روش تقسیم و حل که از روش بازگشتی استفاده می کند بهتر است چون تعداد اعمال جمعش برابر صفر خواهد بود.
سئوال اینجاست: بنده در ادامه‌ی این جزوه‌ی استاد ابراهیمی مقدم به این نکته بر خوردم که حداقل تعداد جمع در ترکیب برابر (m(n-m است.
بنده چنین تصور کردم که این یعنی جایگزینی n=1 در فرمول پویا ؟ آیا غیر ازین است و اگر چنین باشد خوب این کار برای ترکیب در تقسیم و غلبه هم، همان جواب را می دهد که؛ یعنی صفر!

آیا پاسخ دهنده ای هست که مرا یاری کند؟!
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

Mojtaba پاسخ داده:

یک سئوال در ترکیب با روش پویا و تقسیم و غلبه

سلام.
تعداد جمع در حل بازگشتی(تقسیم و غلبه) ترکیب همون فرموله که نوشتید‌، قبول دارم.
میشه بگید فرمول دوم (برای تعداد جمع برای پویا) را چطوری بدست آوردید؟(اگه میشه با یک مثال عددی توضیح بدین؟)
نقل قول این ارسال در یک پاسخ

ارسال:
  

rend4rend پاسخ داده:

RE: یک سئوال در ترکیب با روش پویا و تقسیم و غلبه

(۱۳ آذر ۱۳۹۰ ۱۰:۴۵ ق.ظ)Mojtaba نوشته شده توسط:  سلام.
تعداد جمع در حل بازگشتی(تقسیم و غلبه) ترکیب همون فرموله که نوشتید‌، قبول دارم.
میشه بگید فرمول دوم (برای تعداد جمع برای پویا) را چطوری بدست آوردید؟(اگه میشه با یک مثال عددی توضیح بدین؟)
[/align]

خدمت مجتبای عزیز عرض کنم که طبق جزوه نوشته شده:
۱+۲+۳+...+(m-1) + m *(n-m)
و بدیهی که یک سری حسابی با قدر مطلق یک و ضرب در ادامه حاصل کاره...
البته بنده چون با سیستم تایپ مانشت مشکل دارم باید بگم ضرب (m*(n-m بعد ازm-1 است که نتونستم اونطوری بنویسم ولی فرقی هم در حاصل نمیکنه...
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

rend4rend پاسخ داده:

یک سئوال در ترکیب با روش پویا و تقسیم و غلبه

آیا واقعا پاسخ دهنده ای نبود که مرا یاری کند؟!!! جل الجالب! ما همچنان منتظریم استکان به دست...
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  بهترین زمان برای حل کوله پشتی به روش پویا Mr.R3ZA ۰ ۲۰۴ ۱۲ خرداد ۱۳۹۷ ۰۲:۰۶ ق.ظ
آخرین ارسال: Mr.R3ZA
  دو سئوال طراحی الگوریتم java50 ۱ ۴۲۲ ۱۱ اسفند ۱۳۹۵ ۰۱:۱۲ ق.ظ
آخرین ارسال: alireza01
  روش های بهبود زمان و فضا در مرتب سازی سریع از طریق کاستن عمق پشته بازگشت shamim1395 ۱ ۴۰۵ ۰۳ بهمن ۱۳۹۵ ۰۲:۲۱ ب.ظ
آخرین ارسال: Saman
  روش استراسن shamim1395 ۱ ۵۲۰ ۰۳ بهمن ۱۳۹۵ ۰۲:۰۹ ب.ظ
آخرین ارسال: Saman
  ضرب دو ماتریس به روش استراسن shamim1395 ۱ ۱,۵۱۲ ۲۷ دى ۱۳۹۵ ۰۶:۱۴ ب.ظ
آخرین ارسال: Pure Liveliness
  فوری- حل سوال به روش بازگشتی ziba_khofte ۱ ۴۱۷ ۲۲ آبان ۱۳۹۵ ۰۴:۰۹ ب.ظ
آخرین ارسال: Jooybari
  روابط بازگشتی - روش Akra-Bazi wskf ۶ ۹۴۵ ۱۰ مهر ۱۳۹۵ ۰۲:۵۵ ق.ظ
آخرین ارسال: Behnam‌
  پیچیدگی زمانی به روش ترسیم درخت wskf ۳ ۸۶۶ ۰۷ مهر ۱۳۹۵ ۰۸:۴۷ ب.ظ
آخرین ارسال: wskf
  سوال از روش تقسیم و غلبه kamal3401 ۳ ۸۰۷ ۱۱ خرداد ۱۳۹۵ ۰۲:۴۴ ق.ظ
آخرین ارسال: Behnam‌
  الگوریتم پویا- کامپیوتر آزاد ۸۳ dokhtare payiz ۱ ۵۵۶ ۳۰ اردیبهشت ۱۳۹۵ ۰۱:۳۵ ق.ظ
آخرین ارسال: Saman

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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