ПОШУК ТА СОРТУВАННЯ

          8.1. Дано вектор a з n цілих компонент. Знайти зростаючу підпослідовність компонентів вектора найбільшої довжини.

Вказівка. Використати вектор b, у який записувати останні елементи зростаючих підпослідовностей компонент з a довжини 1, 2, ..., k. Якщо на деякому кроці циклу a[i] > b[k], то записати у (k+1)-й елемент вектора b компонент a[i] та збільшити значення k на 1. Інакше знайти перший елемент вектора b, b[j] такий, що a[i] <= b[j] та записати a[i] на місце b[j]. Оскільки елементи вектора b впорядковані, використати бінарний пошук для знаходження індекса j. Після того, як закінчимо прохід вектора a останній елемент вектора b буде останнім елементом шуканої підпослідовності, а кількість елементів вектора b,k - її довжиною. Для того, щоб показати саму підпослідовність (в оберненому порядку), можна використати цикл:

          i¬n;

          поки k>0 повт

                   поки a[i]<b[k] повт

                             i¬i-1

                   кц;

                   показати(a[i]);

                   k¬k-1

          кц

          8.2. Визначити процедуру впорядкування рядків дійсної матриці

а) за неспаданням їх перших елементів;

б) за незростанням сум їх елементів;

в) за неспаданням їх найменших елементів;

г) за незростанням їх найбільших елементів.

Використати методи обмінного сортування та сортування злиттям.

          8.3. Дано масив з n точок площини, заданих своїми координатами. Впорядкивати точки за неспаданням відстані від початку координат.

          8.4. Дано текстові файли F та G. Відомо, що кількість слів у файлі F не більше n, де n - відома константа. Перевірити, чи всі слова з файлу Gвходять у файл F.

Вказівка. Використати масив рядків a з n елементів, у який записати всі різні слова файлу F, впорядковані за зростанням. Використати бінарний пошук для пошуку слова з файлу G у масиві a.

          8.5. В умовах попереднього завдання визначити кількість входжень кожного слова файлу F у файл G.

Вказівка. У масиві a з попереднього завдання зберігати разом зі словом кількість його входжень у файл G.

          8.6. Даний текстовий файл F. Відомо, що кількість слів у файлі F не більше n, де n - відома константа. Побудувати за файлом F пару файлів G та H, щоб у компонентах файлу G зберігались усі різні слова файлу F, впорядковані за алфавітом, а у файлі H - цілі числа. Причому i-е число файлу H - це номер i-го слова з файлу F у файлі G.

Вказівка. Використати масив рядків a з n елементів, у який записати всі різні слова файлу F, впорядковані за зростанням.

          8.7. Нехай файли A та B, компонентами яких є цілі числа, впорядковані з неспаданням. Отримати у файлі C всі числа з файлів A та B без повторень. Файл C повинен бути впорядкований за зростанням.

          8.8. Даний файл F, компонентами якого є цілі числа. Отримати у файлі G всі непарні числя, що входять у F. Числа у файлі G повинні йти:

а) у порядку незростання;

б) у порядку спадання без повторень.

          8.9. Даний текстовий файл F. Записати у файл G всі різні слова файлу F у порядку зростання.