编程题：输出所有和为S的连续正数序列

╰半夏微凉° 2022-05-23 08:40 141阅读 0赞

## 题目描述 ##

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

## 输出描述: ##

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

思路：利用数学公式i,i+1,i+2,i+3,…,n 累计和为(n+i)(n-i+1)/2，令其等于S，即(n+i)(n-i+1)=2S， 进一步n(n+1) – i(i-1)=2S。 我们从i=1 遍历i=S/2+1,对于每一个i,计算出n=sqrt(2S+i(i-1))，然后检验n(n+1)= 2S+i(i-1)是否成立，成立加入列表。

代码：

import java.util.*;
    
    /**
     * Created by ASUS on 2018/6/5
     *
     * @Authod Grey Wolf
     */
    public class Test1 {
    
        public static void main(String[] args) {
            Test1 test1=new Test1();
            test1.sys();
        }
    
        private void sys() {
            Scanner scanner=new Scanner(System.in);
            int s=scanner.nextInt();
            ArrayList<ArrayList<Integer>>lists=findResult(s);
            for(ArrayList<Integer>list:lists){
                for (Integer num:list){
                    System.out.print(num+" ");
                }
                System.out.println();
            }
        }
    
        private ArrayList<ArrayList<Integer>> findResult(int s) {
            ArrayList<ArrayList<Integer>>lists=new ArrayList<>();
            if (s<=1){
                return lists;
            }
            int i,j,temp,n;
            ArrayList<Integer>list;
            for(i=1;i<=s/2+1;i++){
                temp=2*s+i*(i-1);
                n= (int) Math.sqrt(temp);
                if(n*(n+1)==temp){
                    //加入结果集
                   list=new ArrayList<>();
                   for (j=i;j<=n;j++){
                       list.add(j);
                   }
                   lists.add(list);
                }
            }
            return lists;
        }
    
    
    }

效果：

100  
9 10 11 12 13 14 15 16  
18 19 20 21 22  
  
Process finished with exit code 0

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。