第23，24讲的习题代码以及分析

mumudontcry

啊，木木我头大了，一个小时就憋出来一题，虽然小甲鱼的题目确实不难，我有2个题目都是写得差不多了，但是就差一点点，比如把12345拆成列表的那题，我拆出来了，但是不知道怎么正确放进列表里（我的列表里的元素是54321），感觉有点云里雾里
像第22讲写的，虽然有把习题分析了一下，但写这讲的时候我其实是有那种挖坑等着被你们埋的感觉，这两天我去看看书，帖子先写成这样，明天我会把帖子编辑一下，把小甲鱼的答案讲一遍，但是我自己的代码，或者说我觉得有值得看的代码估计是没有了，抱歉哈，毕竟我觉得要是自己都糊里糊涂地再给什么总结的东西，会误导人的

ps：小甲鱼把python讲得实在是太精简了，如果说真的学完了小甲鱼的视频，又看了木木的讲解（我觉得讲的不是很好啦），就以为会python了，那就……嗯，告诉你们我今晚做的一件事，我把《python学习手册》翻了一下目录，结果，光是用鼠标滚轮滚到函数那里，就滚了一分钟，所以……真的要去看书了


嗯……开始讲 ，请忽略上面孤零零的链接，或者，按ctrl+a就知道为什么了
首先是
0
这个程序木木有写，而且有一点很值得学习，为什么这么说，因为我看别人的书上居然有我这样的写法，程序如下：
已知十进制，用递归求二进制的
def _10to2(n):
    str1 = ''
    if not n:
        return str1
    else:
        str1 = _10to2(n // 2)
    return str1 + str(n % 2)




print(_10to2(int(input("数字："))))



先把程序含义讲一下吧，然后再讲为什么蓝色的那个很值得学习
这是利用“对2取余”的方法将十进制转化为二进制的递归
读程序，咱们首先不看函数，因为函数只是为了实现一种功能，我们先读函数之外的主程序（类似于c++的main里的代码）
打印（函数（自变量））
然后有函数，再看函数的含义：
定义一个空字符串
先把蓝色的代码替换成“if n == 0”，这样更好理解：如果带入函数的值n为零，那么，返回字符串，这个是这个递归函数的终止条件，不能忘了哦~~
如果n不等于0，那么，开始递归：


字符串=函数（带入的值整除2）
返回 字符串 拼接 带入的值对2求余


这是什么意思呢？我们知道求二进制就是：对一个数整除2，余数记下，再整除2，记下余数，直到最后这个数变成了0，然后将刚才的余数反向连起来，就是这个要求的二进制的值


这里，余数是我们要输出的，而整除是一个反复重复的，所以，我们就让整除这个过程递归，而return的就是这个余数连起来的字符串


举个例子：_10to2(6)

（这是木木第三次写递归的步骤了，希望能够清晰地表达给大家）
我们要的是_10to2(6)，根据：


str1 = _10to2(n // 2)
    return str1 + str(n % 2)


这里我们转化这个return为一个赋值语句：_10to2(n) = str1 + str(n % 2)，这个应该知道什么意思吧？不知道赶紧回去学函数！

于是
_10to2(n) = str1 + str(n % 2) = _10to2(n // 2) + str(n % 2)


！！！！！！他喵的，这就是一个递推式！！！没错，递归和递推本来就是有这样的关系的
所以
_10to2(6) =_10to2(3) + '0' =_10to2(1) + '1'+'0' =_10to2(0) + '1' + '1' + '0' = '' + '1' + '1' + '0' ="110"
所以我们就得到了这个二进制的结果


木木之所以写了三次，就是因为本来想把具体的计算过程也告诉大家，但一想，像整除，求余什么的我就不多说了，要是不会就回去做数学题吧


但是其实真正的递归过程不是上面的递推式，而是先求6，3，1，最后求出0原来等于''之后，再返回过去，得到1，3，6的值，嗯……应该看得懂这句话吧，函数名字太复杂，不写了


然后就是我说的值得一说的一个表达式：if not n:
这货居然等价于if n == 0？？是的，但，也不是的，先说为什么是
因为n如果不等于0，那么not n就是等于0，这是从逻辑关系上得出的结果，于是if not n就是等价于if n == 0，而后者是从数学角度上得到的结果


为什么说这个式子很重要？因为这个式子不光代表if n == 0，还有别的含义，只不过在这里它代表的是n == 0


请看下面的例子，还是一个递归函数：
def mysum(L):
    if not L:
        return 0
    else:
        return L[0] + mysum(L[1:])


print(mysum([1,2,3,4,5]))

请大家告诉木木，这个输出是什么？


在这里L就是判断列表是不是为空，如果理解了木木第0题讲解的，那么这个也很容易理解了


什么？你不知道什么是L[1:]……般若波罗蜜，月光宝盒带这位骚年回去复习列表吧~~
当然这个跟小甲鱼的if dec是类似的意思，也就是说，在程序里写if not n或者if dec会让别人觉得很高大上（木木是这么认为的）


最后，这题的答案是15，是分别把1，2，3，4，5加起来，每次相加都会把列表的长度减少一，直到列表变成空，最后得到15，你们答对了么？

1
还记得小甲鱼曾经提到过的函数和过程么，木木进行了一番吐槽，什么函数过程嘛，没有分那么清楚好不啦


如果说要按照函数和过程的分法看这一题和上一题，那么上一题是函数，这一题是过程
理由就是函数和过程的最大区别，一个有返回值，一个没有
（为什么提到这个？没有为什么，就是……提一下？）


请大家按照上一题的分析过程，用递推的方法分析一遍这道题，这题其实木木不用讲，大家都很容易理解，为什么呢？因为……


这题根本就不像递归！！！以木木的理解，这题不是递归！估计小甲鱼也是这么觉得，所以这题小甲鱼并没有说用递归来做
递归的特点是：
有终止条件
调用自身
这两个木木已经很~~~多次强调了，所以，不知道的话就打屁屁
木木认为这题不是递归的理由就是，木木觉得递归还有第三个特点，虽然不是必要的，但木木觉得至少有这个特点，有终止条件和调用自身的一个函数才称得上是递归，这个特点就是：
有去有回


按照木木第0题的分析方法，大家可能会发现，这题是“有去无回”，根本就是一层一层往下，却再也没有回来：
这一题，每次n的值改变，都在列表里插入一个元素，直到最后条件终止，于是列表完成，而程序也结束，没有像什么斐波那契数列，汉诺塔那样，去了然后回来


所以，木木认为这题不是递归，从这个角度上说，木木再一次发现了甲鱼大魔王的失误，木木很有信心将大魔王打败~~
这种题目，木木称它为“不是递归的递归”（知道意思就好，别说出去，因为根本没有这种说法）

2
这一题体现了递归一个很狂拽酷炫的一面：跟二分法交配（，木木什么时候也变得没有节操了？嗯……才没有呢？这讲视频里小甲鱼刚说过这个词，木木只是记住了）
大家有听过“快速排序”吧，就算不知道，那听还是要听过一下的吧


递归就是不断重复一件事，直到到达了最终的条件
二分法就是把一个大的事情，分成两部分来处理


那么，递归+二分法放在一起是什么呢？就是：不断地把一个大问题划分成两个小问题，直到到达终止条件，在排序上就是一坨数字分成很多坨两个数的大小的比较
关于递归的快速排序，有兴趣的鱼油可以看这个：
python实现快速排序http://www.cnblogs.com/scorpioying/archive/2012/09/07/2675327.html（论坛又大姨妈了，链接加不进去，你们自己复制），打不开的话（比如作者关闭了博客），就问木木要一份doc版的吧

这题呢，就是说，小甲鱼设置了一个start，和end，让两边分别比较再+1和-1，直到start > end，就像第0题提到的return的赋值语句，这一题借助了“条件表达式”对递归函数进行了赋值1，除非遇到不相等，就赋值0，由于跟第1题一样，属于“不是递归的递归”，只要一股脑到底不需要返回的，所以这题也容易理解

3
这题小甲鱼解释的很清楚，木木偷个懒，这样的才是木木眼中正宗的递归，有去有回的那种，也可以利用第0题的递推的方法去求，理解的话，建议还是把具体的数字带进去，然后一步一步跟着来（顺便记录一下中间的过程值，不然等你要回来的时候，你可能就回不来了）

以下是看完这讲之后的额外奖励时间：


问：一个n层的汉诺塔，它需要多少步才可以移动完？
你当然可以在程序里设置一个累加器，什么，你不知道怎么设置？那……木木先告诉你一道数学题的奇葩的思维方式，然后你可能就知道怎么设置这个累加器了
有一个乒乓球比赛，参赛选手一共有100名，每局比赛两名选手参加，每局比赛一定要淘汰输掉的选手，被淘汰的不能再参加比赛，比赛结束后，只有一个获胜者。请问，总共比赛了几场？请在一秒钟时间作答！1秒，时间到，答案是：99场
理由：因为每次比赛都淘汰一名，总共个100名，最终只有一个没有被淘汰，于是，就有99场！
累加器在哪里设置知道了么？

再问：如果不是用程序的方法做，用纯粹数学的方法，你能想到什么奇葩的解法？简单迅速求出移动次数？（当然这个解法跟上面的数学题没有关系）
答案在下一讲公布


@小甲鱼尽情向我挥洒意见和鱼币吧
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
点击
当没节操甲鱼遇上傲娇笨笨的木木
查看我的淘帖，喜欢就点“订阅”吧

tractrac

师父领进门，修行在个人

墨白_找

我靠这么快~

mumudontcry

墨白_找 发表于 2014-8-5 11:31
我靠这么快~

木木要看书去了，光看视频有点坑爹啊

mumudontcry

tractrac 发表于 2014-8-5 07:55
师父领进门，修行在个人

U R right

Bruin

mumudontcry 发表于 2014-8-5 15:35
木木要看书去了，光看视频有点坑爹啊

有什么书可以向初学者推荐的么，亲

mumudontcry

Bruin 发表于 2017-2-22 10:17
有什么书可以向初学者推荐的么，亲

木木已经不在学python了，现在是php的拥护者