一个正整数有可能可以被表示为n(n>=2)个连续正整数之和(Java)

发布时间:2023-08-30 19:00

        最近在上Java课做练习时遇到一道,比较简单的Java题,暴力破解非常简单,但是出于对速度和性能的要求,我决定花更少的时间,用更少的内存去解决这道题。本博客提供两种解法,暴力破解和算法分析。

算法分析参考了一个大佬用C写的解法:http://zhidao.baidu.com/question/426301104,然后自己改了一下写成Java了。

原题:

一个正整数有可能可以被表示为n(n>=2)个连续正整数之和,如:
15=1+2+3+4+5 
15=4+5+6 
15=7+8 
请编写程序,根据输入的任何一个正整数,若有符合这种要求的连续正整数序列输出has,否则输出none。
例如:输入15,则输出
has

输入16,则输出
none

以下是两种解法:

①暴力破解:

import java.util.*;

public class NumberSum {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int source = in.nextInt();
		int sum = 0;
		boolean flag = false;
		
		 for(int i=1; i

我觉得这个没什么好说的,就是考虑所有可能性,有一个符合条件直接打破然后输出结果has,否则所有循环完没有符合条件的输出结果none。时间复杂度分析O(n^2)。

②算法分析:

这道题实际上就是一个等差数列求和,如果把数学忘了赶快回去复习一下吧。首先用数学方法分析一下:

首项:a1 = a;

尾项:an = a + (n-1)*d;这里d=1即 an = a + n -1;

等差数列求和:Sn = (a1+an)*n/2 = (2a+n-1)*n/2;(倒序相加法)

由等差数列求和,求得首项a = Sn/n + (1-n)/2;

因为Sn已知(程序输入),所以由项数n计算首项a;然后强转为int类型,若a为整数则其符合条件,标志赋予true,最后输出结果。这里条件n<=(source/2+1),因为本题目条件的原因,所以一个数的连续数字和肯定小于等于它的一半加一,即n<(n/2)+(n/2)+1;然后这里就可以减少循环次数节省时间和空间。时间复杂度分析O(n)。

以下是源代码:

import java.util.*;

public class NumberSum {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		boolean flag = false;
		int source = in.nextInt();
		
		for(float n=2; n<=(source/2+1); n++) {
			float a = source/n + (float)0.5 - n/2;	
			if((int)a == a) {
				flag = true;
				break;
			}
		}
		
		if(flag == true) {
			System.out.println("has");
		}else {
			System.out.println("none");
		}
	}
}

 

ItVuer - 免责声明 - 关于我们 - 联系我们

本网站信息来源于互联网,如有侵权请联系:561261067@qq.com

桂ICP备16001015号