题目描述

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

解题思路

解法1：递归 + 逻辑运算

关键在于利用逻辑与的短路规则来设置递归的出口。

这里给出我写的Python实现以及参考的C++实现

# -*- coding: utf-8 -*-
# @Time         : 2019-10-17 10:56
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : sumSolution.py
# @Blog         : https://sysujayce.github.io/
# @Github       : https://github.com/SysuJayce


class Solution:
    """
    不能使用循环和判断进行求加法，其实暗示了需要将 循环 -> 递归； 判断 -> 逻辑运算
    递归的话比较简单，关键在于如何不使用条件语句设置递归的出口
    
    python中
    a and b: 如果a是0，那么返回0；如果a是非0，那么返回b
    
    利用到上面的技巧，我们就可以不使用条件语句设置递归的出口了
    """
    def Sum_Solution(self, n):
        # 如果n不为0，那么就递归计算 n + f(n - 1)，否则返回n
        return n + (n and self.Sum_Solution(n - 1))
    

链接：https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1?f=discussion
来源：牛客网

int Sum_Solution(int n) {
    int sum = n;
    bool ans = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0);
    return sum;
}

解法2：变相利用乘法

来源于 牛客用户 S向J前W冲 在 https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1?f=discussion 中的分享

本质上 $1 + 2 + 3 + … + n = \frac {n * (n + 1)} {2}$，但是题目规定不能使用乘除法，而分母的除2是容易实现的，只需要进行位移操作即可，关键就在于如何计算分子。

在C++ 中， bool 变量占1个字节的长度，因此，我们可以声明一个bool arr[n][n + 1]，那么sizeof(arr)就是 n * (n + 1)，然后将 sizeof()的返回值右移一位即可。

链接：https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1?f=discussion
来源：牛客网

class Solution {
public:
    int Sum_Solution(int n) {
        bool a[n][n+1];
        return sizeof(a) >> 1;
    }
};