【Pyhon 017讲心得体会】【欧几里得算法和进制转换】

heidern0612

写的内容都是自我思考的过程，难免有疏漏，有错误的地方欢迎广大鱼油给予指正！


1、没听说过DRY，听过DIY，（Do it yourself~）..自己动手努力吧！！


2、函数的参数需要的是变量，而不是一个无法改动的元祖。


3、计算次幂：

def power(x, y):                   #定义一个power函数，包含X、Y变量。
    result = 1                        #result初始化下，值为1.
    
    for i in range(y):                #for循环
        result *= x                #result自增乘X。

    return result                        #返回result给函数power

print(power(2, 3))            #for循环从0到2，第一次循环0，result为2; 第二次循环1，result =2*2 =4；第三次循环2，result为4*2 = 8 ；打印函数。

Y值只是起了一个for循环计算次数的作用，result里则是用于基数x 乘以 次数y。



4、欧几里得算法科普：

欧几里德算法（Euclidean algorithm），又名辗转相除法， 是求最大公约数的一种方法。
它的具体做法是：用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

最大公约数：简单说就是能同时整除它们的最大正整数简写GCD。
如图：




辗转相除法定义：对于任意两个自然数a和b，如果q和r是a除以b的商和余数，那么a和b的最大公因数等于b和r的最大公因数。（这个定义还是比较公道的，起码能知道怎么回事，百度太不科普了）

求解过程可描述如下：

（1）a除以b，得到商q和余数r1；

（2）若r1=0，则a和b最大公因数为b；

（3）若r1≠0，则继续（1），即b除以r1得到商q和余数r2；

（4）若r2=0，则a和b最大公因数为r1；

（5）若r2≠0，则继续（1），即b除以r2得到商q和余数r3；

（6）重复上述步骤，直到能够整除，余数为0时的除数就是a和b的最大公因数。

举例：a= 53   b=17

（1）53 （a） / 17(b) ,得到商3(q)和余数2(r1)

（2）2!=0

（3）17 / 2，得到商（8）和余数 1(r2)

（4）17 / 1，得到商（17）和余数0（r3）

余数为零时，除数（1）就是a（53）和b（17）的最大公约数

def gcd(x, y):
    while y:     #y不为零时，开始循环;
        t = x % y  #一次循环，t =53 % 17 ,余数为2, t = 2;二次循环， t = 17/%2 = 1;三次循环，t = 2% 1 = 0;
        x = y        #一次循环，x = 17 ;二次循环，x = 2;三次循环 x = 1
        y = t        # 一次循环,y = 2 ; 二次循环 ,y = 1;三次循环 y = 0;跳出当前循环；
    return x          #返回x的值为17;返回x = 2 ；返回x的值为 1；
print(gcd(53, 17))                打印当前的值，也就是返回的X值，为1；

5、除2取余，十进制转二进制。

定义：十进制整数转换为二进制整数采用"除2取余，逆序排列"法。

具体做法是：

1、用2整除十进制整数，可以得到一个商和余数；

2、再用2去除商，又会得到一个商和余数；

3、如此进行，直到商为小于1时为止，然后把先得到的余数作为二进制数的低位有效位，后得到的余数作为二进制数的高位有效位，依次排列起来。


分析下小甲鱼老师的代码：

def Dec2Bin(dec):
    temp = []
    result = ''
    
    while dec:                                   #假定当前dec为10，开始一次循环；二次循环，dec=5;三次循环dec = 2；四次循环dec = 1；五次循环dec = 0,跳出while循环。
        quo = dec % 2                        #quo求的就是余数，商5余数0；quo值为0；二次循环quo = 5%2 = 1;三次循环quo = 2%2 = 0;四次循环quo = 1%2 =1
        dec = dec // 2                        #一次循环dec = 10//2 = 5; 二次循环dec = 5//2 = 2;三次循环dec = 2 //2 = 1 ;四次循环dec = 1//2 = 0
        temp.append(quo)                #一次循环，把0加入到temp空列表里；二次循环把1加到temp列表里，temp当前为[0,1];三次循环把0加入temp,temp =[0,1,0];四次循环把1加入temp,temp = [0,1,0,1]

    while temp:                                                #跳出上个循环，执行此循环,当temp不为零或不为空时：
        result += str(temp.pop())                   #result 依次等于temp从尾部开始弹出的值（倒序排列），最终result经过temp四次弹出后，temp为False，跳出循环，result =str[1,0,1,0]   ="1010"
    return result                                                返回result的值。

print(Dec2Bin(10))                                        #打印dec2Bin这个函数。

分析好分析，难点是不好做，pop神来之笔，我是想不出这个办法，求余跟求商很有用，但是要会用才行。

savesr

支持下，刚学过这节课

小高二爸。

这分析实在是太棒了。

段软w

哇！谢谢分析！看好久都弄不懂 看你的就豁然开朗啦

xxwoaini897

def power(x,y):
    mmp=1
    for i in range(y):
        mmp*=x
    return mmp

楼主，这里的为什么要把mmp赋值为1呢？然后这里的mmp=mmp*x的用意是啥?

def mmp(x,y):
        print(x<<y-1)

刚百度的时候无意发现这样也可以求x^y值，可以这样写么？感谢楼主解惑。

heidern0612

xxwoaini897 发表于 2019-11-21 23:33
楼主，这里的为什么要把mmp赋值为1呢？然后这里的mmp=mmp*x的用意是啥?

刚百度的时候无意发现这样也可 ...

1、1的任何次幂结果都是自己。所以这里初始化为1.

2、能算出来，自己验证下结果对就是可以的。并不是说老师的方法就是最好的。

酒醉三分醒

利用pop()把列表中的余数逆转赋给result这个做法真的太妙了完全想不到

永远的渣滓

真的把pop()用得淋漓尽致了，谢谢楼主把我从坑里带出来，我想了好久

wuyanzulqq

永远的渣滓 发表于 2020-4-5 12:16
真的把pop()用得淋漓尽致了，谢谢楼主把我从坑里带出来，我想了好久

pop不是移除列表中的一个元素(默认最后一个元素),并且返回该元素的值嘛？这个pop我还是没懂

wuyanzulqq

酒醉三分醒 发表于 2020-2-22 11:01
利用pop()把列表中的余数逆转赋给result这个做法真的太妙了完全想不到

这个pop我还是不懂