正整数表示为连续自然数的和（难度：1颗星）

深藏阁楼爱情的钟 2022-06-16 07:47 203阅读 0赞

问题描述：

输入一个正整数N，输出能相加等于N的联系序列的和（序列必须多于1项），如果这种序列存在，则输出所有这样的序列，如果不存在，则输出NULL。

例如：输入为15  
输出：  
1+2+3+4+5=15  
4+5+6=15  
7+8=15

首先我们先分析一下这个问题：  
1. 首先1和2是不能表示成连续的自然数之和的，所以我们从3开始  
2. 假设n可以表示成连续的自然数之和【s,t】,那么根据求和公式则有(s+t)\*(t-s+1)=2\*n  
3. 把2\*n表示成两个自然数相乘，则2\*n = a \* b  
4. 另 s+t=a , t-s+1=b,解方程可得s=(a-b+1)/2, t=(a+b-1)/2  
5. 要使得s和t为自然数，那么必须满足a-b和a+b都是奇数  
6. 我们在来讨论一下n的奇偶性，如果n是奇数那肯定可以表示为n=2\*i+1,至少可以分解为【i,i+1】,所以肯定有解  
7. 如果n是偶数，则n可以分解为n=2^i\*3^j\*….,假定只有i不为0，后面的j,k…幂次都为0，那么所有的因子都为偶数，不可能满足两个因子为奇数的条件。  
8. 所以我们可以发现，只要n不是2的幂次并且大于等于3，就一定可以分解为连续正整数之和。

方法1：  
使用简单的循环来进行枚举判断，从一个数为1开始枚举，当和大于n时，把第一个数加1，以此类推，此处采用上面推导的n必须为2的幂次直接判断。

参考代码：

#include <stdio.h>
    
    int IsCanFind(int n)
    {
        if (n < 3)
            return 0;
    
        return n & (n - 1);//如果n是2的幂次则不能找到
    }
    
    int main()
    {
        int n, i, j, k, nSum;
        printf("input a number: ");
        scanf_s("%d", &n);
        if (0 == IsCanFind(n))
        {
            printf("NULL\n");
            return 0;
        }
        for (i = 1; i < (n + 1) / 2; i++)//只需要找到n的一半就可以了，因为再往下找肯定大于n了
        {
            nSum = 0;
            for (j = i; j <= n; j++)
            {
                nSum += j;
                if (nSum == n)
                {
                    if (i == j)
                        break;//这里只有一个元素可以直接退出该层循环，因为后面再加肯定不满足了
                    printf("%d", i);
                    for (k = i + 1; k <= j; k++)
                        printf("+%d", k);
                    printf("=%d\n", n);
                }
                else if (nSum > n)
                    break;
            }
        }
    
        return 0;
    }

方法2：  
查找的方式相同，只是更换了判断不存在的判断方法。

参考代码：

#include <stdio.h>
    
    int main()
    {
        int n, i, j, k, nSum, IsFind = 0;
        printf("input a number: ");
        scanf_s("%d", &n);
        for (i = 1; i <= n; i++)
        {
            nSum = 0;
            for (j = i; j <= n; j++)
            {
                nSum += j;
                if (nSum == n)
                {
                    if (i == j)
                        break;//这里只有一个元素可以直接退出该层循环，因为后面再加肯定不满足了
                    printf("%d", i);
                    for (k = i + 1; k <= j; k++)
                        printf("+%d", k);
                    printf("=%d\n",n);
                    IsFind = 1;
                }
                else if (nSum > n)
                    break;
            }
        }
        if (0 == IsFind)
            printf("NULL\n");
    
        return 0;
    }

方法3：  
使用序列的起点和终点的两个下标记录，这样可以保证在查找失败之后，不用从头加起，只需要减掉之前的第一个继续往后加就可以了。

参考代码：

#include <stdio.h>
    
    int IsCanFind(int n)
    {
        if (n < 3)
            return 0;
    
        return n & (n - 1);//如果n是2的幂次则不能找到
    }
    
    int main()
    {
        int n, startIndex, endIndex, i, nSum;
        printf("input a number: ");
        scanf_s("%d", &n);
        if (0 == IsCanFind(n))
        {
            printf("NULL\n");
            return 0;
        }
    
        startIndex = 1;
        endIndex = 2;
        nSum = startIndex + endIndex;
        while(startIndex < (n + 1) / 2)//起点到一半即可，因为再往后加肯定超过了
        {
            if (nSum == n)
            {
                if (startIndex < endIndex)
                {
                    for (i = startIndex; i < endIndex; i++)
                        printf("%d+", i);
                    printf("%d=%d\n", endIndex, n);
                }
                startIndex++;
                endIndex = startIndex + 1;
                nSum = startIndex + endIndex;
            }
            else if (nSum > n)//如果已经大于n了，减去起点的数，并且起点右移
            {
                nSum -= startIndex;
                startIndex++;
            }
            else
            {
                endIndex++;
                nSum += endIndex;
            }
        }
    
        return 0;
    }

方法4：  
使用求和公式来进行求和，省掉了循环的遍历的时间。

参考代码：

#include <stdio.h>
    
    int IsCanFind(int n)
    {
        if (n < 3)
            return 0;
    
        return n & (n - 1);//如果n是2的幂次则不能找到
    }
    
    int main()
    {
        int n, i, j, k, nSum;
        printf("input a number: ");
        scanf_s("%d", &n);
        if (0 == IsCanFind(n))
        {
            printf("NULL\n");
            return 0;
        }
        for (i = 1; i < (n + 1) / 2; i++)
        {
            for (j = 1;; j++) //遍历项数
            {
                nSum = (i + i + j - 1) * j / 2;
                if (nSum == n)
                {
                    if (j == 1)
                        break;//如果只有1项，因为后面再加肯定不满足了
                    printf("%d", i);
                    for (k = i + 1; k <= i + j - 1; k++)
                        printf("+%d", k);
                    printf("=%d\n", n);
                }
                else if (nSum > n)
                    break;
            }
        }
    
        return 0;
    }

方法5：  
使用我们最开始分析的因子分解法，求出因子必须要满足和为奇数的条件进行求解。

参考代码：

#include <stdio.h>
    
    int IsCanFind(int n)
    {
        if (n < 3)
            return 0;
    
        return n & (n - 1);//如果n是2的幂次则不能找到
    }
    
    int main()
    {
        int n, i, j;
        int mini, maxi, nStart, nEnd;
        printf("input a number: ");
        scanf_s("%d", &n);
        if (0 == IsCanFind(n))
        {
            printf("NULL\n");
            return 0;
        }
        for (i = 1; i * i <= 2 * n; i++)
        {
            if (2 * n % i == 0)
            {
                mini = i;
                maxi = 2 * n / i;
                if ((mini + maxi) % 2 == 1)
                {
                    nStart = (maxi - mini + 1) / 2;
                    nEnd = (maxi + mini - 1) / 2;
                    if (nStart < nEnd)//大于1个元素再输出
                    {
                        printf("%d", nStart);
                        for (j = nStart + 1; j <= nEnd; j++)
                            printf("+%d", j);
                        printf("=%d\n",n);
                    }
                }
            }
        }
    
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/a397c8f56f284e089a4d56e0b5d99e7d.png