SHARE
TWEET

Untitled

a guest Dec 13th, 2018 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. '''
  2. Group Members
  3. =============
  4. '''
  5. userids = ['Thormundur15'] # fill in this array with strings of usernames
  6.  
  7. def m2p1(n):
  8.     '''Given a non-negative integer n calculate n-th Tribonacci number, using recursion.
  9.     '''
  10.     if n <= 1: return 0
  11.     if n == 2: return 1
  12.  
  13.     return m2p1(n-1) + m2p1(n-2) + m2p1(n-3)
  14.        
  15. memo = {0:0, 1:0, 2:1}
  16.  
  17. def m2p2(n):
  18.     '''Given a non-negative integer n calculate n-th Tribonacci number, using recursion and memoization.
  19.     '''
  20.  
  21.     if n < 0: return 0
  22.  
  23.     if n in memo:
  24.         return memo[n]
  25.  
  26.     else:
  27.         new_value = m2p2(n-1) + m2p2(n-2) + m2p2(n-3)
  28.         memo[n] = new_value
  29.         return new_value
  30.  
  31. def m2p3(n):
  32.     '''Given a non-negative integer n calculate n-th Tribonacci number using memoization with a list, and without using recursion
  33.     '''
  34.     T = [0,0,1] + [0]*(n-1)
  35.  
  36.     for i in range(3,n+1):
  37.         T[i] = T[i-3] + T[i-2] + T[i-1]
  38.  
  39.     return T[n]
  40.  
  41. def m2p4(n):
  42.     '''Given a non-negative integer n calculate n-th Tribonacci number, without using recursion and only storing three values.
  43.     '''
  44.     if n <= 1: return 0
  45.  
  46.     t2, t1, t0 = 1,0,0
  47.  
  48.     for i in range(3,n+1):
  49.  
  50.         t2, t1, t0 = t0+t1+t2, t2, t1
  51.  
  52.     return t2
  53.  
  54. def m2p5(n,L):
  55.     '''Project Euler Problem 31.
  56. The input n is a positive integer and the input L is a list of coin values.
  57. The returned value is the number of ways n can be split using the coin values in the list L.
  58.     '''
  59.     T = [1] + [0]*n
  60.     for i in L:
  61.         for j in range(i, n+1):
  62.             T[j] += T[j-i]
  63.     return T[n]
  64.  
  65. def m2p6(k):
  66.     '''Project Euler Problem 76.
  67. The input k should be a positive integer. The returned value is the number of
  68. different ways k can be written as a sum of at least two positive integers.
  69.     '''
  70.     T = [1] + [0]*k
  71.     for i in range(1, k):
  72.         for j in range(i, k+1):
  73.             T[j] += T[j-i]
  74.     return T[k]
  75.        
  76.  
  77. def m2p7(k):
  78.     '''Project Euler Problem 77.
  79. The input k should be a positive integer. The returned value is the smallest positive
  80. integer n such that the number of ways to write n as a sum of primes exceeds k
  81.     '''
  82.     if(k == 1): return 6
  83.     P = Primes()
  84.     summ = 0
  85.     while(True):
  86.         T = [1] + [0]*summ
  87.         for i in P:
  88.             for j in range(i, summ+1):
  89.                 T[j] += T[j-i]
  90.             if(i > 1000):
  91.                 break
  92.         if T[summ] > k:
  93.             break
  94.         summ += 1
  95.     return summ
  96.  
  97. def m2p8(k):
  98.     '''Project Euler Problem 78.
  99. The input k should be a positive integer. The returned value is the smallest positive
  100. integer n such that number of ways n coins can be separated into piles is divisible by k.
  101.     '''
  102.     ''''''
  103.     T = [1] + [0]*k
  104.     for i in range(1, k):
  105.         for j in range(i, k+1):
  106.             T[j] += T[j-i]
  107.     return T[k] + 1
  108.  
  109. def m2p9(M):
  110.     '''Project Euler Problem 81.
  111. The input M should be an n x n matrix containing integers, given as a list of lists.
  112. The output is the minimal path sum, as defined on Project Euler.
  113.     '''
  114.     for i in range(len(M)):
  115.         for j in range(len(M)):
  116.             if(i and j):  
  117.                 M[i][j] += min(M[i-1][j], M[i][j-1])
  118.             elif(i):
  119.                 M[i][j] += M[i-1][j]
  120.             elif(j):
  121.                 M[i][j] += M[i][j-1]
  122.     return M[len(M)-1][len(M)-1]
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