一个整数拆分为连续自然数之和

痛定思痛。 2021-06-10 20:38 532阅读 0赞

问题描述：将一个正整数，拆分成连续的自然数之和，输出所有可能的情况

例如： 3 = 1+2

10 = 1+2+3+4

16 = 5+6+7

...

问题求解：

连续的自然数之和让我们想到了等差数列求和公式：

![20200413162223527.png][]

其中Sum为要分解的正整数，n为连续自然数的个数，aFirst为连续自然数的第一位数  
将以上公式改写成另外一种格式

![2020041316223288.png][]

求解得到连续自然数个数n：

![20200413162243890.png][]  
如果一个数可以分解为几个连续自然数之和，那么就意味着方程有解，那么对于相应的解就有如下限制，

![20200413162255675.png][] 必须为平方数且开根号的结果必须为奇数  
需要注意一点的是：由于是连续自然数，所以首项aFirst必定不可能大于n/2，所以不需要从1-n遍历，只需要从1- n/2 遍历即可

c++代码如下所示

// partitionSum.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include <math.h>
    
    int main(int argc, char* argv[])
    {
    	// 等差数列求和公式 Sum = n*aFirst + n*(n-2)/2;
    	// Sum 为要拆分的整数，
    	// n 为拆分后连续自然数个数
    	// aFirst 为连续自然数中的第一位数
    
    	int Sum, aFirst;
    	int i,j;
    	int w,k,m;  
    	printf("请输入要分解的自然数Sum: ");
        scanf("%d",&Sum);  
        printf("/n");  
    
        for(i = 1; i <= Sum/2; i++)  //由于是连续自然数，所以首项必定不可能大于n/2
        {  
            aFirst = i;                      
            w = (2*aFirst-1) * (2*aFirst-1) + 8*Sum;  
            k = (int)sqrt(w);  
            m = k - 2*aFirst + 1;  
            if(k*k != w)  // k是一个平方数
                continue;  
            else if(m %2 !=0)  // m必须为偶数
                continue;  
            else  
            {  
                printf("可以分解%d个连续自然数：/n",m/2);  
                for(j=1;j<=m/2;j++)  
                    printf("%d ",i+j-1);  
                printf("/n/n");  
            }  
        }  
    
        return 0;  
    }

结果如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o2OTE4Mzc4Nw_size_16_color_FFFFFF_t_70][]

解法2 ----------------------------------------------------------------------------------------------------------------------------

题目描述：

要求写出所有连续的正整数序列，使其之和等于90，小明灵光一闪，立马写上了29,30,31，

他看到解释说明台式告知答案不止一种，过了好一会，他总算算出了所有的5种答案

给你一个正整数Num，请输出所有连续的递增（+1）的正整数序列，使其之和等于Num，如不存在则输出NULL

例如输入：90

输出：\[2,3,4,5,6,7,8,9,10,11,12,13\]

\[6,7,8,9,10,11,12,13,14\]

\[16,17,18,19,20\]

\[21,22,23,24\]

\[29,30,31\]

import java.util.ArrayList;
    import java.util.List;
    public class Demo5 {
        public static void main(String[] args) {
            int number =90;
            Demo5 demo =new Demo5();
            demo.printNum(number);
        }
    
        public void printNum(int num) {
            int sum =0;
            for (int i =0; i < num /2; i++) {
                for (int k =1; ; k++) {
                    sum = (k +1) * (2 * i + k) /2;
                    if (sum > num)
                        break;
                    if (sum == num) {
                        List list =new ArrayList();
                        for (int j =0; j <= k; j++) {
                            list.add(i + j);
                        }
                        System.out.println(list);
                    }
                }
            }
        }
    }

[20200413162223527.png]: /images/20210527/1931455ce7a3426aa58acd8f4bd108f7.png
[2020041316223288.png]: /images/20210527/cfdba5dc5f3548f588d7bf272b6b085a.png
[20200413162243890.png]: /images/20210527/7a5b9d501d50420a87c2fbd4c3ba8cb0.png
[20200413162255675.png]: /images/20210527/ae5b13d849e74f23bcec58b420d3edd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3o2OTE4Mzc4Nw_size_16_color_FFFFFF_t_70]: /images/20210527/eb8bad7d30844e26b10a5b9f277b1dd6.png