【Python编程导论】第三章- 一些简单的数值程序

基本概念

1. 穷举法

穷举法:是猜测与检验算法的一个变种。我们枚举所有可能性,直至得到正确答案或者尝试完所有值。

#寻找完全立方数的立方根
x = int(input('Enter an integer: '))
ans = 0
while ans**3 < abs(x):
    ans = ans + 1
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)

那么,对于何种x值,程序能正常结束呢?答案是“所有整数”。 : 1.表达式ans**3的值从0开始,并随着每次循环逐渐变大; 2.当这个值达到或超过abs(x)时,循环结束; 3.因为abs(x)的值总为正,所以循环结束前进行的迭代次数必然是有限的。编写循环时,应该使用一个合适的递减函数。这个函数具有如下属性:

  1. 它可以将一组程序变量映射为一个整数;
  2. 进入循环时,它的值是非负的;
  3. 当它的值≤0时,循环结束;
  4. 每次循环它的值都会减小。

2. for循环

for循环中常用到 range()函数,因此先对它进行介绍:

  1. range函数接受3个整数参数:start、stop和step。生成一个数列:start、start + step、start + 2*step,等等。
  2. 如果step是正数,最后一个元素就是小于stop的最大整数start + i * step。如果step是负数,最后一个元素就是大于stop的最小整数start + i * step。
  3. 数列中的数值是以“按需产生”的原则生成的,所以即使range(1000000)这样的表达式也只占用很少内存。
#寻找完全立方数的立方根
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)

3. 近似解和二分查找

穷举法是一种查找技术,只在被查找集合中包含答案时才有效

#使用穷举法求近似平方根
x = 25
epsilon = 0.01
step = epsilon**2
numGuesses = 0
ans = 0.0
while abs(ans**2 - x) >= epsilon and ans <= x:
    ans += step
    numGuesses += 1
print('numGuesses =', numGuesses)

if abs(ans**2 - x) >= epsilon:
    print('Failed on square root of', x)
else:
    print(ans, 'is close to square root of', x)

二分查找法,可以提升查询效率

x = 25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**2 - x) >= epsilon:
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to square root of', x)

4. 关于浮点数

很多时候, float类型的数值是实数的一个非常好的 近似。但“很多时候”并不代表所有情况,这个功能失效时会引起不可思议的后果。例如,试着运行以下代码:

x = 0.0
for i in range(10):
    x = x + 0.1
if x == 1.0:
    print(x, '= 1.0')
else:
    print(x, 'is not 1.0')
# 结果
0.9999999999999999 is not 1.0

为什么会出现这样的结果呢?

  1. 其实这和二进制与十进制表示方式有关(python中二进制表示的0.1并不是真的等于十进制中0.1)。
  2. 那Python中写作0.1的十进制分数1/10呢?若使用4位有效数字,最好的表示方式是(0011,-101),等于3/32,也就是0.09375。如果有5位有效的二进制数字,可以将0.1表示成(11001, -1000),等于25/256,也就是0.09765625。那么,需要多少位有效数字才能使用浮点数准确表示0.1呢?需要无穷位!不存在两个整数sig和exp,使sig × 2-exp = 0.1。所以无论Python(或任何一种语言)使用多少位有效数字表示浮点数,都只能表示0.1的一个近似值。
  3. 所以将0.1相加10次真的不等于10乘以0.1的值

5. 牛顿-拉弗森法

牛顿-拉弗森法可以用于求单变量多项式的值,那么什么是单变量多项式?

单变量多项式或者是0,或者是一个有限数目的非零单项式的和。每一项都由一个常数(项的系数)乘以变量的非负整数次方(这里为2次方)组成。

牛顿-拉弗森法的原理

逐次逼近;牛顿证明了一个定理:如果存在一个值guess是多项式p的根的近似值,那么guess -p(guess)/p'(guess)就是一个更好的近似值,其中p'是p的一次导数。

#利用牛顿.拉弗森法寻找平方根
#寻找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)

编程练习

1.编写一个程序,要求用户输入一个整数,然后输出两个整数root和pwr,满足 0<pwr<6,并且 root**pwr等于用户输入的整数。如果不存在这样一对整数,则输出一条消息进行说明。

# 解法1
r = int(input('input an integer'))
root = 0
i = 0
for pwr in range(1, 7):
    result = -1
    while result < abs(r):
        root += 1
        result = root**pwr
    if result == abs(r):
        if r < 0:
            root = -root
        print('root:{},pwr:{}'.format(root, pwr))
        i += 1
    root = 0
print('总共有{}种输出结果'.format(i))
# 解法2
x=int(input('Enter an integer: '))
root=1
pwr=1
w=root**pwr
i=0
while w<abs(x) or root<=abs(x): 
    if pwr<6: 
        w=root**pwr
        if w==abs(x) and x<0:
            i+=1
            print('root','=',-root,'pwr','=',pwr)
        elif w==abs(x):
            i+=1
            print('root','=',root,'pwr','=',pwr)
        pwr+=1
    else:
        pwr=1
        root+=1
        w=root**pwr
print('符合条件的整数对共有{}种'.format(i))

2.假设s是包含多个小数的字符串,由逗号隔开,如 s='1.23, 2.4, 3.123'。编写一个程序,输出s中所有数值的和。

# 解法1
s = '1.23, 2.4, 3.123'
sum = 0.0
for i in map(lambda i: float(i), s.split(',')):
    sum += i
