• API
• FAQ
• Tools
• Archive
daily pastebin goal
15%
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.

Top