cuốn sách gpt4 ai đã làm

thuật toán - Tạo khối "không trong suốt"

In lại Tác giả: Taklimakan 更新时间:2023-11-03 06:29:16 28 4
mua khóa gpt4 Nike

Tôi đang viết chương trình in chu vi của một hình vuông ra màn hình dựa trên tọa độ và độ dài cạnh do người dùng cung cấp cho mỗi hình vuông.

Nếu các hình vuông chồng lên nhau thì các hình vuông phải chồng lên nhau sao cho hình vuông ở dưới bị hình vuông ở trên che đi.

Thứ tự các khối vuông được đặt theo thứ tự nhập vào chương trình (đầu tiên là ở dưới cùng).

Ví dụ:

&&&&
&&
& &$$$
&&&& $
$ $
$ $
$$$$$

Thuật toán tốt nhất tôi nghĩ ra là độ phức tạp thời gian O(n^2) trên mỗi ô vuông.

Bạn có gợi ý nào về cách làm cho hình vuông trở nên "mờ" không?

câu trả lời hay nhất

bạn đã đề cậpO(n^2) Thuật toán này có thể là "thuật toán của họa sĩ" cổ điển trong đó bạn chỉ cần hiển thị ("rasterize") các ô vuông lần lượt từ dưới lên trên. Đây là một thuật toán rất tốt được sử dụng rộng rãi trong đồ họa máy tính. Tuy nhiên, độ phức tạp về thời gian của bất kỳ thuật toán "raster" nào đều như nhau, trên mỗi ô vuông O(n^2).

Nhưng nếu bạn muốn một thuật toán nhanh hơn tiệm cận, bạn phải tìm thuật toán "vectơ", tức là với bình phươngbênCác thuật toán hoạt động cùng nhau nhưng không lãng phí thời gian xử lý phần bên trong của chúng. Một cách để xây dựng thuật toán như vậy là tính toán trước bố cục cạnh hiển thị cuối cùng ở dạng vectơ và sau đó chỉ vẽ các cạnh hiển thị trên màn hình.

Để đạt được chức năng tương tự, ban đầu mỗi hình vuông phải được biểu diễn bằng một bộ bốn cạnh. rồi một lầndòng quétThuật toán sẽ loại bỏ các cạnh vô hình. Sau đó, bạn có thể hiển thị các cạnh hiển thị còn lại trên màn hình. Thuật toán sẽ phức tạp hơn nhiều so với "thuật toán của họa sĩ" vì bạn phải thực hiện logic quét và loại bỏ cạnh. Nhưng đối với bài toán cụ thể này (đặc biệt khi nó liên quan đến hình học trực giao), nó không khó chút nào.

P.S. Điểm mấu chốt ở đây là cách tiếp cận thứ hai chỉ hoạt động nếu khối chủ sở hữu được biết trước, tức là nó chỉ hoạt động đối với các sự cố ngoại tuyến. Nếu bạn đang giải quyết một vấn đề trực tuyến trong đó bạn phải vẽ một hình vuông ngay khi nhận được từ đầu vào, thay vì biết trước tất cả các hình vuông, thì không có lý do gì để cố gắng cải thiện bất cứ điều gì ở đây trong trường hợp chung. Chỉ cần sử dụng thuật toán của họa sĩ.

Về thuật toán - tạo khối vuông "không trong suốt", chúng tôi tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/19913020/

28 4 0
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress