Matematické Fórum

Dobry den,
Mal by som otazku ohladne indukcie, ide o urcenie korektnosti algoritmu.
Mam algoritmus s polom X[] s nahodne zvolenymi kladnymi celymi cislami napr. X[3,2,5,4,3,2,5]
algoritmus prechadza postupne pole a ak dany prvok Xn je vacsi ako vrchol stacku, POPne sa zo stacku, v cykle dokym nenajde vyssi prvok alebo stack nie je prazdny, nasledne sa Xn zapise do stacku.
Pr. behu
S - stack
X - pole

1. iteracia 
X1=3
S prazdne -> push 3 do S
S = 3

2.iteracia
X2 = 2
2 < 3 -> push 2 do S
S = 3,2

3. iteracia
X3 = 5
5>2 -> pop S; 
S = 3
5>3 -> pop S
S prazdne -> push 5 do S
S = 5

4. iteracia
X4 = 4
4<5 push 4 do S
S= 5,4
.....

Invariant tohto algoritmu je
Korektnost by som tu urcoval matematickou indukciou, ktora je podla mna cela chybne uvazovana, ale tu uvadzam:

berme napr. stack zo 4. iteracie aby sme mali nejake data - S[5,4]
Xn > Xn+1
pre n = 1 
   5>4 -> plati
pre n = n+1
   Xn+1 > Xn+2

Mozete ma prosim niekto usmernit/napovedat ako by som mohol/mal riesit korektnost v takomto pripade ?