Задачи на поиск в массиве

Линейный поиск

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

 

Начиная с первого, все элементы массива последовательно просматриваются и сравниваются с искомым значением. Если на каком-то шаге текущий элемент окажется равным искомому, тогда элемент считается найденным, и в качестве результата возвращается номер этого элемента, либо другая информация о нем.Иначе, следуют возвратить что-то, что может оповестить о его отсутствии в пройденной последовательности.

// заполнение массива a из n целочисленных элементов

// ...

int key, found = 0;

cin >> key;                     // искомое значение

for(int i = 0; i<n && !found; i++) // искать пока не нашли до конца

if (a[i] == key) found = i + 1;

if (!found) cout << "Значение не найдено";

else cout << "Номер элемента" << found;

// ...

Бинарный поиск

Бинарный (двоичный) поиск необходимо производить в предварительно отсортированном массиве. Находится средний элемент массива и сравнивается с искомым значением. Если они равны, то поиск завершен, если искомое значение меньше значения среднего элемента, то дальнейший поиск производится в левой половине массива, иначе – в правой. Алгоритм поиска:

1. Определить средний элемент массива

2. Если его значение равно искомому, значит элемент найден. Перейдем к шагу 6

3. Если количество элементов массива равно 1, значит элемент не найден. Перейдем к шагу 6

4. Если искомое значение меньше значения среднего элемента, то возьмем в качестве массива все элементы слева от среднего и перейдем к шагу 1

5. возьмем в качестве массива все элементы справа от среднего и перейдем к шагу 1

6. Конец

Это достаточно эффективный метод поиска. Так в массиве на 32767 элементов потребуется произвести всего не более 15 проверок.

// заполнение массива a из n целочисленных элементов

// ...

int key, left = 0, right = n - 1, mid, found = 0;

cin >> key;                     // искомое значение

while (left<=right && !found){

mid = (left + right) / 2;

if (key < a[mid]) right = mid - 1;

else if (key > a[mid]) left = mid + 1;

     else found = mid + 1;

}

if (!found) cout << "Значение не найдено";

else cout << "Номер элемента" << found;

// ...

Задача №95. Замена повторяющихся

С консоли вводится неупорядоченный набор целых чисел. Замените все повторяющиеся числа нулями.

Входные данные

В первой строке записано число N – количество чисел в наборе (N ≤ 100). Во второй строке записаны через пробел N целых чисел, каждое из которых не превышает по модулю 10⁹.

Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

Выходные данные

Вывести те же числа, разделенные пробелом, заменив все не уникальные (повторяющиеся) значения нулями.

Пример

Ввод	Вывод
12 1 3 15 -2 67 1 14 1 -2 68 67 4	0 3 15 0 0 0 14 0 0 68 0 4

Решение

Идея решения состоит в следующем – запишем все числа в массив. Для каждого элемента массива признак того, что найден равный ему другой элемент массива обозначим с помощью логической переменной found. Затем будем проверять элементы из оставшейся части. Если проверяемый элемент окажется равен текущему, запишем в него 0. Так же поступим с текущим элементом в конце, если переменная found примет значение ИСТИНА.

#include <iostream>

using namespace std;

int main(){

int n, a[100];

cin >> n;

for(int i = 0; i < n; i++)

     cin >> a[i];

bool found;

for(int i = 0; i < n - 1; i++){

     found = false;

     for(int j = i + 1; j < n; j++){

           if(a[i] == a[j]) found = true;

     if(a[i] == a[j] && found) a[j] = 0;

     }

     if (found) a[i] = 0;

     cout << a[i] << ' ';

}

return 0;

}

Задача №96. Модуль суммы (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

Дана последовательность целых чисел. Требуется найти подпоследовательность заданной последовательности с максимальным модулем суммы входящих в нее чисел. Напомним, что модуль целого числа x равняется x, если x ≥ 0 и -x, если x < 0.

Входные данные

Первая строка содержит натуральное число n (1 ≤ n ≤ 10000) - длину последовательности. Во второй строке записаны n целых чисел, по модулю не превосходящих 10000.

Выходные данные

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

Пример

Ввод	Вывод
5 -1  4  -1  6  -7	2 2  4

Решение

Очевидно, что максимальная по модулю суммы подпоследовательность должна содержать элементы одного знака. Таким образом, нам необходимо определить, сумма каких чисел больше – положительных или отрицательных. Для самих элементов будем запоминать в ячейку массива 1 для положительных, -1 – для отрицательных и 0 – для нулевых элементов.

#include <iostream>

using namespace std;

int n, a[10000], s, x, i, t, p, q;

int main() {

cin >> n;

while(i < n){         // считываем элементы

   cin >> t;         // и находим в x сумму положительных

   s += t;           // элементов, в p – их количество

   if (t > 0) {      // в q – количество отрицательных

       x += t;       // в s – сумму всех

       t = 1;

       p++;

   } else

       if (t < 0) {

           t = -1;

           q++;

       }

   a[i++] = t;

}

if(x - s > x) {       // определяем, какая сумма больше

   x = s - x;

   p = q;

}

cout << p << endl;

for(i = 0; i < n; i++)

   if(a[i] * x > 0)

       cout << i + 1 << ' ';

}

Задача №97. Выборы жрецов (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

В стране Олимпиадии снова выборы.

Страна состоит из маленьких графств. Графства объединяются в конфедерации. Каждая конфедерация раз в год выбирает себе покровителя – одного из 200 жрецов. Этот ритуал называется Великими Перевыборами Жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфедерация хочет оставить себе того же покровителя). После этого все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыборов. В Совете все графства занумерованы (начиная с 1). Все Жрецы занумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ничьими покровителями).

Входные данные

В первой строке записано число N – количество графств в стране (1 ≤ N ≤ 5000) – и далее для каждого графства записан номер Жреца-покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число M – количество поданных заявлений, а затем M пар чисел (1 ≤ M ≤ 200): первое число – номер текущего Жреца-покровителя, второе – номер желаемого Жреца-покровителя.

Все числа во входных данных разделяются пробелами и (или) символами перевода строки.

Выходные данные

Вывести для каждого графства одно число – номер его Жреца-покровителя после Великих Перевыборов. Сначала – для первого графства, затем – для второго и т.д.

Пример

Ввод	Вывод
7 1  1  5  3  1  5  1 2 5 1 1  3	3  3  1  3  3  1  3

Решение

Первое «лобовое» решение, которое обычно приходит в голову для данной задачи – это сохранить заявки на замену жрецов в виде двух массивов b1 и b2 –номера старого и нового жреца. Для каждого графства его текущий жрец сохранён в массив a.

#include <iostream>

using namespace std;

int n, a[5000], m, b1[200], b2[200], i, j;

 

int main(){

cin >> n;

for(i = 0; i < n; i++)

     cin >> a[i];

 

cin >> m;

for (i = 0; i < m; i++)

     cin >> b1[i] >> b2[i];

 

for (i = 0; i < n; i++){

     for(j = 0; j < m; j++)

           if (b1[j]==a[i]) {a[i] = b2[j]; break;}

     cout << a[i] << ' ';

}

}

Этот алгоритм крайне неэффективен, поскольку мы для каждого графства делаем вложенный цикл по всем заявкам, проверяя, был ли заменён текущий жрец. Кроме того, мы используем лишний массив, без которого вполне можно обойтись. В итоге, алгоритм неэффективен ни по времени, ни по используемой памяти. Вместо двух массивов b1_i и b2_i, определяющих пару жрецов для замены, заведём один массив b_i который будет определять, что жрец номер i меняется на жреца b_i. Такой массив в котором хранятся пары «ключ-значение» называется ассоциативным. Если заявки на замену жреца i не было, то b[i] останется равным 0.

#include <iostream>

using namespace std;

int n, m, a[5000], b[201] = {0,}, i;

 

int main(){

cin >> n;

for(i = 0; i < n; i++)

cin >> a[i];

cin >> m;

while(m--){

     cin >> i;

     cin >> b[i];

}

for (i = 0; i < n; i++)

     cout << (b[a[i]] ? b[a[i]] : a[i]) << ' ';

}

Простые сортировки