Strona główna » Algorytmy » Artykuły » Trójkąt Magiczny
 

Trójkąt Magiczny

https://mattomatti.com/a0043

Opis

Trójkąt magiczny to taki trójkąt, którego wartości zapisane wzdłuż z krawędzi jest identyczna. Tego typu trójkąt może mieć różne ilości liczb na każdej z krawędzi, ale na każdej musi być ich tyle samo. Każda liczba występująca w trójkącie musi być unikalna i być liczbą naturalną.

Przykład

Przykład 1

Przykładowo trójkąt o boku a = 3 tj. ma 3 liczby na każdej z krawędzi może wyglądać następująco:

1.10
2.53
3.496

Powyższy trójkąt jest trójkąt magicznym o sumie n = 19, ponieważ 4 + 5 + 10 = 10 + 3 + 6 = 4 + 9 + 6 = 19, a ponadto żadna z liczb nie występuje dwa razy. Warto zauważyć

Przykład 2

Innym przykładem trójkąta magicznego będzie:

1.5
2.34
3.271

Ponownie prawdziwość można wykazać poprzez sprawdzenie sumy krawędzi: 5 + 3 + 2 = 5 + 4 + 1 = 2 + 7 + 1 = 10. Tworząc zbiór liczb użytych w trójkącie {1, 2, 3, 4, 5, 7} można zauważyć, że żadna wartość się nie powtórzyła.

Przykład 3

W przypadku większych trójkątów liczb rozwiązań znacząco się zwiększa. Przykładowym trójkątem o a = 4 i sumie n = 21 jest:

1.1
2.108
3.67
4.4935

W celu sprawdzenia poprawności należy wykazać, że 1 + 10 + 6 + 4 = 1 + 8 + 7 + 5 = 4 + 9 + 3 + 5 = 21. Ponadto w zbiorze liczb użytych do budowy trójkąty żadna się nie powtarza. Jest to więc trójkąt magiczny.

Uwaga

Nie istnieje trójkąt magiczny o boku a = 2. Można tego dowieść w następujący sposób:

1.a
2.bc

Z powyższego trójkąta wypisujemy znane równania: a + b = n, b + c = n oraz a + c = n. Sumując wszystkie równania otrzymujemy 2a + 2b + 2c = 3n. Dzieląc obie strony przez dwa: a + b + c = 1.5n. Wyprowadźmy z wzoru wzór na każdy wyraz a, b, c. Okazuje się, że a = b = c = 0.5n, więc drugi warunek nie zostanie nigdy spełniony.

Implementacja

Wyszkiwanie wszystkich trójkątów

Najprostszym sposobem, który znajdzie wszystkie trójkąty magiczne o boku a i sumie n jest przeszukanie wszystkich możliwości. Jednak jak można się spodziewać tego typu rozwiązanie nie działa za szybko i użytkownik bardzo długo czekałby na odpowiedź. Proces szukania wszystkich trójkątów można podzielić na etapy, który każdy można zoptymalizować.

Na początku warto określić górny róg trójkąta. Wartość, która tam może się znaleźć może być z przedziału [1, n]. Jednak optymalnie jest tam wstawiać wartość z przedziału [i, n - (a - 1)*a/2]. Bierze się z to z faktu, że suma krawędzi to n, a (a - 1)*a/2 to najmniejsza suma trzech liczb naturalnych (są to kolejne a - 1 liczb począwszy od 1). Po wybraniu pierwszej wartości można poszukiwać uzupełnień krawędzi.

Drugi krok polega na wygenerowaniu wszystkich list, których suma elementów oraz wartość wybranego wierzchołka dadzą łącznie n. Elementami z tej listy można uzupełnić obie krawędzie, które łączą się z górnym wierzchołkiem. Należy pamiętać, aby wybrane listy nie miały wspólnego elementu oraz wartość wierzchołka górnego nie może w nich występować. W celu ograniczenia szukanych rozwiązań interesują nas jedynie listy na których kolejność elementów jest malejąca, a listy są wybierane tak, aby pierwsza lista zawsze miała większy indeks niż druga.

