Tìm max trong mảng mà không dùng đến vòng lặp

QuangHung1596 · February 24, 2020, 2:43pm

Em đào đề cũ của trường ra làm thì có gặp 1 câu hỏi lạ lùng dnày ạ

Em có nghĩ đến đệ quy nhưng giả sử nó vẫn là cấu trúc lặp thì mấy anh/chị xem còn thuật toán nào khác nữa không ạ?

phamvandung · February 25, 2020, 12:27am

Nếu goto không phải là lặp thì dùng goto chắc là được :V

LocNguyenXuan99 · February 25, 2020, 1:34am

C#:

using System.Linq;
float FindMax(float a[], int n) => a.Max();

C++

float FindMax(float a[], int n) {
    return *max_element(a, a + n);
}

javascript

function FindMax(a, n) {
  return Math.max(...a);
}

Mục đích là để các bạn khai thác tối đa các hàm built-in thay vì reinvent the wheel.
Mà không biết đúng ý mấy ông thầy không.

rogp10 · February 25, 2020, 1:56am

Nhiều khả năng là không

Hai · February 25, 2020, 3:17am

public static float FindMax(float[] a, int n) {
    float max;
    if (n == 0) {
        return a[0];
    } else {
        max = a[n-1];
    }
    return Math.max(max, FindMax(a, n-1);
}

Dùng đệ quy thử xem =)))

anon12276517 · February 25, 2020, 4:40am

Nhưng thực chất thì các hàm built in vẫn đùng đến lặp mà nhỉ @@

SITUVN.gcd · February 25, 2020, 5:17am

Nói chung là phải lặp hoặc đệ quy thì mới xét hết các giá trị trong mảng được.

noz1995 · February 25, 2020, 5:24am

if(n < 1)
    throw exception;
if(n == 1)
    return a[0]
if(n == 2)
    return max(a[0], a[1]);
if(n == 3)
{
    if(a[0] > a[1])
        if(a[0] > a[2])
            return a[0];
        else
            return a[2];
    else
        if(a[1] > a[2])
            return a[1];
        else
            return a[2]
}
...

Lovemagic · February 25, 2020, 5:46am

sort mảng rồi lấy giá trị đầu (cuối) có đc tính k?

Hai · February 25, 2020, 5:48am

Sort vẫn dùng loop, mà độ phức tạp còn cao hơn nữa =)))

Lovemagic · February 25, 2020, 5:51am

nói trên câu chữ chứ bóc tách hàm built-in họ vẫn sử dụng loop mà

LocNguyenXuan99 · February 25, 2020, 6:05am

if(n < 1)
if(n == 1)
if(n == 2)
if(n == 3)
...
if(n == 96000)

Kiểu này thà rớt chứ không làm một dev ngu.
Code khó đọc, khó bảo trì. Giờ nó yêu cầu nhập n từ bàn phím thì chỉ có cách gen code rồi gọi gcc compile lại.

Cũng vì lý do các thầy thích ra đề kiểu thể hiện pro như thế này mà sinh viên chả học được cái gì, đi làm phải hướng dẫn lại từ coding convention đến việc đọc tài liệu để sử dụng thư viện. Đa phần toàn muốn xây dựng thư viện mới cho nhanh.

rogp10 · February 25, 2020, 6:21am

Sort lặp còn ghê hồn hơn

hungaya · February 25, 2020, 7:23am

Do thớt giả sử đó, không phải lỗi của thầy đâu :v

rogp10 · February 25, 2020, 8:08am

Cũng không khác nhau mấy đâu bạn

QuangHung1596 · February 25, 2020, 10:13am

Nghĩa là em phải ghi nguồn đề bài hả anh?

QuangHung1596 · February 25, 2020, 10:28am

Trước khi đăng bài thì em đã chắc chắn trong đầu rằng không thể có thuật toán như vậy rồi ạ, nhưng dù sao đây cũng là đề KTLT của trường em (1 trường khá lớn) nên em mới đăng bài để biết đâu còn một mẹo gì đó mà em không nghĩ tới.

Bài đó là của năm 2014, còn đây là bài trong đề 2012 ạ (sắp xếp không dùng lặp)
Sắp xếp thì em chưa tìm hiểu hết nên không biết ý kiến của mấy anh/chị như nào ạ?

rogp10 · February 25, 2020, 11:55am

Sort là hai vòng lặp lồng nên muốn đệ quy thì phải viết thêm hàm nữa.

noname00 · February 25, 2020, 12:56pm

Tìm max mà nếu code C++ thì dễ rồi.

return *std::max_element(a, a+n);

Sort không dùng lặp mà lại float nữa thì radix có ổn không nhỉ

rogp10 · February 25, 2020, 1:14pm

Radix ăn chặt ở chỗ số lần duyệt và mem không đổi mà chứ logic bên trong phức tạp hơn insertion với selection nhiều.