General: Addendum (Wyszukiwania)

Public message

- Na kółku trochę powspominaliśmy o zmiennoprzecinkowości. * Typy w C++: float, double, long double, __float128. Posortowane wielkością, precyzją i czasem działania (wszystko rosnąco). W praktyce: zawsze double, w razie problemów z precyzją long double, gdy jesteśmy zdesperowani pod względem wydajności float. * Typ zmiennoprzecinkowy (ustandaryzowany pewnym IEEE, więc tak też jest np. w Pythonie) zapisuje liczbę rzeczywistą jako m * 2^e * (-1)^s: zapis składa się z mantysy m, wykładnika e i znaku s. * Dodawanie liczb zmiennoprzecinkowych nie jest łączne i inne kurioza. http://www.walkingrandomly.com/?p=5380 * Jeżeli ktoś jest zaciekawiony tematem to dobrym źródłem jest What Every Computer Scientist Should Know About Floating-Point Arithmetic: https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html - Zadanie Meteory z kółka to tak na prawdę uproszczona wersja prawdziwego zadania Meteory z OIa. Dlatego zmieniłem jego nazwę na kartce na Meteoryty :P - Trik „mniejszy-większy” (jeszcze kiedyś do niego wrócimy i dostanie własne miejsce na dowód): Umiemy dodać zbiór wielkości a do zbioru wielkości b w czasie O(a). Mamy n rozłącznych jednoelementowych zbiorów. Jeżeli mamy wykonywać operacje łączenia dwóch dowolnych zbiorów, to możemy je wykonać w amortyzowanym czasie O(n log n). Rozwiązanie: wystarczy zawsze dodawać mniejszy zbiór do większego. * Jeżeli dodajemy w trochę innym czasie (np. O(a log b)), to możemy przyjąć że O(log b) to stała rzędu O(log n) – otrzymujemy O(n log^2 n). - Zadanie z geometrii pochodziło z AMPPZ 2018: http://www.amppz.ii.uni.wroc.pl/files/amppz_problemset_pl.pdf (A: Aparat na dronie)