ign="justify"> При першому попаданні в точку Х твердження (*) виконується, так як max = A [n-1, 0]
j = n, i = 1-n, r = 1-n, k = 1-r = n = A [n-1 ,1-n + n-1]
n +1 ВЈ 1-n ВЈ j = n ВЈ m-1 + n
Пусти при p - попаданні в точку Х твердження (*) виконується. Доведемо, що твердження (*) виконується при p +1 - попаданні в точку Х.
Для p:
" j, r:-n +1 ВЈ r ВЈ j ВЈ m-rj
$ max: (max Ві ГҐ A [k-1, r + k-1] or max Ві ГҐ A [k-1, r + k-1]) = 1 k = 1-rj (max = ГҐ A [k-1, r + k-1] or max = ГҐ A [k-1, r + k-1]) (*) = 1 k = 1-r
r =-n + p +1.
Щоб потрапити в точку Х необхідно, щоб виконалось умова i
j j
sum = ГҐ A [k-1, r + k-1] or sum = ГҐ A [k-1, r + k-1], де r =-n + p
k = 1 k = 1-r
Якщо max, отриманий на попередніх кроках : = sum. Якщо max> sum, то max залишається колишнім, обчисленим на попередніх кроках.
Таким чином, або r =-n + p, або r - залишається колишнім. При обох варіантах виконується умова (*).
Доведемо, що програма закінчиться.
Так як в кожним кроком значення i збільшується, а n і m-кінцеві і не змінюються, то через деякий час не виконається умова i
Аналіз мереж Петрі на основі дерева досяжності.
Мережа Петрі
P1
a
P2
В
b.true
P3
c b.false
P4
...
