Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

Đề tài: Tìm Median mà không cần sắp xếp như thế nào ?

  1. #1
    Ngày gia nhập
    10 2010
    Bài viết
    21

    Mặc định Tìm Median mà không cần sắp xếp như thế nào ?

    Em biết là dựa vào QuickSort nhưng ko phải sort cả mảng rồi lấy phần tử ở giữa.

    Hic, thầy có nói mà ghi về quên hết. Ae chỉ em với

  2. #2
    Ngày gia nhập
    06 2008
    Bài viết
    54

    Ý bạn là không hiểu Sắp Xếp QuickSort?

  3. #3
    Ngày gia nhập
    10 2010
    Bài viết
    21

    Không phải, mình biết quicksort, nhưng yêu cầu đề là ko đc phép sắp xếp mảng (dù bằng cách nào) mà tìm ra số trung vị..

    VD: cho dãy 2 5 1 10 6 8 9 7 3 13 15

    thì tìm ra Median=7 mà ko đc xếp dãy trên lại từ nhỏ tới lớn

  4. #4
    Ngày gia nhập
    12 2010
    Nơi ở
    Hà Nội
    Bài viết
    60

    Lightbulb Mong giúp đc bạn

    Trích dẫn Nguyên bản được gửi bởi Voldedore Xem bài viết
    Em biết là dựa vào QuickSort nhưng ko phải sort cả mảng rồi lấy phần tử ở giữa.

    Hic, thầy có nói mà ghi về quên hết. Ae chỉ em với
    tha tội cho mình vì minh không đc học lập trình C++ nên chỉ dưa ra code C đc thôi:
    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. void FindMedian(int A[],int n, int k);
    4. void main()
    5. {
    6.    int median;
    7.     int A[] =   {19,47,13,31,8,68,74,89,40,6,25,98,87,10,54};
    8.     int n   =   sizeof(A)/sizeof(int);
    9.         FindMedian(A,n,n/2);
    10.         printf("\nphan tu median la phan tu nam o giua:");
    11.     for(int i = 0; i < n; i++)
    12.         {printf(" %d",A[i]);}
    13.    median=A[n/2];
    14.    printf("\nmedian                              :%d",median);
    15.     getch();
    16. }
    17. void FindMedian(int A[],int n, int k)
    18. {
    19.     int L,R,i,j,temp,x;
    20.     L   =   0;
    21.     R   =   n-1;
    22.  
    23.     while(L < R)
    24.     {
    25.         x   =   A[k];
    26.         i   =   L;
    27.         j   =   R;
    28.         while(i < j)
    29.         {
    30.             while (A[i] < x) i++;
    31.             while (A[j] > x) j--;
    32.  
    33.             if(i <= j)
    34.             {
    35.                 temp    =   A[i];
    36.                 A[i]    =   A[j];
    37.                 A[j]    =   temp;
    38.                 i++;
    39.                 j--;
    40.             }
    41.         }
    42.         if(j < k) L = i;
    43.         if(k < i) R = j;
    44.     }
    45. }
    phần giải thích cụ thể mình có kèm file đính kèm đấy!

  5. #5
    Ngày gia nhập
    06 2008
    Bài viết
    54

    G nghĩ không ra rồi. QuickSort là hàm sắp xếp dữ liệu rồi. Nếu không cho sắp xếp thì còn cách khác nhưng không chính xác. Tính trung bình tổng.

    Ai biết bài này chia sẻ cho G với mấy bạn khác hiểu với.

  6. #6
    Ngày gia nhập
    04 2010
    Nơi ở
    Thâm sơn cùng cốc
    Bài viết
    825

    Mặc định Tìm Median mà không cần sắp xếp như thế nào ?

    Một phát biểu sau bạn tự xem đúng hay sai:
    Lời - Số trung vị của một dãy đã sắp là số một số mà gần giá trị trung bình của dãy đó nhất.
    Toán học: Gọi m là số trung vị của 1 dãy, average(A) là giá trị trung bình của dãy số A
    m={k thuộc A | abs(k-average(A)) đặt giá trị nhỏ nhất}

    Ví dụ:
    Dãy A : -1 ,0, 100,22,99 -> average(A)= 44.
    Ta thấy abs(22-average(A))=22. là nhỏ nhất. Vậy số trung vị là 22 mà ko cần phải sắp xếp

  7. #7
    Ngày gia nhập
    10 2010
    Bài viết
    21

    Rất cám ơn, tại mình quên toán PT rồi nên ko rõ phải kêu là Trung vị ko. Nhưng AV hình như gọi là Median, đại khái nó là cái số [mà nếu sắp xếp mảng rồi thì nằm ở vị trí n/2].

    Chứ xét vd dãy 10 15 20 25 50 thì số trung bình là 24, nhưng theo yêu cầu phải cho ra Median là 20 ch71 ko phải 25..

    Nói chung số median là số vừa nhỏ hơn phân nửa số phần tử có trong mảng VÀ vừa lớn hơn phân nửa số pt có trong mảng...


    À, tại thầy đang dạy tới khúc Chia để trị, sẵn hứng ổng cho bài tập rồi n1oi về nộp làm KT luôn :| Nên bảo đảm là phải áp dụng cái Chia Để Trị rồi

  8. #8
    Ngày gia nhập
    12 2010
    Nơi ở
    Hà Nội
    Bài viết
    60

    Mặc định mình tìm cách chuyển sang C++ rồi này

    C++ Code:
    1. void FindMedian(int A[],int n, int k)
    2. {
    3.     int L,R,i,j,temp,x;
    4.     L   =   0;
    5.     R   =   n-1;
    6.  
    7.     while(L < R)
    8.     {
    9.         x   =   A[k];
    10.         i   =   L;
    11.         j   =   R;
    12.         while(i < j)
    13.         {
    14.             while (A[i] < x) i++;
    15.             while (A[j] > x) j--;
    16.  
    17.             if(i <= j)
    18.             {
    19.                 temp    =   A[i];
    20.                 A[i]    =   A[j];
    21.                 A[j]    =   temp;
    22.                 i++;
    23.                 j--;
    24.                
    25.                 for(int i = 0; i < n; i++)
    26.                     cout << A[i] << "   ";
    27.                 cout << endl << endl;
    28.  
    29.             }
    30.         }
    31.         if(j < k) L = i;
    32.         if(k < i) R = j;
    33.     }
    34. }
    35.  
    36. void main()
    37. {
    38.  
    39.     int A[] =   {19,47,13,31,8,68,74,89,40,6,25,98,87,10,54};
    40.     int n   =   sizeof(A)/sizeof(int);
    41.  
    42.     for(int i = 0; i < n; i++)
    43.         cout << A[i] << "   ";
    44.     cout << endl<<endl;
    45.  
    46.     FindMedian(A,n,n/2);
    47.  
    48.     for(int i = 0; i < n; i++)
    49.         cout << A[i] << "   ";
    50.     cout << endl;
    51. }
    hihi!

  9. #9
    Ngày gia nhập
    12 2010
    Nơi ở
    Hà Nội
    Bài viết
    60

    Trích dẫn Nguyên bản được gửi bởi Voldedore Xem bài viết
    Rất cám ơn, tại mình quên toán PT rồi nên ko rõ phải kêu là Trung vị ko. Nhưng AV hình như gọi là Median, đại khái nó là cái số [mà nếu sắp xếp mảng rồi thì nằm ở vị trí n/2].

    Chứ xét vd dãy 10 15 20 25 50 thì số trung bình là 24, nhưng theo yêu cầu phải cho ra Median là 20 ch71 ko phải 25..

    Nói chung số median là số vừa nhỏ hơn phân nửa số phần tử có trong mảng VÀ vừa lớn hơn phân nửa số pt có trong mảng...


    À, tại thầy đang dạy tới khúc Chia để trị, sẵn hứng ổng cho bài tập rồi n1oi về nộp làm KT luôn :| Nên bảo đảm là phải áp dụng cái Chia Để Trị rồi
    của bạn mình làm cho rồi này !

  10. #10
    Ngày gia nhập
    10 2010
    Bài viết
    21

    Hi, cám ơn bạn nhe

    ?/Hic, mình nghĩ cả chiều mà ko ra

Các đề tài tương tự

  1. Source Code C# Lọc trung vị ( Median Filter ) - Xử lý ảnh
    Gửi bởi banglsvn trong diễn đàn Dự án & Source code C#, ASP.NET
    Trả lời: 7
    Bài viết cuối: 16-10-2016, 09:48 AM
  2. Lập trình C chọn phần tử median trong mảng
    Gửi bởi hunterkhanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 23-12-2010, 09:50 PM
  3. tìm phần tử median trong mảng
    Gửi bởi hunterkhanh trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 23-12-2010, 04:11 PM
  4. Số Median
    Gửi bởi Dark Knight trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 24-07-2009, 08:15 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn