Печатать книгуПечатать книгу

§ 12. Поиск элементов с заданными свойствами

Сайт: Профильное обучение
Курс: Информатика. 10 класс (Повышенный уровень)
Книга: § 12. Поиск элементов с заданными свойствами
Напечатано:: Гость
Дата: Четверг, 2 Май 2024, 14:34

Оглавление

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

Рассмотрим, как осуществляется поиск данных, хранящихся в массиве.

Среди разновидностей простейших задач поиска, встречающихся на практике, можно выделить следующие типы:

1. Найти хотя бы один элемент, равный заданному элементу x. В результате получают i — индекс (номер) элемента массива, такой что a[i] = x. 
2. Найти все элементы, равные заданному x. В результате получают количество таких элементов и (или) их индексы.

Иногда поиск организуется не по совпадению с элементом x, а по выполнению некоторых условий. Примером может служить поиск элементов, удовлетворяющих условию: x1 ≤ a[i] ≤ x2, где x1 и x2 заданы.

Если нет никакой дополнительной  информации о разыскиваемых данных, то самый простой подход — последовательный просмотр элементов массива.

Алгоритм, при котором для поиска нужного элемента просматривают все элементы массива, называется линейным или последовательным поиском.

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

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

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

Примером поиска в неупорядоченном наборе данных может служить поиск тетради конкретного учащегося в стопке тетрадей, сданных учащимися на проверку. Чтобы найти нужную тетрадь, возможно, придется пересмотреть все. Поиск в словаре — поиск в упорядоченном наборе данных, т. к. все слова расположены в алфавитном порядке.

12.2. Поиск одного элемента, удовлетворяющего условию поиска

Пример 12.1. Одномерный массив a состоит из n случайных натуральных чисел (все числа меньше 100). Определить, есть ли в нем хотя бы один элемент, равный x (значение x вводится).

Этапы выполнения задания

I. Исходные данные: массив a, количество чисел n, искомое число x.

II. Результат: вывод сообщения «элемент найден» или «элемент не найден».

III. Алгоритм решения задачи.

1. Ввод количества элементов и генерация элементов массива случайным образом. 
2. Логическая переменная p имеет значение «истина», если элемент в массиве найден, и «ложь» — в противном случае. До просмотра элементов массива p = false. 
3. В цикле будем просматривать все числа в массиве и сравнивать их с числом x. 
4. Поиск заканчивается при выполнении одного из двух следующих условий:

4.1. Элемент найден (p = true), т. е. в массиве есть такой элемент a[i], что a[i] = x.
4.2. Весь массив просмотрен, и совпадения не обнаружено (p = false).

5. Вывод результата.

IV. Описание переменных: n, x – int, p – bool, a – vector <int>.

Часто требуется не только определить, есть ли в массиве искомый элемент, но и установить, на каком месте он находится.

Будем хранить индекс найденного элемента в переменной k, которой до начала просмотра присвоили значение –1 (пример 12.2). После выполнения данного алгоритма по значению переменной k можно определить, есть ли в массиве искомый элемент, и, если есть, то где он стоит. Если в массиве несколько таких элементов, то в переменной k будет храниться номер последнего из них. Если такого элемента нет, то значение переменной k не изменится (k останется равным — 1).

На практике операцию поиска приходится выполнять достаточно часто, и скорость работы программы находится в прямой зависимости от используемого алгоритма поиска.

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

Для сокращения времени поиска можно останавливаться сразу после того, как элемент найден. В этом случае весь массив придется просмотреть только тогда, когда искомый элемент последний или его нет.

Если используется цикл for с условием просмотра всех элементов, то при нахождении элемента нужно прервать выполнение цикла (пример 12.3).

Можно воспользоваться циклом while. Цикл заканчивает работу, когда будет найден искомый элемент либо когда k == n , т. е. элемента, совпадающего с x, нет в массиве (пример 12.4).

При такой реализации на каждой итерации цикла требуется увеличивать индекс k и вычислять логическое выражение. Ускорить поиск можно, упростив логическое выражение. Поместим в конец массива дополнительный элемент со значением х (вектор должен быть описан из n + 1 элемента). Тогда совпадение с х обязательно произойдет, и можно не проверять условие a[k] != x. Такой вспомогательный элемент часто называют барьером или часовым, т. к. он препятствует выходу за пределы массива.

Пример 12.1.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

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

    a[i] = rand() % 100 + 1;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  bool p = false;

  ///линейный поиск элемента

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

    if (a[i] == x)

      p = true;

  }

  if (p)

    cout << "naiden";

  else

    cout << "ne naiden";

  cout << endl;

  return 0;

}

VI. Тестирование.

Пример 12.2. Фрагмент программы:

int k = -1;

///линейный поиск элемента

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

  if (a[i] == x)

    k = i;

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

 

VI. Тестирование.

Пример 12.3. Фрагмент программы:

int k = -1;

///линейный поиск элемента

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

  if (a[i] == x){

    k = i;

    break;

  }

}

if (k == -1)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Пример 12.4. Фрагмент программы:

int k = 0;

///линейный поиск элемента

while (k < n && a[k] != x)

  k++;

if (k == n)

  cout << "ne naiden";

else

  cout << "naiden na meste " << k;

cout << endl;

Пример 12.5. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n + 1);

  cout << "chisla:" << endl;

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

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  int k = 0;

  a[n] = x;

  ///линейный поиск с барьером

  while (a[k] != x)

    k++;

  if (k == n)

    cout << "ne naiden";

  else

    cout << "naiden na meste " << k;

  cout << endl;

  return 0;

}

В примере 12.5 приведена программа решения задачи из примера 12.1, в которой реализован алгоритм поиска с барьером.

12.3. Нахождение всех элементов, удовлетворяющих условию поиска

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

Пример 12.6. Задан одномерный массив из n чисел. Определить количества элементов, кратных x в этом массиве.

Этапы выполнения задания

I. Исходные данные: массив a, количество чисел n, искомое число x.

II. Результат: количество элементов, удовлетворяющих условию — k.

III. Алгоритм решения задачи.Описание переменных: n, x, k – int, a – vector <int>.

1. Зададим числа случайно на [0; 100).
2. Инициализация счетчика.
3. В цикле будем просматривать все числа в массиве и сравнивать с нулем их остатки от деления на число x. Если остаток равен нулю, то счетчик увеличиваем на 1.

IV. Вывод результата.

Если необходимо не только посчитать, сколько элементов удовлетворяют условию, но и сохранить индексы таких элементов, то для этого можно воспользоваться дополнительным массивом. Создадим новый массив b. Как только будет найден необходимый элемент, его индекс будет заноситься в массив b. Количество элементов в массиве b заранее не известно. Поэтому опишем массив b как вектор без размера:

vector <int> b;

В этом случае для добавления элементов в конец вектора используется функция push_back(i). Вектор является динамическим типом данных, поэтому перед тем как добавить элемент в конец вектора, будет выделена память для его размещения. Если к элементу вектора b обратиться по индексу до того, как добавили элемент с помощью функции push_back, то получим ошибку времени выполнения, поскольку для размещения элемента не выделена память. Для того чтобы узнать количество элементов в массиве, можно воспользоваться функцией size(). Чтобы узнать, на каких позициях найдены числа, кратные x, необходимо вывести элементы массива b (пример 12.7).

Пример 12.6.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

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

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  int k = 0;

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

    if (a[i] % x == 0)

      k++;

  }

  cout << "naideno " << k;

  cout << " elementov" << endl;

  return 0;

}

VI. Тестирование.

VII. Анализ результатов. В первом случае кратными двум будут числа 34, 18, 82, 30, 24. Во втором случае — в массиве нет чисел, кратных 13.

Пример 12.7.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdlib>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

  cout << "chisla:" << endl;

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

    a[i] = rand() % 100;

    cout << a[i] << " ";

  }

  cout << endl;

  int x;

  cout << "x = ";

  cin >> x;

  vector <int> b;

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

    if (a[i] % x == 0)

      b.push_back(i);

  int k = b.size();

  cout << "naideno " << k;

  cout << " elementov" << endl;

  if (k) {

    cout << "ih pozicii:" << endl;

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

      cout << b[i] << " ";

    cout << endl;

  }

  return 0;

}

VI. Тестирование.

12.4. Решение задач с использованием алгоритма линейного поиска

Пример 12.8. На складе хранятся пустые ящики для упаковки товара. Известно, что вместимость одного пакета с конфетами x кг. Какова суммарная масса пакетов с конфетами, которые можно упаковать в такие ящики, заполнив ящик целиком?

Этапы выполнения задания

I. Исходные данные: массив а, количество чисел n, число x.

II. Результат: количество ящиков — k, суммарная масса — s.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика и значения суммы:
k = 0; s = 0;
3. Просматривая массив, проверим, является ли текущий элемент числом, кратным x (в этом случае ящик будет заполнен целиком). Если кратен, то  увеличим счетчик k на 1, а переменную s — на значение найденного элемента массива.
4.  Вывод результата.

IV. Описание переменных: n, x, k — int, a – vector <int>.

Пример 12.9. Имеется список мальчиков 10 В класса и результаты их бега на 100 м. Для сдачи норматива необходимо пробежать дистанцию не более чем за 16 с. Вывести фамилии учащихся, которые не выполнили норматив по бегу. Сколько таких учащихся в классе? Исходные данные хранятся в текстовом файле input.txt. Результат вывести в текстовый файл output.txt.

Этапы выполнения задания

Исходные данные: массивы fam (фамилии учащихся) и r (результаты бега в секундах), количество учащихся n.

II. Результат: фамилии тех учащихся, которые не выполнили норматив по бегу.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k = 0;
3. Будем просматривать массив с результатами и проверять, является ли текущий элемент числом, большим 16 (норматив не сдан). Если такое значение найдено, то выведем элемент массива fam с соответствующим номером и увеличим значение счетчика на 1.
4. Вывод значения счетчика.

IV. Описание переменных:  
n, k – int, r – vector <double>,
fam – vector <string>.

Пример 12.10. В двух линейных массивах x и y, заданных случайным образом, хранятся координаты точек плоскости (–200 ≤ x[i], y[i] ≤ 200). Определить, каких точек больше — лежащих внутри или снаружи области, ограниченной окружностью радиуса r, с центром в начале координат (будем считать, что точки, лежащие на окружности, лежат внутри области).

Этапы выполнения задания

I. Исходные данные: x, y — массивы чисел, r — радиус окружности, n — количество точек.

II. Результат — одно из сообщений: «внутри точек больше», «снаружи точек больше» или «точек поровну».

III. Алгоритм решения задачи.

1. Ввод исходных данных. 
2. Инициализация счетчиков: k1 = 0; k2 = 0; 
3. Будем просматривать все точки и для каждой проверять принадлежность области. Если x2 + y2 ≤ R2, то точка лежит внутри области, тогда увеличим значение счетчика k1 на 1, если нет, то увеличим на 1 значение счетчика k2. 
4. Сравним значения k1 и k2 и выведем результат.

IV. Описание переменных: n, k1, k2 — int, x, y – vector <int>.

Пример 12.11. Задан одномерный массив из n целых чисел. Определить количества элементов, которые являются числами Смита. Вывести те элементы, которые являются числами Смита. (Число Смита — такое составное число, сумма цифр которого равна сумме цифр всех его простых сомножителей.) Например, числом Смита является 202 = 2  × 101, поскольку 2 + 0 + 2 = 4 и 2 + 1 + 0 + 1 = 4.

Этапы выполнения задания

I. Исходные данные: а — массив чисел, n — количество чисел в массиве.

II. Результат: числа Смита и их количество в массиве.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k = 0;
3. Будем просматривать каждый элемент массива и определять, является ли он числом Смита. Для проверки создадим функцию check, которая будет получать в качестве параметра элемент массива, а также возвращать значение true, если число является числом Смита, и false в противном случае.

