Python编程:初等数学题解(三)

Python编程:初等数学题解(三)

化乘除为加减
我们知道四则混合运算加减乘除是算数的基础,这里面乘和除又可以通过加减来实现,所以加减是更为基本的运算。这些我们小学就知道了,人类是这么走过来的,计算机也是这么走过来的。

我们先来实现两个数的乘法,ab,按照定义就是把a自加b次,如34,就是把3自己加自己总共加四次。

程序如下:

def multiply(a,b):

    if a==0 or b==0:

        return 0

    elif a==1:

        return b

    elif b==1:

        return a

    else:

        r = 0

        while b>=1:

            r = r + a

            b = b - 1

        return r

print(multiply(123,12))

程序的核心就是那个while循环,将a自加b次。

你肯定看出来了,上面的程序只能计算正整数,负数算不对。所以我们再考虑一下正负数。有四种情况:+ +,+ -,- +,- -。对这四种情况,我们得出它的结果的符号,然后化为正数进行计算。程序如下:

def multiply(a,b):

    sign = 1  #default to positive

    if a>0 and b>0:

        sign = 1

    elif a>0 and b<0:

        sign = -1

        b = 0 - b  # set b to positive

    elif a<0 and b>0:

        sign = -1

        a = 0 - a  # set a to positive

    elif a<0 and b<0:

        sign = 1

        a = 0 - a  # set a to positive

        b = 0 - b  # set b to positive



    if a==0 or b==0:

        return 0

    elif a==1:

        return b

    elif b==1:

        return a

    else:

        r = 0

        while b>=1:

            r = r + a

            b = b - 1

        if sign == 1:  # positive

           return r

        else: #negative

            return 0 - r

好。我们通过加法实现了乘法,循环这么多次,很笨很笨,但是确实是能干活儿。同样我们也可以用减法实现除法。如果有移位操作,我们会极大提高效率。

我们再琢磨一下,如果b是实数就算不对了,因为有小数部分,而上面的循环只对整数有效。实际上实数是由两个整数中间加点组成的,所以还是可以处理。有点复杂,暂不介绍。

好奇的你又会开始问了,计算机内部真的是这么干的吗?答案是部分是,实际上,计算机内部是通过加法和移位操作联合起来实现乘法的,为了处理负数和实数,还需要用到补码和规范化存储规范。后面我们会讲到。

接下来看一下移位操作怎么极大地加快了计算。小学学习的就是这个过程。

举个例子125*103,我们上面的程序需要循环103次,看我们怎么移位加速:

按照十进制的定义,103 = 1102+0101+3*100。这样只要把125移位几次再相加即可。分成三部分:

1*102 将125移位2次,再乘1,得到12500

0*101  0值,不计算

3*100 将125移位0次,再乘3,得到375

然后把三部分相加12500+0+375=12875。

同样得到结果,只用了三次移位外加三次循环。

其实,Python里面是有移位操作的<<。但是结果有点跟想的不一样,你可以试一下45<<,结果会返回90,而不是450,你会有一点吃惊。原因是因为计算机内部用二进制表示,左移一次等效于乘2。我们可以自己模拟写一个shift函数:

def lshift(a,n):

    r = a

    while n>=1 :

        r = r * 10

        n -= 1

    return r

这个函数将一个数乘10,100,1000,相当于移位n次。实现用到了乘法,这个只是示意,实际计算机里面移位是一个独立的基本运算。

这里我们还用到了一个新的表达 n -= 1,这是一个缩写,等同于 n = n-1。

再用这个lshift()改写乘法程序:

def multiply(a,b):

    sign = 1

    if a>0 and b>0:

        sign = 1

    elif a>0 and b<0:

        sign = -1

        b = 0 - b

    elif a<0 and b>0:

        sign = -1

        a = 0 - a

    elif a<0 and b<0:

        sign = 1

        a = 0 - a

        b = 0 - b



    if a==0 or b==0:

        return 0

    elif a==1:

        return b

    elif b==1:

        return a

 

        r = 0 #result

        s = str(b) #convert to string

        for i in range(0,len(s)): # for each digit in the integer string

            n = int(s[len(s)-i-1]) # get the digit from right to left

            c=lshift(a,i) #shift

            while n>=1:

                r = r + c

                n = n - 1

        if sign == 1:

           return r

       

            return 0 - r

程序的关键部分是那个嵌套循环:

        for i in range(0,len(s)): # for each digit in the integer string

            n = int(s[len(s)-i-1]) # get the digit from right to left

            c=lshift(a,i) #shift

            while n>=1:

                r = r + c

                n = n - 1

这里我们看到了一个for语句,这是一个固定次数的循环,次数就是数字串的位数,如对103,循环次数就是3. i的取值依次为0,1,2。之后,根据位置从右往左拿到该位置上的数字,即程序语句:n = int(s[len(s)-i-1]),如对103,第一次i为0,那么就是拿的3-0-1=2这个位置的数字,这个位置是103的最右边一位(记得编号是从0开始的,所以最后一位也就是第三位的位置编号为2)。拿到该数字后,先把被乘数移位,移i次,比如对103中的3,就移位0次,相当于不动,对1就要移位两次。然后拿着这个移位后的数乘以n(通过加循环n次实现),即对103中的3,我们把125循环三次相加得到375,对于103中的0,我们不计算,对于103中的1,我们把12500循环1次相加得到12500,所以最后的结果为12875。

