Контрольна робота Алгоритм прямого пошуку підпослідовності – Варіант №10

« Назад

Задача № 1. Тема: Пошук елемента у масиві

Завдання:

1. Користуючись методом прямого пошуку елемента у масиві, встановити перше входження деякого елемента. Якщо елемент із шуканим значенням є, то вказати його порядковий індекс, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.

2. Користуючись методом модифікованого прямого пошуку елемента у масиві, встановити перше входження деякого елемента. Якщо елемент із шуканим значенням є, то вказати його порядковий індекс, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.

3. Користуючись методом бінарного пошуку елемента у впорядкованому масиві, встановити входження деякого елемента. Якщо елемент із шуканим значенням є, то вказати його порядковий індекс, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.

4. Користуючись методом модифікованого бінарного пошуку елемента у впорядкованому масиві, встановити входження деякого елемента. Якщо елемент із шуканим значенням є, то вказати його порядковий індекс, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.

При аналізі складності різних алгоритмів пошуку елемента у масиві розглянути наступні варіанти вхідних даних:

a = ( 1; 2; 3; 4; 5; 6; 7; 8; 9; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20), x = 0.

Задача № 2. Тема: Пошук підпослідовності у послідовності. Алгоритм прямого пошуку підпослідовності

Завдання:

1. Користуючись методом прямого пошуку підпослідовності у послідовності, встановити входження деякого образу у базовий рядок. Якщо співпадання має місце, то вказати порядковий індекс елемента в базі, починаючи з якого образ повністю співпадає з елементами бази, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.

При аналізі складності різних алгоритмів пошуку підпослідовності у послідовності розглянути наступні варіанти вхідних даних:

a = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2),
b = (1; 1; 1; 1; 1; 1; 1; 1; 2).

Задача № 3. Тема: Прямі алгоритми сортування масивів. Сортування вибором

Завдання:

1. Користуючись методом прямого вибору сортування масивів, впорядкувати заданий набір елементів по зростанню (спаданню). Визначити кількість важких операцій порівняння та переприсвоєння, що виконуються при цьому.

При аналізі складності різних алгоритмів сортування розглянути наступні варіанти вхідних даних:

три випадки довжини структури даних (N=100 – „короткий масив”, N=1000 – „середній масив”, N=10000 – „довгий масив”).

Задача № 4. Тема: Прямі алгоритми сортування масивів. Сортування обміном

Завдання:

1. Користуючись методом прямого обміну (“бульбашка”, “камінець”) сортування масивів, впорядкувати заданий набір елементів по зростанню (спаданню). Визначити кількість важких операцій порівняння та переприсвоєння, що виконуються при цьому.

2. Користуючись модифікованим методом прямого обміну – “шейкерним” сортуванням масивів, впорядкувати заданий набір елементів по зростанню (спаданню). Визначити кількість важких операцій порівняння та переприсвоєння, що виконуються при цьому.

При аналізі складності різних алгоритмів сортування розглянути наступні варіанти вхідних даних:

три випадки початкового порядку елементів (прямо впорядкований, обернено впорядкований, довільний).