Cześć,
jako że nie jestem matematykiem to muszę się Was poradzić. Mam tablicę prostokątną \(\displaystyle{ 4 \times 10}\) (macierz) a w niej różne symbole, ale to akurat nie jest istotne.
Chciałbym pobierając każdy element po kolei w pętli dowiedzieć się jakie kombinacje z tych elementów można zbudować tworząc ciąg z sąsiadami i maksymalnym zagłębieniu \(\displaystyle{ n=7}\). To zupełnie tak jakbym szukał wszystkich możliwych dróg (z punktu \(\displaystyle{ A}\) do dowolnego) ale nie dalej niż o \(\displaystyle{ 7}\) sąsiadów. Nie bardzo wiem jakiego algorytmu mam szukać, aby był najłatwiejszy w implementacji. Nie jest dla mnie istotna za bardzo złożoność obliczeniowa. Ciąg od elementu możemy budować w górę w dół i na boki. Wykluczyłem po skosie.
Chyba coś z grafami trzeba kombinować? Ogólnie na razie macierz zaimplementowałem jako zwykłą tablice dwuwymiarową i chciałem ją zwiedzać brute-force ale coś mi się sknociło z tablicą odwiedzin i odpuściłem sobie... a może jakieś drzewo na wskaźnikach będzie łatwiejsze w implementacji?
Jakieś rady i pomysły?
PS: Od razu zaznaczam, że nie jest to żadne zadanie domowe ani nic w tym stylu
[C++] Wszystkie kombinacje w macierzy
-
- Użytkownik
- Posty: 15
- Rejestracja: 24 sty 2012, o 13:54
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 3 razy
[C++] Wszystkie kombinacje w macierzy
Ostatnio zmieniony 31 sty 2016, o 15:48 przez Afish, łącznie zmieniany 1 raz.
Powód: Całe wyrażenia matematyczne umieszczaj w tagach[latex] [/latex] .
Powód: Całe wyrażenia matematyczne umieszczaj w tagach
-
- Użytkownik
- Posty: 1590
- Rejestracja: 16 maja 2013, o 17:56
- Płeć: Mężczyzna
- Lokalizacja: Trójmiasto
- Podziękował: 11 razy
- Pomógł: 246 razy
[C++] Wszystkie kombinacje w macierzy
Tylko rekurencyjnie to ogarniesz.
Mając tablicę postaci np.
Taka funkcja powinna:
-sprawdzić, czy współrzędne początku są wewnątrz tablicy
-dopisać element z współrzędnych startowych do drogi
-wyświetlić drogę
-zwiększyć długość przebytej drogi o 1
-jeśli przebyta droga nie jest dłuższa niż 7 (dla równej 7 jeszcze tak) to wówczas:
--wywołać się w czterech instancjach, za każdym razem podając jako współrzędne początku te, które dostała przesunięte odpowiednio o 1 w lewo, górę, prawo i dół
Mając tablicę postaci np.
int **tab
gdzie masz \(\displaystyle{ 4}\) kolumny i \(\displaystyle{ 10}\) wierszy musisz wywołać funkcję, której podasz tę tablicę, współrzędne początku drogi i obecną długość drogi - wstępnie 0 oraz już przebytą drogę, najlepiej w formie tablicy, wstępnie pustej.Taka funkcja powinna:
-sprawdzić, czy współrzędne początku są wewnątrz tablicy
-dopisać element z współrzędnych startowych do drogi
-wyświetlić drogę
-zwiększyć długość przebytej drogi o 1
-jeśli przebyta droga nie jest dłuższa niż 7 (dla równej 7 jeszcze tak) to wówczas:
--wywołać się w czterech instancjach, za każdym razem podając jako współrzędne początku te, które dostała przesunięte odpowiednio o 1 w lewo, górę, prawo i dół