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

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

ارسال:
  

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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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