SHARE
TWEET

Programación Dinámica

a guest Nov 14th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import math
  2.  
  3. def f(d,p,C,S):
  4.     if p <= 0:
  5.         C[0] = 0
  6.         return
  7.     f(d,p-1,C,S)
  8.     conteo = math.inf
  9.     moneda = 0
  10.     for di in d:
  11.         if di <= p:
  12.             if C[p-di] < conteo:
  13.                 conteo = C[p-di]
  14.                 moneda = di        
  15.     C[p] = conteo + 1
  16.     S[p] = moneda
  17.        
  18. def monedas(d, n):
  19.     C = [-1] * (n + 1)
  20.     S = [0] * (n + 1)
  21.     f(d,n,C,S)
  22.     return C, S
  23.  
  24. monto = 19
  25. c, s = monedas([1, 5, 10, 20, 25, 50], monto)
  26. print(c)
  27. print(s)
  28. contar = [0] * (monto + 1)
  29. while monto > 0:
  30.     print(s[monto],monto)
  31.     contar[s[monto]] += 1
  32.     monto -= s[monto]
  33.    
  34. for x in range(len(contar)):
  35.     if contar[x] > 0:
  36.         print("Hay " + str(contar[x]) + " monedas de " + str(x))   
  37.  
  38. FIBONACCI
  39.  
  40. import math
  41.  
  42. cont = [0]
  43. def fibo(n):
  44.     t = [0]*(n+1)
  45.     def fibofibo(n):
  46.         cont[0] += 1
  47.         if n == 1:
  48.             t[0] = 0
  49.             t[1] = 1
  50.         else:
  51.             fibofibo(n - 1)
  52.             t[n] = t[n-1] + t[n-2]
  53.     fibofibo(n)
  54.     return t[n]
  55.    
  56. n = 10
  57. print("Fibonacci de %d es %d"%(n, fibo(n)))
  58. print("Iteraciones: %d"%(cont[0]))
  59.  
  60. def mincoins(d, p):
  61.     C = [0]*(p + 1)
  62.     M = [0]*(p + 1)
  63.    
  64.     def recu(p):
  65.         if p == 0:
  66.             C[0] = 0
  67.         else:
  68.             recu(p - 1)
  69.             Cother = []
  70.             minimum = math.inf
  71.             moneda = 0
  72.             for di in d:
  73.                 if p - di >= 0 and C[p-di] < minimum:
  74.                     minimum = C[p-di]
  75.                     moneda = di
  76.        
  77.             C[p] = 1 + minimum
  78.             M[p] = moneda
  79.    
  80.     recu(p)
  81.     return C, M
  82.  
  83. d = [1, 5, 10, 20, 25, 50]
  84. p = 40
  85. C, M = mincoins(d, p)
  86. print(C)
  87. print(M)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top