W trzecim kroku należy określić, które element z wybranych list trafiają do dolnych wierzchołków. Tylko wtedy możliwe jest wygenerowanie wszystkich list dla dolnej krawędzi, które spełniają fakt, że suma elementów listy oraz wartości w dolnych wierzchołkach jest n.

W celu zliczenia ile jest wszystkich możliwości należy pamiętać, że po drodze dokonywaliśmy pewnych ograniczeń. Po pierwsze trójkąt można obrócić na 3 sposoby. Po drugie listę po lewej i po prawej można zapisać odwrotnie, więc są dwie możliwości. Dodatkowo w listach po lewej i po prawej jest a - 2 elementów pomiędzy wierzchołkami, które można spermutować. Zasada ta dotyczy też a - 2 elementów na dolnej krawędzi. Ostatecznie każdy znaleziony trójkąt magiczny można zapisać na 3·2·((a - 2)!)3 sposobów.

Przykład

Postarajmy się znaleźć wszystkie trójkąty o boku a = 3 oraz n = 11. Wartość górnego wierzchołka zmienia się w zakresie [1, 8]. Dla kolejnych wartości otrzymujemy następujące listy uzupełniające:

WierzchołekLista uzupełniająca
1{(6, 4), (7, 3), (8, 2), (9, 1)}
2{(5, 4), (6, 3), (7, 2), (8, 1)}
3{(5, 3), (6, 2), (7, 1)}
4{(4, 3), (5, 2), (6, 1)}
5{(4, 2), (5, 1)}
6{(3, 2), (4, 1)}
7{(3, 1)}
8{(2, 1)}

Jak można zauważyć wraz z wartości wierzchołka dowola lista sumuje się do n = 11. Przypadki 7 i 8 nie pozwolą utworzyć trójkąta magicznego, ponieważ jest tylko jeden element na liście, a potrzeba conajmniej dwóch różnych. Sposób rozumowania jest identyczny dla każdej wartości wierzchołka, więc rozpatrze przykładowo na przykładzie wartości 1. Najpierw należy rozpatrzeć wszystkie pary list tak, aby pierwsza miała większy indeks niż druga.

WierzchołekLista 1Lista 2Komentarz
1(7, 3)(6, 4)Pasuje
1(8, 2)(6, 4)Pasuje
1(8, 2)(7, 3)Pasuje
1(9, 1)(6, 4)Nie pasuje, Lista 1 zawiera wartość wierzchołka
1(9, 1)(7, 3)Nie pasuje, Lista 1 zawiera wartość wierzchołka
1(9, 1)(8, 2)Nie pasuje, Lista 1 zawiera wartość wierzchołka

Ze wszystkich sześciu możliwości zostały tylko 3. Rozpatrzmy pierwszy przypadek z tej części: Lista 1 = (7, 3), Lista 2 = (6, 4). Teraz należy rozpatrzeć wszystkie możliwe przypadki wyboru wierzchołków z wybranych list. Ostatnia kolumna zawiera wartość do której muszą się sumować elementy krawędzi dolnej pomiędzy wierzchołkami:

Wierzchołek 1Wierzchołek 2Wierzchołek 3Komentarz
176Niemożliwe, bo n - (7 + 6) = -2
174Niemożliwe, bo n - (7 + 4) = 0
136Możliwe, bo n - (3 + 6) = 2
134Niemożliwe, bo n - (3 + 4) = 4, a wartość 4 już występuje

Jednym z trójkątów spełniającym wszystkie założenia jest:

1.1
2.74
3.326

Na wszelki wypadek można sprawdzić, że 3 + 7 + 1 = 1 + 4 + 6 = 3 + 2 + 6 = 11 oraz wszystkie elementy są różne. Warto zauważyć, że w tym przypadku otrzymamy inny trójkąt po obrocie w prawo o 120º i 240º oraz po zamianie list. W tym przypadku pomiędzy wierzchołkami jest jeden element, więc ((a - 2)!)3 = 1. Łącznie na podstawie tego trójkąta można wygenerować 6 innych.

