reface :
The Collection interface defines methods that describe the most general storage container. One model for the collection is a bag - like a bag of golf balls. In this section, we create a concrete collection class, appropriately called Bag, that implements the interface. The class is a generic collection that stores elements of a specific type. The underlying storage structure is a fixed length array. The length of the array is the maximum number of elements that the bag can hold. We refer to this as its capacity. The actual number of elements in a bag at any given time is its size. Below figure illustrates a Bag collection with capacity 5 and size 5. A constructor uses an integer argument to set the capacity and to initialize the size to 0 :
The Bag collection implements the Collection interfaces. This fact identifies the majority of methods in the class. Because the underlying storage structure is a fixed length array, we qualify the action of the add() method. Duplicate values are allowed but a new item is inserted only if the collection has room. If the size is less than the capacity, then add() inserts a new item and return true; otherwise it simply return false. In the Bag class, we define the grab() method, which returns a random element in the collection. The method provides access to elements in the collection without having to copy them to an array using toArray(). The class provides a toString() method that returns a comma-separated list of elements enclosed in brackets.
Creating and Using a Bag Collection :
A Bag collection is not a dynamic structure. It is created with a fixed capacity what cannot be changed. An application would typically use a Bag object only if it has prior information on the potential size of the collection. Let us look at an example that illustrates most of the Bag methods.
We input a string from the keyboard and use two Bag collections to store characters as Character objects. The collection bagA uses add() to store all of the characters in the string. A second collection, bagB, is derived from bagA to contain the distinct characters in the string. We build bagB by repeatedly using grab() to identify an element (character) in bagA and then adding it to bagB. All occurrences of the character are then removed from bagA. The process continues until bagA is empty. Afterward, we use sort() and toString(arr) in the java.util.Arrays class to order the elements in the array and to display the sorted list of distinct characters from the string :
Application: Sieve of Eratosthenes
The Green mathematician and philosopher Eratosthenes lived in the third century B.C. He discovered an intriguing method of using a bag to find all primes less than or equal to an integer value n. A prime p is an integer greater than 1 than is divisible only by 1 and p (itself). The algorithm begins by creating a bag with capacity n and then inserting into the collection Integer objects corresponding to integer values in the range form 2 to n. A loop makes multiple passes over the elements in the bag using successive integer key values 2, 3, 4 and so forth. Each pass shakes free nonprime numbers and lets them filter through the sieve. At the end, only the prime numbers remain.
The first pass begins with the integer m=2, which is the smallest prime number. The pass removes from the bag all multiples of 2 having the form 2*k, where k>=2. The multiples, 4=2x2, 6=2x3..., cannot be primes because they are divisible by 2. At the end of the first pass, we have removed all of the even number except 2, leaving the integers 2, 3, 5, 7... and so on. The second pass use integer m=3, which is a prime and is responsible for removing all multiples of 3. The third pass uses integer m=4, which is no longer in the bag. No action is taken and the algorithm moves to m=5, which is still in the collection and is a prime. The pass removes the multiples of 5 (25, 35, 55...) that remain.
The multiple passes use all values of m in the range :
Using the upper bound square-root n is an optimization feature of the algorithm. It is sufficient to remove all nonprime numbers from the bag. To verify this fact, assume that some nonprime (composite) number t = p * q remains in the collection. This leads to a contradiction. If both factory p and q greater than square-root n, then :
Hence, at least one factor, say, p, must satisfy the inequality p <= square-root n. This "small" factor p is the integer m tht defines a pass or p is a multiple ofm (p = m * k) for pass m, where :
for the two cases, t = m * q or t = m * k * q and so t is a multiple of m and has already been removed from the collection, contrary to our assumption. Below is a figure show the Sieve of Eratosthenes where finding all prime numbers in the range from 2 trough 120 :
Below is the sample code to take advantage of Bag class and figure out all the prime numbers between 2 to 120 :
The Collection interface defines methods that describe the most general storage container. One model for the collection is a bag - like a bag of golf balls. In this section, we create a concrete collection class, appropriately called Bag, that implements the interface. The class is a generic collection that stores elements of a specific type. The underlying storage structure is a fixed length array. The length of the array is the maximum number of elements that the bag can hold. We refer to this as its capacity. The actual number of elements in a bag at any given time is its size. Below figure illustrates a Bag collection with capacity 5 and size 5. A constructor uses an integer argument to set the capacity and to initialize the size to 0 :
The Bag collection implements the Collection interfaces. This fact identifies the majority of methods in the class. Because the underlying storage structure is a fixed length array, we qualify the action of the add() method. Duplicate values are allowed but a new item is inserted only if the collection has room. If the size is less than the capacity, then add() inserts a new item and return true; otherwise it simply return false. In the Bag class, we define the grab() method, which returns a random element in the collection. The method provides access to elements in the collection without having to copy them to an array using toArray(). The class provides a toString() method that returns a comma-separated list of elements enclosed in brackets.
Creating and Using a Bag Collection :
A Bag collection is not a dynamic structure. It is created with a fixed capacity what cannot be changed. An application would typically use a Bag object only if it has prior information on the potential size of the collection. Let us look at an example that illustrates most of the Bag methods.
We input a string from the keyboard and use two Bag collections to store characters as Character objects. The collection bagA uses add() to store all of the characters in the string. A second collection, bagB, is derived from bagA to contain the distinct characters in the string. We build bagB by repeatedly using grab() to identify an element (character) in bagA and then adding it to bagB. All occurrences of the character are then removed from bagA. The process continues until bagA is empty. Afterward, we use sort() and toString(arr) in the java.util.Arrays class to order the elements in the array and to display the sorted list of distinct characters from the string :
Application: Sieve of Eratosthenes
The Green mathematician and philosopher Eratosthenes lived in the third century B.C. He discovered an intriguing method of using a bag to find all primes less than or equal to an integer value n. A prime p is an integer greater than 1 than is divisible only by 1 and p (itself). The algorithm begins by creating a bag with capacity n and then inserting into the collection Integer objects corresponding to integer values in the range form 2 to n. A loop makes multiple passes over the elements in the bag using successive integer key values 2, 3, 4 and so forth. Each pass shakes free nonprime numbers and lets them filter through the sieve. At the end, only the prime numbers remain.
The first pass begins with the integer m=2, which is the smallest prime number. The pass removes from the bag all multiples of 2 having the form 2*k, where k>=2. The multiples, 4=2x2, 6=2x3..., cannot be primes because they are divisible by 2. At the end of the first pass, we have removed all of the even number except 2, leaving the integers 2, 3, 5, 7... and so on. The second pass use integer m=3, which is a prime and is responsible for removing all multiples of 3. The third pass uses integer m=4, which is no longer in the bag. No action is taken and the algorithm moves to m=5, which is still in the collection and is a prime. The pass removes the multiples of 5 (25, 35, 55...) that remain.
The multiple passes use all values of m in the range :
Using the upper bound square-root n is an optimization feature of the algorithm. It is sufficient to remove all nonprime numbers from the bag. To verify this fact, assume that some nonprime (composite) number t = p * q remains in the collection. This leads to a contradiction. If both factory p and q greater than square-root n, then :
Hence, at least one factor, say, p, must satisfy the inequality p <= square-root n. This "small" factor p is the integer m tht defines a pass or p is a multiple ofm (p = m * k) for pass m, where :
for the two cases, t = m * q or t = m * k * q and so t is a multiple of m and has already been removed from the collection, contrary to our assumption. Below is a figure show the Sieve of Eratosthenes where finding all prime numbers in the range from 2 trough 120 :
Below is the sample code to take advantage of Bag class and figure out all the prime numbers between 2 to 120 :
This message was edited 10 times. Last update was at 26/09/2010 12:24:29
沒有留言:
張貼留言