نمونه سوالات طراحی الگوریتم

طراحی الگوریتم

سوال ستاره دار استاد شکری

عنوان سوال : ضرب دو عدد n رقمی به روش خطی ؟

جواب :

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

اکنون حاصل عبارت ضرب دو عدد n رقمی P(n) و Q(n) را بدست می آوریم:

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

چون عبارت فوق مجموع ۴ ضرب دو عدد به طول n/2 می باشد لذا خواهیم داشت :

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

بنابراین مرتبه زمانی تابع بازگشتی فوق با استفاده از قاعده مستر تئوری محاسبه می شود :

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

برای کاهش مرتبه زمانی فوق، مجموع ۴ ضرب دو عدد به طول n/2 را به ۳ ضرب به شکل زیر کاهش می دهیم:

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

بنابراین با توجه به روابط بالا خواهیم داشت:

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

پس برای محاسبه ضرب دو عدد n رقمی تنها نیاز به محاسبه حاصلضرب عبارتهایA,B,C خواهیم داشت و مرتبه زمانی تابع بازگشتی زیر با استفاده از قاعده مستر تئوری بدین صورت محاسبه می شود :

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

الگوریتم خطی ضرب دو عدد n رقمی در ادامه آمده است:

for (i = 0; i <= n – 1; i++)

{

for (j = 0; j <= n – 1; j++)

    {

        C[i + j] += P[i] + Q[j];

    }

}

قطعه کد بالا شامل دو حلقه مستقل تو در تو می باشد لذا مرتبه زمانی آن در زیر محاسبه شده است:

ضرب دو عدد n رقمی به روش تقسیم و غلبه

ضرب دو عدد n رقمی به روش تقسیم و غلبه

دانلود فایل

لینک دانلود
لینک دانلود

مطالـب مرتـبـط

لطفا از مطالـب مرتـبـط دیدن فرمایید.



تماس با ما

  • میدان شهدا - خیابان ایران - خیابان مهدوی پور پلاک 30 -شرکت تهران آی تی و مستر آی تی
  • 09121486770
  • 02133503646
  • ahadian2@gmail.com
کلیه حقوق مادی و مادی این اثر برای مستر آی تی محفوظ است
با مــا در تـــماس باشید
تلفن : 02133503646
تلفن همراه : 09121486770
ایمیل : ahadian2@gmail.com
آدرس : میدان شهدا خیابان ایران خیابان مهدوی پور پلاک 20