Implementacja

Wyszukiwanie rozkładu liczby

W celu znalezienia rozkładu liczby została napisana funkcja szukajntek(), która przyjmuje dwa argumenty: wartosc - jaka wartość ma zostać podzielone na ile - elementów. Funkcja wstępna przygotowuej listę wynikową v oraz wektor tymczasowy v2.

  1. vector<vector<int> > szukajntek(int wartosc, int ile){
  2.   vector<vector<int> > v;
  3.   vector<int> v2;
  4.   szukajntek(v, v2, wartosc, ile);
  5.   return v;
  6. }

Główna funkcja ma tę samą nazwę, ale dodatkowo potrzebuje wskaźnik na miejsce w pamięci, gdzie może dopisywać kolejne znalezione n-tki oraz tymczasowo przechowywać aktualny wynik.

  1. void szukajntek(vector<vector<int> > &v, vector<int> &v2, int wartosc, int ile) {
  2.   if (wartosc <= 0)
  3.     return;
  4.   for (int i = 1; i <= wartosc; i++) {
  5.     if (find(v2.begin(), v2.end(), i) == v2.end() && wiekszyRowny(v2, i)) {
  6.       v2.push_back(i);
  7.       if (v2.size() == ile && wartosc == i) {
  8.         vector<int> t;
  9.         for (int j = 0; j < ile; j++)
  10.           t.push_back(v2[j]);
  11.         v.push_back(t);
  12.       } else {
  13.         szukajntek(v, v2, wartosc - i, ile);
  14.       }
  15.       v2.pop_back();
  16.     }
  17.   }
  18. }

Rozwiązania są wyszukiwane rekurencyjnie, a warunkiem stopu jest (2. - 3.) ujemna lub zerowa wartość dla pozostałych elementów. Dla każdego wywołania (4.) sprawdzane są wszystkie wartości jakie można wstawić w to miejsce. (5.) Wybrana wartość jest dopisywana do aktualnej listy. Warunkiem jest: (6.) brak tej wartości na liście oraz to, że następny jest mniejszy od poprzedniego. (7.) Po dopisaniu: (8. - 12.) należy sprawdzić czy cała wartość została rozdzielona i mamy tyle elementów ile miało być. Jeśli tak to wystarczy skopiowany wektore dopisać do zmiennej wynikowej v. W przeciwnym razie (14.) szukamy dalszych elementów. Na koniec każdej iteracji (16.) ostatnio dopisany element należyć usunąć.

Do sprawdzania czy zachowane jest monotoniczność elementów w znalezionych rozkładach służy funkcja wiekszyRowny(), która przyjmuje dwa argumenty: v2 - wektor z danymi oraz v - wartość, która ma być dodana. Wartość prawda jest zwracana tylko, gdy element może zostać dodany.

  1. bool wiekszyRowny(vector<int> &v2, int w) {
  2.   if (v2.size() == 0)
  3.     return true;
  4.   return v2[v2.size() - 1] >= w;
  5. }

Łączenie wektorów

W głównej funkcji przyda się łączenie wektorów, aby wyznaczać listę elementów z której składa się trójkąt. Funkcja dodaj() przyjmuje dwa argumenty el - wektor główny oraz x - wektor z którego elementu mają być dodane do el. Funkcja nie dodaje do el elementów z x, które już tam występują. Funkcja zwraca ile elementów dodała.

  1. int dodaj(vector<int> &el, vector<int> &x) {
  2.   int ile = 0;
  3.   for (int k = 0; k < x.size(); k++)
  4.     if (find(el.begin(), el.end(), x[k]) == el.end()) {
  5.       el.push_back(x[k]);
  6.       ile++;
  7.     }
  8.   return ile;
  9. }

Wyszukiwanie rozwiązań

