Pokrycie biletów lotto z podręcznika projektowania algorytmów?

Question

Czytam Podręcznik projektowania algorytmów autorstwa Stevena S. Skieny. Jestem w pierwszym rozdziale, czytając o problemie z loterią. Twierdzi, że jego pierwsze rozwiązanie dotyczące optymalnej liczby biletów na gwarantowaną wygraną było nieprawidłowe. Nie rozumiem, jak jego następne i ostateczne rozwiązanie jest poprawne?

W figure 1.11 mówi: Gwarantuję wygraną parę od {1,2,3,4,5} za pomocą tylko biletów {1,2,3} i {1, 4, 5} i tam jest schemat. Jestem zdezorientowany, dlaczego nie ma tam innych numerów? Na przykład, co jeśli zwycięskie liczby były (3,4), (2,4), (2,5), (3,5), etc ...? Oczywiście nie można łączyć biletów razem, więc jak możemy to wyjaśnić? Czy ktoś może mi wyjaśnić? W loterii, jeśli powiedzieli, że zwycięskie liczby to 3 i 5, musisz mieć jeden bilet, który ma 3 i 5 w jakiejś kolejności. Czuję się zagubiony w tym.

Answer 1

W przykładzie

• n = 5 - Numery od psychicznej
• j = 3 - ilości wygranych numerach od n
• K = 3 - liczbę przedziałów na bilecie
• l = 2 - liczba meczów potrzebnych, aby uzyskać cenione

Co sprawia, że ​​to sprawa prosta, jest fakt, że wszystkie numery na bilecie musi wynosić od 1..5. Dzieje się tak dlatego, że j = k oznacza, że ​​liczba zwycięskich liczb mieszcząca się w przedziale od 1 do 5 odpowiada liczbie miejsc na bilecie.

Weź więc bilety {1, 2, 3} i {1, 4, 5}. To naprawdę oznacza, że ​​brakuje ci meczu {3, 5}, ale jeśli numery {3, 5} znajdują się na bilecie, to drugi numer na bilecie musi pochodzić z zestawu {1, 2, 4}. Jeśli jest to 1, to mecz 3 został podniesiony przez pierwszy bilet, jeśli jest to 2, to wtedy, jeśli jego 5, drugi bilet go złapie.

Answer 2

Na rysunku 1.11 liczba miejsc na każdym z biletów wynosi 3. Są więc 3 zwycięskie liczby. Z dwoma biletami {1,2,3} i {1,4,5} masz co najmniej 2 z 3 zwycięskich numerów.