编程之美--只考加法的面试题(尺取法)

小胡同的诗

于 2019-01-14 12:47:22 发布

阅读量257

点赞数

分类专栏：思维技巧 ------------Other------------ 编程之美 ----------读书笔记----------

本文链接：https://blog.csdn.net/calculate23/article/details/86475541

版权

思维同时被 3 个专栏收录

59 篇文章

订阅专栏

技巧

26 篇文章

订阅专栏

------------Other------------

4 篇文章

订阅专栏

本文探讨了如何判断一个自然数是否可以被拆分为两个或更多连续自然数的和，并提供了两种算法实现：数学公式推导和双指针法。通过具体的代码示例，展示了如何高效地找到所有可能的拆分组合。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

问题： 对于一个任意的自然数，问是否能将其拆分成2个或2个以上的连续自然数之和，写出所有的等式。

解题思路： 第一种解法是推导出数学公式，因为连续的自然数可以用等差数列Sn求和公式，判断可行性。公式推导以及证明过程:数学解法；
第二种解法是直接穷举解法，不过对于较大的数字复杂度O(n^2)可能不够解决，由于连续的自然数一定是递增状态，我们可以用尺取法，也就是双指针法将复杂度降低到O(n)

双指针解法:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void print_Answer (ll l, ll r) {
    printf("AC Answer is : ");
    for (ll i = l; i<= r; i++) {
        printf("%d%c", i, " \n"[i==r]);
    }
}

//写法1
void get_Answer (ll goal) {
    ll i, j, tmp, flag;
    i = 1, j = 1;
    flag = 0;
    //搜索首项i和尾项j
    while (i <= goal/2 && j <= goal) {
        tmp = (i+j)*(j-i+1)/2;
        if(tmp == goal) {
            print_Answer(i,j);
            flag = 1;
            i++;
            j++;
            continue;
        }
        if(tmp > goal) {
            i++;
            continue;
        }
        j++;
    }
    if(flag == 0) {
        printf("不存在该数的拆分策略!\n");
    }
    return ;
}

//写法2
void get_Answer2 (ll goal) {
    ll i, j, sum, flag = 0;
    i = j = 1;
    sum = 0;
    while (i <= goal/2) {
        while (j <= goal && sum < goal) {
            sum += j;
            j++;
        }
        if(sum < goal) {
            break;
        }
        if(sum == goal) {
            print_Answer(i,j-1);
            flag = 1;
        }
        sum -= i++; //移位
    }
    if(flag == 0) {
        printf("不存在该数的拆分策略!\n");
    }
    return ;
}

int main() {
    int N;
    scanf("%d", &N);
    printf("写法1：\n");
    get_Answer(N);
    printf("\n写法2：\n");
    get_Answer2(N);
    return 0;
}