Лабораторна робота № 3. Тема: Пошук елемента у масиві

Лабораторна робота № 1

Тема: Пошук елемента у масиві.

Завдання:

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

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

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

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

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

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

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

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

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

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

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

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

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

Лабораторна робота № 2

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

Завдання:

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

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

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

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

3) 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);

4) 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; 1; 1; 1; 1; 1; 1; 2);

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

6) a = (1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 4; 5; 6),
b = (1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 4; 5);

Лабораторна робота № 3

Тема: Пошук підпослідовності у послідовності. Алгоритм Кнута – Моріса – Пратта.

Завдання:

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

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

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

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

3) 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);

4) 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; 1; 1; 1; 1; 1; 1; 2);

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

6) a = (1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 4; 5; 6),
b = (1; 2; 1; 2; 3; 1; 2; 1; 2; 3; 4; 5);

Поиск по сайту: