0.前言

上一篇文章主要讨论了Python列表的常规使用，注重的是语法层面，这一次作业的难度上升了不少，因不仅涉及语法层面，还有需要一定的思考。有的问题在我初学Java的时候也碰到了，那时候觉得才是非常难，这次用Python实现，因为思路比较清晰，写起来不是那么吃力。

1.练习

1.1 输出水仙花数

所谓水仙花数是指1个3位的十进制数，其各位数字的立方和等于该数本身。例如：153是水仙花数，因为153 = 1^3 + 5^3 + 3^3 。

这道题算是一个比较经典的语言学习的入门练习题，从这里可以延伸许多的算法知识。先分析一下，首先这个题，我们需要拿到这个三位数的个位，十位和百位，然后把这三个数分别立方之后与原数相比，相等则输出，反之继续寻找。重点在于如何拿到这三个数，最朴素的想法就是通过模除的形式得到这三个数字并分别储存。代码如下：

l = range(100, 1000)
for i in l:
    a = int(i / 100)#Python中默认相除不是取整的，需要转换成int，这个int是向下取整，正好符合预期
    b = int((i - a * 100) / 10)
    c = int(i - a * 100 - b * 10)
    if i == a ** 3 + b ** 3 + c ** 3:
        print(i)

思路很简单，就是需要注意Python中默认相除不是取整的，需要转换成int，这个int是向下取整，正好符合预期。如果需要向上取整有专门的方法，不过多介绍，但如果是我更习惯向下取整后加一这个更通用的方法。

另外这个题可以扩展成一个函数用来得到一个指定的数的各个数位的数值，基本上可以简化成如下代码：

def num(n):
    count = 1#从个位起第count位
    while n - 10 ** (count - 1) >= 0:#判断循环终止条件，比如524-10**2>0继续，524-10**3<0终止
        #从个位数开始，先模除，然后再除商取整即可得当前位的数值
        m = int((n % (10 ** count)) / (10 ** (count - 1)))
        print("从个位数第" + str(count) + "位是" + str(m))
        count = count + 1#加一继续循环求下一位

写成函数之后的区别在于为了方便起见，采用了从最低位开始，当然从最高位开始也可（我之前用Java就是从最高位开始的）。

取数位值的算法除了用数学的方法还可以使用字符串分割。使用字符串分割适用于一些不需要数学计算的地方，如果单纯的取值用字符串分割效率很高，而如果涉及计算，比如求水仙花数，字符串还得转化为数字反而降低了效率。这种思想在ACM等也经常运用。

1.2 打印九九乘法表

这个也算上一个比较简单的入门程序题了，两个for循环即可，代码如下：

for i in range(1, 10):
    for j in range(i, 10):# 为了去重，比如1*9和9*1，j从i开始取值
        print(str(i) + "*" + str(j) + "=" + str(i * j), end=",")#end=","表示用，分割结果
    print()#打印换行

需要注意的一个是去重，一个是换行。

1.3 判断一个数是否为素数

这也是很经典的。还是说一下思想，判断从2到n

^0.5

之间是否有能被n整除的数，有返回是，无则不是。至于为什么是n

^0.5

,很简单，因为n

^0.5

* n

^0.5

=n，如果存在一个数大约n

^0.5

那么这个数肯定需要乘一个小于n

^0.5

的值等于n，那么这个值肯定在前面出现过了。另外在n>4的情况下，n

^0.5

<n/2,也就是说相对于n/2，需要判断的次数少了。代码如下：

def prime(a):
    for i in range(2, int(a ** 0.5) + 1):#循环遍历
        if a % i == 0:
            return str(a) + '不是素数'
    return str(a) + '是素数'

1.4 编写程序，计算组合数C(n,i)，即从n个元素中任选i个，有多少种选法？

这个题目乍一看貌似不容易，但我们已知



所以我们只需要能写出一个算出阶乘的方法就行了。这个方法对于初学者还是有一定的难度的（我刚刚学Java时候，老师让我们试试能不能写出一个算出n!值的程序，我想了好久总是感觉差一步），后来就理解了就比较简单。

分析一下，5!=5* 4 * 3 * 2 * 1, 4!=4* 3 * 2 * 1, 3!=3 * 2 * 1，发现没有，5！=5

4！，n!=n

