Информатика в школе

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

Задача 1.

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке содержится одно целое число x , не превосходящее по модулю 1000. Вывести одно число – сколько раз встречается x в данном массиве.

Решение.

Инициализируем переменные и массив

var a, x, i, n:integer;  //объявляем переменные
mas: array[0..1000] of integer; // объявляем массив элементов целого типа
begin
readln(n);              //ввод количества элементов в массиве
for i:=1 to n do        // ввод значений элементов массива в количестве n штук
read(mas[i]);
readln(x);               //ввод эталонного значения
for i:=1 to n do        
      if mas[i]=x then a:=a+1;   // в цикле сравниваем каждый элемент массива с эталоном, если условие выполняется, к переменной a прибавляется 1
 writeln(a);               //выводим количество совпадений
end.

Задача 2

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке содержится одно целое число x , не превосходящее по модулю 1000.  Вывести YES , если число x встречается в данном массиве, и NO в противном случае.

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

var a, x, i, n:integer;  //объявляем переменные
mas: array[0..1000] of integer; // объявляем массив элементов целого типа
begin
readln(n);              //ввод количества элементов в массиве
for i:=1 to n do        // ввод значений элементов массива в количестве n штук
read(mas[i]);
readln(x);               //ввод эталонного значения
for i:=1 to n do
if mas[i]=x then a:=a+1
else a:=a+0;
if a=0 then writeln('NO') else writeln('YES');
end.

Зачем, скажете вы, переменная а. Почему бы не написать так:

if mas[i]=x then writeln('YES')
else writeln('NO')

Вот что мы получим при этом:

5
35578
5
NO
YES
YES
NO
YES

Команда Write будет выполняться столько раз, сколько будет выполняться цикл.

Мне кажется, что используя переменную а, решение получилось достаточно красивым. Если переменная равна нулю, значит совпадений не было, если больше нуля, значит были. Логика проста. Если есть другие варианты — пишите в комментариях.

Задача 3.

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке содержится одно целое число x , не превосходящее по модулю 1000. Вывести номера элементов, равных данному, в порядке возрастания. Если таких элементов нет, ничего выводить не нужно.

Решение

var a, x, i, n:integer; //объявляем переменные
mas: array[0..1000] of integer; // объявляем массив элементов целого типа
begin
readln(n); //ввод количества элементов в массиве
for i:=1 to n do // ввод значений элементов массива в количестве n штук
read(mas[i]);
readln(x); //ввод эталонного значения
for i:=1 to n do
if mas[i]=x then write(i, ' '); // в цикле сравниваем каждый элемент массива с эталоном, если условие выполняется, выводим индекс элемента массива с пробелом
end.

Я думаю, без комментариев.

Задача 4 (Максимальный элемент массива)

В первой строке задается одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке вводятся N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). Вывести одно число – значение максимального элемента в массиве.

Решение.

var max, i, n:integer; //объявляем переменные
mas: array[0..1000] of integer; // объявляем массив элементов целого типа
begin
readln(n); //ввод количества элементов в массиве
for i:=1 to n do // ввод значений элементов массива в количестве n штук
read(mas[i]);
max:=mas[1];  //присваиваем переменной max значение первого элемента массива
for i:=2 to n do
 if mas[i]>max then max:=mas[i]; // если найдется такой элемент массива, который больше чем max, значение max изменится на новое
writeln(max);
end.

Выделенный фрагмент — классический алгоритм поиска наибольшего значения. Алгоритм поиска наименьшего значения попробуйте составить сами.

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