Линейный поиск в массиве. Часть 2

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

Задача 1.

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

Решение.

Число А называется ближайшим к Х , если модуль разности А-Х наименьший (|A-Х|).  Если два числа будут находиться  в одинаковой близости к числу Х, будем брать любой из них. В условии так и сказано.

Когда решали задачу на нахождение максимального элемента массива, мы  задавали «точку отсчета» (назову ее так), т.е. принимали первый элемент массива за максимальный. В этой задаче мы поступим аналогично, но таких «точек отсчета» будет две: 1. минимальный модуль разности; 2. Ближайший элемент массива.

Рассмотрим код программы (Паскаль):

var x,n,i,min,raz:integer;   
mas: array[0..1000] of integer;
begin
    readln(n);
    for i:=1 to n do read(mas[i]);
    readln(x);
    raz:=ABS(mas[1]-x);    // задаем минимальное значение разности
    min:=mas[1];  //задаем ближайший элемент массива
    for i:=2 to n do
        if ABS(mas[i]-x)<=raz then
        begin
             raz:=ABS(mas[i]-x);  
             min:=mas[i];
        end;
      write(min);
end.

В программе переменная raz отвечает за минимальный модуль разности — Первая  «Точка отсчета», min — ближайший элемент массива к заданному числу X, вторая «Точка отсчета».

Если найдется такой элемент массива, начиная со второго, который окажется меньше чем «точка отсчета», переменные raz и min переопределятся.

Задача 2.

В связи с визитом Императора Палпатина было решено обновить состав дроидов в ангаре 32. Из-за кризиса было решено новых дроидов не закупать, но выкинуть пару старых. Как известно, Палпатин не переносит дроидов с маленькими серийными номерами, так что все, что требуется — найти среди них двух, у которых серийные номера наименьшие.

Формат входного файла

Первая строка входного файла содержит целое число N – количество дроидов. (2 ≤ N ≤ 1000), вторая строка – N целых чисел, по модулю не превышающих 2*109 – номера дроидов

Формат выходного файла

Выведите два числа: первым – последний по величине из номеров дроидов (такого следует утилизировать в первую очередь), а вторым – предпоследний.

Решение.

var x,n,i,min,raz,min2:integer;
mas: array[0..1000] of integer;
begin
readln(n);
for i:=1 to n do read(mas[i]);
if mas[1]<mas[2] then begin min:=mas[1]; min2:=mas[2]; end
                 else begin min:=mas[2]; min2:=mas[1]; end;
   for i:=3 to n  do begin
       if mas[i]<min then begin min2:= min; min:=mas[i]; end
                      else   mas[i]<min2 then min2:=mas[i];
       end;
       writeln(min);
       writeln(min2);
       end.

После задания массива, состоящего из n элементов, мы проверяем: первый или второй элемент массива меньше. Это и есть наша «точка отсчета». Минимальный элемент — min. Min2 — элемент, стоящий после min (по условию задачи).

Далее, в цикле от 3 до n мы проверяем: если элемент массива меньше чем min, то в переменную min2 мы записываем старое значение переменной min и переопределяем ее min:=mas[i]. Если это условие не выполняется (элемент массива больше min), мы проверим, может быть этот элемент меньше нашего второго значения min2.


1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (5 голос, значение: 2,60 из 5)
Загрузка...
Вы можете оставить комментарий, или ссылку на Ваш сайт.

Комментарии:

Продиджы слова Mindfields http://pesennik.org/Prodigy/Mindfields

Оставить комментарий

Антибот *