12 개의 비교를 통해 중간 값을 찾을 수 있습니다. 그러나 최소 비교 횟수와이를 수행하는 방법을 알고 싶습니다.7 개의 숫자의 중간 값을 찾는 비교 횟수
답변
Donald Knuth는 볼륨 III의 "최소 비교 선택"에 관한 장을 컴퓨터 프로그래밍 기술으로두고 있습니다.
Knuth는 "최소의 비교 수에서 선택하는 일반적인 방법은 아직 없습니다"라고 말하지만 그는 최소한에 가까운 몇 가지 일반적인 방법을 제시합니다.
표 5.3.3-1을 보면 V4 (7) = 10 (즉, 최대 10 개의 비교를 사용하여 7 개 항목 중 네 번째로 큰 항목을 찾을 수 있음)과 알고리즘 ("수동으로 찾음 시행 착오로 ") 5.3.3-10 운동 방법에 주어진다.
TAoCP가 필요합니다. @ - @ – zerr
@zerr 의심의 여지없이 항상 필요합니다 –
병렬로 비교할 수있는 경우 (현대 CPU가이 작업을 수행 할 가능성이 높음) sorting network을 사용하여 6 단계로 문제를 해결할 수 있습니다.
6 비교 구현에 대한 참조를 제공해 주시겠습니까? 감사합니다 –
물론, 여기에 간다 : http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Rafe
나는 그 기사를 보았다. 그러나 나는 그것이 n = 7이 6 번의 비교로 끝날 수 있다고 말한다고 생각하지 않는다고 생각한다. . –
나는 귀하의 구현을보고 싶습니다. 18 개 미만의 작업에서는 그것을 수행 할 수 없습니다. –
a, b, c, d, e, f, g에 대해 a zerr