找出所有符合情况的连续正整数_JAVA_编程开发_程序员俱乐部

class="java">
package test;

import java.util.ArrayList;
import java.util.List;

/**
 * 题目描述：一个正整数有可能可以被表示为n(n>=2)个连续正整数之和，如：
 * 15=1+2+3+4+5
 * 15=4+5+6
 * 15=7+8
 * 请编写程序，根据输入的任何一个正整数，找出符合这种要求的所有连续正整数序列。
 * 申明:只是提供了一种较好的算法,必然存在更好的
 * 这是我一位同事的算法,思路很不错,借鉴了
 * 缺点:2*i如果大于int的最大范围就不行了
 */
public class Test {
	
	private static int maxNum =0;
	
	private static List<int[]> list= new ArrayList<int[]>();
	
	public static void main(String[] args) {
		long start=System.currentTimeMillis();
		int num=15;
		calculate(num);
		show(num);
		long end = System.currentTimeMillis();
		System.out.println(end -start);
	}
	
	//核心算法
	private static void judge(int i,int num){
		//maxNum要理解为项数,同时也表示连续整数和最多也就maxNum项
		//因此对于16最多maxNum(6)项相加
		/**
		 * 第一轮:
		 * 第一次:1+2+3+4+5+6 	符合结束循环,不符合继续
		 * 第二次:1+2+3+4+5		符合结束循环,不符合继续
		 * 第三次:1+2+3+4			符合结束循环,不符合继续
		 * 第四次:1+2+3 			符合结束循环,不符合继续
		 * 第五次:1+2				符合结束循环,不符合继续
		 * 第六次:1 				符合结束循环,不符合继续
		 * 
		 * 第二轮:
		 * 第一次:2+3+4+5+6+7 	符合结束循环,不符合继续
		 * 第二次:2+3+4+5+6		符合结束循环,不符合继续
		 * 第三次:2+3+4+5 		符合结束循环,不符合继续
		 * 第四次:2+3+4 			符合结束循环,不符合继续
		 * 第五次:2+3 			符合结束循环,不符合继续
		 * 第六次:2
		 * 
		 * 第最后轮:
		 * 第一次:8+9+10+11+12+13  符合结束循环,不符合继续
		 * 第二次:8+9+10+11+12	符合结束循环,不符合继续
		 * 第三次:8+9+10+11 		符合结束循环,不符合继续
		 * 第四次:8+9+10 			符合结束循环,不符合继续
		 * 第五次:8+9 			符合结束循环,不符合继续
		 * 第六次:8				符合结束循环,不符合继续
		 */
		
		/** 因为是等差数列，当只知道首项(i)和项数(maxNum)时,
		 *  要求首项+末项的和(当然末项也是能求出的,这里用不到)
		 *  公式为:(2*i+maxNum-1)=首项+末项的和=首项*2+项数-1
		 */
		//judgeNum=(首项+末项的和)*项数
		int judgeNum =maxNum*(2*i+maxNum-1);
		while(judgeNum >=2*num){
			if(judgeNum == 2*num){
				int[] a=new int[2];
				a[0]=i;//得到的是首项
				a[1]=maxNum;//得到的是项数
				list.add(a);
				break;
			}else{
				maxNum --;
				if(maxNum < 0){
					break;
				}
				judgeNum=maxNum*(2*i+maxNum-1);
			}
		}
	}
	
	//得到项数,该方法用法只执行一次
	private static int getMaxNum(int start,int num){
		int count =0;
		int i=0;
		for(i=start;i<num;i++){
			count+=i;
			if(count >=num){
				System.out.println(i);
				return i;
			}
		}
		return num;//为了满足语法,其实是根本不会走到的
	}
	
	private static void calculate(int num){
		maxNum=getMaxNum(1,num);//得到项数
		/**
		 * 以15为例
		 * 1+2+...+15    //其中加到某一个数,有可能符合情况
		 * 2+3+4+...+15  //其中加到某一个数,有可能符合情况
		 * ...           //其中加到某一个数,有可能符合情况
		 * 7+8+...+15    //其中加到某一个数,有可能符合情况
		 * 最多加到其一半的情况,即15最多是7+8,永远不可能是8+9
		 * 所以一个数最多加到其一半，不然就要超过这个数了
		 * 如101最多50+51,永远不可能从51开始,即51+52
		 */
		for(int i=1;i<=num/2;i++){
			judge(i,num);
		}
	}
	
	/**
	 * 这里是输出的逻辑,虽然输出看似比较繁琐,但是占用的时间很少,不影响效率
	 * a[0]=i;       //得到的是首项
	 * a[1]=maxNum;  //得到的是项数
	 */
	private static void show(int num){
		for(int i=0;i<list.size();i++){
			int[] ret=list.get(i);
			int start =ret[0];
			int count=ret[1];
			int[] show =new int[count];
			System.out.print(num+" = ");
			int flag =0;
			for(int j=0;j<count;j++){
				show[j]=start+j;
				if(j==0){
					System.out.print(" "+show[j]);
				}else{
					System.out.print(" +"+show[j]);
				}
				flag ++;
				if(flag >20000){
					System.out.println();
					flag =0;
				}
			}
			System.out.println();
		}
	}
}