求含取整函数的print调用次数步骤计数函数

First, let's restate the pseudocode clearly to avoid confusion:

function EXAMPLE(some positive int n)
    i <- 1
    while i <= n do
        i <- i * 2
        j <- 1
        while j <= i do
            j <- j + 1
            print("something")

Step 1: Understand the Inner Loop (j's Loop) #

The inner while loop runs from j=1 to j=i, incrementing j by 1 each time. For a given i, this loop executes exactly i times (since j takes values 1, 2, ..., i, and each iteration triggers one print). So every time we run the inner loop, we add i to the total count T(n).

Step 2: Track the Outer Loop (i's Loop) #

The outer loop starts with i=1 and doubles i each iteration, as long as i <= n. Let's break down the values of i that trigger the inner loop:

• First iteration: i starts at 1 (which is ≤n), so we set i=2, then run the inner loop with i=2 → adds 2 to T(n).
• Second iteration: i=2 (if ≤n), set i=4, run inner loop with i=4 → adds 4 to T(n).
• Third iteration: i=4 (if ≤n), set i=8, run inner loop with i=8 → adds 8 to T(n).
• This continues until the current i exceeds n after doubling.

Let’s define m as the largest integer where 2^m ≤ n. For example:

• If n=1: 2^0=1 ≤1, so m=0.
• If n=2 or 3: 2^1=2 ≤n <2^2=4, so m=1.
• If n=4-7: 2^2=4 ≤n <2^3=8, so m=2.

The outer loop will run m+1 times, and the inner loop will use the values 2^1, 2^2, ..., 2^(m+1) (since we double i each time before running the inner loop).

Step 3: Sum the Print Calls #

The total number of print calls is the sum of these inner loop counts:
T(n) = 2 + 4 + 8 + ... + 2^(m+1)

This is a geometric series with first term a=2, ratio r=2, and m+1 terms. Using the geometric series sum formula a*(r^k -1)/(r-1) (where k is the number of terms):
T(n) = 2*(2^(m+1) -1)/(2-1) = 2^(m+2) - 2

Step 4: Verify with Your Examples #

Let’s check against your test cases to confirm:

• n=1: m=0 → 2^(0+2)-2=4-2=2 ✔️
• n=2 or 3: m=1 → 2^(1+2)-2=8-2=6 ✔️
• n=4 or 5: m=2 → 2^(2+2)-2=16-2=14 ✔️

Final Formula #

We can write T(n) using the floor function to formalize m:
T(n) = 2^(⌊log₂n⌋ + 2) - 2

Or using a piecewise definition for clarity:
For non-negative integers m, if 2^m ≤n <2^(m+1), then T(n)=2^(m+2)-2.

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