7 개의 숫자의 중간 값을 찾는 비교 횟수

12 개의 비교를 통해 중간 값을 찾을 수 있습니다. 그러나 최소 비교 횟수와이를 수행하는 방법을 알고 싶습니다.7 개의 숫자의 중간 값을 찾는 비교 횟수

2010-11-11 zerr

나는 귀하의 구현을보고 싶습니다. 18 개 미만의 작업에서는 그것을 수행 할 수 없습니다. –

a, b, c, d, e, f, g에 대해 a zerr

Donald Knuth는 볼륨 III의 "최소 비교 선택"에 관한 장을 컴퓨터 프로그래밍 기술으로두고 있습니다.

Knuth는 "최소의 비교 수에서 선택하는 일반적인 방법은 아직 없습니다"라고 말하지만 그는 최소한에 가까운 몇 가지 일반적인 방법을 제시합니다.

표 5.3.3-1을 보면 V4 (7) = 10 (즉, 최대 10 개의 비교를 사용하여 7 개 항목 중 네 번째로 큰 항목을 찾을 수 있음)과 알고리즘 ("수동으로 찾음 시행 착오로 ") 5.3.3-10 운동 방법에 주어진다.

2010-11-11 12:32:42

TAoCP가 필요합니다. @ - @ – zerr

@zerr 의심의 여지없이 항상 필요합니다 –

병렬로 비교할 수있는 경우 (현대 CPU가이 작업을 수행 할 가능성이 높음) sorting network을 사용하여 6 단계로 문제를 해결할 수 있습니다.

2010-11-11 23:38:16 Rafe

6 비교 구현에 대한 참조를 제공해 주시겠습니까? 감사합니다 –

물론, 여기에 간다 : http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Rafe

나는 그 기사를 보았다. 그러나 나는 그것이 n = 7이 6 번의 비교로 끝날 수 있다고 말한다고 생각하지 않는다고 생각한다. . –

답변