Browse assignments
33,401 assignments available
Lab 7: FizzBuzz Write a program that prints the numbers from 1 to 100, one per line, but for multiples of three print “Fizz” instead of the number and for multiples of 5 print “Buzz” instead of the number. For numbers which are multiples of both three and five instead print “FizzBuzz”.Example Output:1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 …
Ask the user to enter a positive integer, or -1 to quit. If the user enters a positive integer repeat it and tell them whether it is even or odd. If the user enters -1 then tell them how many odd numbers they entered and how many even numbers they entered. If they entered no numbers, tell them “no numbers were entered” instead of saying 0 even numbers and 0 odd numbers. Think about the three types of loops we have learned (while, do-while and for) and choose the most appropriate type for this problem. You should test your program and make sure it works before asking me to check it off! The examples below are test cases. Your code should work properly with all test cases listed, as well as with other inputs. Please test your code with all test cases included with each lab, and have these test cases already run and on screen when you call me over to check you off.Example Output: Test Case 1: Enter an integer (-1 to quit): 10 is even. Enter an integer (-1 to quit): 5 is odd. Enter an integer (-1 to quit): 12 is even. Enter an integer (-1 to quit): Odd numbers: 1 Even numbers: 2Test Case 2: Enter an integer (-1 to quit): No numbers were entered.
5/5 - (3 votes)
****************************** Apple $ 1.29 Egg Salad Sandwich $ 2.79 Pie $ 5.99 Subtotal $ 10.07 Tax $ 0.81 Total $ 10.88 ****************************** Thank you for shopping with us ******************************
– Ask the user whether they are a CS major or not (have them type 1 for yes and 0 for no) – print the result to the screen as “CS Major: [result]” (note that this will display numerically – add cout
Enter an integer: 2 (user entered 2) Enter another integer: 3 (user entered 3) 2+3=5 2-3=-1 2*3=6 2/3=0r2 BEFORE you write your program you must create a flowchart explaining what you intend to do. Your program must correspond to your flowchart (revising the flowchart is OK).
Create a class called “box” that has the following attributes (variables): length, width, height (in inches), weight (in pounds), address (1 line), city, state, zip code. These variables must be private. Create setter and getter functions for each of these variables. Also create two constructors for the box class, one default constructor that takes no parameters and sets everything to default values, and one which takes parameters for all of the above. Create a calcShippingPrice function that returns the cost of shipping a box, using the following formula: Shipping price for a single box = (((length + width + height) * $0.50) + (weight * $1.00)) Finally, create a print function that prints length, width, height, address, city, state, zip code and shipping price to the screen. Main should create an array of 3 boxes. Have the user enter the information for each box, then display the information for all boxes as well as the total shipping price for all boxes combined. You must use a class file, header file, and main file (3 files with code in them). Show test run(s) proving that your program works. Input validation: Length, width, height, weight should all be positive. If negative or default constructor is used set to 0. Address needs no input validation, but can have spaces in it (remember getline and ignore), if default constructor is used set to blank (assume all addresses are 1 line only). City needs no input validation but can have spaces in it, if default constructor is used set to blank. State should be exactly two characters long. If invalid or default constructor is used set to “XX” (you do NOT need to check if the state is “real”, i.e. “YZ” would be valid input even though there is no state with that abbreviation – Hint: string.length() ). Zip code should be 5 digits and positive (no leading zeros), if invalid or default constructor is used set to 0. Input validation should be done in your setter functions and/or constructors as needed to ensure no bad data can get in to the class variables. Invalid input should instead set the value to a default as specified above. Your program should be split into three files, a .h file for the box class, a .cpp file for the box class, and a .cpp file for main. Your repl must include the following: – Your code – Screenshot(s) of test run(s) of the program showing it being thoroughly tested. – A flowchart and/or written algorithm showing the design of your code. Make sure nothing in your code results in junk values or causes a segmentation fault.
Create four functions for addition, subtraction, multiplication, and division that each accept an array of doubles (remember that arrays are always passed by reference without needing an &) as well as an operand of type double passed by value. Each function will perform its’ operation on each element of the array using the operand. Example: Operation is addition, array contents are [2.5, 4.5, 6.5, 8.5, 10.5], operand is 7, the array would be changed to contain [9.5, 11.5, 13.5, 15.5, 17.5]. Hint: Remember that arrays are always passed by reference, so your return types for these functions should be void. Create a fifth function that prints the contents of the array to the screen, one element per line. This function should accept an array of doubles as its’ only argument. The print function should not modify the contents of the array in any way – declare the parameter as const to ensure that this is the case (note that you could not do this with the four other functions since they need to modify the array). The print function should also return void. In main ask the user to enter the values to store in the array. Print the array using your print function. Have the user select an operation to perform on the array by typing +, – , * or /, then enter an operand. Perform the given function on the array using the given operand and then print the array contents using your print function again. Use a global int constant for the size of the array – set it to 5. If the global constant is changed in the code your program should still work properly. Your repl must include the following: – Your code – Screenshot(s) of test run(s) of the program showing it being thoroughly tested. – A flowchart and/or written algorithm showing the design of your code. Make sure nothing in your code results in junk values or causes a segmentation fault.
Write a program that asks the user to enter the size of a triangle to write to a text file (an integer from 1 to 50), then print the triangle into a file by printing a series of lines consisting of asterisks. Print “Triangle saved to file” to the screen, but do NOT print the triangle itself to the screen, only to the file. Name the output file triangle.txt Input Validation: If the user enters an integer less than 1 or more than 50 tell them it is out of range and have them re-enter it (do not print the triangle for the invalid input, only for the final value in the range of 1-50 inclusive: 1 and 50 are both ok). The first line will have one asterisk, the next two, and so on, with each line having one more asterisk than the previous line, up to the number entered by the user. On the next line print one less asterisk and continue by decreasing the number of asterisks by 1 for each successive line until only one asterisk is printed. Hint: Use nested for loops; the outside loop controls the number of lines to print, and the inside loop controls the number of asterisks to print on a line. For example, if the user enters 5, the output to the file would be: * ** *** **** ***** **** *** ** * Please provide screenshots of your program running (console window AND file contents) for the following test cases (upload screenshots to your repl): Test Case A: 1 Test Case B: 2 Test Case C: 5 Test Case D: -1 (re-enter), 0 (re-enter), 51 (re-enter), 10 (Triangles should NOT be created for -1, 0 or 51) You must include your algorithm (list of steps taken by the program) as a comment at the top of your code or a flowchart showing the design of your program in your repl. Hint: Creating a file with the extension .draw in your repl will provide drawing tools.
Getting started: Provided files Because you will create images in this lab, you should grab and unzip mandelbrot.zip. Be sure to keep the mandelbrot.py file in the mandelbrot folder: it will need the accompanying files. The standard IDLE will work fine — all of this week’s graphics are still images. The Mandelbrot Set In this lab you will build a program to visualize and explore the points in and near the Mandelbot Set. In doing so, you will have the chance to • use loops and nested loops to solve complex problems (quite literally!) • develop a program using incremental design, i.e., by starting with a simple task and gradually adding levels of complexity • connect with mathematics and other disciplines that use fractal modeling Introduction to for Loops! To build some intuition about loops, first write two short functions in your file: • Write a function named mult( c, n ) that returns the product of c times n but without multiplication. Instead, it should start a value (named result) at 0 and repeatedly add the value of c into that result. It should use a for loop to make sure that it adds c the correct number of times. After the loop finishes, it should return the result, both conceptually and literally.The value of n will be a positive integer. Here is a snippet of the function that initializes the value of result to 0 and builds the loop itself, in order to get you started: def mult( c, n ): “”” mult uses only a loop and addition to multiply c by the integer n “”” result = 0 for x in range( n ): # update the value of result here in the loop Here are a couple of cases to try: >>> mult( 6, 7 ) 42 >>> mult( 1.5, 28 ) 42.0 • The next function will build the basic Mandelbrot update step, which is z = z**2 + c for some constant c.To that end, write a function named update( c, n ) that starts a new value, z at zero, and then repeatedly updates the value of z using the assignment statement z = z**2 + c for a total of ntimes. In the end, the function should return the final value of z. The value of n will be a positive integer. Here is the def line and docstring to get you started: def update( c, n ): “”” update starts with z=0 and runs z = z**2 + c for a total of n times. It returns the final z. “”” Here are a couple of cases to try: >>> update( 1, 3 ) 5 >>> update( -1, 3 ) -1 >>> update( 1, 10 ) a really big number! >>> update( -1, 10 ) 0 You’ll use these ideas (through a variant of the update function) in building the Mandelbrot Set, next… .Introduction to the Mandelbrot Set The Mandelbrot set is a set of points in the complex plane that share an interesting property. Choose a complex number c . With this c in mind, start with z0 = 0 and then repeatedly iterate as follows: zn+1 = zn2 + c The Mandelbrot set is the collection of all complex numbers c such that this process does not diverge to infinity as n gets large. There are other, equivalent definitions of the Mandelbrot set. For example, the Mandelbrot set consists of those points in the complex plane for which the associated Julia set is connected. Of course, this requires defining Julia sets… We will leave such details aside for now. The Mandelbrot set is a fractal, meaning that its boundary is so complex that it cannot be wellapproximated by one-dimensional line segments, regardless of how closely one zooms in on it. In fact, the Mandelbrot set’s boundary has a dimension of 2 (!), though the details of this are better left to the many available references. The inMSet function The next task is to write a function named inMSet(c, n) that takes as input a complex number c and an integer n. Your function will return a Boolean: True if the complex number c is in the Mandelbrot set and False otherwise. First, we will introduce Python’s built-in support for complex numbers. Python and complex numbers In Python a complex number is represented in terms of its real part x and its imaginary part y. The mathematical notation would be x+yi, but in Python the imaginary unit is typed as 1.0j or 1j, so that c = x + y*1j would assign the variable c to the complex number with real part x and imaginary part y. Unfortunately, x + yj does not work, because Python thinks you’re using a variable named yj. Also, the value 1 + j is not a complex number: Python assumes you mean a variable named j unless there is an int or a float directly in front of it. Use 1 + 1j instead. Try it out Just to get familiar with complex numbers, at the Python prompt try >>> c = 3 + 4j >>> c (3+4j)>>> abs(c) 5.0>>> c**2 (-7+24j) Python is happy to use the power operator (**) and other operators with complex numbers. However, note that you cannot compare complex numbers directly (they do not have an ordering defined on them since they are essentially points in a 2D space). So you cannot do something like c > 2. However, you CAN compare the magnitude (i.e., the absolute value) of a complex number to the number 2, e.g., abs(c) > 2. Back to the inMSet function… To determine whether or not a number c is in the Mandelbrot set, you will start with z0 = 0 + 0j and repeatedly iterate zn+1 = zn2 + c to see if this sequence of z0, z1, z2, … stays bounded. That is, we would need to know whether or not the magnitude of these zk go off toward infinity. Really determining whether or not this sequence goes off to infinity would take forever! To check this computationally, we will have to decide on two things: • the number of times we are willing to wait for the zn+1 = zn2 + c process to run • a value that will represent “infinity” The first value above is n. That is, n represents the number of times we are willing to run the z-updating process. This is the second input to the function inMSet(c, n). This is a value you will want to experiment with, but 25 is a reasonable initial value. The second value above, the one that represents infinity, can be surprisingly low! One can prove, though we won’t, that if the absolute value of the complex number z ever gets larger than 2during that update process, then the sequence will definitely diverge to infinity. There is no equivalent rule that tells us that the sequence definitely does not diverge, but it is very likely it will stay bounded if abs(z) does not exceed 2 after a reasonable number of iterations, and n is that “reasonable” number.Writing inMSet You should copy your update function and change its name to inMSet. In this case, it’s better to copy and adapt that old function. Don’t call update directly. Thus, the first lines of inMSet will look like this: def inMSet(c, n): “”” inMSet takes in c for the update step of z = z**2+c n, the maximum number of times to run that step Then, it should return False as soon as abs(z) gets larger than 2 True if abs(z) never gets larger than 2 (for n iterations) “””As the docstring notes, the inMSet function should return False if the sequence zn+1 = zn2 + c ever yields a z value whose magnitude is greater than 2. It returns True otherwise. Note that you will not need different variables for z0, z1, z2, and so on. Rather, you’ll use a single variable z) and then update the value of that variable within a loop, just as you did with update Make sure that you are using return False somewhere inside your loop. You will want to return True after the loop has finished all of its iterations!Check your inMSet function by copying-and-pasting these examples: >>> c = 0 + 0j # this one is in the set >>> inMSet(c, 25) True>>> c = 3 + 4j # this one is NOT in the set >>> inMSet(c, 25) False >>> c = 0.3 + -0.5j # this one is also in the set >>> inMSet(c, 25) True>>> c = -0.7 + 0.3j # this one is NOT in the set >>> inMSet(c, 25) False>>> c = 0.42 + 0.2j >>> inMSet(c, 25) # this one seems to be in the set True>>> inMSet(c, 50) # but it turns out that it’s not! False Getting too many Trues?If so, you might be checking for abs(z) > 2 after the for loop finishes. You need to check inside the loop! There is a subtle reason this won’t work. Many values get so large so fast that they overflow the capacity of Python’s floating-point numbers. When they do, they cease to obey greater-than / less-than relationships, and so the test will fail. The solution is to check whether the magnitude of z ever gets bigger than 2 inside the for loop, in which case you should immediately return False. The return True, however needs to stay outside the loop!Creating images with Python This file uses different approach to graphics (writing out images) than previous homework problems. It will work on SnowLeopard, Windows, and pretty much any OS you might have without any special handling. def weWantThisPixel( col, row ): “”” a function that returns True if we want the pixel at col, row and False otherwise “”” if col%10 == 0 and row%10 == 0: return True else: return False def test(): “”” a function to demonstrate how to create and save a png image “”” width = 300 height = 200 image = PNGImage(width, height)# create a loop in order to draw some pixels for col in range(width): for row in range(height): if weWantThisPixel( col, row ) == True: image.plotPoint(col, row)# we looped through every image pixel; we now write the fileimage.saveFile() Save these functions, and then run it by typing test(), with the parentheses, at the Python shell. If everything goes well it will run through the nested loops and print a message that the file test.png has been created. It should be in the same directory as your hw8pr1.py file. Both Windows and Mac computers have nice built-in facilities for looking at png-type images (png is short for portable network graphics). Simply double click on the icon of the test.png image, and you will see it. For the above function, it should be all white except for a regular, sparse point field, plotted wherever the row number and column number were both multiples of 10:You can zoom in and out of bitmaps with the built-in buttons on Windows; on Macs, similar commands are available via menu and keyboard shortcuts. An image thought-experiment to consider… Before changing the above code, write a short comment or triple-quoted string under the test function in your hw8pr1.py file describing how the image would change if you changed the line if col % 10 == 0 and row % 10 == 0: to the line if col % 10 == 0 or row % 10 == 0: Then, make that change from and to or and try it. It seems that both on Macs and PCs, the image does not have to be re-opened: if you leave the previous preview window open, its image will update automatically. Just for practice, you might try creating other patterns in your image by changing the test and weWantThisPixel functions appropriately. Some notes on how the test function works…There are three lines of the test function that warrant a closer look: • image = PNGImage(width, height) This line of code creates a variable of type PNGImage with the specified height and width. The image variable holds the whole image! This is similar to the way a single variable – often called L – can hold an arbitrarily large list of items. When information is gathered together into a list or an image or another structure, it is called a software object or just an object. We will build objects of our own design in a couple ofweeks, so this lab is an opportunity to use them without worrying about how to create them from scratch. • image.plotPoint(col, row) An important property of software objects is that they can carry around and call functions of their own! They do this using the dot . operator. Here, the imageobject is calling its own plotPoint function in order to, well, plot a point at the given column and row. Functions called in this way are sometimes called methods. • image.saveFile() This line actually creates the new test.png file that holds the png image. It demonstrates another method (i.e., function) of the software object named image. From pixel coordinates to complex coordinates Ultimately, we are trying to plot the Mandelbrot set within a complex coordinate system. However, when we plot points in the image, we must manipulate pixels. As the testImage() example shows, pixel values always start at (0, 0) (in the lower left) and grow to (width-1, height-1) in the upper right. In the example above width and height were both 200, giving us a reasonably sized image. However, the Mandelbrot Set lives in the box -2.0 ≤ x (or real coordinate) ≤ +1.0 and -1.0 ≤ y (or imaginary coordinate) ≤ +1.0 which is a 3.0 x 2.0 rectangle. So, we need to convert from each pixel’s col integer value to a floating-point value, x. We also need to convert from each pixel’s row integer value to the appropriate floating-point value, y. Thus, we will write a function named scale: scale( pix, pixelMax, floatMin, floatMax ) that can be run as follows: >>> scale( 150, 200, -1.0, 1.0 ) Here, the inputs mean the following: • the first input is the current pixel value: we are at col 150 or row 150 • the second input is the maximum possible pixel value: pixels run from 0 to 200 in this case • the third input is the minimum floating-point value. This is what the function will output when the input is 0. • the fourth input is the maximum floating-point value. This is what the function will output when the input is pixelMax. Finally, the output should be the floating-point value that corresponds to the integer pixel value of the first input. The output will always be somewhere between floatMin and floatMax (inclusive). This function will NOT use a loop. In fact, it’s really just arithmetic. You will need to ask yourself • How to use the quantity 1.0*pix / pixMax • How to use the quantity floatMax – floatMin Writing the scale function To compute this conversion back and forth from pixel corrdinates to complex coordinates, write a function that starts as follows: def scale(pix, pixMax, floatMin, floatMax): “”” scale takes in pix, the CURRENT pixel column (or row) pixMax, the total # of pixel columns floatMin, the min floating-point value floatMax, the max floating-point value scale returns the floating-point value that corresponds to pix “”” The docstring describes the inputs: • pix, an integer representing a pixel column • pixMax, the total number of pixel columns available • floatMin, the floating-point lower endpoint of the image’s real axis (x-axis) • floatMax, the floating-point upper endpoint of the image’s real axis (x-axis). Note that there is no pixMin because the pixel count always starts at 0. The idea is that scale will return the floating-point value between floatMin and floatMax that corresponds to the position of the pixel pix, which is somewhere between 0 and pixMax. This diagram illustrates the geometry of these values:Once you have written your scale function, here are some test cases to try to be sure it is working: >>> scale(100, 200, -2.0, 1.0) # halfway from -2 to 1 -0.5 >>> scale(100, 200, -1.5, 1.5) # halfway from -1.5 to 1.5 0.0 >>> scale(100, 300, -2.0, 1.0) # 1/3 of the way from -2 to 1 -1.0 >>> scale(25, 300, -2.0, 1.0) -1.75 0.99 Note Although we initially described scale as computing x-coordinate (real-axis) floating-point values, your scale function works equally well for both the x- and the y- dimensions. You don’t need a separate function for the vertical axis! Visualizing the Mandelbrot set in black and white: mset This part asks you to put the pieces from the above sections together into a function named mset(width, height) which will generate images of width width and height height with that computes the set of points in the Mandelbrot set on the complex plane and creates a bitmap of them. We will use images and, to focus on the interesting part of the complex plane, we will limit the ranges within the complex plane to -2.0 ≤ x or real coordinate ≤ +1.0 and -1.0 ≤ y or imaginary coordinate ≤ +1.0 which is a 3.0 x 2.0 rectangle. How to get started? Start by copying the code from the test function and renaming it as mset: def mset(): “”” creates a 300×200 image of the Mandelbrot set “”” width = 300 height = 200 image = PNGImage(width, height)# create a loop in order to draw some pixels for col in range(width): for row in range(height): # here is where you will need # to create the complex number, c! if inMSet( c, n ) == True: image.plotPoint(col, row)# we looped through every image pixel; we now write the fileimage.saveFile() To build the Mandelbrot set, you will need to change a number of behaviors in this function – start where the comment suggests that here is where…: • For each pixel col, you need to compute the real (x) coordinate of that pixel in the complex plane. Use the variable x to hold this x-coordinate, and use the scale function to find it! • For each pixel row, you need to compute the imaginary (y) coordinate of that pixel in the complex plane. Use the variable y to hold this y-coordinate, and again use the scale function to find it! Even though this will be the imaginary part of a complex number, it is simply a normal floatingpoint value. • Using the real and imaginary parts computed in the prior two steps, create a variable named c that holds a complex value with those real (x) and imaginary (y) parts, respectively. Recall that you’ll need to multiply y*1j, not y*j! • Finally, your test for which pixel col and row values to plot will involve inMSet, the first function you wrote. You’ll want to specify a value for the input named n to that inMSet function. I’d start with a value of 25 for n. Once you’ve composed your function, try >>> mset( ) and check to be sure that the image you get is a black-and-white version of the Mandelbrot set, e.g., something like this:
This problem is all about converting numbers from base 10 (where most humans operate) to base 2 (where virtually all computers operate) and vice versa. The Ingredients Remember that at this point in the course we are still using the functional-programming paradigm. If you happen to know about “for” loops or “while” loops or other constructs that we have not yet discussed, you should NOT use them here. Similarly, you should not use any fancy python features or special-purpose packages. Everything you need for these problems has been covered. However, there are a few built-in functions, described below, that you will want to use: • ord(C) is a function that takes a character as input and returns the integer representation (ASCII value) of that character. • chr(N) is a function that takes an integer as input and returns the character represented by that integer (in ASCII). • str(N) is a function that takes an integer as input and returns the string version of that integer. • int(S) is a function that takes a string of digits as input and returns the integer version of that string. • map Look this one up. We use it frequently. • reduce Another handy thing to keep in mind in this assignment is that the * operator can be used with strings. For example: >>> 3*”spam” ‘spamspamspam’ >>> -1*”spam” ” Computing with base-2 (binary) The goal of this part of the problem is to motivate a right-to-left conversion of decimal numbers into binary form. Thus, you will end up writing a function numToBinary(N) that works as follows: >>> numToBinary(5) ‘101’ >>> numToBinary(12) ‘1100’ As background, we’ll recall how to determine whether values are even or odd in Python: • First, write a Python function called isOdd(n) that takes as input an integer n and returns the value True if n is odd and False if n is even. Be sure to return these values, not strings! The evenness or oddness of a value is considered its parity. You should use the % operator (the “mod” operator). Remember that in python n % d returns the remainder when n is divided by d. Here are two examples of isOdd in action: >>> isOdd( 42 ) False >>> isOdd( 43 ) True • Next, let’s revisit the process of converting from base 10 to base 2. In particular, we’ll walk through the process of converting the number 42 in base 10 to a number in base 2. The left-toright way to do this is to observe that the largest power of 2 that occurs in 42 is 32. So, we write down a 1 in the “32’s place”. Now, we have 42-32=10 remaining. The next lower power of 2 after 32 is 16. But 16 doesn’t go into 10, so have a 0 in the “16’s place”. Now what? In a comment in your file, under your isOdd function, include the complete base-2 representation of the number 42. • The method of converting from base 10 to base 2 that we just looked at went from left to right. That is, we computed the most-significant bit – the largest power of 2 – first. Then we wrote down less-significant bits – lower powers of 2 – afterwards. This is not the only way to do the conversion! • In fact, a program to do it from right to left is both shorter and more “elegant.” This is what we will do next. To get started with this right-to-left conversion from decimal to binary, here’s a question for you to answer: If you are given an odd base-10 number, what will the least-significant bit – the rightmost bit – be in its base-2 representation? Similarly, if you are given an even base-10 number, what will the least-significant bit – the rightmost bit – be in its base-2 representation? In 12 sentences in a comment in your file, explain your answer to these two questions. • Next, suppose we have a base-2 number and we eliminate the least-significant bit (the rightmost digit). What does this do to the value of the original number? For example, if we start with1010 and eliminate the 0 at the end, we get 101. Similarly, if we start with 1011 and eliminate the 1 at the right, we get 101. Briefly explain how the value of the original number is changing in another comment in your file. Hint: if you’re not sure, read the next question for a hint… • Imagine that we have a number N written in base 10 (decimal). Let Y denote N/2, where we round down if N is odd (this is Python’s ordinary integer division). If we already had the base-2 representation of Y, perhaps from recursion, how would this allow us to easily find the base-2 representation of N? (You’ll need two answers here: one in the case that N is odd and one in the case that N is even.) Briefly explain your answer. • We can get the binary representation of N/2 by using recursion to call numToBinary on that value! Thus, we have all of the pieces needed to convert a number from base 10 to base 2 using the modulus operator %, division, and recursion. (You can use the shift operator >> instead of division, if you like.) Next, write a Python function numToBinary(N). You should assume that its input N will be >= 0. N will be a normal, base-10 integer. numToBinary should return a string that represents the number N in base 2. If N equals zero, however, your numToBinary function should return the empty string, not the string ‘0’. This is important as a base case!Here is some sample input and output: >>> numToBinary(0) ” >>> numToBinary(1) ‘1’ >>> numToBinary(4) ‘100’ >>> numToBinary(10) ‘1010’ >>> numToBinary(42) ‘101010’ >>> numToBinary(100) ‘1100100’ Hints: Recursion will be helpful here, as the above analysis suggests. If you’re stuck, consider the following skeleton for your approach: if N==0: return ” elif isOdd(N): return numToBinary( … else: return numToBinary( … Here, you will need to carefully choose two things: what inputs to pass to the recursive calls and the additional work needed after the recursive calls. • Next, let’s convert from base 2 to base 10, again from right to left. We’ll represent a base-2 number as a string of 0’s and 1’s. Write a Python function called binaryToNum(S) that takes as input a string S of 0’s and 1’s representing a base-2 number and returns the corresponding integer in base 10. Again, the exception is that an input of the empty string should return the numeric value 0. In this case, input strings of zeros should also output the integer 0. Here are some examples: >>> binaryToNum(“100”) 4 >>> binaryToNum(“1011”) 11 >>> binaryToNum(“00001011”) 11 >>> binaryToNum(“”) 0 >>> binaryToNum(“0”) 0 >>> binaryToNum(“1100100”) 100 >>> binaryToNum(“101010”) 42 It won’t work to compare S[-1] with the integer 0! Binary Counting! In this problem we’ll write several functions to do counting in binary using increasingly fancy techniques. • To get started, write a Python function called increment(S) that takes as input an 8-bit string S of 0’s and 1’s and returns the next largest number in base 2. Here is some sample input and output: >>> increment(‘00000000’) ‘00000001’ >>> increment(‘00000001’) ‘00000010’ >>> increment(‘00000111’) ‘00001000’ >>> increment(‘11111111’) ‘00000000’ Notice that increment(‘11111111’) should wrap around to the all-zeros string. Hint: use both of the conversion functions you wrote earlier in the lab! Consider how could you use the function len() and string multiplication with * to make sure that the output has enough leading zeros? • Now use your increment function to write a function called count(S, n) that takes an 8-bit binary string as input and begins counting up by one from the input S for n increments, printing each number as it goes. This means it will print a total of n+1 binary strings. You should use the python print command, since nothing is being returned in this case—just output to the screen. Here are some examples: >>> count(“00000000”, 4) 00000000 00000001 00000010 00000011 00000100 >>> count(“11111110”, 5) 11111110 11111111 00000000 00000001 00000010 00000011 Computing in base-3 (ternary and balanced ternary) There are 10 types of people in the world: those who know ternary, those who don’t, and those who think this is a binary joke. Ordinary Ternary For this part of the lab, we extend these representational ideas from base 2 (binary) to base 3 (ternary). Just as binary numbers use the two digits, 0 and 1, ternary numbers use the digits 0, 1, and 2. Consecutive columns in the ternary numbers represent consecutive powers of three. For example, the ternary number 1120 when, when evaluated from right to left, evaluates as 0 ones, 2 threes, 1 nine, and 1 twenty-seven. Or, to summarize, it is 0*1 + 2*3 + 1*9 + 1*27 == 42. In a comment or triple-quoted string, explain what the ternary representation is for the value 59, and why it is so. Use the thought processes behind the conversion functions you have already written to create the following two functions: • numToTernary(N), which should output a ternary string representing the value of the input N (just as numToBinary does) • ternaryToNum(S), which should output the value equivalent to the input string S, when S is interpreted in ternary. Here are a pair of examples to check for each: >>> numToTernary(42) ‘1120’ >>> numToTernary(4242) ‘12211010’ >>> ternaryToNum(‘1120’) 42 >>> ternaryToNum(‘12211010’) 4242
In this lab you’re going to be solving the knapsack problem. You are a renowned thief!So, the goal then is to maximize the value of the objects you bring with you, while still being able to carry it. The Knapsack Problem Remember that we care about two things when we’re attempting to fill our knapsack – we care about the value of each item, and we care about whether we can carry it out. So, let’s say we have a list like the following: items = [[2, 100], [3, 112], [4, 125]] Here we have a list of pairs which describes everything we need to know about the items in the museum – the first number in each of the pairs represents the weight of the item. The second number in each pair represents the value of the item. Your goal, then, is to write a function knapsack(capacity, itemList) which returns both the maximum value and the list of items that make this value, without exceeding the capacity of your knapsack. [maxval, [[item1weight, item1val], [item2weight, item2val], [item3weight, item3val]]] Remember NOT to reuse items! Museums don’t keep two of the same painting! (Hint: For each item in the museum, do you use it or lose it?) Finally becoming a successful thief Notice that filling your knapsack isn’t always ideal! Let’s take the example where you have a list of items like this: museumItems = [[1, 4], [5, 150], [4, 180]] capacity = 6 So, you’re in the museum, and you realize you can fit a total weight of “6” in your knapsack.There are these three items for you to choose from: the 4$ tuna fish sandwich, the heavy 150$ calculus textbook from the curator’s nighttime classes, and the pricey 180$ piece of pottery. You realize you can fit at most two items – so you go ahead and grab the tuna sandwich.But which of those other two is a better choice? While the textbook will certainly fill your bag, it’s definitely not worth as much as the vase.Therefore, you take the vase, and even though you have “1” unit of weight that you can still carry, you made a better decision than if you had just tried to fill your bag (184$ instead of 154$).And so, your knapsack function should tell you that – in this case, your python function would look like: >>> knapsack(6, [[1, 4], [5, 150], [4, 180]]) [184, [[1, 4], [4, 180]]]So that’s a total value of 184, while selecting the list of items [[1,4],[4,180]].Here’s some more tests to make sure your function works: >>> knapsack(76, [[36, 35], [10, 28], [39, 47], [8, 1], [7, 24]]) [100, [[10, 28], [39, 47], [8, 1], [7, 24]]] >>> knapsack(24, [[36, 35], [10, 28], [39, 47], [8, 1], [7, 24]]) [52, [[10, 28], [7, 24]]] >>> knapsack(25, [[36, 35], [10, 28], [39, 47], [8, 1], [7, 24]]) [53, [[10, 28], [8, 1], [7, 24]]]What happens if the museum has no items for you to take? >>> knapsack(20, []) [0, []] Then unfortunately, you leave the museum with nothing in the knapsack – and your total monetary gain is 0. And most importantly, don’t forget your knapsack! Let’s see what happens if you do forget it: >>> knapsack(0, [[1, 1000], [2, 3000], [4, 55000]]) [0, []] In this case, you’ve forgotten to bring your knapsack, and so you can’t take any of those wonderful pricey items with you. Your total gain is 0, and you leave with no items.
Making Change In this problem, you will solve a different problem using the powerful use-it-or-lose-it strategy. Imagine that you just got a job working for Cash Register Advanced Products. (The public relations division has suggested that the company avoid using an acronym for the company name.) The company builds electronic cash registers and the software that controls them. The cash registers are used all around the world in countries with different coin systems. Next, imagine that we are given a list of the coin types in a given country. For example, in the U.S. the coin types are: [1, 5, 10, 25, 50] But, in the Kingdom of Shmorbodia, the coin types are: [1, 7, 24, 42] In general, the coin system could be anything, except that there is always a 1 unit coin (penny). In these examples, the denominations were given smallest to largest, but that’s not necessary. There’s nothing about use-it-or-lose-it that depends on the order of the coins. Here’s the problem. Given an amount of money and a list of coin types, we would like to find the least number of coins that makes up that amount of money. For example, in the U.S. system, if we want to make 48 cents, we give out 1 quarter, 2 dimes, and 3 pennies. That solution uses 6 coins and that’s the best we can do in this case. Making 48 cents in the Shmorbodian system, however, is different. Giving out a 42 cent coin – albeit tempting – will force us to give the remaining balance with 6 pennies, using a total of 7 coins. We could do better by simply giving two 24 cent coins. Your first task is to write a function called change(amount, coins) where amount is a non-negative integer indicating the amount of money to be made and coins is a list of coin values with 1 always being in the list when we first call the function. (This ensures that it is always possible to make change for any positive amount.) The function should return a non-negative integer indicating the minimum number of coins required to make up the given amount. Here is an example of this function in action: >>> change(48, [1, 5, 10, 25, 50]) 6 >>> change(48, [1, 7, 24, 42]) 2CS 115 – Lab 3>>> change(35, [1, 3, 16, 30, 50]) 3 A few notes and tips… Not surprisingly, the secret-to-all-happiness is to use the use-it-or-lose-it recursion strategy. >>> float(“inf”) > 42 True >>> 42 + float(“inf”) inf >> min(42, float(“inf”)) 42
1. A cell that has fewer than two live neighbors dies (because of isolation) 2. A cell that has more than 3 live neighbors dies (because of overcrowding) 3. A cell that is dead and has exactly 3 live neighbors comes to life 4. All other cells maintain their state Although these rules seem simple, they give rise to complex and interesting patterns. For more information and a number of interesting patterns see http://en.wikipedia.org/wiki/Conway’s_Game_of_Life. In this lab, you will implement a Python program to run the Game of Life. Thinking about life… As always, it is important to break the problem down into pieces and develop the program in stages so that others can understand the code and so that you can ensure that each piece is correct before building on top of it. We will break this problem down into the following steps: • Creating a 2d array of cells • Displaying the board (in various colors) and updating it with new data • Allowing the user to change the state of the cells • Implementing the update rules for the “Game of Life” • (Optionally) Running and stopping the simulation Before you start, you need to develop a scheme for keeping track of your data. Basically, the data you need to maintain are the states of all of the cells in the board. To do this, you should keep track of this data in a 2D array of integer values, where 0 represents an empty (off) cell and 1 represents a live (on) cell. Files to start with… Start by downloading the .zip file from the following file: life_starter.zipIt will be easiest to place this zip file on the desktop and extract it there. There is some support code for graphically displaying your life generations (at the very bottom of the file), but that will be the final piece of the lab. First, you’ll implement the basic functionality for creating 2d arrays of data, changing them, and having them evolve according to the rules of Life… Step 1: Creating an empty 2d “board” of cells First, in the life.py file, you will see this example function: def createOneRow(width): “”” returns one row of zeros of width “width”… You might use this in your createBoard(width, height) function “”” row = [] for col in range(width): row += [0] return row This function offers a starting-point for creating one-dimensional lists—but the same idea applies for building nested list structures arbitrarily deep. createBoard(width, height) Building on this example, write a function named createBoard(width, height) that creates and returns a new 2D list of height rows and width columns in which all of the data elements are 0 (no graphics quite yet, just a Python list!). Avoid re-implementing the createOneRow function! Rather, use createOneRow inside your createBoard in the same way that 0 is used to accumulate individual elements in createOneRow. Here is a template — copy and paste this and then fill in the parts you’ll need to complete it: def createBoard(width, height): “”” returns a 2d array with “height” rows and “width” cols “”” A = [] for row in range(height): A += SOMETHING # What do you need to add a whole row here? return A That’s all you’ll need! Again, the idea is to follow the example of createOneRow — but instead of adding a 0 each time, the function would add a whole row of 0s, namely the output from createOneRow! Test out your createBoard function! For example, >>> A = createBoard(5, 3) >>> A [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]Printing your 2d board of cells You no doubt noticed that when Python prints a 2d list, it blithely ignores its 2d structure and flattens it out into one line (perhaps wrapping, if needed). In order to print your board in 2d using ASCII (we will use graphics once it’s working…), copy this function into your file: import sys def printBoard( A ): “”” this function prints the 2d list-of-lists A without spaces (using sys.stdout.write) “”” for row in A: for col in row: sys.stdout.write( str(col) ) sys.stdout.write( ‘ ‘ ) This printBoard function by passes Python’s behavior of placing a space between items it prints by using different calls in the library: sys.stdout.write outputs a character to the screen. This is why it needs to convert the integers in the array A to strings before writing them. Make sure your printBoard is working as follows: >>> A = createBoard(5,3) >>> printBoard(A) 00000 00000 00000 Adding patterns to 2d arrays… In order to get used to looping over 2d arrays of data, copy this function named diagonalize(A) into your file: def diagonalize(width,height): “”” creates an empty board and then modifies it so that it has a diagonal strip of “on” cells. “”” A = createBoard( width, height ) for row in range(height): for col in range(width): if row == col: A[row][col] = 1 else: A[row][col] = 0 return AThis function, diagonalize takes in a desired width and height. It then creates an array A and sets A’s data so that it is an array whose cells are empty except for the diagonal where row == col. Try displaying the result with >>> A = diagonalize(7,6) >>> A [[1, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 1, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1, 0]] >>> printBoard(A) 1000000 0100000 0010000 0001000 0000100 0000010 Take a moment to note the direction the diagonal is running—that indicates which way the rows of the board are being displayed: top-to-bottom, in this case. Also, this example shows that the height and width do not have to be the same — though it’s certainly ok if they are.More patterns… innerCells(w,h) Based on the example of diagonalize, write a variation named innerCells(w,h) which returns a 2d array of all live cells – with the value of 1 – except for a one-cell-wide border of empty cells (with the value of 0) around the edge of the 2d array. For example, you might try >>> A = innerCells(5,5) >>> printBoard(A) 00000 01110 01110 01110 00000 Hint: Consider the usual pair of nested loops for this one — except here, the ranges run from 1 to height-1 and from 1 to width-1 instead of the full extent of the board!randomCells(w,h) Here is one of our runs — note the safety margin ! >>> A = randomCells(10,10) >>> printBoard(A) 0000000000 0100000110 0001111100 0101011110 0000111000 0010101010 0010111010 0011010110 0110001000 0000000000 You might recall that random.choice( [0,1] ) will return either a 0 or a 1. You will need to import random to use it!copy( A ) Each of updating functions so far creates a new set of cells without regard to an old “generation” that it might depend on. Conway’s game of life, on the other hand, follows a set of cells by changing one generation into the next. To see why copy( A ) is a crucial helper function for this process, try the following commands: >>> oldA = createBoard(2,2) # create a 2×2 empty board >>> printBoard(oldA) # show it 00 00>>> newA = oldA # create a false (“shallow”) copy >>> printBoard(newA) # show it 00 00>>> oldA[0][0] = 1 # set oldA’s upper left corner to 1 >>> printBoard(oldA) # the upper left will be 1 10 00>>> printBoard(newA) # but newA has changed, too!! 10 00 Here we have made a “copy” of oldA, where we have named the copy newA. However, newA is simply a copy to the reference to the original data in oldA! As a result, when oldA’s data changes, so does newA’s data, even though we never touched newA’s data! The above example shows shallow copying: the copying of a reference to data, rather than making a full copy of all of the data. Making a full copy of all of the data is called deep copying. For this part of the lab, write a function named copy( A ), which will make a deep copy of the 2d array A. Thus, copy will take in a 2d array A and it will output a new 2d array of data that has the same pattern as the input array. To make sure you output new data, use createBoard to get a brand new array of the same size as the input array. Remember that you can get the number of rows (the height) in A with len(A) and the number of columns (the width) in A with len(A[0]). To make sure that your output data has the same pattern of 0s and 1s as the input array, you will want to use a pair of nested loops that sets the output array values to be equal to the input array values. Again, the output array will not reference the same data in the computer’s memory, but it will have a “deep copy” of that data. Make sure your copy function is working properly with this example: >>> oldA = createBoard(2,2) >>> printBoard(oldA) 00 00>>> newA = copy( oldA ) >>> printBoard(newA) 00 00>>> oldA[0][0] = 1 >>> printBoard(oldA) 10 00>>> printBoard(newA) 00 00 This time, newA has not changed just because oldA did! innerReverse( A ) Copying is a very simple — and not overly interesting — way that a new “generation” of array elements might depend on a previous generation of elements. Next you’ll write a function that changes one generation of cells into a new generation. To that end, write a function innerReverse( A ) that takes an old 2d array (or “generation”) and then creates a new generation of the same shape and size (either with copy, above, or createBoard). However, the new generation should be the “opposite” of A’s cells everywhere except on the outer edge. In the same spirit as innerCells, you should make sure that the new generation’s outer edge of cells are always all 0. However, for inner cells – those not on the edge – where A[row][col] is a 1, the new array’s value will be a 0 – and vice versa. Try out your innerReverse function by displaying an example. This one uses randomCells: >>> A = randomCells(8,8) >>> printBoard(A) 00000000 01011010 00110010 00000010 01111110 00101010 01111010 00000000>>> A2 = innerReverse(A) >>> printBoard(A2) 00000000 00100100 01001100 01111100 00000000 01010100 00000100 00000000 Aside: You might point out that it would be possible to simply change the old input A, rather than create and return new data — this is true for simply reversing the pattern of array elements, but it is not true when implementing the rules of Conway’s Game of Life – there, changing cells without copying would change the number of neighbors of other cells! Conway’s Game of Life So, for this step, create a function named next_life_generation( A ). Here is a starting signature: def next_life_generation( A ): “”” makes a copy of A and then advanced one generation of Conway’s game of life within the *inner cells* of that copy. The outer edge always stays 0. “”” This next_life_generation function should take in a 2d array A, representing the “old” generation of cells, and it should output the next generation of cells, each either 0 or 1, based on John Conway’s rules for the Game of Life: 1. All edge cells stay zero (0) (but see the extra challenges, below) 2. A cell that has fewer than two live neighbors dies (because of loneliness) 3. A cell that has more than 3 live neighbors dies (because of over-crowding) 4. A cell that is dead and has exactly 3 live neighbors comes to life 5. All other cells maintain their state For concreteness, let’s call the new generation of cells you’re returning newA in order to contrast it with A. As suggested in innerReverse, always keep all of the outer-edge cells empty!. This is simply a matter of limiting your loops to an appropriate range. However, it greatly simplifies the four update rules, above, because it means that you will only update the interior cells, each of which has a full set of eight neighbors without going out of bounds. It will help to write a helper function, countNeighbors( row, col, A ), that returns the number of live neighbors for a cell in the board A at a particular row and col. Warnings/hints: There are a few things to keep in mind: • Only count neighbors within the old generation A. Change only the new generation, newA. • Be sure to set every value of newA (the new data), whether or not it differs from A. • A cell is NOT a neighbor of itself. • A 2×2 square of cells is statically stable (if isolated) – you might try it on a small grid for testing purposes • A 3×1 line of cells oscillates with period 2 (if isolated)—also a good pattern to test. Here is a set of tests to try based on the last suggestion in the list above: >>> A = [ [0,0,0,0,0], [0,0,1,0,0], [0,0,1,0,0], [0,0,1,0,0], [0,0,0,0,0]]>>> printBoard(A) 00000 00100 00100 00100 00000>>> A2 = next_life_generation( A ) >>> printBoard(A2) 00000 00000 01110 00000 00000>>> A3 = next_life_generation( A2 ) >>> printBoard(A3) 00000 00100 00100 00100 00000 and so on… . Once your Game of Life is working, look for some of the other common patterns, e.g., other statically stable forms (“rocks”), as well as oscillators (“plants”) and others that will move across the screen, known as gliders (“animals/birds”). Graphical Life! Once your next_life_generation code is working, open and run the file lifegraphics.py. This file is counting on these things: • you have life.py in the same directory • you have written next_life_generation correctly in that file (named life.py) It handles four keypresses: PAUSE: ‘p’ RESUME: ‘Return’/’Enter’ RESET: ‘Space’ CLOSE: ‘Esc’ and you can start the simulation (using a 20×20 environment) with start(): >>> start() This call to start() should create a 20×20 2d array of cells, fill them randomly, and then continually call your next_life_generation function in order to update to the next generation. To pause the simulation, click the window and hit the p key. When paused, you should be able to change the state of cells by clicking in them… To resume, hit the Enter key (with the focus in that window). You should be able to close the window by the usual method of clicking the X in the corner — or by hitting the Escape key (Esc) with the focus in the life window. Colorful Life! You can change the colors used to represent 0 and 1 using the provided setColor function. For example, from the prompt you get after loading the lifegraphics.py file: >>> setColor( 0, “black” ) >>> setColor( 1, “gold” ) >>> start() will provide a black and gold color scheme.
Ultimately, all data in a computer is represented with 0’s and 1’s. We’ve explored how symbols can be represented as sequences of 0’s and 1’s; In this problem we’ll explore the representation of images using 0’s and 1’s. Let’s begin by considering just 8-by-8 black-and-white images such as the one below:Each cell in the image is called a “pixel”. A white pixel is represented by the digit 0 and a black pixel is represented by the digit 1. The first digit represents the pixel at the top left corner of the image. The next digit represents the pixel in the top row and the second column. The eighth bit represents the pixel at the right end of the top row. The next bit represents the leftmost pixel in the second row and so forth. Therefore, the image above is represented by the following binary string of length 64: ‘1010101001010101101010100101010110101010010101011010101001010101’ Of course, another way to represent that same string in python is ‘1010101001010101’*4 (recall that this means 4 copies of the string ‘1010101001010101’). Backstory (also optional!) So now what? Here’s the gratuitous background story: You’ve been hired by NASA. NASA has a deepspace satellite that takes 8-by-8 black-and-white images and sends them back to Earth as binary strings of 64 bits as described above. In order to save precious energy required for transmitting data, NASA would like to “compress” the images sent into a format that uses as few bits as possible. One way to do this is to use the run-length-encoding algorithm. Imagine that we have an image that looks like this, for example:Using our standard sequence of 64 bits, this image is represented by a binary string beginning with 16 consecutive 0’s (for two rows of white pixels) followed by 16 consecutive 1’s (for two rows of black pixels) followed by 16 consecutive 0’s followed by 16 consecutive 1’s. Run-length encoding (which, by the way, is used as part of the JPEG image compression algorithm) says: Let’s represent that image with the code “16 white, 16 black, 16 white, 16 black”. That’s a much shorter description than listing out the sequence of 64 pixels “white, white, white, white, …”. In general, run-length coding represents an image by a sequence (called a “run-length sequence”) of numbers: X1, X2, …, XN where X1 is the number of consecutive 0’s until the first 1. X2 is the number of consecutive 1’s until the next 0, etc. until we’re done. So, for our simple image above, we’d have the sequence 16, 16, 16, 16. Notice that, by convention, the first number in the sequence is the number of consecutive 0’s. Therefore, if the image/string starts with a 1, the first number in the run-length sequence would be 0 to indicate that the image begins with zero 0’s. How do we convert the run-length sequence into a binary sequence? After all, the satellite must send a sequence of 0’s and 1’s. One possibility is that we represent each term X1, X2, X3 in the run length sequence with a base-2 number with a fixed number, k, of bits. That way, we know that the first k bits correspond to the base 2 representation of X1. The next k bits correspond to the base 2 representation of X2, and so forth. (What is the right value of k to use? That’s up to you, but you’ll want to think about your choice so as not to use too few or too many bits.) Notice that this run-length encoding will probably result in a relatively small number of bits to represent the 4-stripe image above. However, it will probably do very badly (in terms of the number of bits that it uses) in representing the checkerboard image that we looked at first. In general, run-length encoding does a good job “compressing” images that have large blocks of solid color. Fortunately, this is true of many real-world images (such as the images that NASA gets, which are mostly white with a few black spots representing celestial bodies). Whew! So here’s your job: • Write a function called compress(S) that takes a binary string S of length 64 as input and returns another binary string as output. The output binary string should be a run-length encoding of the input string. • Write compression(S) to return the ratio of the compressed size to the original size for image S. “01111110”+”11111111″+”00111100″+”00100100″ o Smile: “0”*8 + “01100110”*2 + “0”*8 + “00001000” + “01000010” + “01111110” + “0”*8 o Five: “1”*9 + “0”*7 + “10000000”*2 + “1”*7 + “0” + “00000001”*2 + “1”*7 + “0”
Giving Change Just knowing the minimum number of coins is not as useful as getting the actual list of coins. Next, write another version of the change function called giveChange that takes the same kind of input as change but returns a list whose first item is the minimum number of coins and whose second item is a list of the coins in that optimal solution. Here’s an example: >>> giveChange(48, [1, 5, 10, 25, 50]) [6, [25, 10, 10, 1, 1, 1]] >>> giveChange(48, [1, 7, 24, 42]) [2, [24, 24]] >>> giveChange(35, [1, 3, 16, 30, 50]) [3, [16, 16, 3]] The order in which the coins are presented in the input list doesn’t really matter and, similarly, the order in which your solution reports the coins to use is also unimportant: In other words the solution [3, [16, 16, 3]] is the same to us as [3, [3, 16, 16] ] or [3, [16, 3, 16]]. All of these solutions use the same 3 coins after all! that giveChange will always return a list of the form [numberOfCoins, listOfCoins], you can modify your change function relatively modestly to get the giveChange function. First, your base cases must observe the convention and return such a list of the form [numberOfCoins, listOfCoins]. Then, when you call giveChange recursively, remember that it is returning a list of this form. Your function will need to pick apart that list to get at the number of coins and the list of coins in that solution. Finally, after deciding whether the use-it or lose-it solution is better, you can prepare your list of the form [numberOfCoins, listOfCoins] and return that list.
>>> f r o m m a t h i m p o r t factorial >>> factorial( 5) >>> 120 As shown above, we can use the factorial function from the math module. Here, you’ll write your own factorial function. First, we start with a simple function that returns the pro duct of its two inpu ts: def mult(x, y): “””Returns the product of x and y””” return x * y Nothing too surprising here. Now, take a look at this: >>> reduce(mult, [2, 3]) 6 >>> reduce(mult, [2, 3, 4]) 24 >>> reduce(mult, [1, 2, 3, 4]) 24 Notice that reduce takes two inputs: A function and a list and it applies that function to “compress” the list into a single value. In this case, it multiplied all of the values together. Now, write a function factorial(n) that takes a positive integer n and returns n!. This is “mean”… >>> len([1, 3, 5]) 3 >>> len(range(1,10)) 9 Here is the mean function in action: >>> mean([1, 2, 3]) 2 >>> mean([1, 1, 1]) 1
JOGL OpenGL Project Overview In this project you will create a unique 3 graphics scene composed of OpenGL graphic components using transformation methods. Requirements: 1. Using Netbeans or Eclipse, develop a JOGL application that displays a unique 3D scene. The scene has the following specifications: a. Size: minimum 640×480 b. Includes at least 6 different shapes c. Uses at least 6 different transformation methods2. Use Java and JOGL for your implementation of OpenGL 3. All Java source code should be written using Google Java style guide. 4. Prepare, conduct and document a test plan verifying your application is working as expected. This plan should include a test matrix listing each method you tested, how you tested it, and the results of testing.Deliverables: 1. All Java source code used for this project. Code should adhere to the Google Java style guide.Grading guidelines: Attribute Meets Design 20 points Methods used to isolate functionality (10 points)Code is efficient without sacrificing readability and understanding. (5 points) Code can easily be used and maintained. (5 points) Functionality 50 points Uses Netbeans or Eclipse to develop a JOGL application that displays a unique 3D scene. (10 points)Size of scene is at least 640×480. (10 points)1Includes at least 6 different shapes. (10 points)Uses at least 6 different transformation methods (10 points)Use Java and JOGL for your implementation of OpenGL (10 points)Testing 10 points Prepares, conducts and documents a test plan verifying application is functioning properly. (10 points)Documentation and deliverables 20 points Submits all Java source code used for this project. (5 points)Code adheres to the Google Java style guide. (5 points)Submits Word or PDF file demonstrating with clearly labeled screen captures and associated well-written descriptions, the successful execution of your 3D graphics scene. (5 points)2
