Informatics2-2021/Lab11

A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „ =Exercises= == Dynamic programming== === Euclidean algorithm === Implement the greatest common divisor (gcd) function using the [https://en.wikipedia.org/wiki/Euclid…”)
 
4. sor: 4. sor:
 
== Dynamic programming==
 
== Dynamic programming==
  
=== Euclidean algorithm ===
+
===Deep Sum===
Implement the greatest common divisor (gcd) function using the [https://en.wikipedia.org/wiki/Euclidean_algorithm Euclidean algorithm]. Implement it with and without recursion!
+
  
===Paint Bucket Tool===
+
===Palindrome===
Download the [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/picture.txt picture.txt] file and read it as a list of lists in python!
+
  
.....................................
+
===Factorial===
...#######################...........
+
...#.....................#...........
+
...#.....................#...........
+
...#.....................#...........
+
...#.....................#...........
+
...#.....................#...........
+
...#.....................#######.....
+
...###.................##......#.....
+
...#..##.............##........#.....
+
...#....##.........##..........#.....
+
...#......##.....##............#.....
+
...#........#####..............#.....
+
...#........#..................#.....
+
...#.......##..................#.....
+
...#.....##....................#.....
+
...#...##......................#.....
+
...#############################.....
+
.....................................
+
.....................................
+
.....................................
+
.....................................
+
  
Write a function '''fill(x,y)''' which fills a territory starting with the given coordinates, like the bucket tool in Paint.
+
===Sum Digit===
  
Starting from the ''(x, y)'' coordinate replace '''.''' with '''#''', if you encounter a '''#''' then stop. Do this recursively for every neighbor of the given point. This will fill out an enclosed territory.
+
===Sum Series===
  
===Knight===
+
===Power===
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.
+
===Target===
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!
+
 
+
== Finite-state machine==
+
=== Keystrokes ===
+
Download the following text file: [http://sandbox.hlt.bme.hu/~gaebor/ea_anyag/Info2/raw_data.txt raw_data.txt]
+
 
+
This file contains keystroke data when someone was typing.
+
The interesting part starts from the 5<sup>th</sup> line:
+
 
+
* The first column is an event: '''keydown''' or '''keyup'''  (others are irrelevant now)
+
* The next three numbers encode the key, actually the second one is important (third column).
+
* The fourth column refers to capital or lowercase, but thats also irrelevant now.
+
* The last one is a timestamp, the number of milliseconds elapsed since January 1<sup>st</sup>, 1970.
+
 
+
The exercise is to process the keystrokes and reconstruct the typed text.
+
Mind that there is a SHIFT key in the data.
+
 
+
'''Hint:'''
+
 
+
* Store a dictionary of keys which are pressed at a given time.
+
* if a key is released, and it was in the dictionary, then that letter was entered.
+
** in this case, erase that key from the dictionary.
+
* store the state of the SHIFT key (up or down)
+
* There is also a BACKSPACE key!
+
* You can see the [https://www.w3schools.com/jsref/tryit.asp?filename=tryjsref_event_key_keycode2 keycodes here]
+
  
 +
== Finite State Machine==
 
=== Parenthesis ===
 
=== Parenthesis ===
 
Given a string, replace the enclosed parts of the string with a '''$''' character.
 
Given a string, replace the enclosed parts of the string with a '''$''' character.
75. sor: 24. sor:
  
 
  (xc)aa(c(b)) -> $$$$aa$$$$$$
 
  (xc)aa(c(b)) -> $$$$aa$$$$$$
 
Note that the parenthesis can be enclosed into each other.
 

A lap 2021. április 27., 14:32-kori változata


Tartalomjegyzék

Exercises

Dynamic programming

Deep Sum

Palindrome

Factorial

Sum Digit

Sum Series

Power

Target

Finite State Machine

Parenthesis

Given a string, replace the enclosed parts of the string with a $ character. A formula is enclosed if it is surrounded by parenthesis. For example:

(xc)aa(c(b)) -> $$$$aa$$$$$$
Személyes eszközök