python - 如何计算不循环需要循环多少次？

Question

如果我有一个值 A，它以其当前值的 10% 递增，同时被固定数量 B 带走，我如何计算在不实际循环的情况下达到 0 需要多少循环？

这就是我通过循环找到它的方式:

LoopsNeeded = 0
A = 100
B = 20
while A > 0:
   C = A * 0.1
   A = A + C
   A = A - B
   LoopsNeeded = LoopsNeeded + 1
print(LoopsNeeded)

在第一个循环中:

initial values
A = 100
B = 20
-------
A > 0 = True
C = A(100) * 0.1 = 10
A = A(100) + C(10) = 110
A = A(110) - B(20) = 90
LoopsNeeded = 1
-------
A is now 90 on the next round of the loop

这导致总共需要 8 个循环，如果我用非常大的数字执行此操作，这个循环可能会花费很长时间，这样做的更短方法是什么？

Answer 1

设 A_i 为迭代 i 后 A 的值，其中 A₀ 是 100。

让我们为 A_i 创建一个递归公式:

A_i = A_i−1 · 1.1 − B

如果我们展开它，我们得到:

A_i = (A_i−2 · 1.1 − B) · 1.1 − B = A_i−2 · 1.1² − B · 1.1 − B
A_i = (A_i−3 · 1.1 − B) · 1.1² − B · 1.1 − B = A_i−3 · 1.1³ − B · 1.1² − B · 1.1 − B
...
A_i = A₀ · 1.1ⁱ − B · (1.1⁰ + 1.1¹ + ⋯ + 1.1ⁱ⁻¹)

所以:

A_i = 100 · 1.1ⁱ − 10 · B · (1.1ⁱ − 1)

或者一般来说:

A_i = A₀ · (1 + p)ⁱ − B · ^{((1 + p)i - 1)} / _p

要找到 A == 0 之后的迭代 i，我们可以设置 A_i = 0 并求解 i:

0 = A_i
0 = 100 · 1.1ⁱ − 10 · B · (1.1ⁱ − 1)
1.1ⁱ = 10 · B · (1.1ⁱ − 1)
i = log_1.1 (^{10 · B} / _{(10 · B − 100)})

或者一般来说:

i = log_{p + 1} (^-B / _{(p · A0 − B)})

当 B = 20 时，i = 7.2。我们四舍五入，确实得到了 8。

时间复杂度是O(1)。