[解题报告]【第02题】给定 n，求 1 + 2 + 3 + ... + n 的和 | 四种解法

今天是c语言基础打卡的第2天,主要内容是求和，希望大家能够理解呢，我就给大家记一下重点，给点课后题提示0.0。

相关链接：
【第02题】给定 n，求 1 + 2 + 3 + … + n 的和 | 四种解法

六作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)

⏳全文大约阅读时间： 10min

• 主要知识点
• • 等比数列求和公式
  • C语言写法
• 课后习题
• • 剑指 Offer 64. 求1+2+…+n
  • Sum Problem
  • 剑指 Offer 57 - II. 和为s的连续正数序列
• 写在最后

1 + 2 + 3... + n = n ∗ ( n − 1 ) 2 1+2+3...+n = frac{n*(n-1)}{2} 1+2+3...+n=2n∗(n−1)​

错误示例

#include 
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        int ans = n * (n + 1) / 2;   // (1)
        printf("%dnn", ans);
    }
    return 0;
}

直接就溢出了0.0

正确解法1

#include 
int main() {
    int n, ans;
    while (scanf("%d", &n) != EOF) {
        ans = 0;          
        while(n) {        
            ans += n;     
            --n;          
        }
        printf("%dnn", ans);
    }
    return 0;
}

运用循环来求解

正确解法2

#include 
int main() {
    int n, ans;
    while (scanf("%d", &n) != EOF) {
        if(n % 2 == 0) {          
            ans = n / 2 * (n+1);  
        } else {                  
            ans = (n+1) / 2 * n;   
        }
        printf("%dnn", ans);
    }
    return 0;
}

因为错误的解法是假溢出，我们先进行除法缩小范围，再进行乘法就好了呗？根据奇偶判断n和n+1肯定有一个是偶数，让其中一个偶数和2相除就好了。

正确解法3

#include 
int main() {
    unsigned int n;
    while (scanf("%u", &n) != EOF) {
        unsigned int ans = n * (n + 1) / 2;
        printf("%unn", ans);
    }
    return 0;
}

其实就是扩大数据范围。把所有数据变成无符号就好了

正确解法4

#include 
int main() {
    long long n;
    while (scanf("%lld", &n) != EOF) {
        long long ans = n * (n + 1) / 2; 
        printf("%lldnn", ans);
    }
    return 0;
}

其实就是扩大数据范围。把所有数据变成长整形。

剑指 Offer 64. 求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

解题思路

这就剩递归能用了把？冲！

int sumNums(int n){
    if(n == 1) return 1;
    return n + sumNums(n - 1);
}

Sum Problem

这网站关了，占个坑，回头补0.0

剑指 Offer 57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

解题思路

使用双指针，遍历1-target/2去寻找满足条件的解。

int** findContinuousSequence(int target, int* returnSize, int** returnColumnSizes){
    (*returnSize) = 0;
    int ** ans = malloc(sizeof(int *)*100);
    (*returnColumnSizes) = malloc(sizeof(int)*100);
    for(int left = 1, right = 2;left <= target/2;){
        int sum = (left + right) * (right - left + 1) /2;
        if(sum == target){	//满足就保存
            int temp = right - left +1;
            ans[(*returnSize)] = malloc(sizeof(int)*temp);
            (*returnColumnSizes)[(*returnSize)] = temp;
            for(int i = left;i <= right;i++)
                ans[(*returnSize)][i-left] = i;
            (*returnSize)++;
            left++;
        }
        else if(sum < target)   right++;//小了大指针右移
        else left++;//大了小指针右移动
    }
    return ans;
}

最近的重心还是会放到算法笔记上面，希望大家能跟我一起呀，我尽量更。0.0