Задание на L9

Лабораторная работа № 9.

Тема: «Алгоритми злиття та пошуку»

Теоретические сведения.

Поиск. Для определенности примем, что множество, в котором осуществляется поиск, задано как массив: a:array[0..n] of item;

Линейный поиск. Процедура заключается в простом последовательном просмотре всех элементов массива и сравнения их с эталоном x.

Поиск делением пополам (бинарный поиск). В большинстве случаев процедура поиска применяется к упорядоченным данным (телефонный справочник, библиотечные каталоги и пр.). В подобных ситуациях эффективным алгоритмом является поиск делением пополам. В этом методе сравнение эталона X осуществляется с элементом, расположенным в середине массива и в зависимости от результата сравнения (больше или меньше) дальнейший поиск проводится в левой или в правой половине массива.

Пример 1. Составить блок-схему нахождения в одномерном массиве из п элементов порядковых номеров максимального и минимального элементов. Значение элементов и их порядковые номера вывести на экран (рис. 1). Используеться линейный поиск.

Рис. 1. Блок-схема примера 1.

Пример 2. Бінарний пошук у впорядкованому масиві

Текст програми

#include <stdio.h>

#include <conio.h>

#include <iostream>

using namespace std;

const int N=10;

//двоичный поиск

int main()

{int L,R, m;

setlocale(LC_ALL,"Rus");

int i, key;

int A[N];

cout<<"Исходный массив: ";

for (i=0; i<N; i++) //заполнение и вывод массива

{ A[i]=N*i; cout<<A[i]<<" "; }

cout<<"\nИскомый элемент > "; cin>>key; //ввод ключа

L=0;

R=N;

while (L<R) //пока левый крайний элемент больше крайнего правого

{

m=(L+R)/2; // делим массив пополам

if (A[m]<key) //если средний элемент меньше искомого

L=m+1; //тогда берем половину справа

else //иначе

R=m; //крайним правым элементом считаем середину( берем левую половину массива)

}

if (A[R]==key)

{

cout<<" номер искомого элемента "<<key<<" равен "<<R+1;

}

else

cout<<" Элемент не найден";

getch();

}

СОДЕРЖАНИЕ ОТЧЕТА

1. Тема, краткие теоретические сведения.

2. Задание согласно варианту.

3. Блок-схема (см. лабораторную роботу №2).

4. Текст программы.

5. Результат работы программы (скриншоты).

6. Выводы.

Варианты заданий.

1. В массиве В(n) найти количество нулей и единиц.

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

3. Таблица выигрышей денежной лотереи подается в виде массива номеров, которые выиграли a₁,...,a_n и массивом выигрышей в гривнях p₁,...,p_n (p_i- это выигрыш, который выпадает на номер a_i (i=1,...,n)). Определить суммарный выигрыш, который выпадает на билет с номерами b₁,...,b_m. Для решения задачи использовать алгоритм деления пополам.

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

5. Даны действительные массивы А(n) и В(n), подсчитать количество элементов, которые принадлежат условию: А(і)>В(і).

6. Дан массив А(n), n>20. Поменять местами первые пять элементов с последними пятью элементами.

7. Задан массив Х(n) целого типа, переменной t присвоить значение true, если в массиве X нет нулевых элементов и при этом положительные элементы чередуются с отрицательными, и значение false иначе.

8. В массиве В(n), найти сумму всех положительных и произведение всех отрицательных элементов. Результат вывести на экран.

9. Задан массив А(n) символьных элементов. Заменить символы 'G' на символы 'Z' и определить сколько было замен.

10. Дан массив А(n). Уменьшить все его элементы на минимальный элемент массива.

11. Ввести одномерный массив из п элементов. Определить число различных элементов в нем.

12. В массиве В(n) подсчитать количество элементов, расположенных на непарных местах.

13. Элемент называется локальным минимумом (максимумом), если у него нет соседа, меньшего (большего), чем он сам. Найти все локальные минимумы и максимумы в заданном массиве из п элементов.

14. В массиве из п элементов выбрать без повторений все элементы, встречающиеся более одного раза.

15. Знайти мінімальний позитивний елемент масиву (N) і кількість парних елементів.

16. Превратить массив Х по следующему правилу: все отрицательные элементы массива перенести в начало, а все положительные – в конец, храня исходное взаимное расположение, как среди негативных, так и среди положительных элементов.

17. В одномерном массиве из п элементов найти порядковые номера первого отрицательного и последнего положительного элементов (если таковые имеются). Значение элементов и их порядковые номера вывести на экран или выдать соответствующее сообщение.

18. Знайти мінімальний позитивний елемент масиву(N) і кількість парних елементів.

19. Знайти номер першого парного елементу масиву(N), і кількість елементів рівних «5».

20. Знайти номер максимального парного елементу масиву(N) і кількість негативних елементів.

21. Ввести одномерный массив из п элементов. Вычислить сумму и количество всех отрицательных чисел.

22. Ввести одномерный массив из п элементов. Сформировать на его месте новый массив, в котором первым элементом будет последний элемент старого, вторым - предпоследний и т.д.

23. В неубывающей последовательности из п элементов найти количество элементов, меньших заданного числа и напечатать их, использовать алгоритм бинарного поиска.

24. Элемент называется локальным минимумом (максимумом), если у него нет соседа, меньшего (большего), чем он сам. Найти все локальные минимумы и максимумы в заданном массиве из п элементов.

25. Выполнить попарное суммирование произвольного конечного ряда чисел следующим образом. На первом этапе суммировать попарно рядом стоящие числа, на втором - результаты первого этапа аналогичным образом, и т.д., пока не останется одно число.

26. Ввести одномерный массив из п элементов. Вычислить количество и сумму всех положительных чисел.

27. Даны два вектора размерности п. Вычислить их скалярное произведение.

28. В массиве В(n) подсчитать количество элементов, равных 7-ми и количество элементов, больших 7-ми.

29. Превратить массив Х по следующему правилу: все отрицательные элементы массива перенести в начало, а все положительные – в конец, храня исходное взаимное расположение, как среди негативных, так и среди положительных элементов.

30. В одномерном массиве из п элементов найти порядковые номера первого отрицательного и последнего положительного элементов (если таковые имеются). Значение элементов и их порядковые номера вывести на экран или выдать соответствующее сообщение.