Python|奇/偶数倒数求和之循环与递归的奥秘

叁歲伎倆 2022-10-08 11:08 152阅读 0赞

**本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。**

前言

今天我们来解决粉丝提出的一个问题，如图：

![a9b2eae5de202b7ddfa027e6d23dc1fc.png][]

问题描述

编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,当输入n为奇数时，调用函数1/1+1/3+...+1/n,输出结果示例：

输入：5

输出：1.5333333333333332

输入：6

输出：0.9166666666666666

解决方案

用文当我看到这个问题首先就想到可以用if判断加循环来解决。首先定义一个函数Sum，其参数为n，创建一个sum=0来储存相加的和，接下来判断n是奇数还是偶数，如果是奇/偶数，用for循环遍历1到n+1之间的每个数，同时嵌套一个if来筛选其中的奇/偶数，再将筛选出来的数的倒数依次与sum相加，循环结束后返回sum，那么sum即为所求。代码如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;"> <p># 方法一<br> &nbsp;def Sum_1(n):<br> &nbsp;&nbsp;&nbsp;&nbsp; # 创建一个sum来储存相加的和<br> &nbsp;&nbsp;&nbsp;&nbsp; sum = 0<br> &nbsp;&nbsp;&nbsp;&nbsp; # 判断n是否是偶数<br> &nbsp;&nbsp;&nbsp;&nbsp; if n % 2 == 0:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # 用for循环遍历1到n之间的每个数<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for x in range(1,int(n)+1):<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # 嵌套一个if来筛选其中的偶数<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if x % 2 == 0:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; sum += 1 / x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return sum<br> &nbsp;&nbsp;&nbsp;&nbsp; else:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for x in range(1, int(n) + 1):<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; if x % 2 == 1:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; sum += 1 / x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return sum</p> <p>n = int(input('①请输入一个数：'))<br> &nbsp;print('方法一的计算结果为:',Sum_1(n))</p> </td> 
  </tr> 
 </tbody> 
</table>

虽然这个算法可以解决问题，但看上去似乎有那么一丢丢的臃肿，经过思考后发现筛选奇/偶数那一步可以用带判断的列表生成式来代替。列表生成式是Python内置的非常简单却强大的可以用来创建list的生成式。写列表生成式时，把要生成的元素n放到前面，后面跟for循环，就可以把元素为1到n的list创建出来。如果再在for循环后面跟一个if判断语句，那么该生成式就是带判断的列表生成式。这里我们可以用来代替for中嵌套if筛选奇/偶数这一步，让代码更简洁。如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;"> <p># 方法二<br> &nbsp;def Sum_2(n):<br> &nbsp;&nbsp;&nbsp;&nbsp; sum = 0<br> &nbsp;&nbsp;&nbsp;&nbsp; if n % 2 == 0:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # 使用带筛选偶数的列表生成式<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for x in [x for x in range(1 , &nbsp;n + 1) if x % 2 == 0]:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; sum += 1 / x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return sum<br> &nbsp;&nbsp;&nbsp;&nbsp; else:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # 使用带筛选奇数的列表生成式<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; for x in [x for x in range(1 , &nbsp;n + 1) if x % 2 == 1]:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; sum += 1 / x<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return sum</p> </td> 
  </tr> 
 </tbody> 
</table>

虽然列表生产式优雅简洁，但该算法整体上还是比较繁琐。那么有没有其他更简洁的方法呢？答案是运用递归。我们可以先把这个问题当做一道普通的数学题来找规律：

n取1时Sum(1) = 1，n取2时Sum(2)=1/2，n取3时Sum(3) = 1 + 1/3 = Sum(1) + 1/3，n取4时Sum(4) = 1/2 + 1/4 = Sum(2) + 1/4，n取5时Sum(5) = 1 + 1/3+ 1/5= Sum(3) + 1/5……

通过上诉规律我们不难发现：当n取1或2时，得到的结果是固定的，为1或1/2，所以这两个值我们可以直接输出；当n取其他值时得到的结果为Sum(n) = Sum(n-2) + 1/n，相当于在Sum(n)函数内再次调用了Sum()函数本身,即递归。这时我们便可以用递归来解决该问题。代码如下：

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;"> <p>#方法三<br> &nbsp;def Sum_3(n):<br> &nbsp;&nbsp;&nbsp;&nbsp; if n == 1:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 1<br> &nbsp;&nbsp;&nbsp;&nbsp; elif n == 2:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return 1/2<br> &nbsp;&nbsp;&nbsp;&nbsp; else:<br> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return Sum_3(n-2)+1/n</p> </td> 
  </tr> 
 </tbody> 
</table>

接下来我们来运行一下上述三个不同的代码：

![eb0ce0e30562dcdf258cbaac9e80215c.png][]

结语

该问题比较简单，解题思路分为循环和递归两个方向，只要理解了题目意思，先理清解题思路，再写代码便会轻松许多。

实习编辑：衡辉

稿件来源：深度学习与文旅应用实验室（DLETA）

[a9b2eae5de202b7ddfa027e6d23dc1fc.png]: /images/20221005/cfe52fb82f764047b2a910e7d8b723b8.png
[eb0ce0e30562dcdf258cbaac9e80215c.png]: /images/20221005/9f2e1fdbbb114b1e8e20af487baca10d.png