Chức năng trung bình trong Thư viện Toán C?

Question

Có chức năng toán học nào trong thư viện C để tính MEDIAN của số 'n' không?

Answer 1

để có được trung bình bạn có thể sắp xếp các mảng các con số và thực hiện:

1) trong trường hợp khi số lượng các mặt hàng là số lẻ - số ở giữa

2) trong trường hợp khi số hạng mục thậm chí - trung bình của hai số ở giữa

Answer 2

Here you go.

Answer 3

Không, không có hàm trung bình nào trong thư viện C chuẩn.

Answer 4

Không, không có hàm nào như vậy trong thư viện C chuẩn.

Tuy nhiên, bạn có thể triển khai một (hoặc chắc chắn tìm mã trực tuyến). Một thuật toán O (n) hiệu quả để tìm một trung vị được gọi là "thuật toán lựa chọn" và có liên quan đến quicksort. Đọc tất cả về nó here.

Answer 5

Để tính trung bình bằng thư viện C chuẩn, hãy sử dụng hàm thư viện chuẩn qsort() và sau đó lấy phần tử ở giữa. Nếu mảng là a và có n yếu tố, sau đó:

qsort(a, n, sizeof(a[0]), compare); 
return a[n/2]; 

Bạn phải viết compare chức năng riêng của bạn mà sẽ phụ thuộc vào loại của một phần tử mảng. Để biết chi tiết, tham khảo trang hướng dẫn sử dụng cho qsort hoặc tra cứu nó trong chỉ mục của Kernighan và Ritchie.

Answer 6

truyền thống Phương pháp: (không khuyến khích nếu bạn đang làm việc trên xử lý hình ảnh)

/* median through qsort example */ 
#include <stdio.h> 
#include <stdlib.h> 

#define ELEMENTS 6 

int values[] = { 40, 10, 100, 90, 20, 25 }; 

int compare (const void * a, const void * b) 
{ 
    return (*(int*)a - *(int*)b); 
} 

int main() 
{ 
    int n; 
    qsort (values, ELEMENTS, sizeof(int), compare); 
    for (n=0; n<ELEMENTS; n++) 
    { printf ("%d ",values[n]); } 
    printf ("median=%d ",values[ELEMENTS/2]); 
    return 0; 
} 

Tuy nhiên, hai chức năng để tính toán trung bình cách nhanh nhất mà không cần sắp xếp các mảng của các ứng cử viên. Sau đây là ít nhất 600% nhanh hơn cách thông thường để tính trung bình. Thật không may họ không phải là một phần của thư viện chuẩn C hoặc C++ STL.

phương pháp nhanh hơn:

//===================== Method 1: ============================================= 
//Algorithm from N. Wirth’s book Algorithms + data structures = programs of 1976  

typedef int_fast16_t elem_type ; 

#ifndef ELEM_SWAP(a,b) 
#define ELEM_SWAP(a,b) { register elem_type t=(a);(a)=(b);(b)=t; } 

elem_type kth_smallest(elem_type a[], uint16_t n, uint16_t k) 
{ 
    uint64_t i,j,l,m ; 
    elem_type x ; 
    l=0 ; m=n-1 ; 
    while (l<m) { 
    x=a[k] ; 
    i=l ; 
    j=m ; 
    do { 
    while (a[i]<x) i++ ; 
    while (x<a[j]) j-- ; 
    if (i<=j) { 
    ELEM_SWAP(a[i],a[j]) ; 
    i++ ; j-- ; 
    } 
    } while (i<=j) ; 
    if (j<k) l=i ; 
    if (k<i) m=j ; 
    } 
    return a[k] ; 
} 

    #define wirth_median(a,n) kth_smallest(a,n,(((n)&1)?((n)/2):(((n)/2)-1))) 

//===================== Method 2: ============================================= 
//This is the faster median determination method. 
//Algorithm from Numerical recipes in C of 1992 

elem_type quick_select_median(elem_type arr[], uint16_t n) 
{ 
    uint16_t low, high ; 
    uint16_t median; 
    uint16_t middle, ll, hh; 
    low = 0 ; high = n-1 ; median = (low + high)/2; 
    for (;;) { 
    if (high <= low) /* One element only */ 
    return arr[median] ; 
    if (high == low + 1) { /* Two elements only */ 
    if (arr[low] > arr[high]) 
    ELEM_SWAP(arr[low], arr[high]) ; 
    return arr[median] ; 
    } 
    /* Find median of low, middle and high items; swap into position low */ 
    middle = (low + high)/2; 
    if (arr[middle] > arr[high]) 
    ELEM_SWAP(arr[middle], arr[high]) ; 
    if (arr[low] > arr[high]) 
    ELEM_SWAP(arr[low], arr[high]) ; 
    if (arr[middle] > arr[low]) 
    ELEM_SWAP(arr[middle], arr[low]) ; 
    /* Swap low item (now in position middle) into position (low+1) */ 
    ELEM_SWAP(arr[middle], arr[low+1]) ; 
    /* Nibble from each end towards middle, swapping items when stuck */ 
    ll = low + 1; 
    hh = high; 
    for (;;) { 
    do ll++; while (arr[low] > arr[ll]) ; 
    do hh--; while (arr[hh] > arr[low]) ; 
    if (hh < ll) 
    break; 
    ELEM_SWAP(arr[ll], arr[hh]) ; 
    } 
    /* Swap middle item (in position low) back into correct position */ 
    ELEM_SWAP(arr[low], arr[hh]) ; 
    /* Re-set active partition */ 
    if (hh <= median) 
    low = ll; 
    if (hh >= median) 
    high = hh - 1; 
    } 
    return arr[median] ; 
} 
#endif 

Trong C++ Tôi làm cho các chức năng templated và nếu con số này đang tăng hay giảm (một chiều) cho các chức năng như sử dụng int8_fast_t; int16_fast_t; int32_fast_t; int64_fast_t; uint8_fast_t; uint16_fast_t; các loại thay vì các loại [stdint.h] thông thường (ví dụ: uint16_t; uint32_t, v.v.)

Answer 7

Điều gì về std::nth_element? Nếu tôi hiểu chính xác bản chất của trung bình, điều này sẽ cung cấp cho bạn một số nguyên tố lẻ.