Linux迷+Python粉 - pythontip

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:]

寒假挑战PythonTip（一人一python）总结——算法是程序的灵魂，程序员的心法

2014-02-16T14:23:00+08:00

2014年2月中旬，我上升到挑战python英雄榜第3名。这是我寒假修炼算法的成果之一。来一下总结吧！

Linux的创始人Linus Torvalds在一次演讲中有一段涉及“什么才是优秀程序员”的话：

“烂程序员关心的是代码。好程序员关心的是数据结构和它们之间的关系。”

由这句话的启发开始，加上我越来越觉得自己编程能力不足，码代码经常要重构，逻辑思维不过细腻谨慎。正是过于关注代码，完成率所致。我已经学过C/C++/nasm/java/python/html/js/jq/shell等等语言，对计算机世界的工作原理有比较好的认识，但代码能力一直上不去。我想算法，就是我的瓶颈。于是有了以下故事。

第一阶段¶

寒假开始，我便在项目工作之余扫pythontip上的题。十几天里，有时一天7、8道题，有时2、3题，我的排名慢慢从第N页到第4页到第2页，让后到第1页。

当我扫完101题后，我成功了42题，刚好排在第一页最后一名。然后我休息了一下，继续有成功几题。这大概就是我的无算法时代极限了。

第二阶段¶

我网搜博客，算法，学习排序。好来买了《编程珠玑》和《编程之美》，边看边攻克pyhtontip上的题目。

在PythonTip 上的一些水题这博客中学习了很多，尤其是看到问题一句话就解决时，恍然大悟。

1、有很多利用lambda, reduce, map, zip, 列表分片/解析, sum, max, min, divmod, round, hex/oct/bin; set,list,dict; 一句话解决的。这是我认为python强大原因，非常好用。

2、关于二进制‘1’的处理是非常妙的，这些题往往诠释了计算机较人类思维不同的特性，以及如何能让程序员思考得更“计算机”一些。在《编程之美》，上面提到的博客中都有提到。

3、独立思考，让后比较，我获得更多。在最大连续子序列，最大非连续子序列，最长回文子字符串中，我收获很经典的算法。同时还想出来与Manacher算法一拼的做法。

L = '#'.join(list(L)) # len is odd now!
l = len(L)

o,r=0,0 # 圆心，半径(不计圆心)
for i in range(1,l):
    if i+r<l and L[i-r:i] == L[i+r:i:-1]: # 移到:最右方便来计算
        o,r=i,r
        while i+r+1<l and L[i-r-1] == L[i+r+1]:
            r += 1
    # print L[o-r:o+r+1]

L1 = L[o-r:o+r+1]
t1,t2 = L1[::2],L1[1::2]

print t1 if any(i!='#' for i in t1) else t2

3月13日的格式优化版：

L = '#'.join(L)
L = '#'+L+'#'  # 因为这句，末尾print语句统一了。

o,r = 0,0
l = len(L)
for i in xrange(l):
    if i+r >= l:
        break
    if L[i-r:i]==L[i+r:i:-1]:
        o = i

        j = r+1 # 尝试加一
        while o-j>=0 and o+j<l and L[o-j] == L[o+j]:
            j += 1
        r = j-1

print L[o-r+1:o+r:2]

又经过10多天，我又扫完一遍题，这次我以72题的成绩排在GodIsCoding和YOSHINO之后第三名。

总结：¶

做完之后，我的感觉是，python是很美很简单语言，如其名。

生活题外话：¶

没能及时报考C语言二级，非常遗憾，英语六级不知道报呢还是不报好。

Linux迷+Python粉 - pythontip

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

描述:¶

分析：¶

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

题目语义转化¶

扩展欧几里德算法¶

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

算法描述¶

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

Python代码:¶

参考¶

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

描述:¶

分析（动态规划）：¶

错误填表分析过程¶

正确填表分析过程¶

Python代码:¶

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

描述:¶

分析：¶

Python代码:¶

寒假挑战PythonTip（一人一python）总结——算法是程序的灵魂，程序员的心法

第一阶段¶

第二阶段¶

总结：¶

生活题外话：¶

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