Linux迷+Python粉 - python

神奇的环境bug导致python3中出现udc开头字符串

2018-11-07T15:30:00+08:00

注意：LANG=zh_CN.UTF-8与LANG=en_US.UTF-8不可混淆！¶

LANG=zh_CN.UTF-8与LANG=en_US.UTF-8有区别 ，所以不可混淆！想之前在python2时代吃过坑，没想到到了统一unicode的python3，因环境不一致也能导致编码问题！

当时环境与功能：¶

vps系统是ubutnu 14.04, 相关软件python3.4, selenium3+, chrome66, chromedriver。使用crontab启动shell， shell中启动python脚本，脚本中selenium启动chrome，……

出bug的运行流程：¶

crontab中的a.sh启动 LANG=zh_CN.UTF-8 bash a.sh
a.sh末尾调用”b中文名.py”，带中文参数”《xxx》”
b中文.py 中print(参数1) 会异常显示字符串编码问题’ascii’ codec can’t encode characters

调试发现:¶

print repr(中文参数1)，会打印\udc 开头的而非\x开头的utf8型编码。
比如”《” 正常编码是 ‘\xe3\x80\x8a’，此处确是打印了’\udce3\udc80\udc8a’ 。
改变逻辑，直接ssh到vps并执行 b中文.py 《xxx》 没有问题！

问题定位:¶

个人本机ubuntu系统测试不会出现bug，vps才出现，所以应该是shell环境或者是python环境问题。
打印执行a.sh的shell环境，对比发现本机有LANG=zh_CN.UTF-8和LANGUAGE=zh_CN:zh，vps仅有LANG=zh_CN.UTF-8。
把crontab中强加的环境变量LANG=zh_CN.UTF-8去掉，此时a.sh的环境变量为LANG=en_US.UTF-8， vps恢复正常。（2小时排查出结果了！）
总结：之前觉得LANG=zh_CN.UTF-8与LANG=en_US.UTF-8没什么不同，从此改观。

问题解决：¶

去掉LANG=zh_CN.UTF-8，之后执行过程中会自动变成默认LANG=en_US.UTF-8

原因探究：¶

待定

python repr输出udc开头字符串， print(参数)导致异常¶

'/home/maskuser/path/to/ts/\udce3\udc80\udc8a\udce9\udc80\udc97.....mp4'

Traceback (most recent call last):
  File "/home/maskuser/pathtodir/script/20181105\udce8\udca7\udc86\.....py", line 73, in <module>
    video_upload_testsite(*sys.argv[1:])
  File "/home/maskuser/pathtodir/script/20181105\udce8\udca7\udc86\.....py", line 29, in video_upload_testsite
    print (videopath)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 27-50: ordinal not in range(128)

RSA原理：欧几里德算法与奥数内容辗转相除法——挑战PythonTip

2017-12-17T23:00:00+08:00

PythonTip 里未攻克的题目，如RSA密码方程，如今积累工作经验之后从新挑战，仍然失败未成功了。把过程记录分享下。

描述:¶

在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。其中，x,a,n皆为正整数。现在给你a和n的值(1 < a,n < 140000000)，请你求出最小的满足方程的正整数解x（保证有解）. 如：a = 1001, n = 3837，则输出23。

分析：¶

没头绪，在讨论里看时恍然，用到小学奥术内容辗转相除法（求最大公约数）了。如果 (x*a) % n = 1 变成 (x*a) % n = 0 ，那x*a就是a和n公倍数了。如果这是小学奥数题，就先用辗转相除法得最大公约数，而最小公倍数用两数积除以最大公约数得出来。 rsa的原理数学基础欧几里得算法和小学奥数有着这样的联系，发现这点让我觉得不可思议又略有惊叹。看来学小学奥数有用，至少是可以为算法编程做准备的，学到了最朴素的数论。

辗转相除法（朴素欧几里得算法，中国余数定理，韩信点兵）¶

（引用自数论——欧几里得算法）

欧几里得算法，又名辗转相除法，是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

题目语义转化¶

求这样一个数x*a，能被a整除，被n整除余1。

这就很形似 有一个数除以3余2，除以5余3，除以7余4，除以9余5．这个数至少是? 被称为中国余数定理

扩展欧几里德算法¶

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

2，ab!=0 时

设 ax1+by1=gcd(a,b);

bx2+(a mod b)y2=gcd(b,a mod b);

根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

则:ax1+by1=bx2+(a mod b)y2;

即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)by2;

根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

…

同余方程 ax≡b (mod n)对于未知数 x 有解，当且仅当 gcd(a,n) | b。且方程有解时，方程有 gcd(a,n) 个解。

求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x, y为整数)

我的一个另类编程解法（融合了辗转相除法思想）。¶

算法描述¶

(x*a) % n = 1 对应方程 ax - ny = 1 的整数解

（a,n必定互质。如不互质可提取公因子，公因子*X=1，与X为整数矛盾）

化简降解方程分两情况：

a>=n 时变形为方程 (a mod n)x - n(y-[a/n]x) = 1 有整数解
a<n 时变形为方程 a(x-[n/a]a) - (n mod a)y = 1 有整数解

无论那一种都变回 ax - ny = 1 的形式。所以重复化简，因a,n互质，最后会到达a,n其一是1的情况。

例子说明：求能被9整除，被7除余1的最小数¶

9x=1(mod7) 对应方程 9x - 7y = 1 的整数解
变形有2x - 7(y-x) = 1 然后令 x_1=x, y_1=y-x 得方程 2x_1 - 7y_1 = 1
变形有2(x_1-3y_1) - y_1 = 1 然后令 x_2=x_1-3y_1, y_2=y_1 得方程 2x_2 - y_2 = 1 显然有解 x_2=1 y_2=1
好了，往上一步一步回溯得最初的x,y值 (x_2,y_2), (x_1,y_1), (x,y) 分别为(1,1),(4,1),(4,5)
9x = (94 mod 97) = 36 答：求能被9整除，被7除余1的数是36

python语言是弱递归化语言， python之父说递归都可以转成循环。所以我用递归后，转循环了。

Python代码:¶

################################################################################
# print "F: 答案错误 循环解法"
################################################################################
def gcd(a,n): # 辗转相除求最大公约数
    if a < n: a,n = n,a
    while n != 0: a,n = n,a%n
    return a

