Giới thiệu

Trong bài viết này, chúng ta sẽ khám phá một bài toán thú vị về việc tìm hai cặp số trong một mảng số nguyên sao cho hiệu số giữa các tích của chúng là lớn nhất. Đây là một bài toán khá đơn giản để phát biểu nhưng lại thách thức trong việc thực hiện một cách hiệu quả. Hãy cùng tìm hiểu cách giải quyết bài toán này với các phương pháp tối ưu.

Nội dung bài toán

Bài toán 1: Max Diff

Bạn được cung cấp một mảng số nguyên có bốn phần tử trở lên. Viết một script để tìm hai cặp số từ danh sách này (tổng cộng bốn số) sao cho hiệu giữa các tích của chúng là lớn nhất có thể. Cuối cùng, trả về hiệu số tối đa. Với hai cặp (a, b) và (c, d), hiệu số sản phẩm được tính là (a * b) - (c * d).

Ví dụ

• Ví dụ 1:

  • Đầu vào: @ints = (5, 9, 3, 4, 6)
  • Đầu ra: 42
    • Cặp 1: (9, 6) Cặp 2: (3, 4)
    • Hiệu số sản phẩm: (9 * 6) - (3 * 4) => 54 - 12 => 42

• Ví dụ 2:

  • Đầu vào: @ints = (1, -2, 3, -4)
  • Đầu ra: 10
    • Cặp 1: (1, -2) Cặp 2: (3, -4)

• Ví dụ 3:

  • Đầu vào: @ints = (-3, -1, -2, -4)
  • Đầu ra: 10
    • Cặp 1: (-1, -2) Cặp 2: (-3, -4)

• Ví dụ 4:

  • Đầu vào: @ints = (10, 2, 0, 5, 1)
  • Đầu ra: 50
    • Cặp 1: (10, 5) Cặp 2: (0, 1)

• Ví dụ 5:

  • Đầu vào: @ints = (7, 8, 9, 10, 10)
  • Đầu ra: 44
    • Cặp 1: (10, 10) Cặp 2: (7, 8)

Quy trình tư duy

Để giải bài toán này, chúng ta có thể bắt đầu bằng cách thử nghiệm với phương pháp brute force, tức là kiểm tra mọi kết hợp của bốn phần tử trong mảng. Tuy nhiên, phương pháp này có thể gây ra vấn đề về hiệu suất, vì độ phức tạp của nó là O(n^4) nếu thực hiện bằng vòng lặp lồng nhau.

Ví dụ mã nguồn

sub maxDiff_BF(@int) {
    my $max = 0;
    for my $w (0 .. $#int) {
        for my $x (0 .. $#int) {
            next if $x == $w;
            for my $y (0 .. $#int) {
                next if $y == $x || $y == $w;
                for my $z (0 .. $#int) {
                    next if $z == $y || $z == $x || $z == $w;

                    my ($a, $b, $c, $d) = @int[$w,$x,$y,$z];

                    my $diff = max($a*$b - $c*$d, $c*$d - $a*$b);
                    $max = $diff if $diff > $max;
                }
            }
        }
    }
    return $max;
}

Ghi chú

• next if $x == $w – Trong mỗi vòng lặp, chúng ta không thể tái sử dụng các phần tử.
• my ($a, $b, $c, $d) = @int[$w,$x,$y,$z] – Sử dụng một mảng để truy cập bốn phần tử một lần và chuyển đổi các biến sang ngôn ngữ của bài toán.

Hiệu suất

Như dự đoán, hiệu suất của phương pháp này rất kém. Nó không thể hiện rõ trên những ví dụ đơn giản, nhưng khi cho một danh sách 75 số, máy tính của tôi phải mất 12 đến 15 giây để đưa ra câu trả lời. Trong bối cảnh hiện tại, việc tiêu tốn thời gian xử lý như vậy là không khả thi.

Một điều tôi nhận thấy nhanh chóng là tôi muốn có một sản phẩm có độ lớn tối đa, điều này có thể đạt được bằng cách nhân hai phần tử lớn nhất trong mảng. Nếu sản phẩm đó là số âm, tôi sẽ chọn nó làm cặp (c,d) để thêm vào hiệu số của mình.

Cách tiếp cận tối ưu

Làm thế nào để nhanh chóng lấy được các phần tử lớn nhất? Nếu mảng được sắp xếp, thì những giá trị lớn nhất sẽ nằm ở hai đầu của mảng (đầu trái cho số âm, đầu phải cho số dương). Do đó, sản phẩm lớn nhất sẽ được tạo ra bằng cách nhân hai số lớn nhất hoặc hai số nhỏ nhất của mảng.

Dưới đây là cách thực hiện:

sub maxDiff(@int) {
    @int = sort { $a <=> $b } @int;

    my $nn = $int[0] * $int[1];
    my $pp = $int[-1] * $int[-2];
    my $np = $int[0] * $int[-1];
    my $largest;
    if (abs($nn) > abs($pp)) {
        if (abs($nn) > abs($np)) {
            $largest = $nn;
            shift @int; shift @int;
        } else {
            $largest = $np;
            shift @int; pop @int;
        }
    } else { // pp >= nn
        if (abs($pp) > abs($np)) {
            $largest = $pp;
            pop @int; pop @int;
        } else {
            $largest = $np;
            shift @int; pop @int;
        }
    }

Phần còn lại

Sau khi tìm được giá trị lớn nhất, nếu $largest là số âm, chúng ta sẽ chọn nó làm cặp (c,d) để hiệu số của chúng lớn nhất. Ngược lại, nếu $largest là số dương, chúng ta sẽ cần tìm cặp sản phẩm nhỏ nhất để trừ đi.

Để tìm được cặp sản phẩm nhỏ nhất, chúng ta có thể sử dụng phương pháp sắp xếp để đưa các số nhỏ về hai đầu của mảng:

@int = sort { ($a == 0 ? 2 : 1/$a) <=> ($b == 0 ? 2 : 1/$b) } @int;

Kết luận

Chúng ta đã xem xét một bài toán thú vị về việc tìm kiếm cặp số tối ưu trong một mảng. Việc áp dụng các phương pháp sắp xếp đã giúp giảm độ phức tạp tính toán từ O(n^4) xuống O(n log n). Điều này không chỉ giúp tối ưu hóa hiệu suất mà còn dễ dàng hơn trong việc quản lý mã nguồn.

Thực hành tốt nhất

• Nên sử dụng phương pháp sắp xếp để giảm độ phức tạp.
• Tránh việc sử dụng vòng lặp lồng nhau nếu không cần thiết.

Những cạm bẫy phổ biến

• Không kiểm tra các trường hợp đặc biệt như số âm hoặc số bằng 0.

Mẹo hiệu suất

• Sử dụng các cấu trúc dữ liệu tối ưu để lưu trữ và truy cập nhanh chóng các phần tử.

Câu hỏi thường gặp

1. Bài toán này có thể mở rộng cho các mảng lớn hơn không?
Có, nhưng bạn cần chú ý đến hiệu suất và có thể áp dụng các thuật toán khác nhau.

2. Có cách nào khác để giải quyết bài toán này không?
Có, bạn có thể sử dụng các thư viện hỗ trợ để thực hiện các phép toán phức tạp hơn.

Tài nguyên tham khảo

• Perl Documentation
• Algorithm::Combinatorics