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





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









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





نمایش نتایج: از 1 به 3 از 3
  1. #1
    rotin
    كاربر عادي
    http://up.vbiran.ir/images/rgk38wbh3cfxod62rhr2.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gif
    تاریخ عضویت
    2011 Dec
    نوشته ها
    4
    0
    9

    الگوريتم جستجوي دودويي

    با سلام اولین پست من توی این انجمن هستش که می خوام در مورد الگوریتم دودویی یه توضیح مختصری بدم خوب در روش جستجوي دودويي به يک آرايۀ مرتب نياز است.
    هنگام جستجو آرايه از وسط به دو بخش بالايي و پاييني تقسيم مي*شود.

    مقدار مورد جستجو با آخرين عنصر بخش پاييني مقايسه مي*شود.

    اگر اين عنصر کوچک*تر از مقدار جستجو بود، مورد جستجو در بخش پاييني وجود ندارد و بايد در بخش بالايي به دنبال آن گشت.



    دوباره بخش بالايي به دو بخش تقسيم مي*گردد و گام*هاي بالا تکرار مي*شود.

    سرانجام محدودۀ جستجو به يک عنصر محدود مي*شود که يا آن عنصر با مورد جستجو برابر است و عنصر مذکور يافت شده و يا اين که آن عنصر با مورد جستجو برابر نيست و لذا مورد جستجو در آرايه وجود ندارد.

    اين روش پيچيده*تر از روش جستجوي خطي است اما در عوض بسيار سريع*تر به جواب مي*رسيم.



    مثال* جستجوي دودويي

    برنامۀ آزمون زير با برنامۀ آزمون مثال 12-6 يکي است اما تابعي که در زير آمده از روش جستجوي دودويي براي يافتن مقدار درون آرايه استفاده مي*کند:

    int index(int, int[],int);

    int main()

    { int a[] = { 22, 33, 44, 55, 66, 77, 88 };

    cout << "index(44,a,7) = " << index(44,a,7) << endl;

    cout << "index(60,a,7) = " << index(60,a,7) << endl;

    }

    int index(int x, int a[], int n)

    { // PRECONDITION: a[0] <= a[1] <= ... <= a[n-1];

    // binary search:

    int lo=0, hi=n-1, i;

    while (lo <= hi)

    { i = (lo + hi)/2; // the average of lo and hi

    if (a[i] == x) return i;

    if (a[i] < x) lo = i+1; // continue search in a[i+1..hi]

    else hi = i-1; // continue search in a[0..i-1]

    }

    return n; // x was not found in a[0..n-1]

    }

    پس خروجی ما میشه
    index(44,a,7) = 2

    index(60,a,7) = 7

    براي اين که بفهميم تابع چطور کار مي*کند، فراخواني index(44,a,7) را دنبال مي*کنيم.

    وقتي حلقه شروع مي*شود، x=44 و n=7 و lo=0 و hi=6 است.
    ابتدا i مقدار (0+6)/2 = 3 را مي*گيرد.پس عنصر a[i] عنصر وسط آرايۀ a[0..6] است. مقدار a[3] برابر با 55 است که از مقدار x بزرگ*تر است. پس x در نيمۀ بالايي نيست و جستجو در نيمۀ پاييني ادامه مي*يابد. لذا hi با i-1 يعني 2 مقداردهي مي*شود و حلقه تکرار مي*گردد.
    حالا hi=2 و lo=0 است و دوباره عنصر وسط آرايۀ a[0..2] يعني a[1] با x مقايسه مي*شود. a[1] برابر با 33 است که کوچک*تر از x مي*باشد. پس اين دفعه lo برابر با i+1 يعني 2 مي*شود.
    در سومين دور حلقه، hi=2 و lo=2 است. پس عنصر وسط آرايۀ a[2..2] که همان a[2] است با x مقايسه مي*شود. a[2] برابر با 44 است که با x برابر است. پس مقدار 2 بازگشت داده مي*شود؛ يعني x مورد نظر در a[2] وجود دارد.
    حال فراخواني index(60,a,7) را دنبال مي*کنيم. وقتي حلقه شروع مي*شود، x=60 و n=7 و lo=0 و hi=6 است. عنصر وسط آرايۀ a[0..6] عنصر a[3]=55 است که از x کوچک*تر است. پس lo برابر با i+1=4 مي*شود و حلقه دوباره تکرار مي*شود. اين دفعه hi=6 و lo=4 است . عنصر وسط آرايۀ a[4..6] عنصر a[5]=77 است که بزرگ*تر از x مي*باشد. پس hi به i-1=4 تغيير مي*يابد و دوباره حلقه تکرار مي*شود. اين بار hi=4 و lo=4 است و عنصر وسط آرايۀ a[4..4] عنصر a[4]=66 است که بزرگ*تر از x مي*باشد. لذا hi به i-1=3 کاهش مي*يابد.
    اکنون شرط حلقه غلط مي*شود زيرا hi است. بنابراين تابع مقدار 7 را برمي*گرداند يعني عنصر مورد نظر در آرايه موجود نيست.


    در تابع فوق هر بار که حلقه تکرار مي*شود، محدودۀ جستجو 50% کوچک*تر مي*شود. در آرايۀ n عنصري، روش جستجوي دودويي حداکثر به log2 n+1 مقايسه نياز دارد تا به پاسخ برسد.

    حال آن که در روش جستجوي خطي به n مقايسه نياز است.


    تفاوتهاي جستجوي دودويي و خطي

    جستجوي دودويي سريع*تر از جستجوي خطي است.

    دومين تفاوت در اين است که اگر چند عنصر داراي مقادير يکساني باشند، آنگاه جستجوي خطي هميشه کوچک*ترين ايندکس را برمي*گرداند ولي در مورد جستجوي دودويي نمي*توان گفت که کدام ايندکس بازگردانده مي*شود.

    سومين فرق در اين است که جستجوي دودويي فقط روي آرايه*هاي مرتب کارايي دارد و اگر آرايه*اي مرتب نباشد، جستجوي دودويي پاسخ غلط مي*دهد ولي جستجوي خطي هميشه پاسخ صحيح خواهد داد.



    * مثال* مشخص كردن اين كه آيا آرايه مرتب است يا خير

    برنامۀ زير يک تابع بولي را آزمايش مي*کند. اين تابع مشخص مي*نمايد که آيا آرايۀ داده شده غير نزولي است يا خير:

    bool isNondecreasing(int a[], int n);

    int main()

    { int a[] = { 22, 44, 66, 88, 44, 66, 55 };

    cout<<"isNondecreasing(a,4) = " << isNondecreasing(a,4)<< endl;

    cout<<"isNondecreasing(a,7) = " << isNondecreasing(a,7) << endl;

    }


    bool isNondecreasing(int a[], int n)

    { // returns true iff a[0] <= a[1] <= ... <= a[n-1]:

    for (int i=1; i

    if (a[i]

    return true;

    }



    خروجي:

    isNondecreasing(a,4) = 1

    isNondecreasing(a,7) = 0



    اين تابع يک بار کل آرايه را پيمايش کرده و زوج*هاي a[i-1] و a[i] را مقايسه مي*کند.

    اگر زوجي يافت شود که در آن a[i] باشد، مقدار false را بر مي*گرداند به اين معني که آرايه مرتب نيست.

    ببينيد که مقادير true و false به شکل اعداد 1 و 0 در خروجي چاپ مي*شوند زيرا مقادير بولي در حقيقت به شکل اعداد صحيح در حافظه ذخيره مي*شوند.





    اگر پيش*شرط مثال يعني مرتب بودن آرايه رعايت نشود، جستجوي دودويي پاسخ درستي نمي*دهد. به اين منظور ابتدا بايد اين پيش*شرط بررسي شود.

    با استفاده از تابع assert() مي*توان اجراي يک برنامه را به يک شرط وابسته کرد.

    اين تابع يک آرگومان بولي مي*پذيرد. اگر مقدار آرگومان false باشد، برنامه را خاتمه داده و موضوع را به سيستم عامل گزارش مي*کند. اگر مقدار آرگومان true باشد، برنامه بدون تغيير ادامه مي*يابد.

    تابع asset() در سرفايل تعريف شده است.

    مثال* استفاده از تابع assert() براي رعايت كردن يك* پيش*شرط

    برنامۀ زير نسخۀ بهبوديافته*اي از تابع search() مثال 14-6 را آزمايش مي*کند. در اين نسخه، از تابع isNonDecreasing() مثال 15-6 استفاده شده تا مشخص شود آرايه مرتب است يا خير.

    نتيجه اين تابع به تابع assert() ارسال مي*گردد تا اگر آرايه مرتب نباشد برنامه به بيراهه نرود.





    #include // defines the assert() function

    #include // defines the cout object

    using namespace std;

    int index(int x, int a[], int n);

    int main()

    { int a[] = { 22, 33, 44, 55, 66, 77, 88, 60 };

    cout<<"index(44,a,7) = " << index(44,a,7) << endl;

    cout<<"index(44,a,8) = " << index(44,a,8) << endl;

    cout<<"index(60,a,8) = " << index(60,a,8) << endl;

    }



    bool isNondecreasing(int a[], int n);

    int index(int x, int a[], int n)

    { assert(isNondecreasing(a,n));

    int lo=0, hi=n-1, i;

    while (lo <= hi)

    { i = (lo + hi)/2;

    if (a[i] == x) return i;

    if (a[i] < x) lo = i+1;

    else hi = i-1; }

    return n;

    **}

    خروجي:

    index(44,a,7) = 2


    آرايۀ a[] که در اين برنامه استفاده شده كاملا مرتب* نيست* اما هفت* عنصر اول* آن* مرتب* است. بنابراين* در فراخواني*index(44,a,7) تابع بولي مقدار true را به assert() ارسال مي*کند و برنامه ادمه مي*يابد.

    اما در دومين فراخواني index(44,a,8) باعث مي*شود که تابع *isNondecreasing() مقدار false را به تابع assert() ارسال کند كه در اين صورت برنامه متوقف مي*شود و ويندوز پنجرۀ هشدار را نمايش مي*دهد.


    فکر نمی کنم زیاد سخت باشه
    خوب در پست بعدی می ریم برای توضیح استفاده از انواع شمارشي در آرايه رو براتون توضیح بدم که امید وارم به دردتون بخوره
  2. 2
  3. #2
    rotin
    كاربر عادي
    http://up.vbiran.ir/images/rgk38wbh3cfxod62rhr2.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gifhttp://up.vbiran.ir/images/qndtfn66fcrrq7cw6yh.gif
    تاریخ عضویت
    2011 Dec
    نوشته ها
    4
    0
    9
    خوب توضیح مختصر در مورد انواع شمارشی در آرایه ها رو می دم خوب با استفاده از انواع شمارشي نيز مي*توان آرايه*ها را پردازش نمود.

    مثال* شمارش با استفاده از روزهاي هفته

    اين* برنامه* يك* آرايه به نام* high[] با هفت* عنصرازنوعfloat تعريف* مي*كند كه* هر عنصر حداکثر دما در يک روز هفته را نشان مي*دهد:

    int main()

    { enum Day { SUN, MON, TUE, WED, THU, FRI, SAT };

    float high[SAT+1] = {28.6, 29.1, 29.9, 31.3, 30.4, 32.0, 30.7};

    for (int day = SUN; day <= SAT; day++)

    cout << "The high temperature for day " << day << " was "<< high[day] << endl;

    }

    خروجي:



    The high temperature for day 0 was 28.6

    The high temperature for day 1 was 29.1

    The high temperature for day 2 was 29.9

    The high temperature for day 3 was 31.3

    The high temperature for day 4 was 30.4

    The high temperature for day 5 was 32.0

    The high temperature for day 6 was 30.7

    به خاطر بياوريد که انواع شمارشي به شکل مقادير عددي ذخيره مي*شوند.

    اندازۀ آرايه، SAT+1 است زيرا SAT مقدار صحيح 6 را دارد و آرايه به هفت عنصر نيازمند است. متغير day از نوع int است* پس مي*توان مقادير Day را به آن تخصيص داد. استفاده از انواع شمارشي در برخي از برنامه*ها باعث مي*شود که کد برنامه «خود استناد» شود. مثلا در مثال 17-6 کنترل حلقه به شکل

    for (int day = SUN; day <= SAT; day++)

    باعث مي*شود که هر بيننده*اي حلقۀ for بالا را به خوبي درک کند.
  4. 2
  5. #3
    morteza.tehranee
    كاربر عادي
    تاریخ عضویت
    2014 Dec
    نوشته ها
    4
    0
    0
    اگه امکان داره در مورد این کد بیشتر توضیح بدید!!!!!
    [برای نمایش لینک باید عضو شوید. ]
    [برای نمایش لینک باید عضو شوید. ]
    [برای نمایش لینک باید عضو شوید. ]
نمایش نتایج: از 1 به 3 از 3

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

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

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

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

  1. كتاب اموزشي بدست اوردن اطلاعات سيستم در وي بي
    توسط MspSoft در انجمن مقالات مرتبط با برنامه نویسی VB
    پاسخ: 0
    آخرين نوشته: 2012-04-26, 01:54 PM
  2. پاسخ: 0
    آخرين نوشته: 2012-04-17, 03:14 PM
  3. پروژه الگوريتم هاي زمانبندي
    توسط MspSoft در انجمن برنامه نویسی در 6 VB
    پاسخ: 0
    آخرين نوشته: 2012-04-12, 01:39 PM
  4. نشان دادن قابليتهای مرورگر در asp.net
    توسط MspSoft در انجمن ASP.NET
    پاسخ: 0
    آخرين نوشته: 2012-02-15, 02:03 PM
  5. الگوريتم هاي رمز نگاري Cryptographics
    توسط MspSoft در انجمن امنیت در نرم افزار و برنامه نویسی
    پاسخ: 0
    آخرين نوشته: 2012-02-05, 06:48 PM

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

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

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

Content Relevant URLs by vBSEO 3.6.0 RC 2