print(sum)
# 解法2
s = '1.23, 2.4, 3.123'
a=s.split(',')
t=0
for i in a:
    t=t+float(i)
print(t)

3.如果语句x = 25被替换为x = -25,代码会如何运行?

程序会进入无限循环
# 该程序while循环中,x值始终未变。则导致该循环条件(abs(ans**2 - x) >= epsilon)始终成立,程序进入无限循环中。
x = -25
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
while abs(ans**2 - x) >= epsilon: # 这一步永远不会停止
    print('low =', low, 'high =', high, 'ans =', ans)
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print('numGuesses =', numGuesses)
print(ans, 'is close to square root of', x)

4.如何修改图3-4中的代码,才能求出一个数的立方根?这个数既可以是正数,也可以是负数。(提示:修改low保证答案位于待查找区域。)

x = -30
epsilon = 0.01
numGuesses = 0
x_abs = abs(x)  # 关键代码
low = 0.0
high = max(1.0, x_abs)
ans = (high + low) / 2.0
while abs(ans**3 - x_abs) >= epsilon:
    numGuesses += 1
    if ans**3 < x_abs:
        low = ans
    else:
        high = ans
    ans = (high + low) / 2.0
print('numGuesses =', numGuesses)
if x < 0:
    print(-ans, 'is close to square root of', x)
else:
    print(ans, 'is close to square root of', x)

5.二进制数10011等于十进制中的哪个数?

19
# 解法1 进制转换
# 解法2 函数求解
int('10011',base=2)

6.在牛顿.拉弗森法的实现中添加一些代码,跟踪求平方根所用的迭代次数。在这段代码的基础上编写一个程序,比较牛顿.拉弗森法和二分查找法的效率。

#利用牛顿.拉弗森法寻找平方根
#寻找x,满足x**2-24在epsilon和0之间
epsilon = 0.01
k = 24.0
guess = k/2.0
a=0
while abs(guess*guess - k) >= epsilon:
    guess = guess - (((guess**2) - k)/(2*guess))
    a+=1
print('Square root of', k, 'is about', guess)
print('牛顿法迭代次数={}'.format(a))

#利用二分查找法寻找平方根
#寻找x,满足x**2-24在epsilon和0之间
x = 24.0
epsilon = 0.01
numGuesses = 0
low = 0.0
high = max(1.0, x)
ans = (high + low)/2.0
b=0
while abs(ans**2 - x) >= epsilon:
    numGuesses += 1
    if ans**2 < x:
        low = ans
    else:
        high = ans
    ans = (high + low)/2.0
print(ans, 'is close to square root of', x)
print('二分法迭代次数 ={}'.format(numGuesses))
Square root of 24.0 is about 4.8989887432139305
牛顿法迭代次数=4
4.8984375 is close to square root of 24.0
二分法迭代次数 =9

本文分享自微信公众号 - Datawhale(Datawhale)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-07-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序生活

机器学习(十九)EM:期望最大算法

最大期望算法(Expectation Maximization Algorithm,又译期望最大化算法),是一种迭代算法,用于含有隐变量(hidden vari...

17820
来自专栏深度学习与python

算法研习:支持向量机算法基本原理分析

支持向量机(SVM)是一种监督学习算法,可用于分类和回归问题。支持向量机是最常用也是大家最熟悉的算法,你可能不懂其算法原理,但你绝对听说过这种算法。今天算法研习...

9320
来自专栏AI机器思维

这个世界什么最难解决?

我一直在思考一个问题,这个世界什么最难解决?人是社会的群体,每一个人都不会脱离社会而生活,无论是大隐隐于市还是小隐隐于市。人们在生活中交流需要提升效率;人们在生...

9340
来自专栏深度学习与python

你听说过XGBoost吗

这是个深度学习的时代,传统的机器学习算法仿佛已经失去了往日的光彩,你能随处听到卷积神经网络、循环神经网络以及其他各种net,偶尔听到的机器学习算法也是支持向量机...

11120
来自专栏深度学习与python

从业多年,总结几点关于机器学习的经验教训

纯机器学习(ML)模型的训练与建立端到端的数据科学解决方案与实际企业需要之间存在巨大差异。 本文总结了我们团队与来自不同行业的数十家企业客户(包括制造业,金融服...

13620
来自专栏Jerry的SAP技术分享

myAppointment OPA test case issue

Test case description: 在create appointment view中,定义了一个这样的元素:

7440
来自专栏MixLab科技+设计实验室

第一课 读懂代码 - swift简明指南

这个指南有点不一样,每一个章节都可以独立实验,难度都是0基础即可掌握,开发前只需要准备mac电脑,然后装上xcode。

10920
来自专栏深度学习与python

30行代码让你玩转YOLO目标检测

YOLO是一种实时目标检测算法,与faster R-CNN不同的是,YOLO不是过多的注重物体定位的精度,而是着重于速度和物体种类的识别。在实际应用中,实时性是...

11110
来自专栏深度学习与python

Python梯度下降的多项式回归分析

线性回归是多项式回归中多项式次数为1的一个特例,通常在回归问题中,我们使用多项式对曲线进行拟合。假设一个单变量线性回归方程如下:

26410
来自专栏深度学习与python

算法研习:Knn算法基本原理分析

在这篇文章中,我将介绍knn算法,knn算法是机器学习中十大经典算法之一。knn可用于分类和回归问题,其算法原理简单,没有涉及太多数学原理,准确的说用一个数学公...

16710

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励