Линейный поиск в массиве. Часть 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.

Вы можете оставить комментарий, или ссылку на Ваш сайт.
Продиджы слова Mindfields http://pesennik.org/Prodigy/Mindfields

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

Антибот *