Punkty na okręgu

Odpowiedz Nowy wątek
2012-02-14 16:34
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.

edytowany 1x, ostatnio: Plaq, 2012-02-14 16:35

Pozostało 580 znaków

2012-02-14 16:54
0

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

Pozostało 580 znaków

2012-02-14 17:33
0

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

Pozostało 580 znaków

2012-02-14 17:45
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

edytowany 1x, ostatnio: Zjarek, 2012-02-14 17:50

Pozostało 580 znaków

2012-02-14 18:09
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?

Pozostało 580 znaków

2012-02-14 18:39
0

Ja wpadłem na coś takiego:
Powiedzmy, że liczysz tę najkrótszą trasę (http://en.wikipedia.org/wiki/[...]n_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)].

edytowany 1x, ostatnio: Zjarek, 2012-02-14 18:58

Pozostało 580 znaków

2012-02-16 11:14
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").

Poczytaj o Brute Force; - furious programming 2012-02-16 19:53

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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