Notes: Of the three problems given below, one will be solved by the TAs in next week's discussion section, you will have to solve one in class, and the remaining problem is due in the lecture on Friday, 4/7.
Solution: Here is the solution. I have written a function called reverseList as part of the DoublyLinkedApp class. Here is the output I get when I run this program:
p-lnx203.cs.uiowa.edu% java DoublyLinkedApp List (first-->last): 66 44 22 11 33 55 List (last-->first): 55 33 11 22 44 66 The list has been reversed. List (first-->last): 55 33 11 22 44 66 List (last-->first): 66 44 22 11 33 55 List (first-->last): 33 22 44 List (first-->last): 33 88 22 77 44 The list has been reversed. List (first-->last): 44 77 22 88 33 p-lnx203.cs.uiowa.edu%
Solution: Here I have placed a modified Queens.java in which the main function places a queen at position (1, 0), marks all threatened positions, and then calls the function placeQueens to place the remaining 9 queens. Here is the solution I get by running the program.
p-lnx203.cs.uiowa.edu% java Queens Type the chess board size. 10 Here is a placement of the queens. x x Q x x x x x x x Q x x x x x x x x x x x x x x Q x x x x x x x x x x x x Q x x x x x Q x x x x x x x x x x x x x x Q x x x x x x x Q x x x x x Q x x x x x x x Q x x x x x x x x x x x x x x Q x x x
//********************************************** // Earlier I had tried board = oldBoard. I got // strange results. Why? //**********************************************
Once we realize that the current placement of the queen is not going to work, we want to restore the board to how it was earlier and try a new position for the queen. To do this, I kept a copy of board (called oldBoard) before I updated it and then if the current placement of the queen did not work, I want to restore board, by copying oldBoard back into it.
Without thinking too hard about this, in my first attempt, I simply used
board = oldBoard;and got strange results. You should try using this to see the results I got. Your task is to explain why I got those strange results.
Solution: In Java parameters are passed to functions by value. When the 2-d integer array board is passed into the function placeQueens, a local copy of the reference board is made. However, this copy is also pointing to the same 2-d integer array. So any changes that are made to the array using the copy are reflected when we return from the function. However, if during the function, the local copy is made to point to something else, then any changes made via the local copy are lost when we return back from the function. Specifically, the assignment, board = oldBoard; makes the local copy of board point to a new 2-d array that oldBoard is pointing to. Any changes made to this array via board are made to the 2-d array and not to the original array that board was pointing to.
int fibonacci(int n) { if((n == 1) || (n == 2)) return 1; else return fibonacci(n-1) + fibonacci(n-2); }
This function is not very useful for computing large Fibonacci numbers. For example, when I used it to compute the 50th Fibonacci number, it took about a minute and returned the following answer:
serv15.divms.uiowa.edu% java FibonacciTest Type a positive integer. 50 The 50th Fibonacci number is -298632863
Solution This is due to integer overflow. The 4 bytes that Java sets aside for an integer is not large enough to store the 50th Fibonacci number. The solution below fixes this problem.
Solution: Here is the program that contains an efficient, recursive fibonacci function using the idea desrcibed above. It uses the BigInteger class to represent integers in arbitrary precision. Here is the output of two test runs of this function.
p-lnx203.cs.uiowa.edu% javac FibonacciTest.java javap-lnx203.cs.uiowa.edu% java FibonacciTest Type a positive integer. 100 The 100th Fibonacci number is 354224848179261915075 p-lnx203.cs.uiowa.edu% java FibonacciTest Type a positive integer. 200 The 200th Fibonacci number is 280571172992510140037611932413038677189525