Permutacje i zagadka z trójkątem

Rozwiąż poniższą zagadkę:


Rozwiązanie i trochę o permutacjach poniżej. Jednak zachęcam spróbować samodzielnie rozwiązać to zadanie.

Rozwiązanie logiczne

Warunkiem poprawności jest to, by żadna liczba x ∈ {1, 2 ,3 d,4 ,5 ,6 ,7} nie sąsiadowała z liczbami x+1 oraz x-1. W zagadce można wyróżnić dwa zbiory: zbiór liczb 1..7 oraz zbiór pozycji układu trójkąta wraz z przyporządkowaną ilością sąsiadów.

  1. Analiza zbioru liczb
    Na pierwszy rzut oka można zauważyć, że zbiór {1 2 3 4 5 6 7} możemy podzielić na dwa podzbiory:

    1. Liczby posiadające jednego sąsiada: {1, 7}
    2. Liczby posiadające dwóch sąsiadów: {2, 3, 4, 5, 6}
  2. Analiza zbioru pozycji ze sobą sąsiadujących
    Dla każdego pola trójkąta należy określić liczbę sąsiadujących pól. Ponumerujmy pola następująco:
    trojkat_pozycjeWedług tego układu można utworzyć podzbiory dla pól posiadających:

    1. Dwóch sąsiadów:
      • 1: {2, 5}
      • 4: {3, 6}
      • 7: {5, 6}
    2. Czterech sąsiadów:
      • 2: {1, 3, 5, 6}
      • 3: {2, 4, 5, 6}
    3. Pięciu sąsiadów:
      • 5: {1, 2, 3, 6, 7}
      • 6: {2,3, 4, 5, 7}

W tym momencie należy wyszukać liczby posiadające najmniejszą ilość sąsiadów i umieścić je w pozycjach sąsiadujących z maksymalną ilością pól. W związku z tym liczby {1, 7} (posiadające tylko jedną sąsiadującą liczbę) należy umieścić w polach 5 i 6, które sąsiadują aż z pięcioma innymi.

trojkat_pozycje_step1

Do umieszczenia w pozostałych polach zostały liczby {2, 3, 4, 5, 6}. Zauważamy, że liczba 2 może zostać umieszczona tylko na pozycji 4, a liczba 6 na pozycji 1.

trojkat_pozycje_step2

Zostały tylko trzy liczby: {3, 4, 5}. Wśród dostępnych pól znajdują się dwa sąsiadujące ze sobą {2, 3}. W związku z tym należy wybrać jedną liczbę 4 i umieścić ją w ostatnim polu na samym szczycie, aby rozdzielić liczby 3 i 5 (żeby mogły ze sobą sąsiadować).

trojkat_pozycje_step3

W ostatnim etapie dostępne są liczby 3 i 5, które można umieścić tylko w jednej możliwej kolejności.

trojkat_pozycje_step4

Rozwiązanie programistyczne

Ta zagadka jest dosyć prosta i można ją rozwiązać w pamięci w czasie poniżej minuty.
Poniżej jednak opiszę rozwiązanie tego problemu od strony programistycznej.

Permutacje

Dany jest zbiór {x ∈ X: {1, 2 ,3 d,4 ,5 ,6 ,7}}. Ilość wszystkich możliwości rozłożenia liczb zbioru wynosi P=7!=5040. Jest to wartość na tyle mała, że można wygenerować wszystkie permutacje i sprawdzić poprawność każdej z nich.

Sprawdzenie czy dwie liczby sąsiadują ze sobą

Sprawdzenie poprawności rozmieszczenia liczb w trójkącie

 

Brute force na żywo

Gotowy program do „łamania trójkąta”:

To również może Cię zainteresować:

  • Permutacje, cz. 2 – algorytmyPermutacje, cz. 2 – algorytmy W poprzednim wpisie programistyczne rozwiązanie zagadki polegało na wygenerowaniu wszystkich permutacji zbioru i sprawdzeniu każdej z nich pod względem spełnienia warunku […]
  • Zagadka – znajdź zakodowane hasłoZagadka – znajdź zakodowane hasło Zadanie polega na odgadnięciu zakodowanego w poniższym kodzie QR hasła dostępu. Powodzenia 🙂  
  • Idź na całość – paradoks Monty’ego HallaIdź na całość – paradoks Monty’ego Halla Pod koniec lat dziewięćdziesiątych TV Polsat emitował popularny teleturniej Idź na całość. Główna zasada gry była oparta na paradoksie Monty Halla, a polegała na podjęciu decyzji czy […]
  • PHP 7 został wydanyPHP 7 został wydany 3 grudnia 2015 została wydana oficjalna wersja PHP 7.0.0., w której wydajność w stosunku do PHP 5.6 została zwiększona nawet dwukrotnie. To, na co prawie każdy programista PHP czekał, to […]
  • Zagadki algorytmiczne #3 – połowa sumy tablicyZagadki algorytmiczne #3 – połowa sumy tablicy Otrzymujesz listę liczb całkowitych. Twoim zadaniem jest zwrócenie jednego z jej elementów x, który spełnia warunek 2 * x = suma pozostałych elementów. Masz zagwarantowane, że element x […]
  • Origin brute force, czyli Battlefield 3 za darmoOrigin brute force, czyli Battlefield 3 za darmo Był kiedyś na Facebooku taki profil jak "Cyfrowe gry EA", na którym często umieszczane były klucze do gier za darmo. Pewnego dnia wysłali mniej więcej taką wiadomość: Do zdobycia za […]

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *