Решение задач блока ExamBegin 51-60
Решение задач из задачника по программированию М. Э. Абрамяна. Задачи из блока ExamBegin: «ЕГЭ по информатике: базовые алгоритмы».
Задача ExamBegin51
На вход в первой строке подается целое положительное число N, а во второй строке — массив из N целых чисел. Выполнив однократный просмотр массива, найти количество его минимальных элементов.
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of integer;
n, i, min, k: integer;
begin
Task('ExamBegin51');
k := 0;
Readln(n);
min := maxint;
for i := 1 to n do
begin
Read(m[i]);
if min > m[i] then
begin
min := m[i];
k := 0;
end;
if min = m[i] then k := k + 1;
end;
Write(k);
end.Задача ExamBegin52
На вход в первой строке подается целое четное положительное число N, а во второй строке — массив из N целых чисел. Группируя элементы массива по парам (первый-второй, третий-четвертый и т. д.), найти за однократный просмотр массива количество пар с максимальной суммой и вывести в первой строке максимальную сумму, а во второй строке — количество пар с этой суммой.
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of integer;
n, i, sum, max, k, l: integer;
begin
Task('ExamBegin52');
k := 0;
Readln(n);
for i := 1 to n do Read(m[i]);
max := m[1] + m[2];
for i := 1 to n div 2 do
begin
l := i * 2;
sum := m[l] + m[l - 1];
if max < sum then
begin
max := sum;
k := 0;
end;
if sum = max then k := k + 1;
end;
Writeln(max);
Writeln(k);
end.Задача ExamBegin53
На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N различных вещественных чисел. Выполнив однократный просмотр массива, найти два его наименьших элемента и вывести эти элементы в порядке возрастания их значений (каждый элемент выводить на новой строке).
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of real;
n, i: integer;
min1, min2: real;
begin
Task('ExamBegin53');
Readln(n);
for i := 1 to n do Read(m[i]);
min1 := m[1]; min2 := m[2];
for i := 1 to n do
begin
if min1 > m[i] then begin
min2 := min1;
min1 := m[i];
end;
if (min2 > m[i]) and (min1 < m[i]) then
min2 := m[i];
end;
Writeln(min1:2:2);
Writeln(min2:2:2);
end.Задача ExamBegin54
На вход в первой строке подается целое число N (> 2), а во второй строке — массив из N целых чисел, среди которых имеется не менее трех различных. Выполнив однократный просмотр массива, найти три его наибольших элемента с различными значениями и вывести эти элементы в порядке убывания их значений (каждый элемент выводить на новой строке).
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of integer;
min, max1, max2, max3, i, n: integer;
begin
Task('ExamBegin54');
Readln(n);
min := maxint;
for i := 1 to n do
begin
Read(m[i]);
if min > m[i] then min := m[i];
end;
max1 := min; max2 := min; max3 := min;
for i := 1 to n do
begin
if max1 < m[i] then begin
max3 := max2;
max2 := max1;
max1 := m[i];
end;
if (max2 < m[i]) and (max1 > m[i]) then begin
max3 := max2;
max2 := m[i];
end;
if (max3 < m[i]) and (max2 > m[i]) then
max3 := m[i];
end;
Writeln(max1);
Writeln(max2);
Writeln(max3);
end.Задача ExamBegin55
На вход в первой строке подается целое положительное число N, а во второй строке — массив из N вещественных чисел. Выполнив однократный просмотр массива, найти максимальное количество подряд идущих положительных элементов. Если положительных элементов нет, то вывести 0.
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of real;
i, n, k, max: integer;
begin
Task('ExamBegin55');
Readln(n);
k := 0; max := 0;
for i := 1 to n do
begin
Read(m[i]);
if m[i] > 0 then k := k + 1
else k := 0;
if k > max then max := k;
end;
Write(max);
end.Задача ExamBegin56
На вход в первой строке подается целое положительное число N, а во второй строке — массив из N целых чисел. Выполнив однократный просмотр массива, найти максимальное количество подряд идущих одинаковых элементов.
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of integer;
i, n, k, max: integer;
begin
Task('ExamBegin56');
Readln(n);
k := 1; max := 1;
for i := 1 to n do
Read(m[i]);
for i := 1 to n - 1 do
begin
if m[i] = m[i + 1] then k := k + 1
else k := 1;
if k > max then max := k;
end;
Write(max);
end.Задача ExamBegin57
На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N целых чисел. Рассматривая всевозможные пары элементов массива, найти минимальное расстояние между элементами (расстояние между числами x и y равно модулю их разности: |x − y|).
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of integer;
i, j, n, k, max, min: integer;
begin
Task('ExamBegin57');
Readln(n);
max := 0;
for i := 1 to n do
begin
Read(m[i]);
if max < m[i] then max := m[i];
end;
min := max; k := max;
for i := 1 to n do
for j := 1 to n do
if i <> j then begin
k := abs(m[i] - m[j]);
if k < min then min := k;
end;
Write(min);
end.Выше приведенный листинг с примером решения задачи ExamBegin57 является довольно затратным алгоритмом, основанным на переборе всех возможных пар. Но этот алгоритм можно оптимизировать. Ниже приведен более легкий алгоритм нахождения минимальной разности двух чисел. Давайте рассмотрим его.
Чтобы определить максимальную сумму, надо среди всех чисел найти самое больше число и следующее за ним. Чтобы найти максимальную разность, надо определить максимальное и минимальное число в ряде. Для минимальной суммы нам надо искать самое минимальное число и следующий за ним минимум. Казалось бы, чтобы определить минимальную разность, надо взять минимумы ряда и из одного вычесть другой. Но это будет неверным решением, потому как минимальная разность — это минимальное значение между парой чисел. И обрабатывая числовой ряд мы это значение не найдем.
В любом случае нам нужен будем массив для хранения всех значений. После чего мы этот массив отсортируем используя для этого сортировку пузырьком. Так мы получим ряд друг за другом идущих по возрастанию чисел. Затем, перебирая соседние пары будем находить их разность и искать среди нее минимальную.
С 16 по 30 строку алгоритма мы сортируем массив пузырьком. Для этого используем два цикла. Один внешний, с условием, и второй внутренний со счетчиком. Внешний цикл отвечает за количество пробежек в нашей сортировке, по этому как только мы выстроим массив мы его прерываем меняя логическую переменную check на значение false. Во внутреннем цикле мы перебираем пары элементов, и если левый элемент оказывается больше правого, то меняем их местами. Так же у нас есть счетчик j, который мы увеличиваем при каждой итерации внешнего цикла, т.к. нам нет необходимости делать проверку с крайними правыми числами. Это особенность сортировки пузырьком, т.к. после первого же прогона нашего алгоритма в самую правую ячейку попадет самое больше значение из массива. И так будет происходить при каждой итерации. Поэтому мы и смещаем правую границу при итерации вложенным циклом. Это позволит не делать нам лишние итерации цикла когда они бесполезны.
С 31 по 33 строке мы пробегаемся по массиву и выбираем соседние пары, ищем среди них разность по модулю и среди этих разностей находим самую минимальную, которую запоминаем в переменную min.
uses PT4Exam;
const
P = 100;
var
a: array[1..P] of integer;
n, i, j, t, min: integer;
check: boolean;
begin
Task('ExamBegin57');
read(n);
for i := 1 to n do
read(a[i]);
check := true;
j := 1;
while check do
begin
check := false;
for i := 1 to n - j do
if a[i] > a[i + 1] then
begin
t := a[i];
a[i] := a[i + 1];
a[i + 1] := t;
check := true;
end;
j := j + 1;
end;
min := maxint;
for i := 1 to n - 1 do
if abs(a[i] - a[i + 1]) < min then min := abs(a[i] - a[i + 1]);
write(min);
end.Задача ExamBegin58
На вход в первой строке подается целое число N (> 1), а во второй строке — массив из N вещественных чисел. Рассматривая всевозможные пары элементов массива, найти пару ближайших элементов, т. е. элементов, расстояние между которыми минимально (определение расстояния приводится в ExamBegin57). Вывести номера ближайших элементов (элементы нумеруются от 1). Каждый номер выводить на новой строке; первым выводится меньший номер. Предполагается, что в массиве имеется единственная пара ближайших элементов.
uses PT4Exam;
const
P = 100;
var
m: array[1..P] of real;
i, j, n, a, b: integer;
max, min: real;
begin
Task('ExamBegin58');
Readln(n);
max := 0;
for i := 1 to n do
begin
Read(m[i]);
if max < m[i] then max := m[i];
end;
min := max; a := 0; b := 0;
for i := 1 to n do
for j := 1 to n do
if i <> j then
if abs(m[i] - m[j]) < min then
begin
a := i; b := j;
min := abs(m[i] - m[j]);
end;
Writeln(a);
Writeln(b);
end.Задача ExamBegin59
На вход в первой строке подается целое число A, во второй строке — целые положительные числа M и N, а в последующих M строках — двумерный целочисленный массив размера M × N. Найти количество строк массива, содержащих элемент со значением A.
uses PT4Exam;
const
P = 100;
var
arr: array[1..P, 1..P] of integer;
a, m, n, i, j, k: integer;
count: boolean;
begin
Task('ExamBegin59');
Readln(a);
Readln(m, n);
k := 0; count := false;
for i := 1 to m do
begin
for j := 1 to n do
begin
Read(arr[i, j]);
if a = arr[i, j] then count := true;
end;
if count = true then k := k + 1;
count := false;
end;
Write(k);
end.Задача ExamBegin60
На вход в первой строке подаются целые положительные числа M и N, а в последующих M строках — двумерный целочисленный массив размера M × N. Найти количество столбцов массива, содержащих хотя бы одно четное число.
uses PT4Exam;
const
P = 100;
var
arr: array[1..P, 1..P] of integer;
m, n, i, j, k: integer;
count: boolean;
begin
Task('ExamBegin60');
Readln(m, n);
for i := 1 to m do
for j := 1 to n do
Read(arr[i, j]);
k := 0; count := false;
for i := 1 to n do
begin
for j := 1 to m do
if arr[j, i] mod 2 = 0 then count := true;
if count = true then k := k + 1;
count := false;
end;
Write(k);
end.
