7
Tôi có thể tìm thấy trung vị với 12 so sánh. Nhưng tôi muốn biết số lượng so sánh tối thiểu và cách thực hiện.Số so sánh tìm trung vị của 7 số
A
Trả lời
7
Donald Knuth có một chương về "Lựa chọn so sánh tối thiểu" trong Tập III của Nghệ thuật lập trình máy tính.
Knuth nói, "không có phương pháp chung [lựa chọn trong số lượng so sánh tối thiểu] là hiển nhiên" nhưng ông đưa ra một số phương pháp chung gần đến mức tối thiểu.
Nhìn vào Bảng 5.3.3–1, chúng ta có thể thấy rằng V₄ (7) = 10 (nghĩa là bạn có thể tìm thấy 4 mục lớn nhất thứ 4 sử dụng tối đa 10 so sánh) và thuật toán (tìm thấy thủ công bằng cách thử và sai ") được đưa ra trong giải pháp để thực hiện 5.3.3–10.
+1
Có vẻ như TAoCP là cần thiết. @ - @ – zerr
+0
@zerr, Không nghi ngờ gì, Nó luôn luôn là cần thiết –
1
Nếu bạn cho phép so sánh song song (CPU hiện đại có thể sẽ làm điều này cho bạn), bạn có thể sử dụng sorting network để khắc phục sự cố trong sáu bước.
+0
Bạn có thể cung cấp tham chiếu đến việc thực hiện so sánh 6 không? Thanks –
+0
Chắc chắn, ở đây bạn đi: http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Rafe
+0
Tôi thấy bài viết đó nhưng tôi nghĩ rằng nó không thể nói rằng n = 7 có thể được thực hiện với 6 so sánh . –
Tôi muốn xem triển khai của bạn - dường như tôi không thể thực hiện điều đó trong ít hơn 18 hoạt động. –
Đối với a, b, c, d, e, f, g, hãy thử
zerr