ورود به حساب ثبت نام جدید فراموشی کلمه عبور
برای ورود به حساب کاربری خود، نام کاربری و کلمه عبورتان را در زیر وارد کرده و روی “ ورود به حساب” کلیک کنید.





اگر فرم ثبت نام برای شما نمایش داده نمیشود، اینجا را کلیک کنید.









اگر فرم بازیابی کلمه عبور برای شما نمایش داده نمیشود، اینجا را کلیک کنید.





نمایش نتایج: از 1 به 1 از 1
  1. #1
    sina
    sina
    Guest

    تکنیکهای طراحی الگوریتم - روش تقسیم و تسخیر

    تقسیم و تسخیر <span dir=ltr>(Divide-and-Conquer)</span>

    طراحی الگوریتم در این روش بدین صورت حاصل می*شود که:
    مورد اصلی مسئله*ی داده شده برای حل را به چندین مورد کوچکتر (از همان نوع مورد اصلی) تقسیم می*کنیم٬ سپس موارد کوچکتر را بطور مجزا حل و نتیجه حاصل از هر زیر مورد را با هم ترکیب کرده تا نتیجه مورد اصلی مسئله را بیابیم.

    اگر تاکنون از روتینهای بازگشتی (Recursive Procedures) برای حل مسائل استفاده کرده باشید با روش کار تقسیم و تسخیر از پیش آشنایی دارید.

    الگوریتمهایی که با این روش طراحی می**شوند از دید من بسیار زیبا٬ ساده و خوانا هستند. اما این نکته منفی را هم نباید از قلم انداخت که اگر تعداد موارد منقسم شده از مورد اصلی زیاد باشد٬ ممکن است بازده الگوریتم حاصل از روش تقسیم و تسخیر افت کند.

    مثال 1: جستجوی دودویی (Binary Search)
    در نظر بگیرید که فهرستی از اسامی و آدرسهای مرتبط به هر اسم داشته باشیم و این فهرست دارای N جفت اسم و آدرس باشد که به ترتیب حروف الفبا بر اساس اسم مرتب شده و در دو آرایه نگهداری شوند:

    Names&#40;1..N&#41;
    Numbers&#40;1..N&#41;

    می*خواهیم با دادن هر اسم٬ آدرس مربوط به اسم را بیابیم. در این مثال فرض می*کنیم که هر اسم مورد پرسش حتما در آرایه وجود دارد تا الگوریتم و شرح آن را ساده*تر کرده باشیم.

    الگوریتم تقسیم و تسخیری که این مسئله را حل می*کند٬ ساده*ترین الگوریتم در این مدل الگوریتمی است که حاصل نگرشی بگونه زیر است:

    اسم داده شده
    یا
    درست در وسط فهرست قرار دارد
    یا
    در نیمه بالایی فهرست (بالا)
    یا
    در نیمه پایینی فهرست (پایین)

    چون فهرست مرتب شده است٬ پس شرط بالا در صورتی درست است که اسم داده شده کوچکتر از اسم قرارگرفته در قسمت میانی باشد. و شرط پایین در صورتی درست است که اسم داده شده بزرگتر از اسم قرارگرفته در قسمت میانی باشد.

    این دید به مسئله٬ الگوریتم زیر را در پی خواهد داشت:



    function Search&#40;X&#58; name; Start, Finish&#58; integer&#41; return address
    Middle&#58; integer
    begin
    Middle &lt;- &#40;Start + Finish&#41; / 2
    if X = Names&#40;Middle&#41; then
    return Numbers&#40;Middle&#41;
    elseif X &lt; Names&#40;Middle&#41; then
    return Search&#40;X, Start, Middle - 1&#41;
    else -- X > Names&#40;Middle&#41;
    return Search&#40;X, Middle + 1, Finish&#41;
    endif
    end



    الگوریتم بالا رو چگونه باید اصلاح کرد تا جوابگوی حالتی باشد که اسم وارد شده در فهرست موجود نیست؟ یا با عبارت متداول برای الگوریتمهای تقسیم و تسخیر، در چه مرحله*ای این اصلاح صورت گرفته شود؟


    کد:
    function Search&#40;X&#58; name;  Start, Finish&#58; integer&#41;  return address
      Middle&#58; integer
    begin
     
    if&#40; finish&lt;start&#41;or&#40;x&lt;start&#41;or&#40;x  >finish&#41; then
    return&#40;'موجود نبید'&#41;
    else if
     
      Middle &lt;- &#40;Start + Finish&#41; / 2
      if X = Names&#40;Middle&#41; then
        return Numbers&#40;Middle&#41;
      elseif X &lt; Names&#40;Middle&#41; then
        return Search&#40;X, Start, Middle - 1&#41;
      else -- X > Names&#40;Middle&#41;
        return Search&#40;X, Middle + 1, Finish&#41;
      endif
     
    endif
    end
  2. 1
نمایش نتایج: از 1 به 1 از 1

اطلاعات موضوع

کاربرانی که در حال مشاهده این موضوع هستند

در حال حاضر 1 کاربر در حال مشاهده این موضوع است. (0 کاربران و 1 مهمان ها)

موضوعات مشابه

  1. Xml را بهتر بشناسیم
    توسط MspSoft در انجمن XML و کاربرد آن
    پاسخ: 2
    آخرين نوشته: 2015-11-04, 01:39 AM
  2. اعتبار سنج سینتکس sql
    توسط MspSoft در انجمن SQL Server
    پاسخ: 0
    آخرين نوشته: 2012-02-12, 10:50 PM
  3. الگوریتم ساده برای محاسبه سینوس
    توسط sina در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 0
    آخرين نوشته: 2012-01-14, 07:11 PM
  4. الگوریتمی که a به توان n را به روش تقسیم و حل بدست بیاورد
    توسط sina در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 0
    آخرين نوشته: 2012-01-14, 03:16 PM
  5. الگوریتم تقسیم به روش تفریق های متوالی
    توسط sina در انجمن الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها
    پاسخ: 0
    آخرين نوشته: 2012-01-14, 03:14 PM

کلمات کلیدی این موضوع

مجوز های ارسال و ویرایش

  • شما نمیتوانید موضوع جدیدی ارسال کنید
  • شما امکان ارسال پاسخ را ندارید
  • شما نمیتوانید فایل پیوست کنید.
  • شما نمیتوانید پست های خود را ویرایش کنید
  •  

Content Relevant URLs by vBSEO 3.6.0 RC 2