Обработки числовой последовательности. Задания для подготовки
i
В файле содержится последовательность натуральных чисел. Элементы последовательности могут принимать целые значения от 1 до 100 000 включительно. Определите количество пар последовательности, в которых хотя бы одно число делится на минимальный элемент последовательности, кратный 21. Гарантируется, что такой элемент в последовательности есть. В ответе запишите количество найденных пар, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два идущих подряд элемента последовательности.
Решение. Будем последовательно считывать числа из файла. Пройдём по всем числам из файла два раза. В первый проход найдём минимальный элемент последовательности, кратный 21. Во второй проход для каждой пары (двух подряд идущих элементов) будем проверять, делится ли хотя бы одно число из пары на минимальный элемент последовательности, кратный 21. При успешном выполнении условия будем увеличивать значения счётчика count и проверять, больше ли сумма элементов пары текущей максимальной суммы. Если сумма элементов пары больше текущей максимальной суммы, будем обновлять значение переменной maxsum.
Приведём решение задачи на языке Pascal.
var
x, y, count: longint;
maxsum, minelem: longint;
f: text;
begin
assign(f,'C:\17.txt');
reset(f);
minelem := 100001;
while not eof(f) do begin
readln(f, x);
if (x mod 21 = 0) and (x < minelem) then minelem := x;
end;
close(f);
reset(f);
readln(f, x);
maxsum := -20001;
count := 0;
while not eof(f) do begin
readln(f, y);
if (x mod minelem = 0) or (y mod minelem = 0) then begin
count := count + 1;
if x + y > maxsum then maxsum := x + y;
end;
x := y;
end;
writeln(count, ' ', maxsum);
end.
В результате работы данного алгоритма при вводе данных из файла ответ — 126 171120.
Примечание.
Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём решение на языке Python.
f = open("107_17.txt")
s = f.readlines()
k = 0
min = 10000000
maxi = 0
for i in range(len(s)):
s[i] = int(s[i])
for i in range(len(s)):
if s[i] % 21 == 0 and s[i] < min:
min = s[i]
for i in range(len(s) - 1):
if (s[i] % min == 0) or (s[i + 1] % min == 0):
k += 1
maxi = max(maxi, s[i] + s[i + 1])
print(k, maxi)
Приведём решение Евгений Петченко на языке Python.
f = [int(i) for i in open("17.txt")]
min_element = min(f, key=lambda x: x if x % 21 == 0 else 100_000)
result = []
for i in range(len(f) - 1):
if f[i] % min_element == 0 or f[i+1] % min_element == 0:
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем