8. ПОШУК ТА СОРТУВАННЯ
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 у порядку зростання.