A main method is provided to demonstrate this method. The result is at the bottom of the code.
/*
* Data Structures and Object-Oriented Programming - Assignment 10
* Question 24.24 of Introduction to Java Programming (by Daniel Liang)
*
* Find the Smallest Number (Divide and Conquer Approach)
*
* This program finds the smallest number of a list using a
* divide and conquer approach; specifically, recursion, with
* the original list split in two.
*
* Programmed by Gregory Desrosiers
*
* Start Date: April 28, 2013
* End Date: May 5, 2013
*
* File Name: Chapter24Exercise24.java
* Teacher: Amin Ranj Bar
*
* *SPECIAL*: Regardless if the list size is odd, the program is able to
* find the smallest value in the list.
*/
import java.util.*;
public class Chapter24Exercise24
{
public static void main(String[] args)
{
List<Double> values = new ArrayList<Double>();
Random randomizer = new Random();
for (int x = 0; x < 125 ; x ++)
values.add((double)randomizer.nextInt(150));
System.out.println("Test Case Values:");
for (int x = 0; x < values.size() ; x ++)
System.out.println(values.get(x));
System.out.println("\nThe smallest number in the list is " + smallestNumberInList(values)+ ".\n");
}
public static double smallestNumberInList(List<Double> numberList)
{
if (numberList.size() == 2)
{
double smallestNumber = numberList.get(0);
for(int x = 0; x < numberList.size(); x++)
{
if (numberList.get(x) < smallestNumber)
smallestNumber = numberList.get(x);
}
return smallestNumber;
}
else
{
if (numberList.size() > 2)
{
if (smallestNumberInList(numberList.subList(0, numberList.size() / 2)) <
smallestNumberInList(numberList.subList(numberList.size() / 2, numberList.size())))
return smallestNumberInList(numberList.subList(0, numberList.size() / 2));
else
return smallestNumberInList(numberList.subList(numberList.size() / 2, numberList.size()));
}
// The statement below should not be there, but this is to prevent a compiler error.
// And this statement is invoked when the initialized number list only has one value.
return numberList.get(0);
}
}
}
Console Output:
Test Case Values:
26.0
128.0
126.0
55.0
67.0
49.0
85.0
44.0
2.0
64.0
25.0
48.0
75.0
121.0
40.0
115.0
91.0
87.0
2.0
12.0
21.0
149.0
32.0
118.0
98.0
46.0
97.0
72.0
119.0
5.0
142.0
113.0
107.0
47.0
91.0
84.0
4.0
86.0
50.0
97.0
92.0
32.0
7.0
139.0
101.0
80.0
147.0
88.0
111.0
60.0
80.0
111.0
100.0
23.0
118.0
106.0
71.0
133.0
1.0
8.0
59.0
40.0
39.0
143.0
68.0
81.0
90.0
8.0
43.0
39.0
133.0
14.0
44.0
116.0
41.0
58.0
146.0
125.0
78.0
12.0
26.0
90.0
48.0
22.0
92.0
33.0
98.0
73.0
27.0
70.0
99.0
27.0
118.0
103.0
46.0
94.0
40.0
124.0
94.0
128.0
8.0
38.0
66.0
33.0
79.0
91.0
130.0
27.0
90.0
42.0
17.0
63.0
82.0
46.0
35.0
140.0
78.0
14.0
53.0
94.0
126.0
147.0
88.0
119.0
16.0
The smallest number in the list is 1.0.
* Data Structures and Object-Oriented Programming - Assignment 10
* Question 24.24 of Introduction to Java Programming (by Daniel Liang)
*
* Find the Smallest Number (Divide and Conquer Approach)
*
* This program finds the smallest number of a list using a
* divide and conquer approach; specifically, recursion, with
* the original list split in two.
*
* Programmed by Gregory Desrosiers
*
* Start Date: April 28, 2013
* End Date: May 5, 2013
*
* File Name: Chapter24Exercise24.java
* Teacher: Amin Ranj Bar
*
* *SPECIAL*: Regardless if the list size is odd, the program is able to
* find the smallest value in the list.
*/
import java.util.*;
public class Chapter24Exercise24
{
public static void main(String[] args)
{
List<Double> values = new ArrayList<Double>();
Random randomizer = new Random();
for (int x = 0; x < 125 ; x ++)
values.add((double)randomizer.nextInt(150));
System.out.println("Test Case Values:");
for (int x = 0; x < values.size() ; x ++)
System.out.println(values.get(x));
System.out.println("\nThe smallest number in the list is " + smallestNumberInList(values)+ ".\n");
}
public static double smallestNumberInList(List<Double> numberList)
{
if (numberList.size() == 2)
{
double smallestNumber = numberList.get(0);
for(int x = 0; x < numberList.size(); x++)
{
if (numberList.get(x) < smallestNumber)
smallestNumber = numberList.get(x);
}
return smallestNumber;
}
else
{
if (numberList.size() > 2)
{
if (smallestNumberInList(numberList.subList(0, numberList.size() / 2)) <
smallestNumberInList(numberList.subList(numberList.size() / 2, numberList.size())))
return smallestNumberInList(numberList.subList(0, numberList.size() / 2));
else
return smallestNumberInList(numberList.subList(numberList.size() / 2, numberList.size()));
}
// The statement below should not be there, but this is to prevent a compiler error.
// And this statement is invoked when the initialized number list only has one value.
return numberList.get(0);
}
}
}
Console Output:
Test Case Values:
26.0
128.0
126.0
55.0
67.0
49.0
85.0
44.0
2.0
64.0
25.0
48.0
75.0
121.0
40.0
115.0
91.0
87.0
2.0
12.0
21.0
149.0
32.0
118.0
98.0
46.0
97.0
72.0
119.0
5.0
142.0
113.0
107.0
47.0
91.0
84.0
4.0
86.0
50.0
97.0
92.0
32.0
7.0
139.0
101.0
80.0
147.0
88.0
111.0
60.0
80.0
111.0
100.0
23.0
118.0
106.0
71.0
133.0
1.0
8.0
59.0
40.0
39.0
143.0
68.0
81.0
90.0
8.0
43.0
39.0
133.0
14.0
44.0
116.0
41.0
58.0
146.0
125.0
78.0
12.0
26.0
90.0
48.0
22.0
92.0
33.0
98.0
73.0
27.0
70.0
99.0
27.0
118.0
103.0
46.0
94.0
40.0
124.0
94.0
128.0
8.0
38.0
66.0
33.0
79.0
91.0
130.0
27.0
90.0
42.0
17.0
63.0
82.0
46.0
35.0
140.0
78.0
14.0
53.0
94.0
126.0
147.0
88.0
119.0
16.0
The smallest number in the list is 1.0.
That does it for this program. I hope you have a fun afternoon; I'll be in touch.
Follow me through the following pages and be sure to like my e-book page on Facebook for support!!
E-book: https://www.facebook.com/TheAspergerComputerGregDes
Facebook: https://www.facebook.com/pages/Gregory-Desrosiers/171954446270382?ref=hl
Twitter: http://www.twitter.com/GregoryDes
Google+: Search up "Gregory Desrosiers" in the Search Engine, then click on the profile that has a photo of me with two thumbs up.
YouTube: http://www.youtube.com/user/Bammer2001
0 comments:
Post a Comment