计算机科学和编程导论
Week3
递归
递归步骤
基线条件
def recurMul(a, b):
if b == 1:#基线条件
return a
else:
return a + recurMul(a, b-1) #递归步骤
def recurPower(base, exp):
if exp = 0 :#基线条件
return 1
return base * recurPower(base,exp-1) #递归步骤
————————————————————————
def recurPowerNew(base, exp):
if exp == 0:#基线条件
return 1
elif exp % 2 == 0:
return recurPowerNew(base*base, exp/2)#递归步骤
return base * recurPowerNew(base, exp-1)#递归步骤
————————————————————————
def gcdIter(a, b):#迭代
gys = min(a,b)
while a % gys != 0 or b % gys != 0:
gys -= 1
return gys
————————————————————————
def gcdRecur(a, b):
if b == 0:#基线条件
return a
return gcdRecur(b, a % b)#递归步骤
汉诺塔 - #思考
def printMove(fr, to): #输出语句
print('move from ' + str(fr) + ' to ' + str(to))#移动步骤 fr > to
def Towers(n, fr, to, spare): #数量，起始，终点，空
if n == 1:#基线条件
printMove(fr, to)#输出语句
else:
Towers(n-1, fr, spare, to) #倒数第二个 起始>空>终点
Towers(1, fr, to, spare)#第一个 起始>终点>空
Towers(n-1, spare, to, fr)#倒数第二个 空>终点>起始
——————————————————
斐波纳契数
def fib(x):
assert type(x) == int and x >= 0 #断言
if x == 0 or x == 1:#基线条件
return 1
else:
return fib(x-1) + fib(x-2)#递归步骤
assert 断言：声明其布尔值必须为真的判定，如果发生异常就说明表达示为假。
————————————————————————————————
回文结构
def isPalindrome(s): #函数，内部函数调用
def toChars(s):#函数
s = s.lower()#定义所有字符为小写
ans = ''
for c in s:
if c in 'abcdefghijklmnopqrstuvwxyz':
ans = ans + c
return ans#返回重新生成的字符串
def isPal(s):
if len(s) <= 1:#基线条件
return True
else:
return s[0] == s[-1] and isPal(s[1:-1])#递归步骤
return isPal(toChars(s))
-------------------------------------------------------------------------
def lenIter(aStr):#迭代
num = 0
for c in aStr:
num += 1
return num
---------------------------------
def lenRecur(aStr):
if aStr[0:1] == '':#基线条件
return 0
else:
return 1 + lenRecur(aStr[1:]) #递归步骤
————————————————————————
def isIn(char, aStr):
if char=='':#若char为空
return True
if aStr=='':#若aStr为空
return False
if char==aStr[len(aStr)/2]: #char在aStr前半段
return True
if char<aStr[len(aStr)/2]: #char长度小于aStr/2
return isIn(char,aStr[:len(aStr)/2]) #从aSt/2r后半段重新开始
if char>aStr[len(aStr)/2]: #char长度大于aStr/2
return isIn(char,aStr[len(aStr)/2+1:])#从aSt/2+1不断重新开始
————————————————————————
def semordnilap(str1, str2):#镜像
if len(str1) != len(str2):#判断长度
return False
elif len(str1) == 1:#判断长度是否为1
return str1 == str2
elif str1[0] == str2[-1]:#基线条件
return semordnilap(str1[1:],str2[:-1]) #递归步骤
else:
return False
全局变量
global
def fibMetered(x):
global numCalls
numCalls += 1
if x == 0 or x == 1:
return 1
else:
return fibMetered(x-1) + fibMetered(x-2)
def testFib(n):
for i in range(n+1):
global numCalls
numCalls = 0
print('fib of ' + str(i) + ' = ' + str(fibMetered(i)))
print('fib called ' + str(numCalls) + ' times')