Mają przygotowane funkcje pomocnicze można przejść do pisania funkcji szukajTrojkata(), która obliczy ile jest wszystkich możliwych rozwiązań trójkąta o zadanych parametrach. Funkcja przyjmuje dwa argumenty: a - długość boku trójkąta oraz n - suma wartości na dowolnej krawędzi.

  1. int szukajTrojkata(int a, int n) {
  2.   int ile = 0;
  3.   int kombinacji = silnia(a - 2);
  4.   for (int i = 1; i <= n - (a - 1)*a / 2; i++) {
  5.     vector<int> el;
  6.     vector<vector<int> > v = szukajntek(n - i, a - 1);

Pierwszy etap polega na (2.) zanicjalizowaniu licznika ile oraz (3.) wyliczaniu ile jest kombinacji zamiany elementów pomiędzy wierzchołkami. (4.) Dla każdej wartości wierzchołka: (5.) utwórz tymczasową listę i (6.) znajdź wszystkie listy o długości a - 1, które razem z wierzchołkiem sumuja się do n.

  1.     for (int x = 0; x < v.size(); x++) {
  2.       for (int y = 0; y < x; y++) {
  3.         el.push_back(i);
  4.         dodaj(el, v[x]);
  5.         dodaj(el, v[y]);
  6.         if (el.size() == 2*a - 1) {

W dalszej części (7. - 8.) wybierane są dwie listy (do uzupełnienia lewej i prawej krawędzi), a potem (9. - 11.) tworzona jest tymczasowa lista. (12.) Warunkiem dalszego rozpatrywania znalezionego przypadku jest odpowiednia długość wektora: tutaj dwie pełne krawędzie muszą mieć 2a - 1 elementów.

  1.           for (int k = 0; k < a - 1; k++) {
  2.             for (int l = 0; l < a - 1; l++) {
  3.               int o = n - el[k + 1] - el[l + a];
  4.               vector<vector<int> > w = szukajntek(o, a-2);
  5.               for (int g = 0; g < w.size(); g++) {
  6.                 int u = dodaj(el, w[g]);
  7.                 if (el.size() == 3 + 3 * (a - 2))
  8.                   ile++;
  9.                 while (u--)
  10.                   el.pop_back();
  11.               }
  12.             }
  13.           }
  14.         }
  15.         el.clear();
  16.       }
  17.     }
  18.   }
  19.   return ile*6*kombinacji*kombinacji*kombinacji;
  20. }

Ostatni etap polega na (13.) wybraniu jednego i (14.) drugiego wierzchołka z obu list, a następnie (15.) obliczeniu wartości do podzielenia pomiędzy elementy w dolnej krawędzi między wierzchołkami. (16.) Znajdź wszystkie listy spełniające poprzedni warunek i (17.) dla każdego znalezionego rozwiązania: (18.) dołącz wektor do akutalnej listy i (19.) jeśli jest odpowiednia ilość elementów to (20.) zwiększ ilość rozwiązań.Potem (21. - 22.) wycofaj wprowadzone zmiany na liście. (27.) Po zakończeniu pętli wyboru obu list wyczyść wektor, a na sam koniec (31.) zwróć prawidłową ilość kombinacji.

Testowanie funkcji

W celu przetestowania działania napisanych funkcji można skorzystać z poniższego fragmentu kodu:

  1. int main() {
  2.   int a, n;
  3.   cout << "Podaj bok\na = ";
  4.   cin >> a;
  5.   cout << "Podaj sume krawedzi\nn = ";
  6.   cin >> n;
  7.   cout << "Rozwiazan: " << szukajTrojkata(a, n) << endl;
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Napisz program, który wczyta od użytkownika długość boku a, a następnie a wierszy opisujących trójkąt. Program ma sprawdzić czy taki trójkąt jest magiczny i jeśli tak to podać wartość jego krawędzi.

Przykładowo użytkownik wprowadza następujący trójkąt

1.1
2.74
3.326

w następujący sposób:

  1. 3
  2. 1
  3. 7 4
  4. 3 2 6

Jako wynik otrzymuje przykładowo:

  1. Jest to trojkat magiczny o n = 11