13.1. Підпослідовність (рекурентні співвідношення)
Позначимо через f (k, l ) найбільшу довжину спільної підпослідовності двох послідовностей {xj} при j = 1, 2, …, k та {yj} при j = 1, 2, …, l. Якщо одна з послідовностей порожня (кількість її елементів дорівнює нулю), то порожньою є і найдовша спільна підпослідовність: f (k, 0) = 0 = f (0, l ). Крім цього маємо таке рекурентне співвідношення:
| f (k, l ) = f (k – 1, l – 1) + 1 | при xk = yl; |
| f (k, l ) = max{ f (k, l – 1), f (k – 1, l )} | при xk ≠ yl. |
У першому випадку останні члени обох послідовностей можна взяти за останній член найдовшої спільної підпослідовності. У другому випадку щонайменше один з них не є останнім членом найдовшої спільної підпослідовності.
Обидві послідовності можна зберігати в оперативній пам'яті в одному лінійному масиві.
В оперативній пам'яті достатньо зберігати 2 рядки матриці f: той, що визначають, і попередній.
За другу послідовність (її довжина дорівнює кількості стовпчиків матриці f ) потрібно взяти коротшу.
13.2. Сім'я (графи)
При зчитуванні даних визначити називний відмінок імені кожного персонажу, його стать, безпосередніх предків і нащадків.
Встановити всіх безпосередніх предків і нащадків кожного з персонажів: батько (мати) сестри чи брата твій батько (твоя мати).
Знайти ланцюг родичі-свояки між персонажами, що передбачає:
визначення мінімальної кількості ланок і членів послідовності, кожний наступний член якої є сином чи донькою, батьком чи матір'ю, чоловіком чи жінкою попереднього;
встановлення різниці кількості поколінь, на які віддалені персонажі від спільного пращура (передбачено, що граф, що подає відносини родичівства і свояцтва, є деревом, тобто не має циклів):
така різниця між сином чи донькою і батьком чи матір'ю складає 1 покоління, а між батьком і сином складає –1;
така різниця між онуком (онукою) і дідом (бабою) складає 2 покоління, а між дідом і онуком складає –2;
брати і сестри віддалені один від одного на 0 поколінь;
чоловік і дружина віддалені один від одного на 0 поколінь.
Визначати родичівство чи свояцтво згідно з поданих в умові означень.