求助一道小学数学题

ykcbf1100

飞天篮球猪 发表于 2025-1-27 17:32
递归这样写重复分支有点多，时间复杂度较高...改成记忆化递归

不了解记忆化递归呢。指点一二？

桑榆非晚123

Sub CalculateSum()
    Dim n As Integer         ' 计数变量
    Dim an As Double         ' 单项值
    Dim Sn As Double         ' 累计和
   
    ' 初始化Sn
    Sn = 0
   
    ' 循环求和
    For n = 1 To 100
        an = 2 / (n * (n + 1)) ' 计算an
        Sn = Sn + an           ' 累加到Sn
    Next n
   
    ' 输出结果
    MsgBox "Sn的值为: " & Sn
End Sub
每一项是自然数和的倒数，自然数的和是n(n+1)/2，倒数是2/n(n+1)

micch

ykcbf1100 发表于 2025-1-27 18:34
不了解记忆化递归呢。指点一二？

记忆化意思就是把已经计算过的结果保存下来，比如声明一个数组记录dg(n)的结果。

需要在dg的代码里增加一个决策树判断，如果dg(n)已经计算过有结果了，那么就直接返回dg(n)，如果还没计算，才进入dg=dg(n-1)+dg(n)

多了一层判断，省去很多递归。

但从这个角度推理，属于递归的缺点，因为即使少了很多递归，依然没有直接循环更合理，直接循环就不需要进入递归，无效运算更少。

ykcbf1100

micch 发表于 2025-1-27 19:00
记忆化意思就是把已经计算过的结果保存下来，比如声明一个数组记录dg(n)的结果。

需要在dg的代码里增 ...

感谢指点。
确实，此题中循环比我的递归速度更快。

micch

改一下，就是增加一个数组变量，用来记忆每个n对应的累加和值，这样就不会频繁的计算dg(n-1)+n了

飞天篮球猪

ykcbf1100 发表于 2025-1-27 18:34
不了解记忆化递归呢。指点一二？

记忆化递归要先定义一个全局变量数组或者字典，保存递归产生的分支结果，空间换时间，因为递归很容易爆栈，一般栈的大小1兆-3兆左右，记忆化递归可以减少递归次数，避免爆栈。用在这里有点不划算，3楼的递推法就很好了。
有兴趣可以试试斐波那契数列，用记忆化递归和常规递归，差别还是很大的...仅供参考

ykcbf1100

飞天篮球猪 发表于 2025-1-27 19:54
记忆化递归要先定义一个全局变量数组或者字典，保存递归产生的分支结果，空间换时间，因为递归很容易爆栈 ...

谢谢指点，我还得多学学。

飞天篮球猪

ykcbf1100 发表于 2025-1-27 20:05
谢谢指点，我还得多学学。

指点不敢...大佬过谦了...有个小题可以一起学习...

ykcbf1100

飞天篮球猪 发表于 2025-1-27 20:36
指点不敢...大佬过谦了...有个小题可以一起学习...

对于递归，我还处于一知半解状态，我还得继续努力。

飞天篮球猪

ykcbf1100 发表于 2025-1-27 20:40
对于递归，我还处于一知半解状态，我还得继续努力。

仅供参考...1、


2、