第三章
一些简单的数值程序
- 穷举法
#寻找完全立方数的立方根
x = int(input('Enter an integer: '))
for ans in range(0, abs(x)+1):
if ans**3 >= abs(x):
break
if ans**3 != abs(x):
print(x, 'is not a perfect cube')
else:
if x < 0:
ans = -ans
print('Cube root of', x,'is', ans)
实际练习：假设s是包含多个小数的字符串，由逗号隔开，如s = '1.23, 2.4, 3.123'。编写一个程序，输出s中所有数值的和
近似解和二分查找
牛顿拉弗森法
在基于二分求解法求解多项式时，通过牛顿拉弗森的数学推论，对解x的范围做了更精确的数学估值
#利用牛顿拉弗森法寻找平方根
#寻找x，满足x**2-24在epsilon和0之间
epsilon = 0.01
k = 24.0
guess = k/2.0
while abs(guess*guess - k) >= epsilon:
#区别
guess = guess - (((guess**2) - k)/(2*guess))
print('Square root of', k, 'is about', guess)
额外介绍
- for循环和range
range(2,10,2)
# 2,4,6,8
- 浮点数
由于计算机内部是用二进制表示数值，所以当表示小数时
表示0.375，0.3752*3 = 3 = 11（2），表示0.375时，二进制11向左移3位：0.011
表示0.1，由于0.1无法乘以2的n次幂恰好为一个整数，所以只能无限接近
因此，判断两个浮点数是否相等不能用==,应当用abs(float_a)-abs(float_b)<epsilon
第四章 函数、作用域、抽象
前三章介绍的Python的功能：数值、赋值语句、输入/输出、比较语句和循环结构，已满足图灵完备，即实现这些功能的语言理论上可以写出任何算法。然而，一门语言需要更强大的通用性
- 函数定义
#关键字 def、return
def maxVal(x, y):
if x > y:
return x
else:
return y
作用域/命名空间
每个函数内部都是一个命名空间，即作用域
执行到该函数时，就会创建作用域，绑定对象的变量名为局部变量，挂在该作用域下
作用域栈帧的后进先出函数的三引号
记录函数思路，方便维护
双引号\单引号都可，在def下后一行
# 求一个数n次幂的函数思考
def findRoot1(x, power, epsilon):
"""
x和epsilon是整数或者浮点数， power是整数
epsilon>0 且power＞＝ 1
如果y**power和x的差小于epsilon，就返回浮点数y，
否则返回None
"""
low = 0
high = x
ans = (high+low)/2.0
while abs(ans**power - x) > epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (high+low)/2.0
return ans
##print findRoot1(25.0, 2, .001)
##print findRoot1(27.0, 3, .001)
##print findRoot1(-27.0, 3, .001)
# so can't find cube root of negative number
#在2的基础上考虑了x=[-1,1]的情况
def findRoot2(x, power, epsilon):
if x < 0 and power%2 == 0:
return None
# can't find even powered root of negative number
low = min(0, x)
high = max(0, x)
ans = (high+low)/2.0
while abs(ans**power - x) > epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (high+low)/2.0
return ans
##print findRoot2(25.0, 2, .001)
##print findRoot2(27.0, 3, .001)
##print findRoot2(-27.0, 3, .001)
##
##print findRoot2(0.25, 2, .001)
##print findRoot2(-0.125, 3, .001)
#在2的基础上考虑了x=[-1,1]的情况
def findRoot3(x, power, epsilon):
if x < 0 and power%2 == 0:
return None
# can't find even powered root of negative number
low = min(-1.0, x)
high = max(1.0, x)
ans = (high+low)/2.0
while abs(ans**power - x) > epsilon:
if ans**power < x:
low = ans
else:
high = ans
ans = (high+low)/2.0
return ans
print findRoot3(25.0, 2, .001)
print findRoot3(27.0, 3, .001)
print findRoot3(-27.0, 3, .001)
print findRoot3(0.25, 2, .001)
print findRoot3(-0.125, 3, .001)
def testFindRoot():
epsilon = 0.0001
for x in (0.25, -0.25, 2, -2, 8, -8):
for power in range(1,4):
print('Testing x = ' + str(x) +\
' and power = ' + str(power))
res = findRoot3(x, power, epsilon)
if res == None:
print(' No root')
else:
print(' ' + str(res**power) + ' ~= ' + str(x))
递归
#阶乘的迭代实现
def factI(n):
"""假设n是正整数
返回n!"""
result = 1
while n > 1:
result = res
n -= 1
return result
def factR(n):
"""假设n是正整数
返回n!"""
if n==1:
return n
else:
return n*factR(n-1)
斐波那契数列
def fib(n):
"""假定n是正整数
返回第n个斐波那契数"""
if n == 0 or n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
如果使用函数fib计算fib(5)，那么需要计算多少次fib(2)的值:
5 分为 4和3，
5->4分为3,2，5->3分为2，1，
5->4->3分为2,1
共3次
视频中的错题总结
1、寻找‘djadfhbobobkafsjhf’字符串中的'bob'出现次数，如左边字符串中出现了2次
#利用字符串前片
num = 0
for i in range(len(s)-2):
num += s[i:i+3].count('bob')
print 'Number of times bob occurs is: %s' % num
2、返回字符串中最长的且按照字母表顺序排序的子字符串
letter = ans = ''
for i in range(len(s)):
if i <len(s)-1 and s[i] <= s[i+1]:
letter += s[i]
else:
letter += s[i]
if len(letter) > len(ans):
ans = letter
letter = ''
print(ans)
