Thách thức Tuần 339

Mỗi tuần, Mohammad S. Anwar phát động Thách Thức Tuần, tạo cơ hội cho tất cả chúng ta tìm ra giải pháp cho hai nhiệm vụ hàng tuần. Bài viết này sẽ trình bày giải pháp của tôi được viết bằng Python trước, sau đó chuyển đổi sang Perl. Đây là một cách tuyệt vời để chúng ta thực hành lập trình.

Nội dung

• Nhiệm vụ 1: Tìm Hiệu Sản Phẩm Tối Đa
• Giải pháp của tôi
• Nhiệm vụ 2: Tìm Điểm Đỉnh
• Mẹo hiệu suất
• Lỗi thường gặp
• Câu hỏi thường gặp

Nhiệm vụ 1: Tìm Hiệu Sản Phẩm Tối Đa

Nhiệm vụ

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 đoạn mã để 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 sản phẩm của chúng là lớn nhất có thể.

Cuối cùng, trả về hiệu tối đa.

Với hai cặp (a, b) và (c, d), hiệu sản phẩm được tính là (a * b) - (c * d).

Giải pháp của tôi

Nhiệm vụ này thực sự đã thách thức tôi. Tôi đã tìm ra một giải pháp, nhưng không hài lòng với nó. Mohammad đã khen tôi tuần trước vì không "chỉ dùng brute-force để tìm câu trả lời". Nhưng tuần này tôi đã thất bại :-/

Mục tiêu là tìm các cặp số đại diện cho sản phẩm thấp nhất và cao nhất. Nếu tôi lấy danh sách -4 -10 2 0, giá trị thấp nhất là -8 (-4 × 2) và giá trị cao nhất là 40 (-4 × -10). Tuy nhiên, điều này sử dụng giá trị -4 hai lần, và do đó không khả thi. Tôi đã nghĩ đến nhiều cách để giải quyết vấn đề này, nhưng chưa tìm ra cách nào tốt. Tôi rất muốn đọc cách mà các thành viên khác trong Nhóm PWC đã giải quyết.

Cách tiếp cận mà tôi đã chọn là tìm tất cả các kết hợp của 4 số từ danh sách đầu vào. Trong Python, điều này được thực hiện bằng cách sử dụng hàm combinations từ thư viện itertools. Mô-đun Algorithm::Combinatorics cung cấp chức năng tương tự trong Perl.

Đối với mỗi kết hợp, tôi tính toán hiệu số tuyệt đối tối đa giữa ba kết hợp có thể của các cặp (1 2, 3 4; 1 3, 2 4; và 1 4, 2 3). Nếu hiệu này cao hơn bất kỳ giá trị tối đa trước đó, tôi sẽ cập nhật biến solution.

from itertools import combinations

def max_diff(ints: list) -> int:
    solution = 0

    # Tính tất cả các kết hợp của 4 số nguyên
    for c in combinations(ints, 4):
        # Tính hiệu tối đa cho kết hợp này
        diff = max(
            abs((c[0] * c[1]) - (c[2] * c[3])),
            abs((c[0] * c[2]) - (c[1] * c[3])),
            abs((c[0] * c[3]) - (c[1] * c[2])),
        )
        if diff > solution:
            solution = diff

    return solution

Có thể đây là giải pháp tốt nhất. Ngay cả với một danh sách 100 phần tử, có ít hơn 4 triệu kết hợp, có thể được tính toán khá nhanh.

Ví dụ

$ ./ch-1.py 5 9 3 4 6
42

$ ./ch-1.py 1 -2 3 -4
10

$ ./ch-1.py -3 -1 -2 -4
10

$ ./ch-1.py 10 2 0 5 1
50

$ ./ch-1.py 7 8 9 10 10
44

Nhiệm vụ 2: Tìm Điểm Đỉnh

Nhiệm vụ

Bạn được cung cấp một mảng tăng độ cao.

Viết một đoạn mã để tìm điểm đỉnh đạt được.

Giải pháp của tôi

Nhiệm vụ này tương đối đơn giản nên không cần nhiều giải thích. Tôi có hai biến current_altitude ghi lại độ cao hiện tại trong khi peak ghi nhận độ cao cao nhất. Cả hai giá trị đều bắt đầu từ 0.

Sau đó, tôi lặp qua danh sách đầu vào với biến gain. Trong mỗi vòng lặp, tôi tăng giá trị current_altitude với gain. Nếu giá trị này cao hơn biến peak hiện tại, tôi cập nhật peak với độ cao mới.

Cuối cùng, tôi trả về giá trị peak.

def peak_point(gains: list) -> int:
    current_altitude = 0
    peak = 0

    for gain in gains:
        current_altitude += gain
        if current_altitude > peak:
            peak = current_altitude

    return peak

Ví dụ

$ ./ch-2.py -5 1 5 -9 2
1

$ ./ch-2.py 10 10 10 25
55

$ ./ch-2.py 3 -4 2 5 -6 1
6

$ ./ch-2.py -1 -2 -3 -4
0

$ ./ch-2.py -10 15 5
10

Mẹo hiệu suất

• Tối ưu hóa thuật toán: Sử dụng các thuật toán hiệu quả để giảm thiểu số lượng phép toán.
• Tránh lặp lại tính toán: Lưu trữ các giá trị đã tính toán để tránh tính toán lại nhiều lần.

Lỗi thường gặp

• Sử dụng giá trị trùng lặp: Đảm bảo các cặp số không có giá trị trùng lặp.
• Không xử lý trường hợp đặc biệt: Luôn kiểm tra các trường hợp đặc biệt trong dữ liệu đầu vào.

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

Làm thế nào để tối ưu hóa thuật toán của tôi?

Tìm hiểu về các thuật toán phức tạp hơn và cách áp dụng các kỹ thuật như chia để trị hoặc quy hoạch động.

Có cách nào khác để giải quyết nhiệm vụ này không?

Có, bạn có thể xem xét các phương pháp khác như sử dụng đệ quy hoặc lập trình động để giải quyết.

Hy vọng rằng bài viết này sẽ giúp bạn nắm vững các kỹ năng lập trình và tìm ra giải pháp cho các bài toán phức tạp hơn trong tương lai. Hãy tham gia vào Thách thức Tuần và chia sẻ phương pháp của bạn!