Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы)
(Пример работы)
Строка 38: Строка 38:
  
 
<tex>\begin{array}{l l}   
 
<tex>\begin{array}{l l}   
    A \rightarrow \varepsilon|BC\\
+
A \rightarrow \varepsilon|BB|CD\\
    D \rightarrow BC\\
+
B \rightarrow BB|CD\\
    B \rightarrow (\\
+
C \rightarrow (\\
    C \rightarrow )|DE\\
+
D \rightarrow BE|)\\
    E \rightarrow )\\
+
E \rightarrow )\\
 
\end{array}</tex>
 
\end{array}</tex>
  
Строка 129: Строка 129:
 
|-
 
|-
 
! 1
 
! 1
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 149: Строка 149:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 159: Строка 159:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 194: Строка 194:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 204: Строка 204:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 214: Строка 214:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 224: Строка 224:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 234: Строка 234:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 244: Строка 244:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 269: Строка 269:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 299: Строка 299:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 309: Строка 309:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 377: Строка 377:
  
 
|}
 
|}
{| clear="both" |}
 
 
{| clear="both" |}
 
{| clear="both" |}
  
Строка 464: Строка 463:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
 
|  
 
|  
Строка 484: Строка 483:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 491: Строка 490:
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 529: Строка 528:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 539: Строка 538:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 549: Строка 548:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 559: Строка 558:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 569: Строка 568:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 579: Строка 578:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 595: Строка 594:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 604: Строка 603:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 625: Строка 624:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 634: Строка 633:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 644: Строка 643:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 794: Строка 793:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
 
|  
 
|  
Строка 814: Строка 813:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 821: Строка 820:
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 859: Строка 858:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 869: Строка 868:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 879: Строка 878:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 889: Строка 888:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
  
 
|-
 
|-
Строка 899: Строка 898:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 909: Строка 908:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 925: Строка 924:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 934: Строка 933:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 951: Строка 950:
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
Строка 956: Строка 956:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
  
 
|-
 
|-
Строка 964: Строка 963:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 974: Строка 973:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 1124: Строка 1123:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
 
|  
 
|  
Строка 1144: Строка 1143:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 1189: Строка 1188:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1199: Строка 1198:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1209: Строка 1208:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1219: Строка 1218:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
  
 
|-
 
|-
Строка 1229: Строка 1228:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 1239: Строка 1238:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 1255: Строка 1254:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1264: Строка 1263:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1277: Строка 1276:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
Строка 1286: Строка 1286:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
  
 
|-
 
|-
Строка 1294: Строка 1293:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 1304: Строка 1303:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 1454: Строка 1453:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
 
|  
 
|  
Строка 1474: Строка 1473:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 1519: Строка 1518:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1529: Строка 1528:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1539: Строка 1538:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1549: Строка 1548:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
  
 
|-
 
|-
Строка 1559: Строка 1558:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 1569: Строка 1568:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 1585: Строка 1584:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1594: Строка 1593:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1607: Строка 1606:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
Строка 1616: Строка 1616:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
  
 
|-
 
|-
Строка 1624: Строка 1623:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 1634: Строка 1633:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 1724: Строка 1723:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|-
 
|-
Строка 1784: Строка 1783:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"|
|  
 
  
 
|-
 
|-
Строка 1804: Строка 1803:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 1849: Строка 1848:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1859: Строка 1858:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1869: Строка 1868:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1879: Строка 1878:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
  
 
|-
 
|-
Строка 1889: Строка 1888:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 1899: Строка 1898:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 1915: Строка 1914:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 1924: Строка 1923:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 1937: Строка 1936:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
Строка 1946: Строка 1946:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
  
 
|-
 
|-
Строка 1954: Строка 1953:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 1964: Строка 1963:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}
Строка 2054: Строка 2053:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|-
 
|-
Строка 2114: Строка 2113:
 
|-
 
|-
 
! 1
 
! 1
 +
|
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"|
|  
 
  
 
|-
 
|-
Строка 2134: Строка 2133:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
 
|  
 
|  
  
Строка 2179: Строка 2178:
 
|-
 
|-
 
! 1
 
! 1
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 2189: Строка 2188:
 
! 2
 
! 2
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 2199: Строка 2198:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 2209: Строка 2208:
 
|  
 
|  
 
|  
 
|  
 +
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
 
  
 
|-
 
|-
Строка 2219: Строка 2218:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
  
