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

Generator współrzędnych

VPS Starter Arubacloud
+1 głos
1,377 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 (43,020 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 (43,020 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ź 359 wizyt
0 głosów
1 odpowiedź 182 wizyt
pytanie zadane 21 sierpnia 2016 w Offtop przez Alterwar Dyskutant (7,650 p.)
0 głosów
1 odpowiedź 109 wizyt
pytanie zadane 20 stycznia 2023 w JavaScript przez pazo1313 Nowicjusz (140 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...