def  numero_mas_grande(lista):
  n = len(lista)
  a = lista[0]
  i = 1
  while i < n:
    if lista[i] > a:
      a = lista[i]
    i = i + 1
  return a	

def  fact_recursivo(n): 
  if  n == 1:
    fact = 1
  elif n > 1:
    fact = n * fact_recursivo(n-1)
  return fact

def fact_iterativo(n): 
  fact = 1
  for i in range(1,n+1):
    fact = fact*i
  return fact

def mcd(n,m):
  mayor = max(n,m)
  menor = min(n,m)
  resto = mayor % menor
  if  resto == 0:
    return menor
  return mcd(menor,resto)

def gcd(n,m): 
  if n == 0:
     return m
  return mcd(m%n,n)


def  hanoi(n, inicial, final, libre):
  if n == 1:
    print ('mover disco superior de aguja', inicial,'a', final)
  else:
    hanoi(n-1, inicial, libre, final)
    print ('mover disco superior de aguja', inicial,'a', final)
    hanoi(n-1, libre, final, inicial)


def  busqueda_lineal(a, L):
  y = -1
  for j in range(len(L)):
    if a == L[j]:
      y = j + 1
      break
  return y

def  busqueda_binaria(a, L):
  menor = 0
  grande = len(L) - 1
  while menor <= grande:
    mitad = (menor + grande) // 2
    if L[mitad] > a:
      grande = mitad - 1 
    elif L[mitad] < a:
      menor = mitad +1
    else:
      return mitad + 1
  return -1      

def busqueda_binaria_bis(a, L):
    menor = 0
    grande = len(L)-1
    while True:
        if menor > grande:
            return -1
        mitad = (menor + grande) // 2
        if a == L[mitad]:
            return mitad+1
        elif menor == grande:
            return -1
        elif a < L[mitad]:
            grande = mitad - 1
        else:
            menor = mitad + 1

def busqueda_re_binaria(a,M):
  m = len(M)
  L= M[:]
  n = len(L)
  if m==n:
    mitad = n//2
    if n <= 0:
      solu = 0
    if L[mitad] == a:
      solu = mitad + 1
    elif n == 1:
      solu = 0
    elif L[mitad] > a:
      r = mitad
      solu = busqueda_re_binaria(a, L[:mitad])
    else:
      r = mitad
      solu = busqueda_re_binaria(a,L[mitad:])
    return solu

 
def  ordenar_burbuja(L):
  for i in range(1,len(L)):
    for j in range(len(L)-i):
      if L[j] > L[j + 1]:
        temp = L[j]
        L[j] = L[ j+1 ]
        L[j+1] = temp
  return L

def  ordenar_insertando(L):
  for j in range(1, len(L)):
    i = j-1
    temp = L[j]
    while i > -1 and L[i] > temp:
      L[i+1] = L[i]
      i = i - 1
    L[i+1] = temp
  return L

def  mezclando(izquierda, derecha):
  ordenada = []
  i, j = 0, 0
  while i < len(izquierda) and j < len(derecha):
    if izquierda[i] <= derecha[j]:
      ordenada.append(izquierda[i])
      i = i + 1
    else:
      ordenada.append(derecha[j])
      j=j+1
  ordenada += izquierda[i:]
  ordenada += derecha[j:]
  return ordenada

def  ordenar_mezclando(L):
  if len(L) < 2:
    return L
  else:
    mitad = len(L)//2
    izquierda = ordenar_mezclando(L[:mitad])
    derecha = ordenar_mezclando(L[mitad:])
    return mezclando(izquierda,derecha)

def  fibonacci_recursivo(n):
  if n == 1 or n == 2:
    fibo = 1
  elif n > 2:
   fibo = fibonacci_recursivo(n-1) + fibonacci_recursivo(n-2)
  return fibo

def  fibonacci_iterativo(n):
  if  n == 1 or n == 2:
     F = 1
  else:
    f1, f2 = 1, 1
    for i in range(3, n+1):
      F = f1 + f2
      f1, f2 = f2, F
  return F


def  fibo_iterativo(n):
      f1, f2 = 1,1
      for i in range(3, n+1):
        f1, f2 = f2, f1 + f2
      return f2

def  fibonacci_formula(n):
    from math import sqrt
    z = 1/sqrt(5)*( ((1+sqrt(5))/2)**n - ((1-sqrt(5))/2)**n)
    return int(z)

from time import time, process_time
import timeit

def  tiempo_programa(programa):
  t_0 = time()
  programa
  t = time()
  return t-t_0

#total_time = timeit.timeit('[v for v in range(10000)]', number=10000)


def  timeit_programa(programa):
  t=timeit.timeit(programa)
  return t


def  clock_programa(programa):
  t_0 = process_time()
  programa
  t = process_time()
  return t-t_0
  
from timeit import Timer

from random import *
##N=10**7
##L=[]
##i=0
##while i<N:
##    L.append(randint(0,10**8-1))      
##    i+=1

def tiempo_lista(M, N):
    t_0 = process_time()
    L= []
    i = 0
    while i < 10**M:
      L.append(randint(0,10**N))
      i += 1
    t = process_time()  
    return t - t_0

  
def  tiempo_busqueda_lineal(N,M):
  t_0 = process_time()
  busqueda_lineal(randint(0,10**N),range(10**M))
  t = process_time()
  return t - t_0


def  tiempo_busqueda_binaria(N,M):
  from time import  process_time
  t_0 = process_time()
  busqueda_binaria_binaria(randint(0,10**N),range(10**M))
  t = process_time()
  return t - t_0 



def  tiempo_ordenar_burbuja(N,M):
  from time import  clock
  L= sample(range(10**N),10**M)
  t_0 = clock()
  ordenar_burbuja(L)
  t = clock()     
  return t - t_0

def  tiempo_ordenar_insertando(N,M):
  from time import  clock
  L= sample(range(10**N),10**M)
  t_0 = clock()
  ordenar_insertando(L)
  t = clock()     
  return t - t_0


def  tiempo_ordenar_mezclando(N,M):
  from time import  clock
  L= sample(range(10**N),10**M)
  t_0 = clock()
  ordenar_mezclando(L)
  t = clock()     
  return t - t_0