求嵌套循环代码中printf打印"Anjali"次数的通用计算公式

首先给出目标代码：

#include <stdio.h>

int main(int argc, const char *argv[])
{
    int n;

    printf("Input a number: ");
    scanf("%d", &n);

    for (int i = 1; i <= n; i *= 3)
        for (int j = i; j <= n; j++)
            printf("Anjali \n");

    return 0;
}

问题需求 #

推导上述代码中printf()函数执行次数的通用计算公式，已知当n=10时，printf()共执行20次。

推导过程 #

1. 分析外层循环的迭代值
   外层循环中i从1开始，每次乘以3，直到i > n停止。因此i的取值序列为：1, 3, 9, ..., 3^k，其中k是满足3^k ≤ n的最大整数（即k = ⌊log₃n⌋，向下取整）。外层循环总共执行k+1次。

2. 计算单次外层循环对应的内层循环次数
   当外层循环取i=3^m（m从0到k）时，内层循环j从i遍历到n，执行次数为：
   n - i + 1 = n - 3^m + 1

3. 总执行次数求和
   总执行次数是所有内层循环次数的总和，可拆分为两部分求和：

总次数S = Σ（m从0到k）(n - 3^m + 1)
        = Σ（m从0到k）(n+1) - Σ（m从0到k）3^m

• 第一部分求和：共k+1个n+1相加，结果为(k+1)(n+1)
• 第二部分是首项为1、公比为3的等比数列求和，结果为(3^(k+1)-1)/2

4. 最终通用公式
   将两部分结果代入，得到：

S = (k+1)(n+1) - (3^(k+1)-1)/2

其中k是满足3^k ≤ n的最大整数（即k = ⌊log₃n⌋）。

示例验证（n=10） #

• 确定k：3^2=9 ≤10，3^3=27>10，因此k=2
• 代入公式：

S = (2+1)(10+1) - (3^(2+1)-1)/2
  = 3*11 - (27-1)/2
  = 33 -13
  =20

与给定示例结果一致，公式正确。

内容的提问来源于stack exchange，提问作者Tushar K. Sengar