StukiMania
¬
±
·
×
÷
α
β
γ
δ
ε
ζ
η
θ
ι
κ
λ
μ
ν
ξ
ο
π
ρ
ς
σ
τ
υ
φ
χ
ψ
ω
¹
²
³

Hanoi tornyai

Hanoi (n, i, j, k) rekurzív algoritmus

A lépésszám rekurzív egyenlete: T(n) = 2T(n-1)+1, ha n>0, különben 0.

Állítás: T(n) = 2n-1

Bizonyítás (teljes indukcióval):
T(1) = 21-1 = 2-1 = 1
T(n) = 2T(n-1)+1 = 2*(2n-1-1)+1 = 2n-2+1 = 2n-1