Informatics2-2018/Lab09
(Új oldal, tartalma: „previous up next =Exercises= == Dynamic programming== ===Pascal triangle=== Write a funct…”) |
(→Knight) |
||
7. sor: | 7. sor: | ||
===Knight=== | ===Knight=== | ||
− | Let's say that you have a | + | Let's say that you have a knight on the chessboard. Calculate how many steps does it take to optimally reach the other places on the board. |
− | Write a function '''knight(x,y)''' where the parameters are '' | + | Write a function '''knight(x,y)''' where the parameters are the ''x, y'' coordinates of the initial place. |
Return an 8-by-8 table of integers containing the minimum number of steps to reach that position. | Return an 8-by-8 table of integers containing the minimum number of steps to reach that position. | ||
For example the initial state should have 0 on it. | For example the initial state should have 0 on it. |
A lap 2018. április 18., 09:38-kori változata
Tartalomjegyzék |
Exercises
Dynamic programming
Pascal triangle
Write a function that returns the nth row of the Pascal triangle as a list.
Knight
Let's say that you have a knight on the chessboard. Calculate how many steps does it take to optimally reach the other places on the board.
Write a function knight(x,y) where the parameters are the x, y coordinates of the initial place. Return an 8-by-8 table of integers containing the minimum number of steps to reach that position. For example the initial state should have 0 on it.
Use a dynamic programming table!
Zárt terület kifestése
Olvassuk be az alábbi "szöveget" listák listájába (minden karakter egy elem): mentsük le egy fájlba kézzel, majd nyissuk meg a fájlt Pythonnal! Írjunk egy fill(x,y) függvényt, ami ugyanazt csinálja, mint a Paint kitöltő funkciója! Az (x,y) pontból kiindulva a . helyére # jelet tesz, amíg a # jel által jelölt falba nem ütközik! A módszer rekurzív: kifestjük az (x,y) pontot, majd a szomszédait, ha azok nem # jelek. Hívjuk meg a szomszédokra (akik nem # jelek) a függvényt rekurzívan. Ha nincs kit kiszínezni, akkor álljunk meg!
..................................... ...#######################........... ...#.....................#........... ...#.....................#........... ...#.....................#........... ...#.....................#........... ...#.....................#........... ...#.....................#######..... ...###.................##......#..... ...#..##.............##........#..... ...#....##.........##..........#..... ...#......##.....##............#..... ...#........#####..............#..... ...#........#..................#..... ...#.......##..................#..... ...#.....##....................#..... ...#...##......................#..... ...#############################..... ..................................... ..................................... ..................................... .....................................
Állapotgép
Zárójelek
Adott egy sztring. Cseréljük le azokat a karaktereket $ jelre, amelyek zárójelek között vannak (a zárójeleket is beleértve)! Figyelem, a zárójelek lehetnek egymásba ágyazva is, tehát, ha a bemeneti sztring (xc)aa(c(b)), akkor a kimenet $$$$aa$$$$$$ legyen!
Billentyűk
Töltsük le az alábbi adatfile-t: raw_data.txt
A file tartalma egy rövid szöveg begépelése alatt történt billentyű lenyomásokat kódolja. Az érdekes rész az 5. sortól kezdődik:
- Az első szó az esemény, a számunkra érdekesek a keydown és keyup események, ezek rendre a billentyű lenyomás és felengedés.
- A következő három szám a karakter kódja, innen a 2. (azaz a sorban 3. elem) a megbízható, használjuk ezt.
- Az igaz-hamis érték a kis / nagy betűre vonatkozik, de mi ezzel most ne foglalkozzunk.
- Az utolsó elem az érdekes még számunkra, ez az esemény időpontja (pontosan az 1970 január 1. óta eltelt milliszekundumok).
A feladat az, hogy úgy dolgozzuk fel ezt az adathalmazt, hogy a billentyű lenyomások és felengedések közti időt megkapjuk. Csak egy ilyen idősor érdekel minket, a sorrend legyen a lenyomás pillanata szerint. Például az eleje így nézne ki:
145 80 74 ...
A 145-öt az alábbi két sorból kapjuk:
keydown 16 16 0 true 1444121075394 keyup 16 16 0 false 1444121075539
majd a 80-at:
keydown 84 84 0 true 1444121075462 keyup 84 84 0 false 1444121075542
a 74-et:
keydown 72 72 0 false 1444121075693 keyup 72 72 0 false 1444121075767
Az így kapott számsort írjuk egy kimenet.txt file-ba!
Segítség:
Rengeteg módon megoldható a feladat, ez csak egy ötlet:
- Tároljuk a már lenyomott és felengedésre váró gombokat egy szótárban.
- Ha megérkezett egy várt gomb felengedése akkor mentsük a lenyomás időtartamát, majd töröljük a szótárból.
Bónusz: rekonstruáljuk a beírt szöveget. Vigyázat, ez a file tartalmazza a backspace, SHIFT, stb. billentyűk lenyomását is.