Page 61 - 4387

d 4 4 , 1 = ((d 4 1 , 1 ⊗U 4 , 1 ) ⊕ (d 4 2 , 1 ⊗U 4 , 2 ) ⊕ (d 4 3 , 1 ⊗U 4 , 3 )) ⊕ d 3 4 , 1 =

= ((( ) 3 , 2 , 0 ⊗ ( ∞, ∞, ∞)) ⊕ 1(( ) 3 , 2 , ⊗ ( ∞, ∞, ∞)) ⊕ 0(( ) 2 , 1 , ⊗

⊗ ( − ,1 ∞, ∞))) ⊕ ( − ,1 ∞, ∞) = ((( ∞, ∞, ∞) ⊕ ( ∞, ∞, ∞)) ⊕ ( − 0,1 1 , )) ⊕ ( − ,1 ∞, ∞) =
= ((∞ ,∞ ,∞ ) ⊕ (− 1 , 0 , 1 )) ⊕ (− , 1 ∞ ,∞ ) = (− ) 1 , 0 , 1 ⊕ (− , 1 ∞ ,∞ ) = (− ) 1 , 0 , 1 .

Отже, оцінюючий рядок буде наступним:
4
1
d 1 4 = ) 3 , 2 , 0 ( ) 3 , 2 , 1 ( ) 2 , 1 , 0 ( (− ) 1 , 0 , 1 .

Оскільки ≠ , то збільшуємо r на 1 і знову переходимо до
3
4
1
1
кроку 2.
Крок 2. r=2.

Зворотній пошук (використовуємо співвідношення (7.6)):

d 5 4 , 1 = d 4 4 , 1 = (− ) 1 , 0 , 1 .

d 5 3 , 1 = (d 5 4 , 1 ⊗ L 3 , 4 ) ⊕ d 4 3 , 1 = (( − 0,1 ) 1 , ⊗ ,2( ∞, ∞)) ⊕ ,0( ) 2 , 1 =

= ) 3 , 2 , 1 ( ⊕ ) 2 , 1 , 0 ( = ) 2 , 1 , 0 ( ,

d 5 2 , 1 = ((d 5 3 , 1 ⊗ L 2 , 3 ) ⊕ (d 5 4 , 1 ⊗ L 2 , 4 )) ⊕ d 4 2 , 1 = ((( ) 2 , 1 , 0 ⊗

⊗ ( ∞, ∞, ∞)) ⊕ (( − 0, 1 ) 1 , ⊗ , 3( ∞, ∞))) ⊕ , 1( ) 3 , 2 = (( ∞, ∞, ∞) ⊕ 2( 4 , 3 , )) ⊕

⊕ ) 3 , 2 , 1 ( = ) 4 , 3 , 2 ( ⊕ ) 3 , 2 , 1 ( = ) 3 , 2 , 1 ( ,

d 5 1 , 1 = ((d 5 2 , 1 ⊗ L 1 , 2 ) ⊕(d 5 3 , 1 ⊗ L 1 , 3 ) ⊕ (d 5 4 , 1 ⊗ L 1 , 4 )) ⊕ d 4 1 , 1 =

= ((( ) 3 , 2 , 1 ⊗ ,2( , 4 ∞)) ⊕ 0(( ) 2 , 1 , ⊗ ,2( ∞, ∞)) ⊕ (( − 0, 1 ) 1 , ⊗ ( ∞, ∞, ∞))) ⊕

⊕ ,0( ) 3 , 2 = ((( ) 5 , 4 , 3 ⊕ 2( 4 , 3 , )) ⊕ ( ∞, ∞, ∞)) ⊕ ,0( ) 3 , 2 = 2(( ) 4 , 3 , ⊕

⊕ (∞ ,∞ ,∞ )) ⊕ ) 3 , 2 , 0 ( = ) 4 , 3 , 2 ( ⊕ ) 3 , 2 , 0 ( = ) 3 , 2 , 0 ( .

Отже, оцінюючий рядок буде наступним:
5
1
d 1 5 = ) 3 , 2 , 0 ( ) 3 , 2 , 1 ( ) 2 , 1 , 0 ( (− ) 1 , 0 , 1 .

Оскільки = , то робота алгоритму подвійного пошуку
5
4
1 1
завершується. Узагальнені результати дії алгоритму наведені в

60