(n-1)!，我们只要找到一个变量储存我们上一步得到的值然后乘以当前的值即可。所以如果我们从1！开始算起，一步一步最终到达n的阶乘，这个算是比较朴素的想法。如果我们使用套娃的思想来做的话，想求n！，那么我要求（n-1）！，再求（n-2）！……，只到需要我求1！=1，我再往回带，得出2！，3！……，直到n！。我们发现求解n！和（n-1）！阶乘的方法几乎无差。那么我就可以在求n！时候把参数变成(n-1）求（n-1），最后无限套娃。代码如下：

#求阶乘
def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

#求组合数
def combination_number(n, i):
    return factorial(n) / (factorial(i) * factorial(n - i))

1.5 计算理财产品收益，假设收益和本金一起滚动

这题不算难，本质上就是profit = money * (interest + 1)，只不过本金money一直在变，也可以用上个题的套娃思想（递归）。这里换一个思路，代码如下：

#参数分别为起始本金，日利率，时长
def financial_management(money, interest, day):
    profit = 0
    while day >= 1:
        profit = money * (interest + 1)
        money = profit
        day = day - 1
    return "%.2f" % profit #"%.2f" %表示保留两位小数，如果2换成3表示3位小数，以此类推

1.6 编写代码实现冒泡法排序

这题我印象很深，在我学到Java的for循环的时候，老师让我想一个排序的算法，我最开始的思想就是冒泡排序，但当时受限时间，没有完全做出来，但基本成型。学完数据结构之后，了解了那么多的排序算法，发现冒泡排序是最容易想到且最容易编码实现的。本质就是不断比较相邻两个数的大小，如果起那么的数大于后面的数（默认升序排列），就把两个数交换位置，如此循环n次即可得出正确结果。代码如下：

def bubble_sort(l):
    l = list(l)
    for j in range(1, len(l) + 1):#控制循环趟数
        for i in range(0, len(l) - 1):#控制比较次数
            if l[i] > l[i + 1]:
                l[i], l[i + 1] = l[i + 1], l[i]#Python中的交换数值的简便写法，感觉很Python
    return l

1.7 二分法查找

二分法查找的思想很简单，就是不断的取半来缩短查找的时间，前提是序列是有序的。代码如下：

def binary_search(t, l):
    if t not in l:
        return "查找失败," + str(t) + "不在列表中"
    font = 0
    rear = len(l)
    mid = int((font + rear) / 2)
    #之所以要(rear - font) > 1是因为如果还剩下标1和2这两个元素时，向下取整值恒为1，而要查找的是2，此时就会让mid一直为1陷入死循环。
    while t != l[mid] and (rear - font) > 1:
        if t > l[mid]:
            font = mid
            mid = int((font + rear) / 2)
        else:
            rear = mid
            mid = int((font + rear) / 2)
    if t == l[mid]:
        return '查找成功,' + str(t) + '的下标为' + str(mid)

1.8 递归算法求解汉诺塔问题

这个算是这些题中最难的一个，在我学Java的时候就不会，不过在我看了一下大神写的技术博客之后才懂了。这样想，假设只有两个盘子的时候，我们只只需要把上面的盘子挪到B上，最下面的挪到C，再把小的挪到C上。理解这个之后，我们想一下，不管有多少个盘子，

都需要有一步把最大的盘子从A挪到C

，而因为需要从A上挪那么A上肯定只有一个最大的盘子（因为最大的盘子肯定在最下面而且如果还有别的盘子，肯定是在最大盘子上面，也就是还需要挪其余的盘子，但终归有这么一步），

而此时C肯定是空的

，因为如果C不为空，它就无法放最大的盘子，还需要把C清空之后把最大的盘子放在最下面。那么剩余的盘子肯定都在B上且肯定是按照顺序堆放的。是不是相当于我们把n-1个盘子从A挪到了B。而我的目的是把n个盘子从A挪到C，像不像阶乘？找到了通用的表达式，我们再找一下规律。**如果我们把n-1个盘子看成一个整体，**这句话很关键，那么最开始A上就只有两个盘子，先把最上面的盘子放在B上，再把最大的盘子放在C上，最后把B上的盘子放在C上。是不是找到规律了。代码如下：

def hanoi(n, a, b, c):
    if n == 1:
        print(a + "->" + c);
    else:
        hanoi(n - 1, a, c, b)#先把n-1个盘子从A挪到B（B和C交换位置是因为在n-1个时候，B是目的地，C是过渡）
        print(a + "->" + c)#此时n-1个盘子已到达B，我们需要把A上仅存的那一块最大的放到C上
        hanoi(n - 1, b, a, c)#此时的问题变成把n-1个盘子在A为过渡的情况下从B到C

先开始可能不懂，多读多想就明白了。关键是要理解把n-1个看成整体，问题就转化成两个盘子转移到C上的问题了，以此类推。

1.9 编写程序，输出星号组成的菱形

又是一道经典题目，思想很简单，根据空格和* 之间的数量的关系输出，数量关系很简单，中学生都会。

代码如下：

def diamond(n):
    a = n
    b = n
    for i in range(1, n + 1):
        print((a - 1) * ' ', (2 * i - 1) * '*')#前面的*是代表输出多少个后面的字符，相当于乘，比较Python的写法
        a -= 1
    for j in range(1, n):
        print(j * ' ', (2 * b - 3) * '*')#上下两部分不一样所以要单独写
        b -= 1

1.10 编写程序，实现十进制整数到其他任意进制的转换

这题的解法很多，但我自己直觉的方法还是使用递归，感觉也比较简单而且容易理解

我的想法是这样的，比如原十进制数位a，要转化成n进制（简单起见设为n<10）,每次用a/n，获得的余数r肯定比n小，是最后一位，商为s，a=s*n+r，如果我把s也用n进制表示了，不就得出结果了吗？而且每进行一次，我都余数用字符串拼接起来，那么下面就是套娃了。原代码如下：

def transfer(a, n):
    s = a // n  # s为商，//表示取商
    r = a % n  # r为余数
    if s == 0:  # 如果s==0，代表每一位（余数）都是比n小的数，就完成了
        return r  # 返回余数即可，比如7%8=7，那么7就是8进制的数
    else:
        return str(transfer(s, n)) + str(r)#求s用n进制表示的值和当前位的数值拼接

这题可以好好体会一下，也是我自己想的方法。这也是解决这题一个比较简洁的方法了。

2.总结

这次的学习主要动了很多脑子，大量使用了递归思想。而使用递归总共需要有两点，其一是找到通项表达式f（n）=f（n-1）+某个表达式，然后再在这个的基础上找到相应的规律和表示方法即可。感觉递归的强大在于把复杂的问题简单化，一个不熟悉的问题化成熟悉的问题，堪称降维打击。

但缺点也是有的，如果学过数据结构或者参加过算法比赛的同学应该知道，递归需要临时储存大量的数据，而且需要先从后往前的求值，再从前往后的带入值，时间复杂度和空间复杂度都很高，在一些对于性能要求较高的地方不太适合用递归。