Informatics2-2020/Lab10

A MathWikiből
(Változatok közti eltérés)
(Új oldal, tartalma: „previous up next =Exercises= == Dynamic programming== ===Paint Bucket Tool=== Download th…”)
 
a (Dynamic programming)
 
3. sor: 3. sor:
 
=Exercises=
 
=Exercises=
 
== Dynamic programming==
 
== Dynamic programming==
 +
 +
=== Euclidean algorithm ===
 +
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===
 
===Paint Bucket Tool===
 
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!
 
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!

A lap jelenlegi, 2020. április 21., 20:41-kori változata

previous up next

Tartalomjegyzék

Exercises

Dynamic programming

Euclidean algorithm

Implement the greatest common divisor (gcd) function using the Euclidean algorithm. Implement it with and without recursion!

Paint Bucket Tool

Download the picture.txt file and read it as a list of lists in python!

.....................................
...#######################...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#...........
...#.....................#######.....
...###.................##......#.....
...#..##.............##........#.....
...#....##.........##..........#.....
...#......##.....##............#.....
...#........#####..............#.....
...#........#..................#.....
...#.......##..................#.....
...#.....##....................#.....
...#...##......................#.....
...#############################.....
.....................................
.....................................
.....................................
.....................................

Write a function fill(x,y) which fills a territory starting with the given coordinates, like the bucket tool in Paint.

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.

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!

Finite-state machine

Keystrokes

Download the following text file: raw_data.txt

This file contains keystroke data when someone was typing. The interesting part starts from the 5th 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 1st, 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 keycodes here

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$$$$$$

Note that the parenthesis can be enclosed into each other.

previous up next

Személyes eszközök