Em không hiểu về bài tìm max này?

[nhocxinh]

int max (int *array, int len)
{
    int n1,n2 ;
    if (len == 0) return array[0];
    n1 = max(array , len/2) ;
    n2 = max(array + len/2 , len - len/2); 
    return (n1 > n2 ? n1 : n2) ;
} 

Em không hiểu về đoạn code trên lắm.Mong các anh giải thích giúp em!!

[rox_rook]

n2 = max(array + len/2 , len - len/2);

Em khó hiểu chắc anh đoán chỗ này, đây là phép cộng con trỏ :
<-> *(array + len/2);
suy nghĩ lại xem ?

[nhocxinh]

Hix.Phép cộng con trỏ thì em học rồi nhưng đoạn code trên có cho ra giá trị max trong mảng không anh?

[rox_rook]

Không em à , sai 1 tí !

#include <iostream> namespace vv{    template <typename T>    T max(T* ary, unsigned size){        if(size == 1)             return ary[0];        return max(ary, size/2) > max(ary + size/2, size - size/2)              ?  max(ary, size/2) : max(ary + size/2, size - size/2);    }} int main(){    int ary[5] = {1,3000,34000,4393,51913};    std::cout << vv::max<int>(ary, 5);}

C version đây luôn em :

#include <cstdio> int max(int* ary, unsigned size){     if(size == 1)         return ary[0];     return max(ary, size/2) > max(ary + size/2, size - size/2)          ?  max(ary, size/2) : max(ary + size/2, size - size/2);} int main(){    int ary[5] = {1,3000,34000,4393,51913};    printf("%d", max(ary, 5));}

[sieuphuong]

À , bài tìm max trong một mảng sử dụng đệ quy hả . bạn xem code này nè :

int max(int *a,int len){ if(len==1) return a[0]; if(a[len-1]>max(a,len-1)) return a[len-1]; else return max(a,len-1);}

Ý tưởng chính của thuật toán đệ quy này là : Ví dụ bài toán tìm ra em học sinh cao nhất trong 1 lớp học . Nếu như lớp đó chỉ có một học sinh thì học sinh đó là người cao nhất . Còn nếu có nhiều học sinh thì ta lấy ra một học sinh bất kỳ trong lớp và đem so sánh với người cao nhất trong đám học sinh còn lại . Nếu như em vừa lấy ra cao hơn em cao nhất trong đám đó thì em đó là cao nhất lớp , ngược lại thì em cao nhất trong đám đó sẽ là người cao nhất.

[rox_rook]

Bài của sieuphuong là đệ qui tail, độ phức tạp không đổi vẫn O(n), trong khi giải thuật của nhocxinh là dạng divide-conquer, code chạy hiệu quả hơn nhiều, O(nlogn)

[nhocxinh]

Thanks các anh nhiều lắm!

int max(int *a, int n)
{
 if (n == 1)
      return a[0];
 else
 {
      if(a[n-1] > a[n-2])
           a[n-2] = a[n-1] ;
      return max(a, n-1) ;
 }
}

Đoạn code trên với đoạn code của anh siêu phương thì độ phức tạp bằng nhau phải không anh?

[sieuphuong]

Bài của sieuphuong là đệ qui tail, độ phức tạp không đổi vẫn O(n), trong khi giải thuật của nhocxinh là dạng divide-conquer, code chạy hiệu quả hơn nhiều, O(nlogn)

Rõ ràng nếu như n tiến đến vô cực thì n < nlogn chứ anh Rok .

[huybka]

Đoạn code của nhocxinh độ phức tạp chỉ là O(log n) thôi.

[rox_rook]

Ặc anh nhầm T_T, thanks cậu Huybk, O(logn). Sorry sieuphuong !