3.1. Найдем сумму цифр числа.
3.2. Будем разлагать число на простые множители и для каждого множителя находить сумму цифр. 
3.3. Для разложения числа на простые множители будем делить его сначала на 2 (пока делится), затем на 3. На 4 число уже делиться не будет, будем делить на 5 и т. д. Закончится разложение тогда, когда после всех делений число станет равным 1.

4. Также нам понадобится функция sum, которая для числа будет возвращать его сумму цифр. 

IV. Описание переменных:
n, k – int, a – vector <int>.

Пример 12.12. Задан одномерный массив из n строк. Данные в массиве читаются из текстового файла input.txt. Каждая строка является предложением из слов, разделенных пробелами. Найти и вывести в текстовый файл output.txt те предложения, в которых нечетное количество слов. Сколько предложений вывели?

Этапы выполнения задания

I. Исходные данные: а — массив строк, n — количество строк в массиве.

II. Результат: искомые строки и их количество.

III. Алгоритм решения задачи.

1. Ввод исходных данных.
2. Инициализация счетчика: k = 0;
3. Будем просматривать каждую строку и определять, сколько в ней слов. Для проверки создадим функцию check, которая будет получать в качестве параметра элемент массива и возвращать количество слов в строке. Если количество слов является нечетным числом, то выведем строку и увеличим значение счетчика.

3.1. Перед каждым словом предложения, кроме первого, стоит пробел. Слово начинается с символа, который пробелом не является. 
3.2. Добавим пробел перед первым словом, тогда количество слов будет определяться количеством сочетаний пар символов: пробел и не пробел.

IV. Описание переменных:
n, k – int, а – vector <string>.

Пример 12.8.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int main()

{

  setlocale(0,"");

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int x;

  cout << "масса конфет ";

  cin >> x;

  int s = 0, k = 0;

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

    if (a[i] % x == 0){

      k++;

      s += a[i];

    }

  cout << "упаковали " << k;

  cout << " ящиков, масса ";

  cout << s << " кг" << endl;

  return 0;

}

VI. Тестирование.

VII. Анализ результатов. Ящики, удовлетворяющие условию задачи, имеют массу 15, 25, 10, 20, 45.

Пример 12.9.

V. Программа:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

 

using namespace std;

 

int main()

{

  ifstream fin ("input.txt");

  ofstream fout ("output.txt");

  int n;

  fin >> n;

  fin.ignore (); 

  vector <string> fam(n);

  vector <double> r(n);

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

    fin >> fam[i] >> r[i];

  int k = 0;

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

    if (r[i] > 16){

      fout << fam[i] << endl;

      k ++;

    }

  fout << "не сдали норматив ";

  fout << k << " учащихся" << endl;

  return 0;

}

VI. Тестирование.

 

VII. Анализ результатов. Результат Сидорова 21, а Королева 16.1, что превышает норматив.

Пример 12.10.

V. Программа:

#include <iostream>

#include <vector>

#include <ctime>

#include <cstdio>

 

using namespace std;

 

int main()

{

  srand(time(NULL));

  int n, r;

  cout << "n = ";

  cin >> n;

  cout << "r = ";

  cin >> r;

  vector <int> x(n), y(n);

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

    x[i] = rand() % 401 - 200;

    y[i] = rand() % 401 - 200;

  }

  int k1 = 0, k2 = 0;

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

    if (x[i] * x[i] + y[i] * y[i] 
        <= r * r)

      k1++;

    else

      k2++;

  if (k1 > k2)

    cout << "vnutri";

  else

    if (k1 < k2)

      cout << "snarugi";

    else

      cout << "porovnu";

  cout << endl;

  return 0;

}

VI. Тестирование.

VII. Анализ результатов. По сообщениям, которые выдает программа, сложно судить о ее правильности. Для проверки можно вывести значения координат каждой точки в файл и при проверке ставить дополнительные пометки. Например, «+», если точка внутри, и «-», если снаружи.

Пример 12.11.

V. Программа:

#include <iostream>

#include <vector>

 

using namespace std;

 

int sum(int x)

{

  int s = 0;

  while (x >0){

    s += x % 10;

    x /= 10;

  }

  return s;

}

 

bool check(int x)

