-
Data: 2013-05-12 22:51:45
Temat: Re: Zabawy w algorytmikę.
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu 2013-05-12 22:49, bartekltg pisze:
> W dniu 2013-05-12 21:21, Vax pisze:
>> W dniu 2013-05-12 19:24, bartekltg pisze:
>>> W dniu 2013-05-12 17:14, Vax pisze:
>>
>>> No nie wiem, uwaga o przeszukiwaniu kazdej kombinacji na całej
>>> tablicy kliknięć sugeruje, że nawet nie przeczytałeś dokładnie:/
>>
>> ten ustęp tyczył rozwiązania "kombinacje wszystkich kliknięć w tablicę"
>> vs "kombinacje wszystkich kliknięć w krótszy bok". Jeżeli złożoność
>> drugiego określamy jako 2^(N*M) to także nie uwzględniając złożoności
>> "testu".
>
> No to wypadałoby to dorzucić do złożoności:) Ok, da sie to poprawić
>
> Rozpatrywanie tego algorytmu jest mało sensowne, ale skoro chcesz:
> mamy 2^(m*n) prób. W każdej musimy wygenerować tablicę opisującą
> stan lampek. Jeśli rzeczywiście będziemy budować ją od początku,
> wykonamy O(m*n) operacji. Ale nie musimy tego robić, wystarczy, że
> naniesiemy poprawki. Jeśli różnił się jeden bit, poprawka jest w 5
> miejscach. Super. Jeśli przeszukujemy wszystkie kombinacje włączony/
> wyłączony jak liczby naturalne, zamortyzowany koszt jest również stały.
Urwało mi komentarz: każdy w 'szkole' miał analizę "licznika binarnego"
http://www.im.pwr.wroc.pl/~kik/AiSD/wyklady/aisd7.pd
f
to dokładnie to samo.
> Można użyć też kodów Graya, wtedy następna kombinacja na pewno będzie
> się różniła tylko o jeden bit (a wygenerowanie graya z kolejnych liczb
> to jeden shift i jeden xor:)).
>
> Rzeczywiście da się więc zrobić każdą iterację z 2^(m*n) testów
> w czasie stałym. Tylko po co;)
pzdr
bartekltg
Następne wpisy z tego wątku
- 12.05.13 23:01 Vax
- 13.05.13 00:09 bartekltg
- 13.05.13 00:12 bartekltg
- 13.05.13 01:13 A.L.
- 13.05.13 02:19 bartekltg
- 13.05.13 02:20 bartekltg
- 13.05.13 02:49 A.L.
- 13.05.13 10:14 R.e.m.e.K
- 13.05.13 10:58 M.M.
- 13.05.13 11:54 Miroslaw Kwasniak
- 13.05.13 13:07 Miroslaw Kwasniak
- 13.05.13 13:46 bartekltg
- 13.05.13 13:57 bartekltg
- 13.05.13 13:59 bartekltg
- 13.05.13 14:00 bartekltg
Najnowsze wątki z tej grupy
- Alg. kompresji LZW
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
Najnowsze wątki
- 2025-02-27 Warszawa => Junior Rekruter <=
- 2025-02-27 China-Kraków => Key Account Manager IT <=
- 2025-02-27 Warszawa => Sales Assistant <=
- 2025-02-27 Kraków => Frontend Vue Developer <=
- 2025-02-27 Re: Zwolniony z IKEA za "wąty" przeciw firmowej promocji LGBT-IQ+ przywrócony do pracy - SN odrzucił kasacje (sygn. akt I PSK 62/24)
- 2025-02-27 Częstochowa => Manager ds. produktu <=
- 2025-02-27 Warszawa => Business Systems Analyst <=
- 2025-02-27 Nagranie poglądowe
- 2025-02-26 Zasilacz USB na ścianę.
- 2025-02-26 Błonie => Specjalista ds. public relations <=
- 2025-02-26 Zielonka => Team Lead / Tribe Lead FrontEnd <=
- 2025-02-26 Warszawa => Specjalista ds. Sprzedaży (transport drogowy) <=
- 2025-02-26 Białystok => Data Engineer (Tech Leader) <=
- 2025-02-26 Kraków => Business Development Manager - Dział Sieci i Bezpieczeńst
- 2025-02-26 Kraków => Business Development Manager - Network and Network Security