• 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
270 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ź 111 wizyt
0 głosów
1 odpowiedź 89 wizyt
pytanie zadane 21 sierpnia 2016 w Offtop przez Alterwar Mądrala (7,280 p.)
–1 głos
0 odpowiedzi 34 wizyt
pytanie zadane 18 czerwca w C# i .NET przez Sc4red Początkujący (330 p.)
Porady nie od parady
Zadając pytanie postaraj się o poprawną pisownię i czytelne formatowanie tekstu.Kompozycja

64,892 zapytań

111,362 odpowiedzi

234,305 komentarzy

46,742 pasjonatów

Przeglądających: 174
Pasjonatów: 5 Gości: 169

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.

...