> 文档中心 > 每日一题 - 007 - 五种方法求 1+2+3+...+n 的和

每日一题 - 007 - 五种方法求 1+2+3+...+n 的和

每日一题系列


文章目录

  • 求 1+2+3+...+n 的和
  • 思路一:迭代(循环)
    • 代码一:迭代(循环)
  • 思路二:公式法
    • 代码二:公式法
  • 思路三:递归
    • 代码三:递归
  • 思路四:改良递归
    • 代码四:改良递归
  • 思路五:调用构造函数(C++)
    • 代码五:公式法
  • // 后记

求 1+2+3+…+n 的和

🏃 题目非常简单,就是给你一个 n,然后求最基础的等差数列的和

💘 例如:

🏃 输入:n = 50
🏃 输出:1275

思路一:迭代(循环)

🏃 如果给小学二年级的小朋友出这么一道题,他们一定拿出铅笔和草纸,一个一个数的开始加了
🏃 所以我们的第一种方法就是一步一步来,从 1 开始累加到 n 即可

代码一:迭代(循环)

int SumSolution(int n){int i = 1;int sum = 0;//i的值从1~n,sum一直加i即可for (i = 1; i <= n; i++){sum += i;}return sum;}int main(){int n = 50;printf("%d\n", SumSolution(n));}

🏃 这个方法时间开销为o(n),是比较容易想到的方法

思路二:公式法

🏃 伟大的数学家高斯没有这么做,而是将它们倒着书写一遍,总结出了求和公式,即伟大的高斯求和公式
🏃 (首项 + 末项)× 项数 ÷ 2

代码二:公式法

#include int SumSolution(int n){//首项是1 末项是n 项数是n 代入公式即可int front = 1;int back = n;return (n + 1) * n / 2;}int main(){int n = 5;printf("%d\n", SumSolution(n));}

🏃 这种方法最简单粗暴,时间开销和空间开销都很 nice

思路三:递归

🏃 整个大问题都可以拆分成小问题
🏃 比如求和到 n ,相当于 n + 求和到(n-1)
🏃 求和到 n-1,相当于(n-1)+ 求和到(n-2)…
🏃 直到变成求和到 1
🏃 以此,可用递归求解这个问题

代码三:递归

int SumSolution(int n){//递归出口if (n <= 1) return n;else return n + SumSolution(n - 1);}int main(){int n = 50;printf("%d\n", SumSolution(n));}

🏃 代码虽简单,但是时间复杂度和空间复杂度都达到了o(n),不太实用

💘 如果题目要求不使用乘除法forwhileifelseswitchcase等关键字及条件判断语句(A?B:C)
💘 那么我们之前的方法就会被全部干掉。因此,让我们脑洞大开,寻找新的解题思路

思路四:改良递归

🏃 当不能使用 if 条件句的时候,寻常递归就不能在使用,因为无法判断递归的结束
🏃 但是在c语言中有一个 && 操作符,它有一个特点:当 && 左边判断为假时,右边的就不会再执行
🏃 我们可以利用这个特性,模拟出递归的入口和出口

代码四:改良递归

int Sum_Solution(int n) {int ret = n;//当n为0时,&& 判断为假,右边就不会执行,相当于递归结束n && (ret+=Sum_Solution(n-1));return ret;}int main(){int n = 50;printf("%d\n", SumSolution(n));}

🏃 这个方法是非常巧妙的,巧用&&的判断机制能让我们模拟递归的实现

思路五:调用构造函数(C++)

🏃 C++的类实体化时(创建类的对象时)会调用构造函数
🏃 我们可以在构造函数中实现累加
🏃 具体细节请看代码中的注释

代码五:公式法

//这一个类用来创建n个对象,同时调用n次构造函数class Add{public: Add()    { _i++; _ret += _i;    }    //避免出了作用域,变量就销毁,所以定义两个静态成员    static int _i;    static int _ret;};//静态变量的定义和初始化int Add::_i = 0;int Add::_ret = 0;//定义一个解决问题的类class Solution {public:    int SumSolution(int n)    { //创建一个Add的类,用它来创建对象时,就可以调用构造函数 //创建n个对象,就调用n次构造函数 Add a[n]; return Add::_ret;    }};int main(){int n = 50;printf("%d\n", Solution().SumSolution(n));}

🏃 思路四和思路五都能解决不能使用乘除法forwhileifelseswitchcase等关键字及**条件判断语句(A?B:C)**的问题,值得我们反复推敲。

// 后记

🏃以后每天更新一道算法题,并且附带超级详细的讲解和注释,所有代码均可复制到编译器里自测。
🏃如果有疑问的小伙伴,欢迎评论留言,我会详细解答。

// 文章中任何错误都请大佬指正。