山东大学09年复试机试题1

（题干为前辈回忆所得，并非原文，但已表达清楚）
    输入一个整数,它可以由n(n>=2)个连续整数相加得到,输出所有可能的连续整数序列,每个序列占一行,数字之间用空格分开,数据从小到大,每列按最小元素递增顺序排列,如果找不到,输出none
    例:21=1+2+3+4+5+6
       21=6+7+8
       21=10+11
    则输出 1 2 3 4 5 6
           6 7 8
           10 11

思路1：
    题目一拿到手，就觉得是和队列相关，因为是从1开始累加测试。队列初始时已经放入1，2（因为只有从3开始，才有1+2=3成立）。开始时先对队列元素总和进行计算：当小于要求值的时候把队尾元素值+1（也就是向后再取一个元素），将其入队，然后递归调用当前算法；当满足要求值的时候，把队列中的元素打印出来，并且将第一个元素出队，然后递归调用当前算法；当大于要求值的时候，将第一个元素出队，然后递归调用当前算法；当入队元素值=要求值/2+2时，return，因为此后的数据已经没有测试的意义。

具体程序如下：

递归版本

package test.shandong09;

import java.util.ArrayDeque;
import java.util.Iterator;

public class No1_1 {
	private ArrayDeque<Integer> arrayDeque;
	private int start;
	private int destination;
	private int times;
	
	public No1_1(int destination) {

		this.arrayDeque = new ArrayDeque<Integer>();
		this.start = 3;
		this.destination = destination;
		this.times=0;

		arrayDeque.offer(new Integer(1));
		arrayDeque.offer(new Integer(2));
	}

	public void getResult() {
		int temp = this.calculateSum(arrayDeque);
		if (start <= (destination / 2 + 2)) {
			if (temp < this.destination) {
				arrayDeque.offer(new Integer(this.start));
				this.start++;

			} else if (temp == this.destination) {
				System.out.println(arrayDeque.toString());
				arrayDeque.poll();
			} else if (temp > destination) {
				arrayDeque.poll();
			}
			this.getResult();
		} else {
			return;
		}
	}

	
	public int calculateSum(ArrayDeque<Integer> arrayDeque) {
		int result = 0;
		if (!arrayDeque.isEmpty()) {
			Iterator<Integer> iterator = arrayDeque.iterator();
			while (iterator.hasNext()) {
				Integer tempI = iterator.next();
				result += tempI.intValue();
			}
		}
		this.times++;
		return result;
	}

	public static void main(String[] args) {
		No1_1 no1_1 = new No1_1(500);//这里是要测试的数据
		no1_1.getResult();
		System.out.println("测试总次数为：" + no1_1.getTimes()+"\t测试截止数为（从3起始）："+no1_1.getStart());
	}
	
	public int getStart() {
		return start;
	}

	public int getTimes() {
		return times;
	}

}

输出为：

[8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

[59, 60, 61, 62, 63, 64, 65, 66]

[98, 99, 100, 101, 102]

测试总次数为：501     测试截止数为（从3起始）：253

最后输出的结果，数字之间是“，”隔开，这是不符合题目要求的，有待改进。

思路2
使用普通的循环累加计算法。即，开始值初始为1，截止值=目标值/2+2，累加值初始为0。从1开始累加，当发现累加值正好为目标值时，打印出当前序列（从当前的开始位到截止位，逐个+1然后打出），并将累加值清零后跳出此次循环；当累加值大于目标值时，将累加值清零后跳出此次循环。然后从开始值+1，再次进行……直到开始值=截止值结束运算。

具体程序如下：
循环版本：

package test.shandong09;

public class No1_2 {
	private long times;//测试（求和计算）总次数
	private int destination;//目标值
	
	public No1_2(int destination) {
		this.times = 0;
		this.destination = destination;
	}

	public boolean getResult() {
		boolean hasAnswer=false;//初始化hasAnswer变量
		int temp = destination / 2 + 2;//截止值
		int result = 0;//累加结果
		if (destination<=2){//传入的目标值必须>=3
			return false;
		}
		
		for (int i = 1; i <= temp; i++) {//外层循环，控制每轮累加的起始值
			for (int j = i; j <= temp; j++) {//内层循环，控制每轮累加的总值
				if (result == destination) {
					for (int k = i; k < j; k++) {//若找到目标序列，只需知道其起始值和终止值就行，然后累加得到每个元素
						System.out.print(k + " ");
						hasAnswer=true;
					}
					System.out.println();
					result = 0;
					break;
				} else if (result > destination) {//若大于目标值，则将累加结果清零，退出此轮叠加。
					result = 0;
					break;
				}
				result += j;//若前两种可能均不成立，则累加
				times++;//测试数+1
			}
		}
		return hasAnswer;
	}
	
	public long getTimes() {
		return times;
	}

	public static void main(String[] args) {
		No1_2 no1_2 = new No1_2(500);
		boolean b=no1_2.getResult();// 这里是要测试的数据
		if (b){
			System.out.println("测试总次数为：" + no1_2.getTimes());
		}else {
			System.out.println("none");
		}
	}
}

输出结果为：

8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

59 60 61 62 63 64 65 66

98 99 100 101 102

测试总次数为：1768 测试截止数为（从1开始）：252

评论

2 楼 chinaemerson 2010-02-20  

      非常感谢你的关注，其实在测试的时候我也注意到了这一点（内存问题和效率问题），在学习程序设计的时候就知道要尽量避免使用递归。但考虑到这是考研的机试题，不会出的太大吧～呵呵。
      在发布第一个解法之后我又写了第二个解法，经测试，这个算法在时间效率和耐压性上比上一个算法有大幅提高。原因在于，我的第二个算法没有使用任何存储结构。我们都被自己的知识给套住了思维，都以为要有一个存储结构来储存现有的序列。其实错了，只要知道现有序列的起始值和终止值就可以使用for来迭代出序列来！因为都是连续的整数～～第二个程序在大数的压力下（如999999999），还是表现的不错的。但这种用for循环的方法，牺牲的是大量的处理器运算。当然，在存储器的访问时间面前，处理器运算所耗费的时间还是相当短的。

再次感谢你的关注！

1 楼 cxzucc 2010-02-20  

测试了下你的程序，在数字较大的时候会内存溢出，而且速度较慢，自己动手写了一个不用递归的，大家交流一下。
public class HHH {
public void find(int value) {
int i = value / 2;
List<Integer> list = new ArrayList<Integer>();
boolean result = false;
for (int j = 1; j <= i; j++) {
int sum = j, temp = j;
list.add(j);
while (sum < value) {
temp++;
sum += temp;
list.add(temp);
}
if (sum == value) {
result = true;
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
System.out.println();
}
list.clear();
}
if (!result)
System.out.println("none");
}

public static void main(String[] args) {
HHH hhh = new HHH();
hhh.find(111111);
}
}