Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 12 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. #11
    Ngày gia nhập
    09 2010
    Bài viết
    207

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

    C++ Code:
    1. //
    2. // LearnCpp.cpp : Defines the entry point for the console application.
    3. //
    4.  
    5. #include<stdio.h>
    6. #include<conio.h>
    7. #include<iostream>      
    8. #include<math.h>
    9. using namespace std;
    10.  
    11.  
    12. int FindMedian(int arr[], int n) {
    13.     for(int i=0; i<n; i++) {
    14.         int left = 0, right = 0;
    15.         for(int j=0; j<n; j++) {
    16.             if(arr[i] > arr[j])
    17.                 left++;
    18.             else if(arr[i] < arr[j])
    19.                 right++;
    20.         }
    21.         if(abs(left-right) <= 1) {
    22.             return arr[i];
    23.         }
    24.     }
    25.     return -1;
    26. }
    27. int main() {
    28.     int a[] = {47,13,31,8,68,74,89,19,6,25,98,87,10,54,40};
    29.     cout << FindMedian(a, 15) << endl;
    30.  
    31.     system("pause");
    32.     return 0;
    33. }
    C++ Code:
    1. while ( ! Love(I, You) )
    2.     try { Send(I, You, ..... ); .....; } catch (LoveException lvex) { fix_error(); }
    3. Marry ( I, You );
    4. while ( true )
    5.     try { ....together; } catch (Exception ex) { remove_bad_things(); }

  2. #12
    Ngày gia nhập
    11 2018
    Nơi ở
    Hà Nội
    Bài viết
    1

    Em đọc một cuốn sách của thầy Hoàng , có một thuật cũng là Quicksort như thế này, nhưng mà là tìm khóa thứ p chứ không phải là (n+1)/2 ( cơ bản thì thay p thành n+1/2 là đc )
    Ta trước hết viết hàm Select(L,H,p) trả về khóa đứng thứ p khi sắp xếp dãy khóa k[L...H]
    Nếu dãy có nhỏ hơn 50 khóa thì dùng insertion sort trả về k[L+p-1]
    Dãy của mình là k[0...n-1] thì ta chia các khóa l[L...H] thành các nhóm 5 khóa :
    k[L+0...L+4]
    k[L+5...L+9]
    ... ( đến hết )
    Nếu cuối cùng quá trình chia nhóm mà còn lại ít hơn 5 khóa ( nếu độ dài đoạn không chia hết cho 5) ta sẽ bỏ qua không xét những khóa này.
    Với mỗi nhóm 5 khóa kể trên ta sẽ tìm trung vị nhóm - hay khóa đứng thứ ba sau khi sắp xếp 5 khóa và đẩy nó về đầu đoạn k[L...H], cụ thể:
    Trung vị nhóm k[L+0...L+4] thì đảo cho k[L]
    Trung vị nhóm k[L+5...L+9] thì đảo cho K[L+1]
    ................................................. cứ thể
    Coi trung vị nhóm cuối cùng đảo cho k[j] thì các trung vị sẽ tập trung về các vị trí k[L...j] ta đặt Pivot là trung vị của các trung vị nhóm bừng một lệnh gọi đệ quy hàm Select( có nói bên trên) :
    Pivot=Select(L,j,(j-L+1)/2 );
    Khi đã có Pivot thì ta xác định được bao nhiêu khóa trong đoạn k[L...H] nhỏ hơn, bằng, lớn hơn Pivot; nếu giá trị cần tìm bằng Pivot thì trả về Pivot trong kết quả hàm, nếu nhỏ hơn thì dồn các khóa nhỏ hơn Pivot trong đoạn L-> H về đầu đoạn và gọi đệ quy đoạn đầu này, tương tự nếu lớn hơn.

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