顺便提一下,while循环里的r=r+c, n=n-1写成r += c, n -= 1更加显得像是高手。

测试一下print(multiply(125,103))。

再解释一下二进制下的乘法实现,为以后讲计算机内部实现做点准备。

我们已经知道,计算机内部用二进制表示数,101010…,其数值等于k2n+K2n-1+…+k*20。

所以ab就相当于ak2n+aK2n-1+…+ak*20,即把a移位后累加。二进制的好处是它只有0和1两个数字,所以不用考虑别的,直接移位或者不移位就可以了(十进制里面还要考虑个位数的乘法)。

试一下65,6二进制表示为110,二进制表示为101,我们计算110101的值:

  1. 101的右边第一位为1,将110左移0位得到110

  2. 101的右边第二位为0,因此不计算(结果当成0)

  3. 101的右边第三位为1,将110左移2位得到11000

  4. 把1,2,3三步的结果相加:11000+0+110=11110,该结果就是30。

除法类似的,是通过减法和移位操作实现的,我们看一个例子。

我们看815/23,手工按照这几步从高位到低位做:

  1. 先用8除23,商为0,余数为8;

  2. 余数8左移,得到80,再加上第二位1,得到81,除23,商为3,余数为12;

  3. 余数12左移,得到120,再加上第三位5,得到125,除23,商为5,余数为10。

计算完毕,得到商为035,即35,余数为10。

程序如下:

def lshift(a,n):

    r = a

    while n>=1 :

        r = r * 10

        n -= 1

    return r



def divide(a,b):

    sign = 1

    if a>0 and b>0:

        sign = 1

    elif a>0 and b<0:

        sign = -1

        b = 0 - b

    elif a<0 and b>0:

        sign = -1

        a = 0 - a

    elif a<0 and b<0:

        sign = 1

        a = 0 - a

        b = 0 - b



    if a==0:

        return 0

    elif b==1:

        return a

   :

        result = 0

        remaining = 0

        s = str(a)

        for i in range(0,len(s)): # for each digit in a

            n = int(s[i]) # get the digit from left to right

            divident = lshift(remaining,1)+n

            if divident>=b:

                #divide

                count=0

                while divident>=b:

                    count = count + 1

                    divident = divident - b

                result = lshift(result,1) + count

                remaining = divident

          

                result = lshift(result,1) + 0

                remaining = divident



        if sign == 1:

            return result

      

            return 0 - result

你们按照乘法的过程自己把除法跟踪一遍。

测试print(divide(815,23))。

二进制除法也是同样的原理,也因为只有0,1两个数,所以比十进制简单,不用除个位数,只需要比大小,大就是1,小就是0。

我们试一下85/6,用二进制表示为1010101/110,按照如下步骤操作:

  1. 先拿最高位,1,跟110比大小,小,商为0,余数为1;

  2. 余数左移,为10,再加上第二位数字0,得数还是10,跟110比大小,小,商为0,余数为10;

  3. 余数左移,为100,再加上第三位数字1,得数是101,跟110比大小,小,商为0,余数为101;

  4. 余数左移,为1010,再加上第四位数字0,得数是1010,跟110比大小,大,商为1,余数为100;

  5. 余数左移,为1000,再加上第五位数字1,得数是1001,跟110比大小,大,商为1,余数为11;

  6. 余数左移,为110,再加上第六位数字0,得数是110,跟110比大小,大,商为1,余数为0;

  7. 余数左移,为00,再加上第七位数字1,得数是1,跟110比大小,小,商为0,余数为1;

计算完毕,最后的商为0001110(即14),余数为1。

现在我们就知道把四则运算化成了加减运算,以后我们还会进一步将减法化为加法。这样从原理上,只需要有加法操作就可以了。万法归一。

计算机好神奇啊,你肯定会这么想。它通过简单数字(0/1)和基本运算叠加累计,最后构成了复杂的运算。但是这么想并不全对,更准确的说法是计算机很笨而人很神奇,计算机只能做最简单的操作,而人通过算法一步步让计算机完成了复杂运算。一直到现在发展出Internet,智能手机,发射火箭,穿越星际空间,传播视频,远程医疗,破译DNA,发展无人驾驶汽车,但是我们须知循着路径回溯,一层层破解技术,最后的内核就是一个简单极了的操作孤单地摆在我们眼前。正如大千世界,分析到了最后,就只有几个基本粒子漂浮在虚无缥缈的时空。古来圣贤皆寂寞。

地球上现存的人类只有一种,统一叫做智人(Homo Sapiens)。

扩展一下,如果你在中学学得多一点,有可能学到了复数。我们的程序又不能支持了。这里我们需要一个新的表达,用一个数是不行,复数包含实部和虚部,所以Python用12 + 3j表示。注意这里用的是j,不是数学中的i,这么做是为了遵从电子工程界的惯例。

有了这个知识,我们也是可以写出程序来实现复数域的运算的。我不演示程序了,你们自己做。

 

 

上一篇:220kV东山变工程电气部分初步设计任务书


下一篇:【Ybtoj 第19章例3】宝物筛选【背包问题】