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…”)
 
 
(egy szerkesztő 11 közbeeső változata nincs mutatva)
2. sor: 2. sor:
  
 
=Exercises=
 
=Exercises=
−
== Dynamic programming==
 
  
−
=== Euclidean algorithm ===
+
==Dynamic Programming==
−
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===
+
===Deep Sum===
−
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!
+
Write a recursive function whose input is a list containing lists up to any depth containing positive integers. The function must return the sum of all numbers inside the list.
  
−
.....................................
+
Example:
−
...#######################...........
+
  [1, 2, 3, [4, 5], [[[6], 7]]] -> 28
−
...#.....................#...........
+
−
...#.....................#...........
+
−
...#.....................#...........
+
−
...#.....................#...........
+
−
...#.....................#...........
+
−
...#.....................#######.....
+
−
...###.................##......#.....
+
−
...#..##.............##........#.....
+
−
...#....##.........##..........#.....
+
−
...#......##.....##............#.....
+
−
...#........#####..............#.....
+
−
...#........#..................#.....
+
−
...#.......##..................#.....
+
−
...#.....##....................#.....
+
−
...#...##......................#.....
+
−
...#############################.....
+
−
.....................................
+
−
.....................................
+
−
.....................................
+
−
  .....................................
+
  
−
Write a function '''fill(x,y)''' which fills a territory starting with the given coordinates, like the bucket tool in Paint.
+
===Palindrome===
 +
Write a recursive function which checks whether a given string is a palindrome or not. Then try to write a non recursive function for that and compare the time complexity.
  
−
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.
+
Example:
 +
aba -> True
 +
abb -> False
  
−
===Knight===
+
===Factorial===
−
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 recursive function to compute the factorial of a given natural number. Then try to write a non recursive function for that and compare their time complexity.
  
−
Write a function '''knight(x,y)''' where the parameters are the ''x, y'' coordinates of the initial place.
+
===Sum Digit===
−
Return an 8-by-8 table of integers containing the minimum number of steps to reach that position.
+
Write a recursive function to compute the sum of the digits of a given positive integers.
−
For example the initial state should have 0 on it.
+
  
−
Use a dynamic programming table!
+
Example:
 +
234-->9
  
−
== Finite-state machine==
+
===Sum Series===
−
=== Keystrokes ===
+
Write a recursive function to compute sum of the nonnegative series n+(n-2)+... for a given input n.
−
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.
+
===Power===
−
The interesting part starts from the 5<sup>th</sup> line:  
+
Write a recursive function to compute a power of a number without using **.
 +
Example:
 +
power(2,4)-->16
  
−
* The first column is an event: '''keydown''' or '''keyup'''  (others are irrelevant now)
+
==Finite State Machine==
−
* The next three numbers encode the key, actually the second one is important (third column).
+
===Target===
−
* The fourth column refers to capital or lowercase, but thats also irrelevant now.
+
Write a function whose input is a string of digits and an integer.
−
* The last one is a timestamp, the number of milliseconds elapsed since January 1<sup>st</sup>, 1970.
+
Write down all possible combinations of digits and +, -, * operations that result in the given integer.
  
−
The exercise is to process the keystrokes and reconstruct the typed text.
+
Example:
−
Mind that there is a SHIFT key in the data.
+
Target("123", 6) -> '1+2+3', '1*2*3'
−
 
+
−
'''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]
+
  
 
=== Parenthesis ===
 
=== Parenthesis ===
75. sor: 48. sor:
  
 
  (xc)aa(c(b)) -> $$$$aa$$$$$$
 
  (xc)aa(c(b)) -> $$$$aa$$$$$$
−
 
−
Note that the parenthesis can be enclosed into each other.
 

A lap jelenlegi, 2021. április 28., 19:00-kori változata


Tartalomjegyzék

Exercises

Dynamic Programming

Deep Sum

Write a recursive function whose input is a list containing lists up to any depth containing positive integers. The function must return the sum of all numbers inside the list.

Example: 

[1, 2, 3, [4, 5], [[[6], 7]]] -> 28

Palindrome

Write a recursive function which checks whether a given string is a palindrome or not. Then try to write a non recursive function for that and compare the time complexity.

Example: 

aba -> True 
abb -> False

Factorial

Write a recursive function to compute the factorial of a given natural number. Then try to write a non recursive function for that and compare their time complexity.

Sum Digit

Write a recursive function to compute the sum of the digits of a given positive integers.

Example: 

234-->9

Sum Series

Write a recursive function to compute sum of the nonnegative series n+(n-2)+... for a given input n.

Power

Write a recursive function to compute a power of a number without using **. Example: 

power(2,4)-->16

Finite State Machine

Target

Write a function whose input is a string of digits and an integer. Write down all possible combinations of digits and +, -, * operations that result in the given integer.

Example: 

Target("123", 6) -> '1+2+3', '1*2*3'

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$$$$$$
A lap eredeti címe: „http://wiki.math.bme.hu/index.php?title=Informatics2-2021/Lab11&oldid=14937”