Строка 2229: Строка 2228:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|}
 
|}
Строка 2245: Строка 2244:
 
! 1
 
! 1
 
|  
 
|  
| align="center"| ●
+
|  
 
|  
 
|  
 
|  
 
|  
Строка 2254: Строка 2253:
 
! 2
 
! 2
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
 
|  
 
|  
Строка 2267: Строка 2266:
 
|  
 
|  
 
|  
 
|  
| align="center"| ●
+
|  
  
 
|-
 
|-
 
! 4
 
! 4
 +
|
 
|  
 
|  
 
|  
 
|  
Строка 2276: Строка 2276:
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
|
 
  
 
|-
 
|-
Строка 2284: Строка 2283:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
 
|  
 
|  
  
Строка 2294: Строка 2293:
 
|  
 
|  
 
|  
 
|  
|  
+
| align="center"| ●
  
 
|}
 
|}

Версия 02:25, 5 ноября 2014

Задача:
Пусть дана контекстно-свободная грамматика [math]\Gamma[/math] в нормальной форме Хомского и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.


Алгоритм

Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK - алгоритм) — универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Будем решать задачу динамическим программированием. Дана строка [math]w[/math] размером [math]n[/math]. Заведем для неё трехмерный массив [math]d[/math] размером [math]|\Gamma| \times n \times n[/math], состоящий из логических значений, и [math]d[A][i][j] = true[/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]w[i \dots j][/math].

Рассмотрим все пары [math]\lbrace \langle j, i \rangle | j-i=m \rbrace[/math], где [math]m[/math] — константа и [math]m \lt n[/math].

  • [math]i = j[/math]. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки [math]w[/math]. В таком случае [math]d[A][i][i] = true[/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math]. Иначе [math]d[A][i][i] = false[/math].
  • [math]i \ne j[/math]. Значения для всех нетерминалов и пар [math]\lbrace \langle j', i' \rangle | j' - i' \lt m \rbrace[/math] уже вычислены, поэтому [math]d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j][/math]. То есть, подстроку [math]w[i \dots j][/math] можно вывести из нетерминала [math]A[/math], если существует продукция вида [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]w[i \dots k][/math] выводима из [math]B[/math], а подстрока [math]w[k + 1 \dots j][/math] выводится из [math]C[/math].

CYK rule 2.jpg

После окончания работы значение [math]d[S][1][n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где [math]S[/math] — начальный символ грамматики.

Модификации

Количество способов вывести слово

Если массив будет хранить целые числа, а формулу заменить на [math]d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j][/math], то [math]d[A][i][j][/math] — количество способов получить подстроку [math]w[i \dots j][/math] из нетерминала [math]A[/math].

Минимальная стоимость вывода слова

Пусть [math]P(A \rightarrow BC)[/math] — стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + P(A \rightarrow BC) )[/math], то [math]d[A][i][j][/math] — минимальная стоимость вывода подстроки [math]w[i \dots j][/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является обобщением задачи динамического программирования на подотрезке.

Асимптотика

Обработка правил вида [math]A \rightarrow w[i][/math] в шаге 1 выполняется за [math]O(n \cdot |\Gamma|)[/math].

Проход по всем подстрокам в шаге 2 выполняется за [math]O(n^2)[/math]. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(n \cdot |\Gamma|)[/math]. В итоге получаем конечную сложность [math]O(n^3 \cdot |\Gamma|)[/math].

Следовательно, общее время работы алгоритма — [math]O(n^3 \cdot |\Gamma|)[/math]. Кроме того, алгоритму требуется память (на массив [math]d[/math]) объемом [math]O(n^2 \cdot |N|)[/math], где [math]|N|[/math] — количество нетерминалов грамматики.

Пример работы

Дана грамматика правильных скобочных последовательностей [math]\Gamma[/math]:

[math]\begin{array}{l l} A \rightarrow \varepsilon|BB|CD\\ B \rightarrow BB|CD\\ C \rightarrow (\\ D \rightarrow BE|)\\ E \rightarrow )\\ \end{array}[/math]

Дано слово [math]w = $()(())$[/math].

Инициализация массива [math]d[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Заполнение массива [math]d[/math].
Итерация m = [math]1[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Итерация m = [math]2[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Итерация m = [math]3[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Итерация m = [math]4[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Итерация m = [math]5[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6
Итерация m = [math]6[/math].
A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

См. также

Источники информации