Как рассчитать, сколько циклов нужно без циклов?

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 будет значением A после итерации i , где 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 ^{i -1} )

Итак:

A _i = 100 · 1,1 ⁱ - 10 · B · (1.1 ⁱ - 1)

Или вообще:

A _i = A ₀ · (1 + p ) ⁱ - B · ^{((1 + p *)1186 *) i - 1)} / _p

Чтобы найти итерацию i , после чего A == 0, мы можем установить 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 · A 0 - B )} )

Для B = 20 это дает i = 7,2. Мы округлим и получим 8.

Время сложность O(1).