Разбор 26 задания
Алгоритм решения:
- Прочитать файл
- Отсортировать массив
- Найти медиану и среднее число
- Найти их индексы в массиве
- Вычислить количество чисел в диапазоне
1.Прочитать файл
f = open('26-j2.txt')
n = int(f.readline())
a = [int(f.readline()) for i in range(n)]2.Отсортировать массив
a = sorted([int(f.readline()) for i in range(n)])
a = sorted(a) # так можно отсортировать после считывания, a.sort() # или так
3.Найти медиану и средние число
Чтобы найти медиану в последовательности, нужно определить количество чисел в упорядоченном массиве.
По-условию задачи оно нечётное. Первой строке записано нечетное число N – количество чисел.
print(len(a)) # вывод длинны последовательности
Если длинна последовательности НЕЧЁТНОЕ, то медиана это число, которые находится посередине массива, разделяя его на два равные части.
a = [1, 4, 5, 19, 553] print(len(a)) # вывод: 5
Следовательно, медиана данного массива, число 5.
a = [1, 4, 5, 19, 553] print( len(a)//2 ) # индекс медианы в массиве print( a[len(a)//2] ) # медиана в массиве
Если длинна последовательности ЧЁТНОЕ, то медиана это полусумма двух чисел посередине
a = [1, 4, 5, 19, 553,1000] print(len(a)) # вывод: 6
Следовательно, медиана равна (5 + 19) / 2 = 12
a = [1, 4, 5, 19, 553,1000] print( (len(a)//2) - 1, (len(a)//2) ) # индекс 1-го и 2-го числа медианы print( a[(len(a)//2) - 1], a[(len(a)//2)] ) # 1-ое и 2-ое число print( ( a[(len(a)//2) - 1] + a[(len(a)//2)] ) / 2 ) # медиана
median = a[len(a//2)] # выше мы уже нашли медиану для нечётного кол-ва average = sum(a) / len(a) # сумма всех чисел разделить на их кол-во
4.Найти их индексы в массиве
Это самая сложная часть этого задания, да и в целом 26. Просто-на-просто среднего числа массива может не оказаться в нём самом, например оно может быть дробным. А также поиск в большом массиве числа - это труднозатратная операция, которая без оптимизации может занять продолжительное время.
Чтобы найти индекс такого числа нужно воспользоваться бинарным поиском, который мало того оптимизирован для поиска в больших массивах, так ещё и определяет индекс числа, которого вообще не может быть в массиве или значение такого числа может быть несколько.
from bisect import * # импортируем содержимое библиотеки # поиск самого крайнего значения медианы справа median_index = bisect_right(a, median) average_index = bisect_left(a, average) # поиск наиболее подходящего среднего числа слева # Оно само, или число на 1 позиция больше # # Как итог должно получиться следующие: # average_index <= (средние число — числа — медиана) <= median_index
Почему мы ищем индекс также для медианы?
Ответ: В массиве может содержаться множество значачний медианы, а так как, по-заданию, они тоже считаются, то нужно найти индекс крайнего числа-медианы.
Более подробно про бинарный поиск можно почитать в интернете.
docs.python.org/3/library/bisect.html
5.Вычислить количество чисел в диапазоне
print( media_index - average_index)
Так-как мы производим бинарный поиск для каждого числа, то получаемые индексы уже покрывают наши числа. Следовательно, чтобы найти количество входящих чисел в промежуток нам достаточно из индекса медианы вычесть индекс среднего числа.
Полный код:
from bisect import *
f = open('26-j2.txt')
n = int(f.readline())
a = sorted( [int(f.readline()) for i in range(n)] )
median = a[ len(a//2)]
average = sum(a) / len(a)
median_index = bisect_right(a, median)
average_index = bisect_left(a, average)
print( media_index - average_index)Редактор: andy