7
Mogę znaleźć medianę z 12 porównaniami. Ale chcę poznać minimalną liczbę porównań i jak to zrobić.Liczba porównań znajduje medianę 7 liczb
A
Odpowiedz
7
Donald Knuth ma rozdział "Wybór minimalnego porównania" w tomie III z Sztuka programowania komputerowego.
Knuth mówi: "żadna ogólna metoda [wyboru w minimalnej liczbie porównań] nie jest jeszcze widoczna", ale podaje pewne ogólne metody, które zbliżają się do minimum.
Patrząc na Tabelę 5.3.3-1, widzimy, że V₄ (7) = 10 (to znaczy, że można znaleźć 4. co do wielkości z 7 pozycji przy użyciu co najwyżej 10 porównań) i algorytmu ("znaleziono ręcznie metodą prób i błędów ") podano w rozwiązaniu, aby wykonać 5.3.3-10.
+1
Wygląda na to, że TAoCP jest konieczne. @ - @ – zerr
+0
@zerr, Bez wątpienia, Zawsze jest to konieczne –
1
Jeśli zezwalasz na porównywanie równolegle (nowoczesny procesor prawdopodobnie zrobi to za Ciebie), możesz użyć narzędzia sorting network, aby rozwiązać problem w sześciu krokach.
+0
Czy możesz podać odniesienie do implementacji 6 porównań? Dzięki –
+0
Oczywiście, proszę bardzo: tutaj: http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html – Rafe
+0
Widziałem ten artykuł, ale uważam, że nie można powiedzieć, że n = 7 można zrobić przy 6 porównaniach . –
Powiązane problemy
- 1. Minimalne nie. porównań, aby znaleźć medianę 3 liczb
- 2. Zdobądź medianę z serii liczb za pomocą Apache Commons Math
- 3. Jak znaleźć medianę
- 4. Znajdź medianę w drzewie wyszukiwania binarnego
- 5. Koszt wydajności porównań typów
- 6. Znaleźć medianę nieposortowanej tablicy
- 7. Znaleźć medianę tablicy?
- 8. Wykonywanie porównań DateTime w filtrze SQLAlchemy
- 9. Liczba rekordów utworzonych w ciągu ostatnich 7 dni
- 10. znaleźć, jeśli istnieje liczba całkowita w postaci listy liczb całkowitych
- 11. znaleźć, jeśli istnieje liczba pomiędzy zakresu liczb podanych przez liście
- 12. Algorytm ustalania, czy liczba jest sumą wielokrotności innych liczb
- 13. Dlaczego liczba # nie działa dla bardzo małych liczb?
- 14. Określanie liczb parzystych/nieparzystych (liczb całkowitych)?
- 15. Jak mogę obliczyć medianę wartości w SQLite?
- 16. Oblicz medianę w strukturze agregacji MongoDB
- 17. Jak zlokalizować medianę na działce KDE (seaborn)?
- 18. Wydajny sposób, aby uzyskać środkową (medianę) std :: set?
- 19. znaczenie (liczba) i (liczba)
- 20. Dodawanie liczb razem
- 21. Konwersje i liczba zmiennoprzecinkowa
- 22. WYSZUKAJ.PIONOWO nie znajduje wartości w tablicy
- 23. Ciągła liczba całkowita działa
- 24. Sortowanie ArrayList mieszane liczb i ciągów zachowując względną kolejność łańcuchów i liczb
- 25. Podział anova i porównań (ortogonalny pojedynczy df) w r
- 26. Generator liczb losowych Crossplatform
- 27. Liczba bitów reprezentujących liczby ujemne
- 28. Java: grupowanie liczb całkowitych
- 29. liczba Liczba przedmiotów z nieruchomości
- 30. Liczba i liczba duplikatów SQL
Chciałbym zobaczyć twoje wdrożenie - nie mogę tego zrobić w mniej niż 18 operacjach. –
Dla a, b, c, d, e, f, g, wypróbuj
zerr