木小木
Moderator
- 注册
- 2002-02-24
- 消息
- 12,213
- 荣誉分数
- 2
- 声望点数
- 218
可否请帮忙解释一下这个作业呢 该从何做起呢 看notes的话该主要看哪部分呢
Assignment 2
COMP 1005/1405
Due October 14 by 16:00
Question 1. Compute a list of prime numbers
A prime is an integer greater than or equal to 2 such that it can be divided only by 1 and itself. 2 is the smallest prime and the only even prime. For this question you will create a class named PrimeGenerator that can generate all primes less than a given number n. There should be three static methods in this class:
1) main ? is the method that asks the user for a positive number n, and then calls computePrimes, and displayPrimes
2) displayPrimes ? takes two parameters, the int n, and an array of ints containing the primes (called primes). This method prints the output as shown below (the method assumes that n is positive and that the array actually contains primes). The method should be private (not public).
3) computePrimes ? takes the single int n as its only parameter and returns an array of ints containing the prime numbers less than n. The method should be private (not public). The method must use the technique described below:
If integer k is not a prime, then k = ab, where either a or b must be less than the square root of n. Therefore, an integer k less than n is a prime if and only if it does not have a factor less than the square root of n. (You may use function Math.sqrt(x) to find the square root of x). The following is an example to show how to find all primes less than 100 by an algorithm called the sieve method. The square root of 100 is 10.
Step 1. Create an array of 100 Boolean values, and initialize all of them to true:
0 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9 T
10 T 11 T 12 T 13 T 14 T 15 T 16 T 17 T 18 T 19 T
20 T 21 T 22 T 23 T 24 T 25 T 26 T 27 T 28 T 29 T
30 T 31 T 32 T 33 T 34 T 35 T 36 T 37 T 38 T 39 T
40 T 41 T 42 T 43 T 44 T 45 T 46 T 47 T 48 T 49 T
50 T 51 T 52 T 53 T 54 T 55 T 56 T 57 T 58 T 59 T
60 T 61 T 62 T 63 T 64 T 65 T 66 T 67 T 68 T 69 T
70 T 71 T 72 T 73 T 74 T 75 T 76 T 77 T 78 T 79 T
80 T 81 T 82 T 83 T 84 T 85 T 86 T 87 T 88 T 89 T
90 T 91 T 92 T 93 T 94 T 95 T 96 T 97 T 98 T 99 T
Step 2. Starting from the member with index 2, change all the members with indices being multiples of 2 (except 2 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 T
10 F 11 T 12 F 13 T 14 F 15 T 16 F 17 T 18 F 19 T
20 F 21 T 22 F 23 T 24 F 25 T 26 F 27 T 28 F 29 T
30 F 31 T 32 F 33 T 34 F 35 T 36 F 37 T 38 F 39 T
40 F 41 T 42 F 43 T 44 F 45 T 46 F 47 T 48 F 49 T
50 F 51 T 52 F 53 T 54 F 55 T 56 F 57 T 58 F 59 T
60 F 61 T 62 F 63 T 64 F 65 T 66 F 67 T 68 F 69 T
70 F 71 T 72 F 73 T 74 F 75 T 76 F 77 T 78 F 79 T
80 F 81 T 82 F 83 T 84 F 85 T 86 F 87 T 88 F 89 T
90 F 91 T 92 F 93 T 94 F 95 T 96 F 97 T 98 F 99 T
Step 3. Look into the table, after index 2, the first index with a true value is 3. Then change the value of the members with indices being multiple of 3 (except 3 itself) to false. If a member is already false then it should remain false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 T 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 T 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 T
50 F 51 F 52 F 53 T 54 F 55 T 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 T 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 T 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 T 86 F 87 F 88 F 89 T
90 F 91 T 92 F 93 F 94 F 95 T 96 F 97 T 98 F 99 F
Step 4. After the value 3, the first index with a true value is 5. Change all members with indices being a multiple of 5 (except 5 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 F 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 F 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 T
50 F 51 F 52 F 53 T 54 F 55 F 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 F 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 T 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 F 86 F 87 F 88 F 89 T
90 F 91 T 92 F 93 F 94 F 95 F 96 F 97 T 98 F 99 F
Step 5. After the value 5, the first index with a true value is 7. Change all members with indices being a multiple of 7 (except 7 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 F 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 F 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 F
50 F 51 F 52 F 53 T 54 F 55 F 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 F 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 F 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 F 86 F 87 F 88 F 89 T
90 F 91 F 92 F 93 F 94 F 95 F 96 F 97 T 98 F 99 F
Step 6. The next index with a true value is 11, which is not less than 10, the square root of 100. All indices of the array that have a value True are the primes. Now, create another array of integers, that is just big enough, to store the indices in the first array with a value true starting from 2. This new array contains all primes less than 100, which are:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97
Your program should ask the user to enter a value n, and output a list of all primes less than n, with at most 10 primes in a row. Every number should take up four characters of space so that the output lines up nicely (assume that n is at most 1000).
The following is the output of a test run (user input is indicated with italics):
Enter an integer. This program will output a list of primes less than this number.
1000 // this line is entered by the user
The primes less than 1000 are
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
Question 2. Insertion Sort
In this question, we are going to use the Insertion Sort algorithm to sort arrays of integers. To sort an array means that to re-arrange the members of the array in increasing or decreasing order. To make it specific, in this assignment, we always sort arrays in increasing order.
Part I. Insertion Sort
During the Insertion Sort algorithm, an array is separated into two parts: the first part is sorted, and the second part is not sorted. When the algorithm begins, the first part contains one member. The insertion sort algorithm sorts an array by successively inserting members from the unsorted section of the array into the sorted section of the array. In the base case, an array with a single member is trivially sorted. Suppose that we have already sorted the first m members (with indices 0 to m 1) of an array a. Look at the member a[m]. Find the first member a, 0 i m 1, that is greater than a[m]. This i is called the insertion point, where a[m] is supposed to be (Note: finding the insertion point must be done as described below). If a[m 1] is not greater than a[m], the insertion point is m. Move members a to a[m 1] one location towards the end, (remember save the value of a[m]), and insert the value of a[m] into the location a. Then, the array is sorted from a[0] to a[m]. Continue in the way until the last member is inserted to its right location.
For example, suppose we want to sort the array 5, 1, 3, 7, 2, 6, 4, again by insertion sort.
The successive changes of the array are as follows:
5 | 1, 3, 7, 2, 6, 4. The sub-array with only the first member is sorted.
Insert 1 into the sorted part of the array.
1, 5 | 3, 7, 2, 6, 4. The first two members are sorted.
Insert 3 into the sorted part.
1, 3, 5 | 7, 2, 6, 4. The first three members are sorted.
Insert 7 into the sorted part.
1, 3, 5, 7 | 2, 6, 4. The first four members are sorted.
Insert 2 into the sorted part.
1, 2, 3, 5, 7 | 6, 4. The first five members are sorted.
Insert 6 into the sorted part.
1, 2, 3, 5, 6, 7 | 4. The first six members are sorted.
Insert 4 into the sorted part.
1, 2, 3, 4, 5, 6, 7. All members are sorted.
The remaining problem in this algorithm is how to find the insertion point to insert the next member a[m]. The brute-force algorithm is to scan all the members one by one in the sorted part from the beginning until the first member greater than a[m] is found. However, in this assignment, you must use a more efficient algorithm, called binary search, as described below.
Suppose we have an array a, whose first m members are sorted. We want to find, from a[0] to a[m 1], the insertion point for a[m], i.e., the index of the first member in a that is greater than a[m]. If a[m 1] is not greater than a[m], the insertion point is m. Define two variables lowerIndex, and upperIndex. The initial value of lowerIndex is 0, and the initial value of upperIndex is m. According to the binary search algorithm, a[m] is compared with the middle member a[k] in the sorted part, where k = (lowerIndex + upperIndex) / 2 (integer division). If a[m] is less than a[k], the insertion point must be in the range from 0 to k. In other words, upperIndex is changed to k. If a[m] is greater than or equal to a[k], then the insertion point must be in the range from k + 1 to m 1. That is, lowerIndex should change to k + 1. Repeat the same procedure in the new range until the lowerIndex = upperIndex, then the insertion point is determined.
Example. Suppose we have an array 1, 3, 5, 5, 7, 8, 9, 10, 5, with the first seven members sorted. m = 8. Using the binary search algorithm, we have the following steps:
1. lowerIndex = 0, upperIndex = 8, k = 4, ((a[8] = 5) < (a[k] = 7)).
2. lowerIndex = 0, upperIndex = 4, k = 2, ((a[8] = 5) > (a[k] = 5)).
3. lowerIndex = 3, upperIndex = 4, k = 3, ((a[8] = 5) >= (a[k] = 5)).
4. lowerIndex = 4, upperIndex = 4. Insertion point = 4.
Write a class called InsertionSort with the following three static methods:
a private static method printArray, which outputs the members in an array one by one with commas and a space separating them;
a private static method binarySearch that returns the insertion point;
a public static method sort that accepts an array and sorts it by the insertion sort algorithm. Note that, this method re-arranges the members in the original array. No new array is created and nothing is returned.
Additional requirement: the method sort should output the insertion point and the intermediate arrays after every step, as shown below.
Part II.
Write a class called SortTest that has three methods:
a private method readArray that reads, and returns an array of integers entered by the user from the keyboard using method getIntegerArray in class Keyboard;
a private method printArray that is the same as method printArray in class InsertionSort;
a method main that does the following:
(i) Calls method read array an array entered by the user.
(ii) Outputs the inputted array using printArray.
(iii) Sorts the input array using the InsertionSort sort method, and outputs the detailed process and the sorted array.
(iv) Ask whether the user want to sort another array, depending on the answer (by entering a character 'y' or 'n') that the use gives, repeat the procedure, or exit. If the user enters a letter other than 'y' or 'n', ask the user to re-enter it.
The following is the output of a sample run: (The Italic lines are entered by the user.)
Enter an array of integers separated by blanks.
3 1 4 4 5 6 4
The input array is
3, 1, 4, 4, 5, 6, 4,
Insert 1
The insertion point is 0
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 2
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 3
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 5
The insertion point is 4
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 6
The insertion point is 5
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 4
The array becomes 1, 3, 4, 4, 4, 5, 6,
The sorted array is
1, 3, 4, 4, 4, 5, 6,
Do you want to sort another array? (y/n)
a
Please enter either 'y' or 'n'.
n
Question 3. Class Fraction
A fraction is a quotient of two integers a/b, where b 0. The arithmetic operations of fractions follow following rules:
a/b + c/d = (ad + bc)/bd;
a/b c/d = (ad bc)/bd;
We say two fractions a/b and c/d are equivalent, if ad = bc.
This class uses two public fields (instance variables) numerator and denominator, both of type int, to represent fractions in their equivalent reduced form. A fraction is in its reduced form if the denominator is positive, and the greatest common divisor of the numerator and the denominator is 1.
Write two private helper methods in this class:
The first is a static method called gcd that takes two positive integer parameters a and b, and returns the integer that is the greatest common divisor of a and b. The algorithm to find the greatest common divisor (gcd) of two positive integers is called the Euclidean algorithm, which goes like the following:
Let a and b be two positive integers. Denote b by r0. Divide a by r0. The quotient is q1 and the remainder is r1. If r1 = 0, the gcd of a and b is r0 = b. If r1 > 0, then divide r0 by r1. The quotient is q2 and the remainder is r2. If r2 is 0, the gcd is r1. Otherwise, divide r1 by r2. Continue in this way, the last non-zero remainder is the gcd.
For example, the greatest common divisor of 931 and 721 is 7 found by the following steps:
931 % 721 = 210,
721 % 210 = 91,
210 % 91 = 28,
91 % 28 = 7,
28 % 7 = 0.
The second method is an instance method, called reduce, that reduces a fraction to an equivalent reduced form in the following way:
(i) Every fraction of the type 0/a, where a is any non-zero integer, is reduced to 0/1.
(ii) Suppose the numerator of a fraction is not 0, and we want to reduce it to an equivalent fraction of the reduced form. Let n be the absolute value of the numerator, and let d be the absolute value of the denominator. Suppose g is the gcd of n and d. Divide both the numerator and the denominator by g. If the denominator is negative, multiply both the numerator and the denominator by 1.
Write three constructors in this class:
The first constructor accepts two int parameters a and b, assuming b 0. It creates a fraction with a numerator a and a denominator b. Then it calls method reduce to represent this fraction to the reduced form. For example, the call Fraction(4, 6) creates an object of class Fraction with numerator 2 and denominator 3; the call Fraction(0, 2) creates and object of class Fraction with numerator 0 and denominator 1.
The second constructor accepts one int parameter n, and it creates a fraction n/1. This constructor must call the first constructor.
The third constructor is a default constructor. This default constructor creates a fraction 0/1. This constructor must call the second constructor.
Write methods to do the following arithmetic operations:
For both of the operations add and subtract, write two methods: one instance method and one class method (i.e., static method).
For the case of add, the instance method adds the second operand to the first operand and returns the modified first operand. For example, if an instance method is called to add two Fraction objects x and y representing the fractions 2/3 and 1/4 respectively, then x is changed to 2/3 + 1/4 = 11/12 and returned, while y is still 1/4. The class method returns the result of the operation without changing the operands. For example, if thea class method is called to add x and y, then it returns the sum 11/12, while object x is still 2/3, and object y is still 1/4.
To make two methods that perform the same operation, you should use one method to implement the other. In this assignment, you mustshould use the instance method to implement the class method. For example, assume you have written an instance method add to add two Fractions. In the class method add, you should find a way to call the instance method add to find the sum without changing either parameter of the class method, and return the sum. You should not use the formula to calculate the sum again.
The result of an operation may not be of the reduced form. For example, 5/6 1/6 = 4/6, which is not in the reduced form. We have to called the method reduce after every operation is done.
Write a toString method that converts a fraction to a String of the format such as "2/3", "5/7", and so on. If the denominator is 1, this fraction should be converted to the String version of the demoninator. For example, the fraction 57/1 should be converted to the String "57", and the fraction 0/1 should be converted to the String "0". To convert a single integer to a String, use the method Integer.toString(n). This method returns a String representing integer n. For example, if n = 123, then the call Integer.toString(n) returns a String "123".
A tester class for your class Fraction is provided in the FractionTester.java file. You should change the object to make sure your implementation works for all cases.
The output of running FractionTest is
f1 = 7/8, f2 = -4/3
f3 = 0, f4 = -1/3
f5 = 4, f6 = 12
f7 = -4, f8 = 0
The sum of 7/8 and -4/3 is -11/24
The sum of 7/8 and 0 is 7/8
The sum of 0 and 0 is 0
The sum of 4 and -4 is 0
The sum of -1/3 and 4 is 11/3
The difference of 7/8 and -4/3 is 53/24
The difference of -4/3 and -1/3 is -1
The difference of 0 and -1/3 is 1/3
The difference of 7/8 and 0 is 7/8
The difference of 0 and 0 is 0
Add -4/3 to 7/8, 7/8 is changed to -11/24
Subtract -4/3 from -11/24, -11/24 is changed to 7/8
Marking Scheme:
This assignment is out of 90.
Question 1. 15 marks.
If your program does not compile, give at most 5 marks according to how much is achieved. If the output is not correct, give at most 10 marks. If the output is not in a nice format as specified in the question, give at most 12 marks.
Question 2. 35 marks.
If your program does not compile, give at most 5 marks according to how much is achieved.
Method BinarySearch: 10 marks.
Method Insertion: 10 marks.
Class SortTest: 10 marks.
5 more marks are awarded for the style, organization and the readability of the program.
Question 3. 40 marks
If your program does not compile, give at most 10 marks according to how much is achieved.
Method gcd: 5 marks
Method reduce: 5 marks
Constructors: 10 marks
The arithmetic operation methods: 10 marks
The toString method: 5 marks
5 more marks are awarded for the style, readability, and organization of your program.
:blowzy:
Assignment 2
COMP 1005/1405
Due October 14 by 16:00
Question 1. Compute a list of prime numbers
A prime is an integer greater than or equal to 2 such that it can be divided only by 1 and itself. 2 is the smallest prime and the only even prime. For this question you will create a class named PrimeGenerator that can generate all primes less than a given number n. There should be three static methods in this class:
1) main ? is the method that asks the user for a positive number n, and then calls computePrimes, and displayPrimes
2) displayPrimes ? takes two parameters, the int n, and an array of ints containing the primes (called primes). This method prints the output as shown below (the method assumes that n is positive and that the array actually contains primes). The method should be private (not public).
3) computePrimes ? takes the single int n as its only parameter and returns an array of ints containing the prime numbers less than n. The method should be private (not public). The method must use the technique described below:
If integer k is not a prime, then k = ab, where either a or b must be less than the square root of n. Therefore, an integer k less than n is a prime if and only if it does not have a factor less than the square root of n. (You may use function Math.sqrt(x) to find the square root of x). The following is an example to show how to find all primes less than 100 by an algorithm called the sieve method. The square root of 100 is 10.
Step 1. Create an array of 100 Boolean values, and initialize all of them to true:
0 T 1 T 2 T 3 T 4 T 5 T 6 T 7 T 8 T 9 T
10 T 11 T 12 T 13 T 14 T 15 T 16 T 17 T 18 T 19 T
20 T 21 T 22 T 23 T 24 T 25 T 26 T 27 T 28 T 29 T
30 T 31 T 32 T 33 T 34 T 35 T 36 T 37 T 38 T 39 T
40 T 41 T 42 T 43 T 44 T 45 T 46 T 47 T 48 T 49 T
50 T 51 T 52 T 53 T 54 T 55 T 56 T 57 T 58 T 59 T
60 T 61 T 62 T 63 T 64 T 65 T 66 T 67 T 68 T 69 T
70 T 71 T 72 T 73 T 74 T 75 T 76 T 77 T 78 T 79 T
80 T 81 T 82 T 83 T 84 T 85 T 86 T 87 T 88 T 89 T
90 T 91 T 92 T 93 T 94 T 95 T 96 T 97 T 98 T 99 T
Step 2. Starting from the member with index 2, change all the members with indices being multiples of 2 (except 2 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 T
10 F 11 T 12 F 13 T 14 F 15 T 16 F 17 T 18 F 19 T
20 F 21 T 22 F 23 T 24 F 25 T 26 F 27 T 28 F 29 T
30 F 31 T 32 F 33 T 34 F 35 T 36 F 37 T 38 F 39 T
40 F 41 T 42 F 43 T 44 F 45 T 46 F 47 T 48 F 49 T
50 F 51 T 52 F 53 T 54 F 55 T 56 F 57 T 58 F 59 T
60 F 61 T 62 F 63 T 64 F 65 T 66 F 67 T 68 F 69 T
70 F 71 T 72 F 73 T 74 F 75 T 76 F 77 T 78 F 79 T
80 F 81 T 82 F 83 T 84 F 85 T 86 F 87 T 88 F 89 T
90 F 91 T 92 F 93 T 94 F 95 T 96 F 97 T 98 F 99 T
Step 3. Look into the table, after index 2, the first index with a true value is 3. Then change the value of the members with indices being multiple of 3 (except 3 itself) to false. If a member is already false then it should remain false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 T 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 T 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 T
50 F 51 F 52 F 53 T 54 F 55 T 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 T 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 T 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 T 86 F 87 F 88 F 89 T
90 F 91 T 92 F 93 F 94 F 95 T 96 F 97 T 98 F 99 F
Step 4. After the value 3, the first index with a true value is 5. Change all members with indices being a multiple of 5 (except 5 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 F 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 F 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 T
50 F 51 F 52 F 53 T 54 F 55 F 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 F 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 T 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 F 86 F 87 F 88 F 89 T
90 F 91 T 92 F 93 F 94 F 95 F 96 F 97 T 98 F 99 F
Step 5. After the value 5, the first index with a true value is 7. Change all members with indices being a multiple of 7 (except 7 itself) to false.
0 T 1 T 2 T 3 T 4 F 5 T 6 F 7 T 8 F 9 F
10 F 11 T 12 F 13 T 14 F 15 F 16 F 17 T 18 F 19 T
20 F 21 F 22 F 23 T 24 F 25 F 26 F 27 F 28 F 29 T
30 F 31 T 32 F 33 F 34 F 35 F 36 F 37 T 38 F 39 F
40 F 41 T 42 F 43 T 44 F 45 F 46 F 47 T 48 F 49 F
50 F 51 F 52 F 53 T 54 F 55 F 56 F 57 F 58 F 59 T
60 F 61 T 62 F 63 F 64 F 65 F 66 F 67 T 68 F 69 F
70 F 71 T 72 F 73 T 74 F 75 F 76 F 77 F 78 F 79 T
80 F 81 F 82 F 83 T 84 F 85 F 86 F 87 F 88 F 89 T
90 F 91 F 92 F 93 F 94 F 95 F 96 F 97 T 98 F 99 F
Step 6. The next index with a true value is 11, which is not less than 10, the square root of 100. All indices of the array that have a value True are the primes. Now, create another array of integers, that is just big enough, to store the indices in the first array with a value true starting from 2. This new array contains all primes less than 100, which are:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97
Your program should ask the user to enter a value n, and output a list of all primes less than n, with at most 10 primes in a row. Every number should take up four characters of space so that the output lines up nicely (assume that n is at most 1000).
The following is the output of a test run (user input is indicated with italics):
Enter an integer. This program will output a list of primes less than this number.
1000 // this line is entered by the user
The primes less than 1000 are
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
73 79 83 89 97 101 103 107 109 113
127 131 137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223 227 229
233 239 241 251 257 263 269 271 277 281
283 293 307 311 313 317 331 337 347 349
353 359 367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457 461 463
467 479 487 491 499 503 509 521 523 541
547 557 563 569 571 577 587 593 599 601
607 613 617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719 727 733
739 743 751 757 761 769 773 787 797 809
811 821 823 827 829 839 853 857 859 863
877 881 883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997
Question 2. Insertion Sort
In this question, we are going to use the Insertion Sort algorithm to sort arrays of integers. To sort an array means that to re-arrange the members of the array in increasing or decreasing order. To make it specific, in this assignment, we always sort arrays in increasing order.
Part I. Insertion Sort
During the Insertion Sort algorithm, an array is separated into two parts: the first part is sorted, and the second part is not sorted. When the algorithm begins, the first part contains one member. The insertion sort algorithm sorts an array by successively inserting members from the unsorted section of the array into the sorted section of the array. In the base case, an array with a single member is trivially sorted. Suppose that we have already sorted the first m members (with indices 0 to m 1) of an array a. Look at the member a[m]. Find the first member a, 0 i m 1, that is greater than a[m]. This i is called the insertion point, where a[m] is supposed to be (Note: finding the insertion point must be done as described below). If a[m 1] is not greater than a[m], the insertion point is m. Move members a to a[m 1] one location towards the end, (remember save the value of a[m]), and insert the value of a[m] into the location a. Then, the array is sorted from a[0] to a[m]. Continue in the way until the last member is inserted to its right location.
For example, suppose we want to sort the array 5, 1, 3, 7, 2, 6, 4, again by insertion sort.
The successive changes of the array are as follows:
5 | 1, 3, 7, 2, 6, 4. The sub-array with only the first member is sorted.
Insert 1 into the sorted part of the array.
1, 5 | 3, 7, 2, 6, 4. The first two members are sorted.
Insert 3 into the sorted part.
1, 3, 5 | 7, 2, 6, 4. The first three members are sorted.
Insert 7 into the sorted part.
1, 3, 5, 7 | 2, 6, 4. The first four members are sorted.
Insert 2 into the sorted part.
1, 2, 3, 5, 7 | 6, 4. The first five members are sorted.
Insert 6 into the sorted part.
1, 2, 3, 5, 6, 7 | 4. The first six members are sorted.
Insert 4 into the sorted part.
1, 2, 3, 4, 5, 6, 7. All members are sorted.
The remaining problem in this algorithm is how to find the insertion point to insert the next member a[m]. The brute-force algorithm is to scan all the members one by one in the sorted part from the beginning until the first member greater than a[m] is found. However, in this assignment, you must use a more efficient algorithm, called binary search, as described below.
Suppose we have an array a, whose first m members are sorted. We want to find, from a[0] to a[m 1], the insertion point for a[m], i.e., the index of the first member in a that is greater than a[m]. If a[m 1] is not greater than a[m], the insertion point is m. Define two variables lowerIndex, and upperIndex. The initial value of lowerIndex is 0, and the initial value of upperIndex is m. According to the binary search algorithm, a[m] is compared with the middle member a[k] in the sorted part, where k = (lowerIndex + upperIndex) / 2 (integer division). If a[m] is less than a[k], the insertion point must be in the range from 0 to k. In other words, upperIndex is changed to k. If a[m] is greater than or equal to a[k], then the insertion point must be in the range from k + 1 to m 1. That is, lowerIndex should change to k + 1. Repeat the same procedure in the new range until the lowerIndex = upperIndex, then the insertion point is determined.
Example. Suppose we have an array 1, 3, 5, 5, 7, 8, 9, 10, 5, with the first seven members sorted. m = 8. Using the binary search algorithm, we have the following steps:
1. lowerIndex = 0, upperIndex = 8, k = 4, ((a[8] = 5) < (a[k] = 7)).
2. lowerIndex = 0, upperIndex = 4, k = 2, ((a[8] = 5) > (a[k] = 5)).
3. lowerIndex = 3, upperIndex = 4, k = 3, ((a[8] = 5) >= (a[k] = 5)).
4. lowerIndex = 4, upperIndex = 4. Insertion point = 4.
Write a class called InsertionSort with the following three static methods:
a private static method printArray, which outputs the members in an array one by one with commas and a space separating them;
a private static method binarySearch that returns the insertion point;
a public static method sort that accepts an array and sorts it by the insertion sort algorithm. Note that, this method re-arranges the members in the original array. No new array is created and nothing is returned.
Additional requirement: the method sort should output the insertion point and the intermediate arrays after every step, as shown below.
Part II.
Write a class called SortTest that has three methods:
a private method readArray that reads, and returns an array of integers entered by the user from the keyboard using method getIntegerArray in class Keyboard;
a private method printArray that is the same as method printArray in class InsertionSort;
a method main that does the following:
(i) Calls method read array an array entered by the user.
(ii) Outputs the inputted array using printArray.
(iii) Sorts the input array using the InsertionSort sort method, and outputs the detailed process and the sorted array.
(iv) Ask whether the user want to sort another array, depending on the answer (by entering a character 'y' or 'n') that the use gives, repeat the procedure, or exit. If the user enters a letter other than 'y' or 'n', ask the user to re-enter it.
The following is the output of a sample run: (The Italic lines are entered by the user.)
Enter an array of integers separated by blanks.
3 1 4 4 5 6 4
The input array is
3, 1, 4, 4, 5, 6, 4,
Insert 1
The insertion point is 0
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 2
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 3
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 5
The insertion point is 4
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 6
The insertion point is 5
The array becomes 1, 3, 4, 4, 5, 6, 4,
Insert 4
The insertion point is 4
The array becomes 1, 3, 4, 4, 4, 5, 6,
The sorted array is
1, 3, 4, 4, 4, 5, 6,
Do you want to sort another array? (y/n)
a
Please enter either 'y' or 'n'.
n
Question 3. Class Fraction
A fraction is a quotient of two integers a/b, where b 0. The arithmetic operations of fractions follow following rules:
a/b + c/d = (ad + bc)/bd;
a/b c/d = (ad bc)/bd;
We say two fractions a/b and c/d are equivalent, if ad = bc.
This class uses two public fields (instance variables) numerator and denominator, both of type int, to represent fractions in their equivalent reduced form. A fraction is in its reduced form if the denominator is positive, and the greatest common divisor of the numerator and the denominator is 1.
Write two private helper methods in this class:
The first is a static method called gcd that takes two positive integer parameters a and b, and returns the integer that is the greatest common divisor of a and b. The algorithm to find the greatest common divisor (gcd) of two positive integers is called the Euclidean algorithm, which goes like the following:
Let a and b be two positive integers. Denote b by r0. Divide a by r0. The quotient is q1 and the remainder is r1. If r1 = 0, the gcd of a and b is r0 = b. If r1 > 0, then divide r0 by r1. The quotient is q2 and the remainder is r2. If r2 is 0, the gcd is r1. Otherwise, divide r1 by r2. Continue in this way, the last non-zero remainder is the gcd.
For example, the greatest common divisor of 931 and 721 is 7 found by the following steps:
931 % 721 = 210,
721 % 210 = 91,
210 % 91 = 28,
91 % 28 = 7,
28 % 7 = 0.
The second method is an instance method, called reduce, that reduces a fraction to an equivalent reduced form in the following way:
(i) Every fraction of the type 0/a, where a is any non-zero integer, is reduced to 0/1.
(ii) Suppose the numerator of a fraction is not 0, and we want to reduce it to an equivalent fraction of the reduced form. Let n be the absolute value of the numerator, and let d be the absolute value of the denominator. Suppose g is the gcd of n and d. Divide both the numerator and the denominator by g. If the denominator is negative, multiply both the numerator and the denominator by 1.
Write three constructors in this class:
The first constructor accepts two int parameters a and b, assuming b 0. It creates a fraction with a numerator a and a denominator b. Then it calls method reduce to represent this fraction to the reduced form. For example, the call Fraction(4, 6) creates an object of class Fraction with numerator 2 and denominator 3; the call Fraction(0, 2) creates and object of class Fraction with numerator 0 and denominator 1.
The second constructor accepts one int parameter n, and it creates a fraction n/1. This constructor must call the first constructor.
The third constructor is a default constructor. This default constructor creates a fraction 0/1. This constructor must call the second constructor.
Write methods to do the following arithmetic operations:
For both of the operations add and subtract, write two methods: one instance method and one class method (i.e., static method).
For the case of add, the instance method adds the second operand to the first operand and returns the modified first operand. For example, if an instance method is called to add two Fraction objects x and y representing the fractions 2/3 and 1/4 respectively, then x is changed to 2/3 + 1/4 = 11/12 and returned, while y is still 1/4. The class method returns the result of the operation without changing the operands. For example, if thea class method is called to add x and y, then it returns the sum 11/12, while object x is still 2/3, and object y is still 1/4.
To make two methods that perform the same operation, you should use one method to implement the other. In this assignment, you mustshould use the instance method to implement the class method. For example, assume you have written an instance method add to add two Fractions. In the class method add, you should find a way to call the instance method add to find the sum without changing either parameter of the class method, and return the sum. You should not use the formula to calculate the sum again.
The result of an operation may not be of the reduced form. For example, 5/6 1/6 = 4/6, which is not in the reduced form. We have to called the method reduce after every operation is done.
Write a toString method that converts a fraction to a String of the format such as "2/3", "5/7", and so on. If the denominator is 1, this fraction should be converted to the String version of the demoninator. For example, the fraction 57/1 should be converted to the String "57", and the fraction 0/1 should be converted to the String "0". To convert a single integer to a String, use the method Integer.toString(n). This method returns a String representing integer n. For example, if n = 123, then the call Integer.toString(n) returns a String "123".
A tester class for your class Fraction is provided in the FractionTester.java file. You should change the object to make sure your implementation works for all cases.
The output of running FractionTest is
f1 = 7/8, f2 = -4/3
f3 = 0, f4 = -1/3
f5 = 4, f6 = 12
f7 = -4, f8 = 0
The sum of 7/8 and -4/3 is -11/24
The sum of 7/8 and 0 is 7/8
The sum of 0 and 0 is 0
The sum of 4 and -4 is 0
The sum of -1/3 and 4 is 11/3
The difference of 7/8 and -4/3 is 53/24
The difference of -4/3 and -1/3 is -1
The difference of 0 and -1/3 is 1/3
The difference of 7/8 and 0 is 7/8
The difference of 0 and 0 is 0
Add -4/3 to 7/8, 7/8 is changed to -11/24
Subtract -4/3 from -11/24, -11/24 is changed to 7/8
Marking Scheme:
This assignment is out of 90.
Question 1. 15 marks.
If your program does not compile, give at most 5 marks according to how much is achieved. If the output is not correct, give at most 10 marks. If the output is not in a nice format as specified in the question, give at most 12 marks.
Question 2. 35 marks.
If your program does not compile, give at most 5 marks according to how much is achieved.
Method BinarySearch: 10 marks.
Method Insertion: 10 marks.
Class SortTest: 10 marks.
5 more marks are awarded for the style, organization and the readability of the program.
Question 3. 40 marks
If your program does not compile, give at most 10 marks according to how much is achieved.
Method gcd: 5 marks
Method reduce: 5 marks
Constructors: 10 marks
The arithmetic operation methods: 10 marks
The toString method: 5 marks
5 more marks are awarded for the style, readability, and organization of your program.
:blowzy:
