Niemniej zadania z grubsza dotyczyły operacji na tablicach jednowymiarowych. W skrócie obliczenia dotyczące danych w tablicach. Ot, algorytmika.
Na 5 zadań było raptem 150 minut. Smutne, ale nie dałem rady. Na razie... Przyjdzie czas - dam radę. W mojej ocenie, byłbym w stanie zrobić co najmniej 3 z nich. Ale nie w 2 godziny, a w dwa tygodnie. Może nie codziennie, ale po godzinie, dwie dziennie. I wreszcie dałbym radę. Niestety, test miał ograniczenie czasowe... Szkoda.
Post piszę jednak w innym celu. Mianowicie moje przemyślenia młodego programisty są takie, że dość abstrakcyjne testy służą chyba tylko wykazaniu się w logicznym myśleniu. Podejrzewam, że w codziennej pracy programisty raczej takie problemy nie występują zbyt często.
Niemniej postanowiłem dołączyć (powrócić) do mojego zestawu rzeczy do nauczenia - zestaw problemów algorytmicznych. Uznałem bowiem, że biegłość w operowaniu na tablicach, czy w ogóle algorytmach różnych, uzyskać można wyłącznie poprzez nieustanne ćwiczenia.
Mam pewne tajemne źródło kilkudziesięciu problemów algorytmicznych - czas do niego wrócić...
Pierwszym przykładem jest tzw. problem 100 drzwi. Polega on na tym, iż:
"mamy 100 zamkniętych drzwi. W każym przebiegu zmieniamy ich stan otwarte/zamknięte. W każdym przebiegu zwiększamy skok o 1. Czyli w drugim przebiegu zaczynamy od 1., ale następne to co drugie, potem co trzecie itp... Jaki stan drzwi będzie po 100 przebiegach.
Moja propozycja - najprostsza, czyli nie optymalizowana wygląda tak:
package pakiet; public class Doors100 { private boolean[] doors = new boolean[101]; private int[] visits = new int[101]; public void countDoors () { for (boolean door : doors) { door = false; } for (int visit : visits) { visit = 0; } for (int i=1; i<101; i++) { for (int j=1; j<101; j+=i) { doors[j] = (doors[j]) ? false : true; visits[j]++; } } for (int i=1; i<101; i++) { System.out.println(i + " " + doors[i] + " " + visits[i]); } } }
Wynikiem jest listing (lp., stan, ilość zmian):
1 false 100
2 true 1
3 false 2
4 false 2
5 true 3
6 false 2
7 false 4
8 false 2
9 false 4
10 true 3
11 false 4
12 false 2
13 false 6
14 false 2
15 false 4
16 false 4
17 true 5
18 false 2
19 false 6
20 false 2
21 false 6
22 false 4
23 false 4
24 false 2
25 false 8
26 true 3
27 false 4
28 false 4
29 false 6
30 false 2
31 false 8
32 false 2
33 false 6
34 false 4
35 false 4
36 false 4
37 true 9
38 false 2
39 false 4
40 false 4
41 false 8
42 false 2
43 false 8
44 false 2
45 false 6
46 false 6
47 false 4
48 false 2
49 false 10
50 true 3
51 false 6
52 false 4
53 false 6
54 false 2
55 false 8
56 false 4
57 false 8
58 false 4
59 false 4
60 false 2
61 false 12
62 false 2
63 false 4
64 false 6
65 true 7
66 false 4
67 false 8
68 false 2
69 false 6
70 false 4
71 false 8
72 false 2
73 false 12
74 false 2
75 false 4
76 false 6
77 false 6
78 false 4
79 false 8
80 false 2
81 false 10
82 true 5
83 false 4
84 false 2
85 false 12
86 false 4
87 false 4
88 false 4
89 false 8
90 false 2
91 false 12
92 false 4
93 false 6
94 false 4
95 false 4
96 false 4
97 false 12
98 false 2
99 false 6
100 false 6
False to zamknięte, true - otwarte. Naturalnie widać jakiś pattern w tym wyniku. Generalnie ostatecznie co nieparzyste drzwi są otwarte. Czyli 1, 3, 5, 7... itd. Odległości między drzwiami otwartymi wzrastają natomiast parzyście, czyli 2, 4, 6, 8... itd.
Pozostaje opracować wzór na taki ciąg i, znając wynik, podstawić go do zoptymalizowanego kodu.