每日一题 - 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),不太实用
💘 如果题目要求不使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句(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));}
🏃 思路四和思路五都能解决不能使用乘除法、for、while、if、else、switch、case等关键字及**条件判断语句(A?B:C)**的问题,值得我们反复推敲。
// 后记
🏃以后每天更新一道算法题,并且附带超级详细的讲解和注释,所有代码均可复制到编译器里自测。
🏃如果有疑问的小伙伴,欢迎评论留言,我会详细解答。
// 文章中任何错误都请大佬指正。