Решаю задачку (https://www.codewars.com/kata/5b5ce2176d0db7331f0000c0/train/python). Вот моё решение:
def get_rope_length(field_diameter, eaten_ratio):
import math
R = field_diameter/2
eps = 10**(-(len(str(field_diameter)))-1)
def square(r):
import math
alpha = (math.asin(r/(2*R)))*2
beta = math.acos(r/(2*R))
square_alpha = (R**2)*(alpha - 0.5*math.sin(alpha*2))
square_beta = (r**2)*(beta - 0.5*math.sin(beta*2))
square = square_alpha + square_beta
return(square)
if (R > 0) and (eaten_ratio < 1):
S = math.pi*R*R
step = R
r = step
while True:
delta = (S * eaten_ratio) - square(r)
if abs(delta) < eps:
break
if delta > 0:
r = r + step
else:
r = r - step
step = step/2
return (int(r))
elif (R == 0):
return(0)
elif (eaten_ratio == 1):
return(int(R*2))
Вкратце. Функция square определяет площадь фигуры, образованной наложением окружностей (центр "искомой" окружности лежит на одной из точек "зафиксированной" окружности). Далее идет само решение задачи. Решал методом деления отрезка пополам. Искомый радиус последовательно приближается к искомому значению, при котором площадь наложения не отличается от требуемой на заданную точность (переменная eps). Однако такой метод медленно работает при больших входных величинах. Не подскажете, как решать данную задачу и вообще задачи подобного типа, когда составить какую-то зависимость достаточно проблематично. Как мне кажется, ускориться можно, если выбрать другое начальное приближение и шаг сближения (В моем решении я начинаю безусловно решать при step == R == r)
field_diameter
? Может это как-то неправильно? Эпсилон для больших чисел должен быть больше, а не меньше. Либо я чего-то не понимаю.