Некое растровое изображение было сохранено в файле p1.bmp как 24-разрядный рисунок. Во сколько раз будет меньше информационный объем файла p2.bmp, если в нём это же изображение сохранить как 256-цветный рисунок?
Идея такая: разбиваем отрезок [a, b] на два: [a, m] и [m, b], где m = (a + b)/2. Длина такого отрезка h = b - a. Cмотрим значения функции f в точках m - ε и m + ε. Если f(m - ε) < f(m + ε), то думаем, что функция возрастает в точке m, и разумно искать ответ на отрезке [a, m]; если f(m - ε) > f(m + ε), то оставляем отрезок [m, b]. Если нам ОЧЕНЬ не повезло, и f(m - ε) = f(m + ε), то оставим отрезок [m - h/4, m + h/4]. При этом в любом случае длина нового отрезка будет h/2. В качестве ε разумно взять желаемую точность, и останавливаться, если новая длина h/2 окажется меньше ε.
Очень маленький ε ставить не следует, при этом очень большую роль начинаю играть ошибки округления.
Точный ответ можно найти, посчитав производную. Должно получиться
import typing
from typing import Callable
from typing import AnyStr
from typing import Any
from typing import Iterable
from typing import List
def ListTransform(Data: List[Any], Tranformer: Callable[[Any], Any], Selector: Callable[[Any], bool] = lambda p: True):
'''Трансформирует элементы list, удовлетворяющие условию, в соответствии с заданным правилом
По умолчанию трансформирует все элементы'''
for index, item in enumerate(Data):
if (Selector(item)):
Data[index] = Tranformer(item)
return Data
def ReadSeq(SeqLen: int, CastType):
'''
Возвращает последовательность элементов в указанном типе, считанных с клавиатуры, заданной длины.
'''
try:
for _ in range(SeqLen):
yield CastType(input())
except TypeError:
raise RuntimeError(f'Unsupported type: {CastType}')
def main():
n = int(input())
Lst = list(ReadSeq(n, int))
def Filter(number):
if number % 2 == 0: return 1
else: return 0
print(*ListTransform(Lst, Filter))
if __name__ == "__main__":
main()
Идея такая: разбиваем отрезок [a, b] на два: [a, m] и [m, b], где m = (a + b)/2. Длина такого отрезка h = b - a. Cмотрим значения функции f в точках m - ε и m + ε. Если f(m - ε) < f(m + ε), то думаем, что функция возрастает в точке m, и разумно искать ответ на отрезке [a, m]; если f(m - ε) > f(m + ε), то оставляем отрезок [m, b]. Если нам ОЧЕНЬ не повезло, и f(m - ε) = f(m + ε), то оставим отрезок [m - h/4, m + h/4]. При этом в любом случае длина нового отрезка будет h/2. В качестве ε разумно взять желаемую точность, и останавливаться, если новая длина h/2 окажется меньше ε.
Очень маленький ε ставить не следует, при этом очень большую роль начинаю играть ошибки округления.
Точный ответ можно найти, посчитав производную. Должно получиться
Реализация (python 3.7):
from math import sqrt
def find_min(function_to_minimize, left, right, tolerance=1e-6):
assert left <= right
# print(left, right) # если хотите проследить за тем, как меняются границы
length = right - left
if length <= tolerance:
return left
midpoint = (left + right) / 2
y_left, y_right = function_to_minimize(midpoint - tolerance), function_to_minimize(midpoint + tolerance)
if y_left < y_right:
return find_min(function_to_minimize, left, midpoint, tolerance)
elif y_left > y_right:
return find_min(function_to_minimize, midpoint, right, tolerance)
else:
return find_min(function_to_minimize, midpoint - length / 4, midpoint + length / 4)
calculated = find_min(lambda x: x ** 3 - x, 0, 1)
exact = 1 / sqrt(3)
print(calculated)
print(calculated - exact)
Мне выводится ответ 0.5773496627807617
Разница между точным решением и найденным примерно