Punkty na okręgu

0

Witajcie, mam problem z programem, który ma wykonywać następujące czynności.

Wybieramy liczbę punktów z przedziału 1..20. Na okręgu rozmieszczamy równomiernie 2n punktów. Program na wyrysować wszystkie możliwości połączenia punktów w odcinki (dwa punkty - jeden odcinek). Warunek dodatkowy jest taki, że nie mogą się one przecinać.

Mógłbym prosić o pomoc, sam próbowałem coś zrobić, ale każda próba kończyła się fiaskiem. Z rysowaniem sobie poradzę, problemem jest wybranie tych par punktów, które spełniają warunki.

Z góry dziękuję za pomoc.

0

Jeżeli się nie mylę, to dla n=20 tych możliwości będzie 6564120420. Trochę dużo do rysowania.

0

No tak, zgodnie z liczbą Catalana. Pomijając ten fakt, mogę liczyć na pomoc w jaki sposób napisać program?

0

To wystarczy, że napiszesz algorytm generujący rozwiązania dowolnego problemu którego ilość rozwiązań jest równa tej liczbie i funkcje zmieniającą formę rozwiązania. Przykładowo odpowiadające sobie nawiasy w dobrym nawiasowaniu są równoważne odcinkowi pomiędzy dwoma punktami. Łatwo można zrobić algorytm generujący najkrótsze ścieżki między przeciwległymi punktami w kwadratowej siatce, będące w całości poniżej przekątnej

0

A mógłbym prosić o podpowiedź konkretniejszą? Mam podaną liczbę punktów, która wynosi np. 6 i teraz jak krok po kroku wybrać pary liczb, które spełniają warunki? Da się zrobić sprawdzanie czy odcinki łączące punkty się przecinają nie wyznaczając współrzędnych i nie licząc, czy proste zawierające odcinki mają punkty wspólne?

0

Ja wpadłem na coś takiego:
Powiedzmy, że liczysz tę najkrótszą trasę (http://en.wikipedia.org/wiki/File:Catalan_number_4x4_grid_example.svg). Przyporządkujmy trasom liczby (czy tablicę) w następujący sposób: 000, 001, 002, 011, 111, 012, 003, 112, 022, 013, 023, 113, 122, 123.

Wygenerować kolejną sekwencję zaczynając z danej można następująco:

Zaczynamy od końca. Jeżeli możemy dodać jeden do liczby na danej pozycji to to robimy, jest to możliwe gdy liczba na danej pozycji jest mniejsza niż indeks pozycja oraz przypisujemy tę liczbę na każdej następującej pozycji. Jeżeli nie możemy dodać zmniejszamy indeks o jeden. Przykładowo następnik 023 robimy tak:
Na pozycji 3 jest 3, nie możemy dodać. Sprawdzamy pozycje 2, jest 2, nie możemy dodać. Sprawdzamy pozycję 1, jest 0, możemy dodać i przypisujemy jeden wcześniej sprawdzonym pozycjom, otrzymując 111.

Zamiana na pary punktów:

W celu łatwiejszego opisu algorytmu dodajemy na początku 0 i na końcu n, czyli dla naszego przykładu mamy 01114 (oznaczone jako tab). Teraz idziemy po naszej ścieżce z punktu 0,0, co oznaczę przez row=0, col=0 (teraz numeruje pozycje od 0, nie od 1 jak wcześniej). Num oznaczam numer punktu. Startujemy algorytm z num = 0.

Jeżeli Num jest większe równe niż 2*n kończymy algorytm. Zwiększamy num. Jeżeli tab[col] jest równe row to wrzucamy num na stos i zwiększamy col. Z kolei jeżeli row jest mniejsze, to zwiększamy row o jeden i zabieramy liczbę ze stosu, która z num tworzy parę, którą dodajemy do wyników. Czynność powtórzyć.

Dla 01114 wyjściem tego algorytmu powinien być: [(1,2),(5,6),(4,7),(3,8)]. Dla 01234 będzie [(1,2),(3,4),(5,6),(7,8)].

0

Mógłbym prosić o podpowiedź jak z dwójek {1-2, 1-4, 1-6, 2-3, 2-5, 3-4, 3-6, 4-5, 4-6} utworzyć wszystkie możliwe kombinacje sześciu cyfr, gdzie żadne z nich się nie powtarzają. Dwójki wpisane są do tablicy stringów (np. pod tab[1]="1-2").

1 użytkowników online, w tym zalogowanych: 0, gości: 1