-
Data: 2013-05-12 16:15:46
Temat: Re: Zabawy w algorytmikę.
Od: Vax <...@i...nie.ma> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu 2013-05-12 01:59, M.M. pisze:
[...]
> Mozna troche przerobic Twoje spostrzezenie. Kazdy klik pewne pola zapala a
> inne gasi. Niech to bedzie klik x. Wiec klik x determinuje kliki ktore
> musza zgasic to co on zapalil. Jesli kolejnosc jest niewazna, to klik x
> moze determinowac je jako kliki w nastepnej kolejnosci. Wiec kazde pole moze
> miec zapamietany numer+1 rekurencyjnego wywolania w ktorym zostalo zapalone
> lub jeden jesli bylo dane w ukladzie poczatkowym. Algorytm w kazdym
> kroku musi zgasic dowolne pole o najmniejszym numrze. To na pewno zmniejszy
> breanch-faktor.
W skrócie, to wyszedłem z takiego założenia:
1. działa to jak XOR, czyli jest naprzemienne
2. skoro kolejność nie ma znaczenia, to ja ją (na swoje potrzeby)
uporządkuję np. od góry, do dołu
3. po wykonaniu wszystkich klików pierwszego wiersza już do niego nie
wracam, zatem w wierszu drugim MUSZĘ ustawić pożądany stan wiersza
pierwszego, klikając POD polami (i TYLKO POD nimi), które mają ów stan
niewłaściwy. W kolejnym wierszu już takiej szansy nie będzie, więc nie
zostanie spełniony warunek zadania.
np. gdy pierwszy rząd po testowym klikaniu wygląda tak:
11010001 to muszę kliknąć pod nim: --x-xxx- (gdzie "x" to click, a "-"
jego brak, nie chcę używać 0/1 żeby się komuś clicki i stany nie myliły :)),
rząd 1 wówczas wygląda już tak: 11111111,
nastąpiły zmiany w rzędzie 2 oraz 3, ale tu już iteracyjnie powtarzamy
aż do ostatniego, po czym badamy, czy on też przyjął postać 11111111.
> Pozostaje kwestia czy mozna jakos uniknac spamietywania?
Trzymając się dalej tablicy np. 8 x 1024, musimy wykonać najwyżej 256
iteracji, od 00000000(bin) do 11111111(bin), czyli np. zwykłą pętlą od 0
do 255 sobie polecieć. Licznik pętli ma już sam z siebie na sobie
zapisane wszystkie układy "klików" do przetestowania.
Gdy kombinacja dla pierwszego wiersza jest dobra, to mamy sukces (i
możemy prościutko odtworzyć wszystkie pola wymagające kliknięcia).
> Algorytm z spamietywaniem jest prosty Jesli docieramy do ukladu ktory byl
> wczesniej, to wnioskujemy ze zaczyna sie petlic. Ale takie podejscie
> wymagaloby sporo pamieci.
Tu, poza tablicą wejściową, masz licznik + 2 bufory o rozmiarze
krótszego boku każdy, wszystko na bitach. Nazwa pliku zajmie więcej
pamięci ;)
> Moze wystarczy zapamietac z kazdym polem, ze juz bylo raz zapalone i potem
> zgaszone? Intuicja podpowiada, ze nie ma sensu zapalac danego pola dwa razy.
> Nie wiem czy moja intuicja sie nie myli, ale jesli to prawda, to algortym
> moze przerwac przeszukiwanie danej galezi, jesli nie da sie zgasic jakiegos
> pola bez zapalania tych pol, ktore juz wczesniej byly zgaszone.
Jeszcze raz: iteracyjnie XOR-ujesz licznik z pierwszym rzędem i drugim,
pamiętając, że XOR w rzędzie klikniętym to nie zwykły XOR, ale również
odwrócenie sąsiadujących bitów.
Tak swoją drogą, to znalezienie nieiteracyjnego algorytmu (lub formuły),
które dla danego ciągu bitów zwróca ciąg z którym wystarczy RAZ wykonać
"zwykły XOR" (czyli: 0001 => 0011, 0010 => 0111, 0011 => 0100 itd.) to
też fajna rozrywka, ale to takie "podzadanie" w zadaniu raczej :)
Kontynuując:
Po wykonaniu testowanej serii klików na pierwszym rzędzie (pamiętaj,
pierwszy wiersz zmienia się "nieco magicznie", drugi to już zwykły XOR,
poprzez negację wiersza pierwszego otrzymujemy mapę kliknięć do
wykonania na następnym wierszu. I tak z każdym kolejnym wierszem aż do
ostatniego. I albo się udało (po "magicznym XOR" mam same jedynki), albo
przechodzimy do kolejnej kombinacji kliknięć w pierwszy rząd.
Następne wpisy z tego wątku
- 12.05.13 16:44 bartekltg
- 12.05.13 17:14 Vax
- 12.05.13 18:23 A.L.
- 12.05.13 18:40 bartekltg
- 12.05.13 18:44 A.L.
- 12.05.13 19:24 bartekltg
- 12.05.13 19:48 A.L.
- 12.05.13 20:02 bartekltg
- 12.05.13 21:21 Vax
- 12.05.13 22:49 bartekltg
- 12.05.13 22:51 bartekltg
- 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.
Najnowsze wątki z tej grupy
- Grok zaczął nadużywać wulgaryzmów i wprost obrażać niektóre znane osoby
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
Najnowsze wątki
- 2025-07-23 Gdańsk => Programista Delphi <=
- 2025-07-23 Gdańsk => Programista Mainframe (z/OS, Assembler) <=
- 2025-07-23 Warszawa => Starszy inżynier DevOps (AWS) <=
- 2025-07-23 Gdańsk => Mainframe (z/OS, Assembler) Developer <=
- 2025-07-23 Kraków => Senior Fullstack Engineer (Low-Code Platform) <=
- 2025-07-23 Wrocław => Senior Key Account Manager IT <=
- 2025-07-23 Trójmiasto => Head of Social Media <=
- 2025-07-23 Rzeszów => Spedytor Międzynarodowy <=
- 2025-07-23 Lublin => ERP Implementation Consultant (AP Module) <=
- 2025-07-23 Środa Wielkopolska => SAP FI/CO Internal Consultant <=
- 2025-07-23 Warszawa => Inżynier oprogramowania .Net <=
- 2025-07-23 Kraków => Kotlin Developer <=
- 2025-07-23 Żerniki => Dyspozytor Międzynarodowy <=
- 2025-07-23 Warszawa => Java Developer <=
- 2025-07-23 Wrocław => Konsultant wdrożeniowy (systemy controlingowe) <=