Difference between revisions of "CSC212 Homework 5 2014"
Line 1: | Line 1: | ||
--[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 23:24, 22 October 2014 (EDT) | --[[User:Thiebaut|D. Thiebaut]] ([[User talk:Thiebaut|talk]]) 23:24, 22 October 2014 (EDT) | ||
---- | ---- | ||
− | + | ||
<br /> | <br /> | ||
Line 40: | Line 40: | ||
− | * If the array contains [ | + | * If the array contains [3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63], and we are searching for key '''24''', then your program will output |
− | + | 6 | |
− | + | 7 | |
+ | 8 | ||
+ | 9 | ||
* You cannot use an iterative method that is not recursive. | * You cannot use an iterative method that is not recursive. | ||
− | * | + | * Submit your program on Moodle, in the Homework 5, Problem 1 section. |
Line 52: | Line 54: | ||
<br /> | <br /> | ||
− | =Problem # | + | =Problem #2= |
+ | <br /> | ||
+ | * Modify the N-Queens problem seen in [[CSC212_Lab_9_2014| Lab #9]] and make it compute the total number of different solutions existing for an NxN board. The program as we have seen in the lab stops when it finds a solution, but there might be many different possible ways of putting N queens on the NxN board. Make your program compute the total number of such solutions. | ||
+ | * The output of your program should just be an integer number representing the number of solutions. | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
+ | <br /> | ||
<br /> | <br /> | ||
− | |||
− | |||
<br /> | <br /> | ||
− | + | [[Category:CSC212]][[Category:Homework]] |
Revision as of 11:07, 23 October 2014
--D. Thiebaut (talk) 23:24, 22 October 2014 (EDT)
Problem #1
- Write a recursive Java program called Hw5_1.java that implements a modified recursive binary search that, instead of returning the index where the key was found, returns an ArrayList of all the indexes where the key is located.
- You must use this function to create a sorted array of dimension N:
private static int[] initSortedArray( int N ) {
if ( N<10 ) N = 10;
int[] array = new int[N];
array[0] = 3;
for ( int i=1; i<N; i++ )
array[ i ] = array[i-1] + (i*11)%7;
// duplicate some keys
for ( int i=1; i<4; i++ )
array[ N/3 + i] = array[N/3];
return array;
}
- This way the indexes for a given key will be known to the testing program in Moodle. For verification, this is the array created by the function for N = 20:
3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63
- If the array contains [3 7 8 13 15 21 24 24 24 24 34 36 42 45 45 49 50 55 57 63], and we are searching for key 24, then your program will output
6 7 8 9
- You cannot use an iterative method that is not recursive.
- Submit your program on Moodle, in the Homework 5, Problem 1 section.
Problem #2
- Modify the N-Queens problem seen in Lab #9 and make it compute the total number of different solutions existing for an NxN board. The program as we have seen in the lab stops when it finds a solution, but there might be many different possible ways of putting N queens on the NxN board. Make your program compute the total number of such solutions.
- The output of your program should just be an integer number representing the number of solutions.