{

  int s1 = sum(x);

  int s2 = 0;

  int d = 2;

  //разложение на простые множители

  while (x != 1){

    while (x % d == 0){

      s2 += sum(d);

      x /= d;

    }

    d++;

  }

  return (s1 == s2);

}

 

int main()

{

  int n;

  cout << "n = ";

  cin >> n;

  vector <int> a(n);

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

    cin >> a[i];

  int k = 0;

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

    if (check(a[i])){

      k++;

      cout << a[i] << " ";

  }

  cout << endl << "vsego " << k;

  cout << " chisel Smita" << endl;

  return 0;

}

VI. Тестирование.

Пример 12.12.

V. Программа:

#include <iostream>

#include <fstream>

#include <vector>

#include <string>

#include <windows.h>

 

using namespace std;

using namespace std::__cxx11;

 

int check(string x)

{

  int k = 0;

  x = " " + x;

  int len = x.length();

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

    if (x[i] == ' ' && x[i + 1] != ' ')

      k++;

  return k;

}

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  ifstream fin("input.txt");

  ofstream fout("output.txt");

  int n;

  fin >> n;

  fin.ignore();

  vector <string> a(n);

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

    getline(fin, a[i]);

  int k = 0;

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

    if (check(a[i]) % 2){

      fout << a[i] << endl;

      k++;

    }

  fout << "Всего - " << k;

  fout << " строк(–а, –u)" << endl;

  return 0;

}

VI. Тестирование.

 

Вопросы к параграфу

1. Что называют последовательным поиском?

2. Как определить, что в массиве был найден элемент с определенными свойствами?

3. Для чего используют переменные-счетчики?

4. Что такое инициализация переменной?

Упражнения

    

1. Рост учащихся класса представлен в виде массива. Напишите программу, которая определит количество учащихся, рост которых больше среднего роста по классу.

2. Заданы фамилии и рост учащихся 10-го класса. Напишите программу, которая выведет фамилии учащихся, рост которых меньше среднего роста по классу.

3. Известны данные о площади n стран (в млн кв. км) и численности населения (в млн). Напишите программу, которая выведет номера тех стран, плотность населения в которых больше x.

4. Для упражнения 3 добавьте возможность вводить и выводить названия стран из текстового файла.

5. Напишите программу, которая определит, есть ли в линейном массиве хотя бы один элемент, который удовлетворяет указанному ниже свойству. Если да, то выведите его номер.

1. Является положительным числом. 
2. Является четным числом. 
3. Является нечетным, кратным 7 числом.  
4. При делении на 7 дает в остатке 1, 2 или 3.

6. Написать программу, которая посчитает количество элементов массива, удовлетворяющих свойствам, описанным в упражнении 5.

7. Напишите программу, которая найдет в линейном массиве и выведет все простые числа с нечетной суммой цифр. Указать, сколько чисел вывели.

8. В примере 7.15 рассматривалась рекурсивная функция для разложения числа на простые множители. Измените функцию check в примере 12.11 на рекурсивную по аналогии с функцией из примера 7.15.

9. Написать программу, которая посчитает количество пар соседних (номера таких элементов отличаются на 1) элементов массива, удовлетворяющих указанному ниже свойству:

1. Оба числа в паре являются положительными.
2. Числа в паре имеют разные знаки.
3. Ни одно число из пары не равно нулю.
4. Числа имеют одинаковую четность (или оба четные, или оба нечетные).

10. Напишите программу, которая найдет в линейном массиве и выведет все числа Армстронга. Числом Армстронга называется такое число, которое равно сумме своих цифр, возведенных в степень, равную количеству его цифр. Например, числом Армстронга является число 371 = 33 + 73 + 13 = 27 + 343 + 1. Указать, сколько чисел вывели.

11. Задан одномерный массив из N строк. Каждая строка является предложением из слов, разделенных пробелами. Напишите программу, которая найдет и выведет те предложения, в которых есть слова, начинающиеся на гласную букву (строчную или прописную). Исходные данные прочитать из текстового файла input.txt. Результат записать в текстовый файл output.txt.