układ współrzednych ta: Witam, czy istnieje metoda, sposób aby znaleźć takie ustawienie odcinka o określonej długości w układzie współrzędnych, aby początek i koniec stanowiły punkty kratowe, oraz odcinek ten przechodził przez jak najmniejszą ilość punktów kratowych(oprócz początku i końca)

Trivial: Chodzi Ci o algorytm?

ta: w pewnym sensie tak, problem w tym, że nie mam na to pomysłu, możesz mi dać wskazówki(nie rozwiązanie) , może nie znam jakiegoś faktu matematycznego, zadanie wydaje się być dla mnie dziwne, więc jak możesz mi dać jakąś wskazówkę, która mnie może naprowadzić to dzięki, może coś powinienem zauważyć, coś rozważyć? btw, znasz się na algorytmice?

Trivial: Nie mam pojęcia jak to zrobić inaczej niż po prostu sprawdzić po kolei możliwości (co i tak nie jest złe − złożoność O(n²), gdzie n jest długością). Miałem jeden semestr algorytmów. Trzeba zacząć od tego, że można odcinek zaczepić w punkcie (0, 0) co już znacznie sprawę ułatwia. Potem możemy jeszcze bardziej uprościć problem, bo jest on bardzo symetryczny − możemy rozważyć tylko pół pierwszej ćwiartki układu współrzędnych, bo resztę możemy uzyskać przez proste przekształcenia symetryczne − ilość obliczeń ulegnie zmniejszeniu osiem razy. Jeżeli chcesz to mogę ci napisać jakiś tego typu algorytm.

Trivial: Możemy potem iterować po x−ie kolejne liczby całkowite. Dla każdego x wyliczymy y z równania okręgu x² + y² = L², gdzie L − długość. Potem sprawdzamy, czy y jest liczbą całkowitą. Jeżeli jest to musimy policzyć ile ma punktów kratowych przez cały odcinek − znów iteracja. Potem wyciągamy te odcinki, które mają jak najmniej tych punktów i gotowe. Odbijamy symetrycznie względem prostej y = x. Potem wszystkie punkty (łącznie z nowymi) względem prostej y = 0, a potem wszystko znów względem prostej x=0. Otrzymaliśmy wszystkie odcinki, które są zaczepione w punkcie (0, 0). Możesz je teraz przesunąć o dowolny wektor, którego współrzędne są liczbami całkowitymi i to będzie równie optymalne rozwiązanie. (Jeżeli miałeś na myśli układ 3D, to oczywiście trzeba iterować po jeszcze jednej zmiennej − złożoność wzrasta do O(n³)).