Run update21, if you haven't already, to create the cs21/labs/09 directory. Then cd into your cs21/labs/09 directory and create the python programs for lab 09 in this directory.
This week we will write a few different, smaller programs, all using recursion.
insertPattern(string, pattern) recursiveInsertPattern(string, pattern)
Examples are shown below:
$ python insert.py string: hello pattern: * iterative: h*e*l*l*o recursive: h*e*l*l*o $ python insert.py string: ponies pattern: !! iterative: p!!o!!n!!i!!e!!s recursive: p!!o!!n!!i!!e!!s
Note: this could be accomplished using join() and list()
(e.g., "!!".join(list("ponies"))).
You should not need/use join() or list() in your solution.
Write a program called parse.py that parses a user-given string for matching parentheses. Your program should output a simple True or False, depending on if the given string has the correct syntax (all parens have a match). Your program should use a recursive function to determine if the string has correct syntax or not. Here are a few examples:
$ python parse.py string: ()()() True $ python parse.py string: ((( () () )) False $ python parse.py string: (we)((LOVE))(C)(S) True $ python parse.py string: r = Rectangle(Point(x1,y1),Point(x2,y2) False
Note: the user can type in any string, and your program should work.
One way to do this is to keep track of matching parentheses with a level indicator. For example, starting at level 0, if you are parsing a string and encounter three consecutive opening parens, "(", that would change the level to 3. Encountering a closing paren would decrease the level by 1. Here are the rules and some examples:
Here are some examples of parsing a string for matching parens. These are only to help you understand the algorithm -- your program does not need to produce this output.
string: ((()())) level: 012323210 result: OK string: (()) )() level: 012100-1 result: incorrect syntax string: 4*(5+6)*(3.14) level: 000111100111110 result: OK string: int(raw_input("int: ") level: 00001111111111222222221 result: incorrect syntax
Write a program called binary.py that uses recursion to convert integers into their binary equivalent. Here are some examples:
$ python binary.py number: 412 110011100 number: 256 100000000
Binary numbers are just like regular numbers, except there are only two possible values, 0 and 1. When you count using regular numbers, when you get to 9 (the highest single-digit value), the digit in the ones column goes back to 0 and you "carry" the 1 to the tens column, producing 10. The same happens in binary, except the highest single-digit value is 1, so the carry happens after only two numbers. Here's a table of the first ten numbers:
Decimal pattern | Binary numbers |
---|---|
0 | 0 |
1 | 1 |
2 | 10 |
3 | 11 |
4 | 100 |
5 | 101 |
6 | 110 |
7 | 111 |
8 | 1000 |
9 | 1001 |
Notice how the digit in the ones column just repeats 0, then 1, then back to 0, etc.
For this problem you can use the %
and /
operators
to get the rightmost digits of the binary number from the original number. Here's
an example using 6:
n = 6 n%2 = 0 (rightmost digit of binary 6) n/2 = 3 (use to get next rightmost digit of binary number) 3%2 = 1 (next rightmost digit of binary 6) 3/2 = 1 (use to get next...) 1 is less than 2, so this is the last digit put them all together to get 110
Here's the start of the 412 example above:
n = 412 n%2 = 0 (rightmost digit of binary 412) n/2 = 206 (use to get next rightmost digit of binary number) 206%2 = 0 (next rightmost digit of binary 412) 206/2 = 103 (use to get next...) 103%2 = 1 (next rightmost digit of binary 412) 103/2 = 51 (and so on...)
Hint: what type of data should this function return? If we are
putting together digits (1's and 0's) to make the final result (e.g, 110011100),
should the digits be integers that we just add together??
Write a graphics program called diamonds.py that uses
a recursive function to display the following image (using
Zelle graphics):
Your recursive function should have the following 4 parameters:
(adding another parameter for how much the size changes with each recursion is a nice addition)
Your picture does not have to be identical to the one above (you may use different colors and sizes), but it should:
For the above image, I reduced the size of the diamond each time to 0.33 * the previous size, and each subsequent diamond is moved horizontally and vertically from the previous diamond by size.
Note: to draw diamonds, you will need to use the
Polygon() constructor.
Once you are satisfied with your program, hand it in by typing handin21 in a terminal window.