Generator współrzędnych

Question

Witam.

Wykonuje projekt w C++ rozwiązujący problem komiwojażer. Miasta (czyli ich punkty w układzie x,y), mają być generowane losowo. Pojawia się tutaj moje pytanie. Czy język C++ oferuje generator losowy (bądź pseudolosowy), który będzie w stanie wylosować określoną ilość unikatowych par liczbowych? Czy istnieją biblioteki, które jakoś mi z tym pomogą? A może któryś z Użytkowników posiada zoptymalizowany kod takiego generatora? Oczywiście biorę pod uwagę sprawdzanie wszelkich poprzednich par, jednak chciałbym lepiej rozwiązać ten problem.

Pozdrawiam.

Answer 1

Biblioteka random. Algorytm losujący liczby bez powtórzeń będziesz musiał sam napisać.

Answer 2

Generator par? Zastanów się spokojnie co chcesz zrobić... chcesz otrzymać parę losowych współrzędnych... parę losowych liczb... 2 losowe liczby...

Hmm... więc po prostu je wylosuj?

#include <cstdlib>
#include <ctime>

struct Punkt
{
    int x;
    int y;
}

int main()
{
    int a = 1;
    int b = 100;
    Punkt p1;
    p1.x = rand() % (b-a+1) + a;
    p1.y = rand() % (b-a+1) + a;
}

W jaki inny sposób chciałbyś generować współrzędne?

Jeśli jakieś współrzędne się pokryją, to musisz wylosować je jeszcze raz. Aż do skutku.

Pozdrawiam :-)

Comments

Dokładnie o to mi chodzi. Jednak porównywanie nowego losowania z poprzednimi wynikami, przy dużej ilości "miast", nie jest zbyt efektywne.

---

Nie jest efektywne? Toż to złożoność liniowa zaliczana do szybkich!

Przy 100'000 miast sprawdzenie czy współrzędne się nie powtarzają to raptem w najgorszym możliwym przypadku 200'000 porównań. Komputer z procesorem 1GHz wykonuje miliard operacji na sekundę. U Ciebie to nawet daleko do miliona, a tę liczbę stu tysięcy miast i tak zmyśliłem, a jest pewnie zbyt duża.

Zawsze możesz losować liczby i wkładać do drzewa binarnego. Złożoność zmaleje do logarytmicznej, ale ma to sens tylko w przypadku, gdy danych jest bardzo dużo (ok. miliarda) albo liczy się każde 0,01 s (na konkursach algorytmicznych).

Zastanów się jak Ty byś losował bez powtórzeń w realnym życiu. Wyciągasz z pudełka karteczki z numerkami. Wyciągasz 21 karteczkę i co robisz? Oglądasz dotychczasowe karteczki i sprawdzasz czy już takiej nie wylosowałeś. Dokładniej: spoglądasz na każdy wylosowany numerek i porównujesz.

Nie da się tego zrobić szybciej. Spokojnie, komputery są wystarczająco szybkie. Jak będziesz miał około miliarda miast, to napisz do mnie. Napiszę Ci sposób na szybsze losowanie bez powtórzeń ;-)