递归问题
问题描述:
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Collections;
import java.util.List;
public class TennisTournament {
public static void main (String [] args) {
Scanner input = new Scanner(System.in);
ArrayList <Integer> nums = new ArrayList<Integer>();
while (input.hasNextInt()) {
nums.add(input.nextInt());
}
System.out.println(nums);
tournament(nums);
}
public static void tournament(ArrayList <Integer> list) {
int midPoint = list.size()/2; // returns the index number of half of the lists size
int midPoint2 = list.size()/2;
if (list.size() != 1 || midPoint != 1) {
for (int i = 0; i < midPoint2; i++) { // while is bigger than mid point, increment by one
if (list.get(i) < list.get(midPoint)) {
Collections.swap(list, i, midPoint);
}
midPoint++;
}
System.out.println(list);
int newPoint = midPoint2/2;
midPoint2 = newPoint;
}
tournament(list);
}
}
好吧,所以我现在对递归的想法还很陌生,现在我所得到的只是一个无限循环。所以在第一种方法中,我想通过将它分成一半来分析数组,并且比较数组前半部分的第一个元素和数组后半部分的第一个元素,并且如果第二个元素是更大,然后交换这一切都工作正常,它正在做我想要它做的。 [3,5,8,2,1,7,6,4] [3,7,8,4,1,5,6,2] 我想要采取的下一步是我只想一半我正在处理的元素。所以在第一个例子中,我想要我工作的元素数量的一半,所以而不是0-list.size,我希望它在0-list.size()/ 2上工作,所以它只会交换前四个数字,然后再做两次,直到中点变成一个数字。 只要对我如何实现这一点有一点了解就太好了。 不,不是功课。递归问题
答
我猜你需要停止分裂,当列表尺寸小于2
答
与半长的子列表两个递归调用(使用List.subList(...)
)更换tournament(list);
电话。然后,如果列表的长度为1,则快捷方式。
我很想将其标记为家庭作业。是吗? – 2012-04-01 01:22:32
递归的“结束条件”是什么?就目前来看,无论它只是将原始未修改列表中的“锦标赛()”永久地称为它,似乎都是如此。它从来没有用较小的列表调用,也没有任何东西阻止递归调用。 – 2012-04-01 01:22:47
@Brandon:注意问题的最后一行:_不,不是作业._ :) – sarnold 2012-04-01 01:27:14