نمایش نتایج 1 تا 24 از 24

نام تاپیک: برنامه merg sort با روشهای تقسیم و حل

  1. #1

    برنامه merg sort با روشهای تقسیم و حل

    سلام
    کسی می تونه در برنامه merg sort بجای تقسیم به 2 زیر آرایه از 3 زیر آرایه به من کمک کنه

  2. #2
    کاربر دائمی آواتار MiRHaDi
    تاریخ عضویت
    تیر 1383
    محل زندگی
    تهران - سوهانک
    پست
    982
    سلام
    پروژه دانشگاته ؟
    من میتونم ! حالا سوالت چیه ؟
    خوب ببین ! یکم باید الگوریتمتو عوض کنی
    به جای اینکه نصفه پاینی و بالایی رو جدا سورت کنی 3 قسمت میکنیش ! یعنی از اول تا 3/1 از 3/1 تا 3/2 و از 3/2 تا آخر ! بعد مرج میکنی و یه تا اشاره گر به 3 تا لیستت میذاری و یکی یکی مثل حالت دو تایی میری جلو
    بای

  3. #3
    سلام
    نه پروژه دانشگاه نیست یه تمرین
    من خودم قبلا اینکارو کردم ولی جواب نداده
    اینهم چیزی که نوشتم
    #include <iostream.h>
    #include <conio.h>
    #include <stdio.h>
    //**************************
    int a[12];
    int temp = 0;
    //**************************
    void Merg(int low , int high)
    {
    int i , j , k , mid;
    int temp[10];
    mid = (low + high)/2;
    for(i = low ; i <= mid ; i++)
    temp[i] = a[i];
    for(i = mid+1 ; i <= high ; i++)
    temp[mid+1+high-i] = a[i];
    j = low ; k = high;
    for(i = low ; i <= high ; i++)
    a[i] = (temp[j] < temp[k]) ? temp[j++] : temp[k--];
    }
    //**************************
    void MergSort(int low , int high)
    {
    int mid , mid1;

    if(high > low){
    mid = (low + high)/3;
    mid1 = (2 * mid) + 1;
    MergSort(low, mid);
    MergSort(mid+1,mid1);
    MergSort(mid1+1 , high);
    Merg(low , high);
    }
    }
    //**************************
    void main()
    {
    int n;
    clrscr();
    cin>>n;
    //*************Input********************
    for(int i = 0 ; i < n ; i++) cin>>a[i];
    //*****************Sort******************
    MergSort(0 , n-1);
    //****************OutPut*****************
    for( i = 0; i < 5 ; i++)
    cout<<a[i];
    }
    //***************************

    اگر بتونی اشکال برنامه رو بگی یا اونو دورست کنی ممنون میشم

  4. #4
    با سلام،

    الگوریتم Merge فوق تنها برای تقسیم به دو بخش عمل درست را انجام میدهد. کافیست آن را برای حالت سه بخشی دوباره بنویسید.

  5. #5
    متاسفانه این سوال رو در امتحان پایان ترم داده بودند

  6. #6
    سلام
    آقای B-Vedadian من هم می خوام همینو بدونم که چطوری این کارو انجام بدم اگر شما می دونید لطفا کمک کنید

  7. #7
    نمی دونم الآن چقدر به درد می خوره ولی الگوریتم معمولش رو که ما استفاده می کردیم اینیه که بعد توضیح مینویسمش، اگه بدون دیدن خود برنامه بتونید از توضیحات پیاده سازیش کنید قاعدتا خیلی به نفعتونه.

    فرض کنید اسم سه بخش که باید با هم مخلوط شن A,B,C و نتیجه D باشه.

    روش عامش به این صورته که از عنصر صفر D شروع میکنیم و در بین عناصر باقیمانده از A,B,C بزرگترین و یا کوچکترین رو انتخاب کرده در عنصر صفر D قرار میدیم و از لیست عناصر باقیمانده خطش می زنیم، برای عناصر بعدی هم دقیقا همین کار رو انجام میدیم.









    void merge(s1,e1,s2,e2,s3,e3,sr)
    {
    int i=0,j=0,k=0;
    for(int l=0;l++;l<e1-s1+e2-s2+e3-s3+3)
    {
    if(i<e1-s1+1)
    if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
    {
    a[sr+l]=a[s1+i];
    i++;
    }
    if(j<e2-s2+1)
    if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
    {
    a[sr+l]=a[s2+j];
    j++;
    }
    if(k<e3-s3+1)
    if(a[s3+k]>a[s1+i] && a[s3+k]>a[s2+j])
    {
    a[sr+l]=a[s3+k];
    k++;
    }
    }
    }


    در متن زیربرنامه مرتب ساز هم


    .
    .
    .

    Merge(low,mid,mid+1,mid1,mid1+1,high,low,high& #41;;

    .
    .
    .

  8. #8
    خیلی ممنون
    برنامه رو امتحان میکنم اگر مشکلی بود بازم میپرسم

  9. #9
    سلام آقای B-Vedadian
    من این کد رو که نوشتید امتحان کردم اصلا کار نمیکرد
    لطفا اگه برنامه اش رو نوشتید یا اگه بتونید یه توضیح بیشتری بدید ممنون میشم

  10. #10
    در الگوریتم merge از یک آرایه کمکی (auxiliary array) برای مرتب کردن دو لیستی که می خواهند ادغام شوند استفاده می شود . در نهایت هم نتیجه از این آرایه به آرایه اصلی کپی میشود.


    آیا راهی وجود دارد که از آرایه کمکی استفاده نکرد،چون در هر حال این آرایه سبب به هدر رفتن حافظه می شود.

    void merge (float v[], int start, int mid, int end) {
    int i, j, k;
    float tmp[end-start];
    i = start;
    j = mid;
    k = 0;
    while ((i < mid) && (j < end)){
    if (v[i] <= v[j])
    tmp[k++] = v[i++];
    else
    tmp[k++] = v[j++];
    }
    while (i < mid) tmp[k++] = v[i++];
    while (j < end) tmp[k++] = v[j++];
    for (i = 0; i < (end-start); i++) v[start+i] = tmp[i];
    }


    در اینجا از آرایه کمکی temp استفاده شده است.

  11. #11
    سلام
    این کد که شما نوشتید برای Merg Sort برای تقسیم به 2 زیر آرایه هست من برای تقسیم به 3 زیر آرایه می خوام
    اگر می دونید کمک کنید

  12. #12
    سلام،

    مشکلی که در اجرا نشدن برنامه اریه شده از طرف من وجود دارد، همین آرایه کمکی است. در زیر برنامه داده شده نتیجه بلافاصله در آرایه مبدا ذخیره می شود و این مساله باعث از بین رفتن داده های اولیه می گردد.

    احتمالا کد زیر درست کار کند.

    void merge(s1,e1,s2,e2,s3,e3,sr) 
    {
    int i=0,j=0,k=0;
    int* temp;
    temp=new int[e1-s1+e2-s2+e3-s3+3];
    for(int l=0;l++;l<e1-s1+e2-s2+e3-s3+3)
    {
    if(i<e1-s1+1)
    if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
    {
    temp[l]=a[s1+i];
    i++;
    }
    if(j<e2-s2+1)
    if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
    {
    temp[sr+l]=a[s2+j];
    j++;
    }
    if(k<e3-s3+1)
    if(a[s3+k]>a[s1+i] && a[s3+k]>a[s2+j])
    {
    temp[sr+l]=a[s3+k];
    k++;
    }
    }
    for(l=sr;l<sr+e1-s1+e2-s2+e3-s3+3;l++)
    a[l]=temp[l-sr];
    delete[] temp;
    }

  13. #13
    تابع merge که اینجا code شده همون چیزی که دوستمون نوشته بود فقط شاید یکم خوانا تر باشه .
    فقط یک مشکلی هست. فرض کنید ما اینقدر لیست اصلی را تقسیم کردیم که به سه زیر لیست
    27,10,12 می رسیم.اشاره گر اولی (h) به 27 دومی(l) به 10 و سومی(j) به 12 اشاره دارد. mid1=1 و mid2=2 است.
    بعد 10 بعنوان کوچکترین عنصر در شرط if چهارمی صدق می کند. مقدارl برار 3 میشود ودیگر وارد if دومی نمی شویم. و باید a[j] و a[h]مقایسه شوند.در صورتی که ما هر بار مقایسه با a[l] هم داریم. واین باعث ایجاد مشکل می شود. اگر trace کنید معلوم میشود.

    void merge (float a[], int start, int mid1, int mid2, int end)
    { int i, j, k,l,h;
    float tmp[end-start+1];
    h = start;
    i = start;
    l = mid1+1;
    j = mid2+1;
    for(k=0;k++;k<=end){
    if (h<=mid1)//h must be between start..mid1
    if ((a[h]<=a[l]) && (a[h]<=a[j]))//is a[h] the smallest in the three sublist
    tmp[i++] = a[h++];

    if (l<=mid2)//l must be between mid1+1..mid2
    if ((a[l]<=a[h]) && (a[l]<=a[j]))//is a[l] the smallest in the three sublist
    tmp[i++] = a[l++];

    if (j<=end)//j must be between mid2+1..end
    if ((a[j]<=a[h]) && (a[j]<=a[l]))//is a[j] the smallest in the three sublist
    tmp[i++] = a[j++];
    }//end for
    }//end merge

  14. #14
    سلام
    آقای B-Vedadian این متغیر ها رو میشه معرفی کنید
    s1,e1,s2,e2,s3,e3,sr
    ممنون

  15. #15
    سلام،

    اندیس شروع بخش اول : s1

    اندیس پایانی بخش اول : e1

    ...

    اندیس شروع بخش نتیجه : sr

  16. #16
    در ضمن دوست عزیز zizi

    من مشکل رو نفهمیدم مخصوصا که اصلا سه زیر لیست 10و12و27 یعنی چه و چطوری mid ها 1و2 میشند.

  17. #17
    آقای B-Vedadianفرض کنید
    ما می خواهیم لیست حاوی اعداد 27,10,12,20,25,13,15,22,8 را mergesort کنیم. ابتدا توسط mergesort لیست ما به سه زیر لیست 20,25,13 / 15,22,8 27,10,12 / تقسیم میشود. بعد دوباره بعد دوباره mergesort روی لیست سمت چپ اعمال میشه. سه زیر لیست 27/10/12 خواهیم داشت.
    که این سه تا تابع merge را فراخوانی می کنند.
    پس s1,e1,s2,e2,s3,e3 به ترتیب 1,1,2,2,3,3 میشند.
    وارد if ا ولی میشیم 0<1 است
    وارد if د ومی میشیم if(a[s1+i]>a[s2+j] && a[s1+i]>a[s3+k])
    if(a[1]>a[2] && a[1]>a[3]) ( یعنی 27>10,27>12) =T ، پس i =1 و27 هم در temp قرار می گیره.
    بعد وارد if چهارمی که شد :
    if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k])
    if(a[2]>a[1+1] && a[2]>a[3]) ( یعنی 10>10,10>12) = F
    بعد وارد if ششمی که شد:
    if(a[s3]>a[1+1] && a[3]>a[2]) (12>10,12>10) =T، K=1 و12 هم در temp قرار می گیره.
    بعد دوباره if ها چک میشند و به if می رسیم
    if(a[s2+j]>a[s1+i] && a[s2+j]>a[s3+k]) = if(a[2]>a[1+1] && a[2]>a[3+1])=F

    بنا براین عدد 10 در temp قرار نمی گیره!

  18. #18
    درست است ، وقتی که k>e3-s3+1 است و هنوز دو زیر لیست دیگر باقیمانده اند مشکل پیش میآید. باید هر کدام از if ها بصورت زیر اصلاح شوند:

    if( (a[s1+i]>a[s2+j] || j>=e2-s2+1) && (a[s1+i]>a[s3+k] || k>=e3-s3+1) )
    {
    temp[l]=a[s1+i];
    i++;
    }

  19. #19
    من این برنامه را بکمک دوستم نوشتم که از یک روش دیگه انجام شده.اول لیست رو سه قسمت می کنیم بعد دوتا دوتا merge کنیم. تابع merge همان چیزیه که برای دوتایی بکار می ره.درست جواب میده.

    void sort (int start, int end) {
    int mid;
    if (begin < end)
    sols(ثلث)= حد بالای (end-strat+1)/3
    msort (start,strat+sols-1 );
    msort (start+sols,start+2sols-1 );
    msort (start+2sols,end);
    merge (start,start+sols-1,start+2sols-1);
    merge (start,start+2sols-1,end);
    }


  20. #20
    من این برنامه را بکمک دوستم نوشتم که از یک روش دیگه انجام شده.اول لیست رو سه قسمت می کنیم بعد دوتا دوتا merge کنیم. تابع merge همان چیزیه که برای دوتایی بکار می ره.درست جواب میده.


    void msort (int start, int end) {
    int sols;
    if (begin < end)
    sols= ceil((end-strat+1)/3);
    msort(start,strat+sols-1 );// recursive functuion
    msort(start+sols,start+2sols-1 ); // recursive functuion
    msort(start+2sols,end); // recursive functuion
    merge(start,start+sols-1,start+2sols-1);
    merge(start,start+2sols-1,end);
    }


    :موفق:

  21. #21
    دوستان عزیز
    نکته بسیار مهم در اینگونه الگوریتمها در استفاده از توابع بازگشتی ( Recursive ) است. من توی هیچ یک از کدهای دوستان این حالت را ندیدم. ولی قبل از اینکه راه حلم را بنویسم می خواهم از دوستمون lionking_1360 بپرسم که چرا می خواهی این حالت را امتحان کنی؟ توجه داشته باش که در بخش Merge در حالت سه تایی تعداد مقایسه ها بالا می رود ، پیچیدگی زیاد می شود و کارآیی الگوریتم پایین می آید. چیزی که این الگوریتمها به شدت از آن پرهیز دارند.
    من فقط در مورد الگوریتم، شبه کد می نویسم البته شبیه به کد C. لطفا پیاده سازی اصلی را یکی از دوستان انجام دهد و نتیجه را اعلام کند ممنون . فقط توجه داشته باشید که تابع ceil تابعی است که سقف یک عدد اعشاری را می دهد. Ceil(1.3) = Ceil(1.6)= 2 مطمئن نیستم که این تابع درست باشد یا خیر. شرمنده ! یک کم C یادم رفته. :sorry:
    این روش مرتب سازی صعودی است. طبیعتا در نزولی تغییرات مربوطه را دارد.



    // Declare Array A
    int A[MAXNUMBER];
    // or int A[] = { ... }
    int Min(A1Indx , A2Indx , A3Indx )
    {
    if ( A1Indx = -1 )
    {
    if ( A3Indx = -1 ) return 2;
    if ( A2Indx = -1 ) return 3; // you can use "else if" for more readability
    if ( A[A2Indx] > A[A3Indx] ) return 3
    return 2;
    }

    if ( A2Indx = -1 )
    {
    if ( A3Indx = -1 ) return 1;
    if ( A1Indx = -1 ) return 3;
    if ( A[A1Indx] > A[A3Indx] ) return 3
    return 1;
    }

    if ( A3Indx = -1 )
    {
    if ( A2Indx = -1 ) return 1;
    if ( A1Indx = -1 ) return 2;
    if ( A[A1Indx] > A[A2Indx] ) return 2
    return 1;
    }

    if ( A[A1Indx] > A[A2Indx] )
    {
    if (A[A2Indx] > A[A3Indx] ) return 3;
    return 2;
    }
    else
    {
    if (A[A1Indx] > A[A3Indx] ) return 3;
    return 1;
    }
    }

    Merge (A1Start , A1End , A2Start , A2End , A3Start , A3End)
    {
    int temp[100]; //if you want you can use dynamic allocation if your programming language let you. int * Temp , Temp = malloc(...) ...
    int A1Indx , A2Indx , A3Indx , Indx ;

    for (Indx = 0 , A1Indx = A1Start , A2Indx = A2Start , A3Indx = A3Start ;
    A1Indx != -1 || A2Indx != -1 || A3Indx != -1 ; )
    {
    switch (Min(A1Indx , A2Indx , A3Indx) )
    {
    case 1 :
    Temp[Indx++] = A[A1Indx++];
    if ( A1Indx > A1End ) A1Indx = -1;
    break;
    case 2 :
    Temp[Indx++] = A[A2Indx++];
    if ( A2Indx > A2End ) A2Indx = -1;
    break;
    case 3 :
    Temp[Indx++] = A[A3Indx++];
    if ( A3Indx > A3End ) A3Indx = -1;
    break;
    }
    }
    for ( Indx = Start ; AIndx < A3End ; Indx++)
    {
    A[Indx] = Temp[Indx - Start];
    }
    }

    Merge_sort( int Start , int End )
    {
    int Len;

    Len = End - Start + 1
    if ( Len = 1 || Start = -1 ) return;

    //split Array A to 3 part; A1 , A2 , A3 with related Start and End (A1Start , A1End , ... )
    A1Start = Start;
    A1End = ceil(Start + Len/3 - 1 )

    A2Start = A1End + 1
    A2End = ceil(Start + (2*Len)/3 - 1)

    A3Start = A2End + 1
    A3End = End;
    if Len = 2
    A3Start = -1;

    MergeSort(A1Start , A1End); // recursive functuion
    MergeSort(A2Start , A2End); // recursive functuion
    MergeSort(A3Start , A3End); // recursive functuion

    Merge(A1Start , A1End , A2Start , A2End , A3Start , A3End);
    }

    void main(void)
    {
    int Start = 0; // or 1;
    int End = MAXNUMBER; // or any value I mean number of items in A to be sorted.
    // Initial A
    MergeSort(Start , End );
    // Print Array A which is sorted;
    }

  22. #22
    نکته بسیار مهم در اینگونه الگوریتمها در استفاده از توابع بازگشتی ( Recursive ) است. من توی هیچ یک از کدهای دوستان این حالت را ندیدم.
    دوست عزیز تمام زیربرنامه های این topic بازگشتی هستند. چون ما آرایه اصلی را با کمک تابع mergesort به آرایه های کوچکتر تقسیم می کنیم . وانقدر تابع را بصورت بازگشتی صدا می کنیم تا زیر آرایه ها بقدر کافی کوچک باشند.
    الگوریتم های mergesort از روش تقسیم و حل (Divide and Conquer) تبعیت می کنند. که این روش یک روش طراحی بالا به پایین ( top_down design ) است. یعنی حل یک مسله باحل نمونه های کوچک از آن. که این همای روش بکار رفته در حل روالهای بازگشتی است.

  23. #23
    توجه داشته باش که در بخش Merge در حالت سه تایی تعداد مقایسه ها بالا می رود ، پیچیدگی زیاد می شود و کارآیی الگوریتم پایین می آید.
    البته زمان اجرای یک الگوریتم بستگی به خود الگورینم دارد. پیچیدگی زمانی mergesort در حالث دوتایی )nlogn در مبنای 2 ) می باشد. برای حالتی که آرایه به سه قسمت تقسیم می شود ، برای الگوریتمی که من نوشتم پیچیدگی زمانی nlogn ( در مبنای 3) میباشد.
    چون nlogn ( در مبنای 2) > nlogn ( در مبنای 3) ، پس کارایی mergesort در حالت سه قسمتی بهتر است.

  24. #24
    کاربر تازه وارد
    تاریخ عضویت
    مهر 1386
    محل زندگی
    Movable
    سن
    37
    پست
    44

    نقل قول: برنامه merg sort با روشهای تقسیم و حل لطفاْ کمک کنید

    ببخشید که این تاپیک زیر خاکی را بالا آوردم
    من میخام همین الگوریتم مرج سورت رو به جای سه زیر لیست به پنج زیر لیست تقسیم کنم
    کسی هست که بتونه کمکم کنه ؟

تاپیک های مشابه

  1. Merg کردن دوتا جدول در datagridview
    نوشته شده توسط once4ever در بخش C#‎‎
    پاسخ: 7
    آخرین پست: یک شنبه 27 خرداد 1386, 09:34 صبح
  2. merg چند سلول در MSFlexGrid
    نوشته شده توسط riyahiyan در بخش برنامه نویسی در 6 VB
    پاسخ: 15
    آخرین پست: پنج شنبه 25 خرداد 1385, 19:01 عصر
  3. Auto merg
    نوشته شده توسط mzjahromi در بخش گفتگو با مسئولین سایت، درخواست و پیشنهاد
    پاسخ: 0
    آخرین پست: جمعه 12 خرداد 1385, 11:06 صبح
  4. Zip,split,merg
    نوشته شده توسط مطهر در بخش برنامه نویسی در 6 VB
    پاسخ: 2
    آخرین پست: شنبه 24 آبان 1382, 16:14 عصر

قوانین ایجاد تاپیک در تالار

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