-
Notifications
You must be signed in to change notification settings - Fork 6
/
pset3fingerex.py
172 lines (118 loc) · 2.85 KB
/
pset3fingerex.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
def iterPower (base, exp):
'''
base: int or float.
exp: int >= 0
returns: int or float, base^exp
'''
result = 1
if exp == 0:
return result
while exp > 0:
result = result*base
exp = exp - 1
return result
def recurPower(base, exp):
'''
base: int or float.
exp: int >= 0
returns: int or float, base^exp
'''
if exp == 0:
return 1
else:
base = base * recurPower(base, exp - 1)
return base
def recurPowerNew(base, exp):
'''
base: int or float.
exp: int >= 0
returns: int or float; base^exp
This function recursively computes exponentials using multiplication
and remainders.
'''
if exp == 0:
return 1
elif exp%2 == 0:
base = recurPowerNew(base*base, exp/2)
else:
base = base * recurPowerNew(base, exp - 1)
return base
def gcdIter(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
result = min(a,b)
while result > 1:
if a%result == 0 and b%result == 0:
return result
else:
result = result - 1
return result
def gcdRecur(a, b):
'''
a, b: positive integers
returns: a positive integer, the greatest common divisor of a & b.
'''
if b == 0:
return a
else:
return gcdRecur(b, a%b)
def lenIter(aStr):
'''
aStr: a string
returns: int, the length of aStr
'''
result = 0
for letter in aStr:
result = result + 1
return result
def lenRecur(aStr):
'''
aStr: a string
returns: int, the length of aStr
'''
if aStr == '':
return 0
else:
return 1 + lenRecur(aStr[1:])
def isIn(char, aStr):
'''
char: a single character
aStr: an alphabetized string
returns: True if char is in aStr; False otherwise
This example uses the bisection search algorithm.
'''
mid = len(aStr)/2
if aStr == '' or len(aStr) == 1:
return char == aStr
elif char == aStr[mid]:
return True
elif char < aStr[mid]:
aStr = aStr[: mid]
return isIn(char, aStr)
else:
aStr = aStr[mid + 1:]
return isIn(char, aStr)
def oddTuples(aTup):
'''
aTup: a tuple
returns: tuple, every other element of aTup.
'''
return aTup[0::2]
def howMany(aDict):
'''
aDict: A dictionary, where all the values are lists.
returns: int, how many values are in the dictionary.
'''
count = 0
for i in aDict:
count = count + len(aDict[i])
return count
def biggest(aDict):
'''
aDict: A dictionary, where all the values are lists.
returns: The key with the largest number of values associated with it
'''
if aDict:
return max(aDict.items(), key=lambda x: len(x[1]))[0]