Изменения

Перейти к: навигация, поиск

Быстрый поиск наибольшей возрастающей подпоследовательности

5206 байт добавлено, 19:41, 7 января 2017
→‎Пример: Подподраздел написан (предыдущий был о Визуализации)
|style="background:#FFCC80"|2||style="background:#FF9980"|4||style="background:#FF8080"|5||style="background:#FFE680"|1||style="background:#FFB380"|3
|}
 
|}
<tex>merged</tex> аналогичен сортированному, т.к. предыдущих ключей нет.
{| class="wikitable" style="center"
! colspan="5"|Ключи сортированного блока
|-align="center"
| 2||4||5||1||3
|}
{| class="wikitable" style="center"
! colspan="5"| <tex>\xi</tex>
|-align="center"
| 4||1||5||2||3
|}
Пропускаем их через <tex>LIS</tex>:
{| class="wikitable" style="center"
|-align="center"
| style="background:#FFCC00"| 2 4 || || || style="background: #77A9F4"| 24
|-align="center"
| 2 || style="background:#FFCC00"| 4 1 || || || style="background: #77A9F4"| 41
|-align="center"
| 2 || 4 1 || style="background:#FFCC00"| 5 || || style="background: #77A9F4"| 5
|-align="center"
| 1 || style="background:#FFCC00"| 1 2 || 4 || 5 || style="background: #77A9F4"| 12
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || 5 || style="background: #77A9F4"| 3
|}
''' Результат работы '''
 
<tex>B: \{1, 2, 3\}</tex>
 
<tex>merged: \{3, 4, 8, 9, 10\}</tex>
===== Второй блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>merged: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>
{|
| ||
|-align="center"
|style="background:#FFE680"|1||style="background:#FFCC80"|2||style="background:#FF8080"|5||style="background:#FF9980"|4||style="background:#FFB380"|3
|}
|}
 
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="8"|<tex>merged</tex>
|-align="center"
| 1||2||3||4||5||6||8||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>ind's\#0</tex> - индексы текущих
|-align="center"
| 3||4||7
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>ind's\#1</tex> - индексы новых
|-align="center"
| 1||2||5||6||8
|}
|}
 
{| class="wikitable" style="center"
! colspan="5"|Ключи сортированного блока
|-align="center"
| 1||2||5||4||3
|}
{| class="wikitable" style="center"
! colspan="5"| <tex>\xi</tex>
|-align="center"
| 1||2||5||4||3
|}
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="5"| новые ключи
|-align="center"
| 1||2||8||6||5
|}
Обновление старых ключей:
{| class="wikitable" style="center"
|-align="center"
| style="background:#FFCC00"| 3 || || || style="background: #77A9F4"| 3
|-align="center"
| 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4
|-align="center"
| 3 || 4 || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
|}
<tex>LIS</tex> новых:
{| class="wikitable" style="center"
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 7 || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 7 || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || 7 || style="background:#FFCC00"| 8 || style="background: #77A9F4"| 8
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 6 || 8 || style="background: #77A9F4"| 6
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 5 || 8 || style="background: #77A9F4"| 5
|}
''' Результат работы '''
 
<tex>B: \{1, 2, 5, 8\}</tex>
 
<tex>merged: \{1,2,3,4,5,6,8,12\}</tex>
 
===== Третий блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>merged: \{1,2,3,4,5,6,8,12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>
{|
| ||
{| style="center"
! colspan="5"|Первый блок
|-align="center"
|style="background:#FFB580"|7||style="background:#FF8B80"|11
|-align="center"
|style="background:#FFC080"|1||style="background:#FF8080"|2
|}
| ||
{| style="center"
! colspan="5"|Cортированный
|-align="center"
|style="background:#FFB580"|7||style="background:#FF8B80"|11
|-align="center"
|style="background:#FFC080"|1||style="background:#FF8080"|2
|}
|}
 
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="8"|<tex>merged</tex>
|-align="center"
| 1||2||5||7||11||12
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>ind's\#0</tex> - индексы текущих
|-align="center"
| 1||2||3||6
|}
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>ind's\#1</tex> - индексы новых
|-align="center"
| 4||5
|}
|}
{| class="wikitable" style="center"
! colspan="5"|Ключи сортированного блока
|-align="center"
| 1||2
|}
{| class="wikitable" style="center"
! colspan="5"| <tex>\xi</tex>
|-align="center"
| 1||2
|}
Восстанавливаем порядок новых из <tex>ind's\#1</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="2"| новые ключи
|-align="center"
| 4||5
|}
Обновление старых ключей:
{| class="wikitable" style="center"
|-align="center"
| style="background:#FFCC00"| 1 || 4 || 7 || || style="background: #77A9F4"| 1
|-align="center"
| 1 || style="background:#FFCC00"| 2 || 7 || || style="background: #77A9F4"| 2
|-align="center"
| 1 || 2 || style="background:#FFCC00"| 3 || || style="background: #77A9F4"| 3
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 6 || style="background: #77A9F4"| 6
|}
<tex>LIS</tex> новых:
{| class="wikitable" style="center"
|-align="center"
| 1 || 2 || 3 || style="background:#FFCC00"| 4 || || style="background: #77A9F4"| 4
|-align="center"
| 1 || 2 || 3 || 4 || style="background:#FFCC00"| 5 || style="background: #77A9F4"| 5
|}
''' Результат работы '''
 
<tex>B: \{1, 2, 3, 4, 5\}</tex>
 
<tex>merged: \{1,2,5,7,11,12\}</tex>
 
===== Восстановление НВП =====
{| class="wikitable" style="center"
! colspan="12"| <tex>predecessor</tex>
|-align="center"
| 1||2||3||4||5||6||7||8||9||10||11||12
|-align="center"
| ||1|| ||3||2||2||5||4|| ||3||7||8
|}
Начинаем восстановление с <tex>merged[5] = 11</tex>:
{| class="wikitable" style="center"
|+ обратный порядок
| 11||7||5||2||1
|}
{| class="wikitable" style="center"
|+ НВП
| 1||2||5||7||11
|}
==== Псевдокод ====
Good-Morning
47
правок
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/59150»

Навигация