---

import math


def f(x):
  return x**2 + x + math.sin(x)


def df(x):
  return 2 * x + 1 + math.cos(x)


def d2f(x):
  return 2 - math.sin(x)


def zolotoe_sechenie(a, b, eps=1e-6):
  phi = (3 - math.sqrt(5)) / 2
  x1 = a + phi * (b - a)
  x2 = b - phi * (b - a)
  f1 = f(x1)
  f2 = f(x2)
  iterations = 0

  while (b - a) / 2 > eps:
    iterations += 1
    if f1 < f2:
      b = x2
      x2 = x1
      f2 = f1
      x1 = a + phi * (b - a)
      f1 = f(x1)
    else:
      a = x1
      x1 = x2
      f1 = f2
      x2 = b - phi * (b - a)
      f2 = f(x2)

  x_min = (a + b) / 2
  return x_min, f(x_min), iterations


def lomanie(a, b, eps=1e-6, L=4.2):
  iterations = 0
  points = [(a, f(a)), (b, f(b))]

  def get_vertex(p1, p2):
    x1, f1 = p1
    x2, f2 = p2
    xv = 0.5 * (f1 - f2 + L * (x1 + x2)) / L
    pv = 0.5 * (f1 + f2 + L * (x1 - x2))
    return xv, pv

  vertices = [get_vertex(points[0], points[1])]

  while True:
    iterations += 1

    idx_min = min(range(len(vertices)), key=lambda i: vertices[i][1])
    xv, pv = vertices[idx_min]

    f_min_current = min(p[1] for p in points)

    if f_min_current - pv <= eps:
      break

    p_new = (xv, f(xv))
    points.insert(idx_min + 1, p_new)

    v_left = get_vertex(points[idx_min], p_new)
    v_right = get_vertex(p_new, points[idx_min + 2])

    vertices[idx_min] = v_left
    vertices.insert(idx_min + 1, v_right)

  best_point = min(points, key=lambda p: p[1])
  return best_point[0], best_point[1], iterations


def newton(x0, eps=1e-6, max_iter=100):
  x = x0
  iterations = 0
  for _ in range(max_iter):
    iterations += 1
    df_val = df(x)
    d2f_val = d2f(x)
    if abs(df_val) < eps:
      break
    x_next = x - df_val / d2f_val
    if abs(x_next - x) < eps:
      x = x_next
      break
    x = x_next
  return x, f(x), iterations


if __name__ == '__main__':
  a, b = 0.0, math.pi / 2
  print('рузльтаты\n')

  x_g, f_g, it_g = zolotoe_sechenie(a, b, 1e-6)
  print(
      f'1 метод золотого сечения (0 порядок):\n   x* = {x_g:.6f}, f(x*) ='
      f' {f_g:.6f}, итераций = {it_g}\n'
  )

  x_b, f_b, it_b = lomanie(a, b, 1e-6)
  print(
      f'2 метод ломаных (0 порядок, глобальный):\n   x* = {x_b:.6f}, f(x*) ='
      f' {f_b:.6f}, итераций = {it_b}\n'
  )

  x_n, f_n, it_n = newton(0.5, 1e-6)
  print(
      f'3 метод ньютона (2 порядок):\n   x* = {x_n:.6f}, f(x*) = {f_n:.6f},'
      f' итераций = {it_n}'
  )