如何以求和形式计算任意N下fun1打印语句的调用次数？

问题拆解 #

我们需要计算当输入参数为任意正整数N时，myAlg函数中fun1对应的print语句的调用次数。先明确三层循环的执行逻辑：

• 外层循环：i从1遍历到N
• 中层循环：j从1遍历到当前的i值
• 内层循环：k从1遍历到当前的j值
• fun1触发条件：j > k

逐层推导求和式 #

1. 固定j时的fun1调用次数
   对于某个确定的j，k的取值范围是1到j。满足j > k的k值为1、2、…、j-1，共j-1个（当j=1时，j-1=0，无fun1调用）。因此每个j对应的fun1调用次数是j-1。

2. 固定i时的fun1调用次数
   对于某个确定的i，j的取值范围是1到i。此时fun1的总调用次数是对每个j的调用次数求和：

   Σ（j=1到i）(j-1) = Σ（m=0到i-1）m （令m = j-1）
   

   这是从0到i-1的整数和，结果为(i-1)*i/2。

3. 总调用次数的求和式
   对所有i从1到N求和，得到总的fun1调用次数：

   总次数 = Σ（i=1到N）[i*(i-1)/2]
   

求和式化简 #

展开表达式i*(i-1)/2 = (i² - i)/2，总次数可拆分为：

总次数 = (1/2) * [ Σ（i=1到N）i² - Σ（i=1到N）i ]

利用已知的数学求和公式：

• 整数和：Σ（i=1到N）i = N*(N+1)/2
• 平方和：Σ（i=1到N）i² = N*(N+1)*(2N+1)/6

代入后逐步化简：

总次数 = (1/2) * [ N*(N+1)*(2N+1)/6 - N*(N+1)/2 ]
= (1/2) * N*(N+1)/2 * [ (2N+1)/3 - 1 ]
= (1/2) * N*(N+1)/2 * (2N-2)/3
= N*(N+1)*(N-1)/6
= N*(N² - 1)/6

验证示例 #

• 当N=2时，总次数=2*(4-1)/6=1，与实际执行结果一致（仅i=2、j=2、k=1时调用1次）。
• 当N=3时，总次数=3*(9-1)/6=4，实际执行：i=2时调用1次，i=3时调用3次，合计4次，结果正确。

内容的提问来源于stack exchange，提问作者BeanBop