Одним из самых частых алгоритмов, которые используются в программировании — это поиск максимального и минимального элементов в потоковом получении данных(когда данные появляются друг за другом, например, с помощью цикла).
11 010 просмотров
Здесь необходимо выделить 2 случая:
— когда Вы знаете диапазон чисел, который будет приходить(например, строго трёхзначные, то есть от 100 до 999 или строго записанный диапазон от числа а до числа b);
— когда Вы не знаете диапазон чисел, который будет к вам приходить;
Рассмотрим первый случай, то есть когда вы знаете диапазон чисел:
В Этом случае вы должны перед получением данных в переменную, отвечающую за поиск минимума положить верхнюю границу диапазона, а в переменную, отвечающую за поиск максимума положить нижнюю границу диапазон, после чего в цикле просто обрабатывать числа по стандартному правилу нахождения наибольшего и наименьшего из двух.
При использовании такого алгоритма ваши максимум и минимум сменятся на адекватные значения, которые по окончанию работы цикла и будут действительным максимумом и минимумом.
Стрим №20. Программирование. Задание 17. ЕГЭ по информатике 2023
Рассмотрим второй случай, когда диапазон неизвестен:
Алгоритм точно такой же за исключением того, что первоначально в минимум кладётся самое наибольшее число из используемого типа данных, а в максимум самое наименьшее число из используемого типа данных.
Границы типов данных можно найти в другой моей статье:
Пример программы по поиску минимального и максимального целого числа числа при неизвестном диапазоне:
int min = INT_MAX; //константа наибольшего числа в int
int max = INT_MIN; //константа наименьшего числа в int
int val;
Источник: vc.ru
Найти сумму элементов между минимальным и максимальным элементами массива
В одномерном массиве найти сумму элементов, находящихся между минимальным и максимальным элементами. Сами минимальный и максимальный элементы в сумму не включать.
- Сначала надо найти минимальный и максимальный элементы массива. Это можно сделать в цикле заполнения массива. Причем лучше запоминать в переменных не сами значения элементов, а их индексы.
- Поскольку неизвестно, какой из элементов (минимальный или максимальный) встречается в массиве раньше, то неизвестно, как в последующем делать перебор участка массива: от начала этого участка к его концу или от конца к началу. Данную проблему можно решить путем обмена значений переменных, если, например, переменная, содержащая индекс минимума, окажется больше содержащей индекс максимума.
- До подсчета суммы элементов, находящихся между минимумом и максимумом, следует переменной (например, sum) присвоить 0. Далее перебираем в цикле for массив от следующего за минимумом элемента до элемента предшествующего максимуму. Для этого к первой переменной прибавляем 1, а из второй вычитаем 1. В теле цикла к значению sum добавляем значение текущего элемента массива.
Примечание. Если минимумов или максимумов оказывается несколько, то программа находит сумму только между первыми из них.
Задание 27 (Подпоследовательности) // ЕГЭ по информатике 2022
Pascal
const
N = 10;
var
arr: array[1..N] of integer;
i, min, max: byte;
sum: integer;
begin
randomize;
for i := 1 to N do begin
arr[i] := random(50);
write (arr[i]:3);
end;
writeln;
min := 1;
max := 1;
for i := 2 to N do begin
if arr[i] < arr[min] then min := i else
if arr[i] > arr[max] then max := i;
end;
writeln(arr[min],’ ‘,arr[max]);
if min > max then begin
i := min;
min := max;
max := i;
end;
sum := 0;
for i:=min+1 to max-1 do begin
sum := sum + arr[i]
end;
writeln(sum);
end.
25 20 20 20 24 48 40 24 46 16
16 48
110
Язык Си
#include
#define N 10
main() int a[N], i, min, max, sum;
srand(time(NULL));
for (i=0; i < N; i++) a[i] = rand()%50;
printf(«%3d», a[i]);
>
printf(«n»);
min = 0;
max = 0;
for (i=1; i < N; i++) if (a[i] < a[min]) min = i;
else if (a[i] > a[max]) max = i;
>
printf(«%3d, %3dn», a[min], a[max]);
if (min > max) i = min;
min = max;
max = i;
>
sum = 0;
for (i=min+1; i < max; i++)
sum += a[i];
printf(«%4dn», sum);
>
39 21 12 14 24 37 33 46 38 22
12, 46
108
Python
from random import random
N = 10
a = [0]*N
for i in range(N):
a[i] = int(random()*50)
print(‘%3d’ % a[i], end=»)
print()
min_id = 0
max_id = 0
for i in range(1,N):
if a[i] < a[min_id]:
min_id = i
elif a[i] > a[max_id]:
max_id = i
print(a[min_id], a[max_id])
if min_id > max_id:
min_id, max_id = max_id, min_id
summa = 0
for i in range(min_id+1, max_id):
summa += a[i]
print(summa)
10 5 8 14 16 42 18 33 2 32
2 42
51
Поиск индексов минимального и максимального элементов можно было выполнить так:
min_id = a.index(min(a))
max_id = a.index(max(a))
Здесь встроенные функции min() и max() языка Python находят соответственно минимальный и максимальный элементы списка. А метод списка index() определяет индекс (номер) переданного в качестве аргумента элемента.
КуМир
алг сумма между
нач
цел N = 10
цел таб arr[1:N]
цел i, mini, maxi, sum
нц для i от 1 до N
arr[i] := irand(0,50)
вывод arr[i]:3
кц
вывод нс
mini := 1
maxi := 1
нц для i от 2 до N
если arr[i] < arr[mini] то
mini := i
иначе
если arr[i] > arr[maxi] то
maxi := i
все
все
кц
вывод arr[mini]:3, arr[maxi]:3, нс
если mini > maxi то
i := mini
mini := maxi
maxi := i
все
sum := 0
нц для i от mini+1 до maxi-1
sum := sum + arr[i]
кц
вывод sum, нс
кон
26 6 35 35 36 25 39 22 5 1
1 39
27
Basic-256
N = 10
dim arr(N)
for i=0 to N-1
arr[i] = int(rand()*50)
print arr[i] + » «;
next i
print
min = 0
max = 0
for i=1 to N-1
if arr[i] < arr[min] then min = i
if arr[i] > arr[max] then max = i
next i
print arr[min] + » » + arr[max]
if min > max then
i = min
min = max
max = i
endif
sum = 0
for i=min+1 to max-1
sum = sum + arr[i]
next i
print sum
28 16 16 33 32 17 1 17 3 17
1 33
49
Источник: gospodaretsva.com
Информатика 11 класс пробный вариант №9 решу ЕГЭ 2022 задания с ответами
1)На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице звёздочками обозначено наличие дорог. Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Найдите номера пунктов F и H. В качестве ответа запишите найденные номера в порядке убывания без разделителей.
Ответ: 63
2)Логическая функция F задаётся выражением a ≡ b ∨ b → c. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c.
Ответ: bca
Ответ: 1897
4)По каналу связи передаются сообщения, содержащие только шесть букв: А, В, Г, У, С, Т; для передачи используется двоичный код, удовлетворяющий условию Фано. Буквы Т, У, С, А имеют коды 10, 000, 11, 001 соответственно. Укажите наименьшую возможную длину закодированной последовательности для слова СУСТАВ.
Ответ: 15
Ответ: 176
6)Определите наименьшее и наибольшее введённое значение переменной s, при котором программа выведет число 56. В ответ запишите оба числа в порядке возрастания без пробелов и других разделителей.
Ответ: 2427
7)Какой минимальный объём памяти (целое число Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 1104×542 пикселей при условии, что в изображении могут использоваться 128 различных цветов? В ответе запишите только целое число, единицу измерения писать не нужно.
Ответ: 512
8)Все 5-буквенные слова, составленные из букв А, З, Н, С, записаны в алфавитном порядке и пронумерованы. Вот начало списка: 1. ААААА 2. ААААЗ 3. ААААН 4. ААААС 5. АААЗА … Какое количество слов находятся между словами САЗАН и ЗАНАС (включая эти слова)?
Ответ: 496
Ответ: 1033
Ответ: 3
11)Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код, состоящий из двух частей. Первая часть кода содержит 10 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода содержит 8 символов, каждый из которых может быть одной из десятичных цифр.
При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для этой части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 60 пользователях потребовалось 1980 байт. Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число – количество байтов.
Ответ: 22
12)Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов. 1. заменить (v, w) 2. нашлось (v) Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку.
Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Дана программа для исполнителя Редактор: НАЧАЛО ПОКА нашлось(01) ИЛИ нашлось(02) ИЛИ нашлось(03) заменить(01, 302) заменить(02, 3103) заменить(03, 20) КОНЕЦ ПОКА КОНЕЦ Известно, что исходная строка начиналась с нуля, а далее содержала только единицы, двойки и тройки. После выполнения данной программы получилась строка, содержащая 28 единиц, 34 двойки и 45 троек. Сколько единиц было в исходной строке?
Ответ: 17
13)На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует маршрутов из А в К?
Ответ: 24
14)Значение выражения 5∙2161256 – 5∙361146 + 4∙61053 – 1087 записали в системе счисления с основанием 6. Найдите сумму цифр получившегося числа и запишите её в ответе в десятичной системе счисления.
Ответ: 12642
15)На числовой прямой даны два отрезка: P=[2,10] и Q=[6,14]. Какова максимальная длина отрезка A, при выборе которого формула ((x ∈ А) → (x ∈ P)) ∨ (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
Ответ: 12
Ответ: 5101
17)В файле 17-10.txt содержится последовательность целых чисел. Элементы последовательности могут принимать значения от 0 до 10000 включительно. Определите сначала количество троек элементов последовательности, из которых можно составить прямоугольный треугольник, а затем сумму всех гипотенуз треугольников в подходящих тройках. Под тройкой подразумевается три идущих подряд элемента последовательности.
Ответ: 370 209813
Ответ: 1536 666
22)Ниже записана программа, которая вводит натуральное число x, выполняет преобразования, а затем выводит результат. Укажите наименьшее значение x, при вводе которого программа выведет число 45.
Ответ: 106
23)Исполнитель Калькулятор преобразует число, записанное на экране в троичной системе счисления. У исполнителя есть две команды, которым присвоены номера: 1. Умножь на 2 2. Умножь на 2 и прибавь 1 Сколько различных результатов можно получить из исходного числа 1 после выполнения программы, содержащей ровно 15 команд?
Ответ: 32768
24)Текстовый файл 24-171.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Файл разбит на строки различной длины. Определите максимальную длину цепочки символов, состоящей из повторяющихся фрагментов XYZ. Цепочка должна начинаться с символа X и заканчиваться символом Z. Например, для строки SAZZXYZXYZXZQW длина цепочки равна 6: XYZ+XYZ.
Ответ: 51
25)Обозначим через M разность максимального и минимального числа среди простых делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то считаем значение M равным нулю. Напишите программу, которая перебирает целые числа, большие 450000, в порядке возрастания и ищет среди них такие, для которых значение M при делении на 29 даёт в остатке 11. Выведите первые 4 найденных числа в порядке возрастания, справа от каждого числа запишите соответствующее значения M.
26)В текстовом файле записан набор натуральных чисел. Гарантируется, что все числа различны. Рассматриваются пары с чётной суммой, такие что: — хотя бы половина чисел набора меньше среднего арифметического пары — хотя бы четверть чисел набора больше среднего арифметического пары Определите количество таких пар и наименьшее из средних арифметических таких пар.
Входные данные представлены в файле 26-50.txt следующим образом. Первая строка содержит целое число N – общее количество чисел в наборе. Каждая из следующих N строк содержит одно число, не превышающее 109. В ответе запишите два целых числа: сначала количество пар, затем наименьшее среднее арифметическое.
27)Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно два числа так, чтобы сумма всех выбранных чисел оканчивалась либо на 3 в семеричной записи, либо на 5 в десятичной записи, но не оканчивалась на 3 в семеричной записи и на 5 в десятичной записи одновременно, и при этом была максимально возможной.
Гарантируется, что искомую сумму получить можно. Входные данные. Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество троек N (N ≤ 250000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10 000.
Источник: 100ballnik.com