J'ai besoin d'écrire une fonction récursive qui renvoie les éléments les plus grands et les plus petits dans ArrayList et les indices correspondants. Pour renvoyer ces quatre éléments, je dois renvoyer un objet qui est une instance d'une classe interne appelée MinMaxObject qui a quatre variables privées définies: max, min, maxPos, minPos de types double, double, int et int.
I Je suis arrivé ici tout seul et j'ai besoin de commencer la récursion mais je ne sais pas comment y aller. Si quelqu'un pouvait me diriger dans la bonne direction, je devrais être en mesure de le ramasser.
public static void main(String args[]) {
Scanner console = new Scanner(System.in);
System.out.print("Please enter a file name");
String fileName = console.next();
try {
File fileRef = new File(fileName);
Scanner tokens = new Scanner(fileRef);
double input = tokens.nextDouble();
ArrayList<Double> list = new ArrayList<Double>();
while (tokens.hasNextLine()) {
list.add(input);
}
System.out.println("For Loop");
for (int counter = 0; counter < list.size(); counter++) {
System.out.println(list.get(counter));
}
} catch (FileNotFoundException e) {
e.printStackTrace();
}
// 2 functions, one initialize & one to call the original recursion
//can start at beggining and recurse to the end or vice versa
//updates the min and max as it goes
//update minPos and maxPos as well
}
public class MinMaxObject {
private double min;
private double max;
private int minPos;
private int maxPos;
public MinMaxObject(double newMin, double newMax, int newMinPos, int newMaxPos){
min = newMin;
max = newMax;
minPos = newMinPos;
maxPos = newMaxPos;
}
public double getMin(){
return min;
}
public void setMin(double newMin){
min = newMin;
}
public double getMax(){
return max;
}
public void setMax(double newMax){
max = newMax;
}
public int getMinPos(){
return minPos;
}
public void setMinPos(int newMinPos){
minPos = newMinPos;
}
public int getMaxPos(){
return maxPos;
}
public void setMaxPos(int newMaxPos){
maxPos = newMaxPos;
}
5 Réponses :
La récursivité n'est pas nécessaire. En utilisant la ArrayList List , voici un exemple.
Collections.sort(List) return List.get(0); // Least number return List.get(List.size()-1); // Max number
On dirait que la récursivité fait partie du devoir.
Le moyen le plus simple est de parcourir l'arraylist, mais comme vous avez besoin d'une récursivité, c'est un peu plus complexe. Puisque ce sont des devoirs et que je suis paresseux, je ne vais pas vous donner de code Java compilable. C'est une approximation proche. Je ne vais pas non plus vous donner toute la méthode, car vous devriez comprendre le reste à partir d'ici.
private int min = 0;
private int max = 0;
findMinMax(int index, List<int> list)
{
//in recursion always start your method with a base-case
if(index >= list.Count)
return ;
//find min and max here
//this is called tail recursion, it's basically the same as a loop
findMinMax(index + 1, list);
}
public void getMinMax(MinMaxObject minMaxObject, List list, int currentIndex)
{
if(list.get(currentIndex) < minMaxObject.getMin())
minMaxObject.setMin(list.get(currentIndex) );
minMaxObject.setMinPos(currentIndex) ;
else if(list.get(currentIndex) > minMaxObject.getMax())
minMaxObject.setMax(list.get(currentIndex));
minMaxObject.setMaxPos(currentIndex) ;
if(currentIndex < list.size-1) getMinMax(minMaxObject, list, ++currentIndex)
}
Quelque chose comme ceci:
MinMaxObject findMaxMin(final ArrayList<Double> nums, MinMaxObject minMax, int pos){
//Base Case
if(pos >= nums.size()){
return minMax;
}
//Check to see if the current element is bigger than max or smaller than min
Double value = nums.get(pos);
if(value > minMax.getMax()){
//adjust minMax
}
if(value < minMax.getMin()){
//adjust minMax
}
//recursion
return findMaxMin(nums, minMax, pos+1);
}
Assurez-vous simplement d'initialiser votre MinMaxObject avec les valeurs appropriées (cela devrait probablement faire partie d'un constructeur par défaut), quelque chose comme:
MinMaxObject minMax = new MinMaxObject (Integer.MAX_VALUE, Integer.MIN_VALUE, -1, -1);
J'espère avoir obtenu le bon ordre des paramètres.
Une recherche sur les termes «récursion» et «accumulateur» vous éclairerait probablement un peu là-dessus.
Merci @ScubaSteve! ... Je décris un peu plus / détaillé:
void findMinMax(int left, int right, items, result) {
if(left > right) {
return;// alternatively do nothing
} else if (left == right) {
//check items[left] ...
// return;
} else { // left < right
int mid = (right - left) / 2;
findMinMax(left, mid, items, result);
findMinMax(mid + 1, right, items, result);
// return;
}
}
L'invocation initiale / finale / externe serait:
void findMinMax(int head, int tail, List items, MinMaxObject result) {
if(head > tail) {
// done!
return;
}
// check items[head] and items[tail]... store to result
// iterate:
return findMinMax(head + 1, tail - 1, items, result);
}
A l'alternative de récursivité serait: de recourir non seulement à la "tête" de la liste ( idx: 0 ... size - 1 ), mais aussi à la "queue" comme:
// initialize with high min, low max and "out of range" indices // ...alternatively in default constructor/field declaration. MinMaxObject result = new MinMaxObject(Integer.MAX_VALUE, Integer.MIN_VALUE, -1, -1); // start recursion at index 0: findMinMax(0, items, result);
l '«alternative» divise par deux le nombre de récursions (mais double la «complexité en ligne»).
Une autre approche «diviser et conquérir»:
XXX
... avec la (même) complexité O (n) .