• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Generator współrzędnych

+1 głos
248 wizyt
pytanie zadane 21 maja 2016 w C i C++ przez vasiv Użytkownik (590 p.)
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.

2 odpowiedzi

0 głosów
odpowiedź 21 maja 2016 przez niezalogowany
Biblioteka random. Algorytm losujący liczby bez powtórzeń będziesz musiał sam napisać.
0 głosów
odpowiedź 21 maja 2016 przez Sebastian Fojcik Nałogowiec (42,580 p.)

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 :-)

komentarz 21 maja 2016 przez vasiv Użytkownik (590 p.)
Dokładnie o to mi chodzi. Jednak porównywanie nowego losowania z poprzednimi wynikami, przy dużej ilości "miast", nie jest zbyt efektywne.
komentarz 21 maja 2016 przez Sebastian Fojcik Nałogowiec (42,580 p.)

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ń ;-)

Podobne pytania

0 głosów
1 odpowiedź 98 wizyt
0 głosów
1 odpowiedź 88 wizyt
pytanie zadane 21 sierpnia 2016 w Offtop przez Alterwar Mądrala (7,280 p.)
0 głosów
1 odpowiedź 47 wizyt
Porady nie od parady
Pytania na temat serwisu SPOJ należy zadawać z odpowiednią kategorią dotyczącą tej strony.SPOJ

63,168 zapytań

109,404 odpowiedzi

228,554 komentarzy

42,695 pasjonatów

Przeglądających: 61
Pasjonatów: 4 Gości: 57

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...