Dự án Euler # 163 sự hiểu biết

Question

Tôi đã dành khá nhiều thời gian tìm kiếm giải pháp cho this problem. Tôi đã vẽ vô số hình tam giác chéo, đếm hình tam giác trong những trường hợp đơn giản, và tìm kiếm một số loại hoa văn. Thật không may, tôi đã đâm vào tường. Tôi khá chắc chắn kỹ năng lập trình/toán của tôi không đáp ứng được yêu cầu trước cho vấn đề này.

Vì vậy, tôi đã tìm thấy giải pháp trực tuyến để có quyền truy cập vào diễn đàn. Tôi không hiểu hầu hết các phương pháp, và một số dường như quá phức tạp.

Có ai có thể cho tôi biết sự cố này không? Một trong những phương pháp được tìm thấy ở đây: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Sự cố C) được phép sử dụng một chức năng duy nhất.

Làm thế nào để họ tìm ra giải pháp đó? Tại thời điểm này, tôi thực sự muốn hiểu một số khái niệm đằng sau vấn đề thú vị này. Tôi biết tìm kiếm giải pháp không phải là một phần của tinh thần Euler, nhưng tôi khá chắc chắn rằng tôi sẽ không giải quyết vấn đề này dù sao đi chăng nữa.

Answer 1

Đây thực chất là một vấn đề trong tổ hợp liệt kê, đó là nghệ thuật kết hợp đếm sự vật. Đó là một chủ đề đẹp, nhưng có lẽ phải mất một số ấm lên trước khi bạn có thể đánh giá cao các thủ thuật ninja trong tài liệu tham khảo bạn đã đưa ra.

Mặt khác, các nhận xét trong chuỗi giải pháp cho vấn đề cho thấy nhiều người đã giải quyết được vấn đề bằng cách sử dụng phương pháp tiếp cận vũ lực. Một trong những thủ thuật phổ biến nhất liên quan đến việc lấy tất cả các kết hợp có thể có của ba dòng trong biểu đồ và xem liệu chúng có tạo ra một hình tam giác nằm trong tam giác lớn nhất hay không.

Bạn có thể cắt giảm không gian tìm kiếm một cách đáng kể bằng cách lưu ý rằng các dòng nằm trong một trong sáu hướng. Vì một sự kết hợp của các dòng bao gồm hai dòng song song sẽ không tạo ra một tam giác, bạn có thể lặp qua ba dòng để mỗi dòng trong ba có một hướng khác nhau.

Cho ba dòng, tính điểm giao nhau của chúng. Bạn sẽ có ba khả năng 1) các đường là trùng hợp - tất cả đều giao nhau trong một điểm chung 2) hai trong số các đường giao nhau tại một điểm bên ngoài tam giác 3) tất cả ba điểm giao nhau là khác biệt, và tất cả đều nằm trong hình tam giác bên ngoài

Chỉ cần đếm điều kiện thỏa mãn combo (3) và bạn đã hoàn tất. Số lượng các combo đường thẳng mà bạn phải kiểm tra là O (n), không bị cấm.

EDIT1: đọc lại câu hỏi của bạn, tôi nhận được ấn tượng rằng bạn có thể quan tâm hơn đến việc giải thích về giải pháp/công thức tổ hợp hơn phác thảo phương pháp tiếp cận vũ phu. Nếu đúng như vậy, hãy nói như vậy và tôi sẽ xóa câu trả lời này.Nhưng tôi cũng nói rằng câu hỏi trong trường hợp đó sẽ không phù hợp với trang web này.

EDIT2: Xem thêm a combinatorics solution by Bill Daly and others. Nó là toán học nhẹ nhàng hơn một chút.

Answer 2

Tôi chưa giải quyết được sự cố này cho project euler và tôi sẽ tắt câu hỏi và giải pháp bạn đã cung cấp. Trong trường hợp của hàm đơn, phương pháp được trình bày cuối cùng là tìm mẫu đơn giản. Người giải quyết đã phá vỡ câu hỏi được trình bày thành ba phần, dựa trên các loại hình tam giác có mặt từ các nút giao. Đó là một sản phẩm khá tiêu chuẩn đối với loại vấn đề này, phá vỡ mô hình lớn hơn thành những hình nhỏ hơn để giải quyết dễ dàng hơn. Các hàm được sử dụng để biểu diễn các dạng tam giác khác nhau mà tôi chỉ có thể giả định được tạo ra với một mẫu tìm kiếm rất cấp tính hoặc một số lý thuyết/hình học số. Nó cũng nằm ngoài phạm vi giải thích và kiến ​​thức của tôi. Vấn đề này không liên quan gì tới lập trình. Về cơ bản nó hoàn toàn là toán học. Nếu bạn đọc qua trang web bạn thích, bạn có thể thấy logic đã trải qua để tiếp cận các câu hỏi.