def exgcd(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     
    # print a,n
    if gcd(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    l = []
    while a!=1 and n!=1: # a,n总会有个先到1，触底条件就是1
        l.append((a,n))
        if a>n: a,n = a%n,n
        else:   a,n = a,n%a
    if a==1:    p = (n+1, 1)
    elif n==1:  p = (1, a-1)

    for a,n in l[::-1]:
        if a>n: p = (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
        else:   p = ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])
    return p

print exgcd(a,n)

################################################################################
# print "F: 答案错误 递归解法"
################################################################################
def gcd_r(a,n): # 辗转相除求最大公约数
    if a * n == 0: return a+n
    return gcd_r(a%n,n) if a>=n else gcd_r(a,n%a)
# print gcd(a,n)

def exgcd_r(a, n): # ax=1(mod n) 即 ax-ny=1 求x,y     # a,n总会有个先到1，触底条件就是1
    # print a,n
    if gcd_r(a,n) != 1:   raise Exception('fei hu zhi') # 先检查是否互质
    if a==1: return (n+1, 1)
    if n==1: return (1, a-1)
    if a>n:     
        p = exgcd_r(a%n, n)
        return (p[0] % n, (a//n*p[0]+p[1]) % a) # 这个值也是解，但没有最简：return (p[0], a//n*p[0]+p[1])
    else:
        p = exgcd_r(a, n%a) 
        return ((p[0]+n//a*p[1]) % n, p[1] % a) # 这个值也是解，但没有最简：return (p[0]+n//a*p[1], p[1])

print exgcd_r(a,n)

小学初中就知道数论，数论真有魅力，非常漂亮。

参考¶

数论——欧几里得算法 https://xuanwo.org/2015/03/11/number-theory-gcd/

欧几里德与扩展欧几里德算法 http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html

欧几里得算法（辗转相除法） https://my.oschina.net/u/1780798/blog/646739

https://zhidao.baidu.com/question/406531667.html?qbl=relate_question_3

威佐夫博弈：取石子游戏算法——挑战PythonTip

2017-12-16T16:30:00+08:00

PythonTip 里未攻克的题目，如取石子游戏，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:¶

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目a和b，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。如果你是胜者，输出Win,否则输出Loose。例如，a=3,b=1, 则输出Win(你先在a中取一个，此时a=2，b=1,此时无论对方怎么取，你都能将所有石子都拿走).

分析（动态规划）：¶

我的思路是转变成图形化表示，二维表中点(x,y)用W表示会赢，L表示为输。

(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。所以可以用动态规划。根据之前失败坐标的集合推算本行的失败坐标。

并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。

当我从(0,0)开始，填到(a,b)时就知道结果了。

明显(x,y)和(y,x)结果一样，因此我刚开始只填半个表，导致结果不准，看了其他人的奇异坐标才明白到自己的错误。从新填好。

错误填表分析过程¶

我根据这个过程写出版本一代码。

正确填表分析过程¶

我本来猜测需要推到前面代码从来。幸运的是，运行正常的版本二的代码只在版本一加一行就可以了。

下面是我的算法代码，比较简洁。动态规划确实强大，另外还有分治法也强。

Python代码:¶

################################################################################
# print "T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误，改正" 
################################################################################
if a < b: a,b = b,a

m = [(0,0)]  # 失败的坐标纪录池
for i in range(1,a+1):
    for j in range(i+1):
        # if i == j or j == 0: # win
        #     continue

        for x in m:
            if (i-x[0]) == (j-x[1]) or i == x[0] or j == x[1]: # win
                break
        else:  # else 是for的部分，break for的时候也break了else
            m.append((i,j)) # 版本一：二维表只填半边，所以只有这行代码
            m.append((j,i)) # 版本二：二维表两边都填，多加这一行就OK了
        #print i,j,m

print "Loose" if (a,b) in m else "Win"

Python解无穷大数除法算法——挑战PythonTip

2017-12-15T16:30:00+08:00

PythonTip提供了一个不错的学习算法平台，大学毕业前挑战进入了前几名pythonwood解题数量。

当时有些未攻克的题目，比如密码生成题目，如今积累工作经验之后从新挑战，成功了。把过程记录分享下。

描述:¶

生活在当代社会，我们要记住很多密码，银行卡，qq，人人，微博，邮箱等等。小P经过一番思索之后，发明了下面这种生成密码方法：给定两个正整数a和b, 利用a / b我们会得到一个长度无限的小数(若a / b不是无限小数，比如1/2=0.5,我们认为0.5是0.5000000…，同样将其看做无限长的小数），小P将该小数点后第x位到第y位的数字当做密码，这样，无论密码有多长，小P只要记住a,b,x,y四个数字就可以了，牢记密码再也不是那么困难的事情了。现在告诉你a,b,x,y（0 < a,b <= 20132013, 0 < x <= y < 100000000000),请你输出密码。例如：a = 1, b = 2, x = 1, y = 4, 则 a / b = 0.5000000…, 输出小数点后第1到4位数字，即5000

分析：¶

计算机浮点计算有精度问题，所以直接除法得结果的思路不通。这次我想到小学的列竖式除法算法本身是可以解无穷除法的。于是，这道题就是把我们小学早已学过的算法，用代码表示出来。

下面包含几个算法，都比较简介，比较pythonic（在网上看到是算法代码普遍臃肿）。只有最后的循环记录法是在规定时间内通过的。

Python代码:¶

#! /usr/bin/env python
#coding: utf8

# 返回a除以b的商的小数部分的第x位到第y位
a = 22; b = 300003; x = 1; y = 50

################################################################################
print "F: 不能引入sys 模拟手工除法"
################################################################################
import sys

t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        sys.stdout.write( str(t//b) )
    t %= b
print

################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
code = ""
t = a % b

for c in range(y):
    t *= 10
    if c+1 >= x:
        code += str(t//b) 
    t %= b
print code


################################################################################
print "F: 时间复杂度不足 变除为乘补零难"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(t * 10 ** y // b)[x-1:]


################################################################################
print "F: 时间复杂度不足 同上"
################################################################################
t = a % b
lzero = ""
_t = t * 10
while _t < b:
    lzero += "0"
    _t *= 10
print lzero + str(int( str(t) + '0' * y ) // b)[x-1:]


################################################################################
print "T: 挑战成功 循环小数记录法"
################################################################################

code = "" # 遇见循环即止
rep = ""  # 循环体
left = [] # 余数池
t = a % b

for c in xrange(y):
    if t in left:
        rep = code[left.index(t):]
        break
    else:
        left.append(t)
    t *= 10
    code += str(t//b) 
    t %= b
else:
    print code[x-1:]

print ( code + rep * ( (y - len(code))/len(rep) ) + rep[: ( (y - len(code))%len(rep) ) ] )[x-1:]

Python量化之数据处理——小数浮点精度问题解决

2017-04-18T14:03:00+08:00

量化金融刚结果：计算出差了一分钱的涨停价¶

量化金融用Python，最近在处理浮点问题的时候，发现一个问题，比较有意思，分享出来。

python计算79.035的四舍五入结果是79.03，这是错误的。

以下是IPython中输入程序语句，IPython能即时编译运算和输出结果。

# 计算71.85的涨停价
In [1]: 71.85 * 1.10
Out[1]: 79.035
# 涨停价四舍五入应该是79.04，但由精度损失，只有79.03。
In [2]: round(71.85 * 1.10, 2)
Out[2]: 79.03

原因分析¶

这个问题和Python语言本身无关，原因是浮点数即小数在计算机的二进制化标准有关。

所以很多计算机语言都存在浮点精度损失问题，但庆幸python已有解决方法。Python已经写出了一些库，能屏蔽下层计算机架构带来的浮点问题。

Python浮点运算的正确方法¶

Python解决浮点精度问题的办法是使用decimal库。

In [26]: from decimal import *

In [31]: print Decimal(79.035).quantize(Decimal('.01'), rounding=ROUND_HALF_UP)
79.04

为此我特地写了邮件，写出期望优矿支持引入decimal库。得到回复说优矿下一个版本中引入。

（更新：到了5月份确实可以引入decimal库了，至此问题解决）

参考¶

谈谈关于Python里面小数点精度控制的问题 http://www.cnblogs.com/herbert/p/3402245.html

Python 为什么不解决四舍五入(round)的“bug”？ https://www.zhihu.com/question/20128906

python:0.1 + 0.2 == 0.3:False https://stackoverflow.com/questions/588004/is-floating-point-math-broken

round() in Python doesn’t seem to be rounding properly https://stackoverflow.com/questions/56820/round-in-python-doesnt-seem-to-be-rounding-properly

Linux迷+Python粉 - python

神奇的环境bug导致python3中出现udc开头字符串

注意：LANG=zh_CN.UTF-8与LANG=en_US.UTF-8不可混淆！¶

当时环境与功能：¶

出bug的运行流程：¶

调试发现:¶

问题定位:¶

问题解决：¶

原因探究：¶

python repr输出udc开头字符串， print(参数)导致异常¶

RSA原理：欧几里德算法与奥数内容辗转相除法——挑战PythonTip

描述:¶

分析：¶

辗转相除法（朴素欧几里得算法，中国余数定理，韩信点兵）¶

题目语义转化¶

扩展欧几里德算法¶

我的一个另类编程解法（融合了辗转相除法思想）。¶

算法描述¶

例子说明： 求能被9整除，被7除余1的最小数¶

Python代码:¶

参考¶

威佐夫博弈：取石子游戏算法——挑战PythonTip

描述:¶

分析（动态规划）：¶

错误填表分析过程¶

正确填表分析过程¶

Python代码:¶

Python解无穷大数除法算法——挑战PythonTip

描述:¶

分析：¶

Python代码:¶

Python量化之数据处理——小数浮点精度问题解决

量化金融刚结果：计算出差了一分钱的涨停价¶

原因分析¶

Python浮点运算的正确方法¶

参考¶

例子说明：求能被9整除，被7除余1的最小数¶