我的天

我是看着题目的中文版做题的

练习10：要检查一个单词是不是在上面这个词汇列表里，你可以使用 in 运算符，但可能会很慢，因为这个 in 运算符要从头到尾来搜索整个词汇表。我们知道这些单词是按照字母表顺序组织的，所以我们可以加速一下，用一种对折搜索（也叫做二元搜索），这个过程就和你在现实中用字典来查单词差不多。你在中间部分开始，看看这个要搜索的词汇是不是在中间位置的前面。如果在前面，就又对前半部分取中间，继续这样来找。当然了，不在前半部分，就去后半部分找了，思路是这样的。不论怎样，每次都会把搜索范围缩减到一半。如果词表包含了113809个单词，最多就是17步就能找到单词，或者能确定单词不在词汇表中。那么问题来了，写一个函数，名为 in_bisect，接收一个整理过的按照字母顺序排列的列表，以及一个目标值，在列表中查找这个值，找到了就返回索引位置，找不到就返回空。

做到死去活来词语在词汇表里有索引正确，没有时却会疯掉的时候我不得不去看答案，看到答案后傻眼了，答案对单词的判断只有True和False，再去找原题，我那个去，题目改了！不要求索引了好吗！

Exercise 10: To check whether a word is in the word list, you could use the in operator, but it would be slow because it searches through the words in order. Because the words are in alphabetical order, we can speed things up with a bisection search (also known as binary search), which is similar to what you do when you look a word up in the dictionary (the book, not the data structure). You start in the middle and check to see whether the word you are looking for comes before the word in the middle of the list. If so, you search the first half of the list the same way. Otherwise you search the second half. Either way, you cut the remaining search space in half. If the word list has 113,809 words, it will take about 17 steps to find the word or conclude that it’s not there. Write a function called in_bisect that takes a sorted list and a target value and returns True if the word is in the list and False if it’s not. Or you could read the documentation of the bisect module and use that! Solution: http://thinkpython2.com/code/inlist.py.

又纠结一番后我终于写出了一句“first > last”返回例外情况，终于，世界被拯救了！记录索引和不记录索引很不一样啊，按照参考答案的解法，i即便返回也永远是1，索引无能。纠结是有好处的，让我明白到二分法搜索有多么的高效，简直甩while循环几十条街，但如果真索引的话，估计我会很懒地直接用list.index()，虽然用之前必须用in历遍列表，判断是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import time
def in_bisect(library, first, last, myword): # 二分法搜索，10万数据查询最多只需不到20步
    if first > last: # 这是一句拯救了我的条件
        return None
    else:
        mid = (first + last)//2
        if myword == library[mid]:
            return mid
        elif library[mid] > myword:
            return in_bisect(library, first, mid-1, myword)
        else:
            return in_bisect(library, mid+1, last, myword)
myword = 'zoo' # input('myword is: ')
i = 0
library = []
fin = open('words.txt')
for line in fin:
    word = line.strip()
    library.append(word)
library.sort()
start = time.time()
 
# j = 0
# while i < len(library) - 1: # 我的脑洞第一反应用的循环
#     if myword == library[i]:
#         j = i
#         break
#     i += 1
# if j == 0:
#     print('myword is not in library')
# else:
#     print('index =', j)
 
# if myword in library: # 伟大列表自带的查询索引号，但先得确定单词在那里
#     i = library.index(myword, 0, len(library)-1)
# if i == 0:
#     print('myword is not in library')
# else:
#     print('index =', i)
 
if in_bisect(library, 0, len(library), myword) == None: 
    print('myword is not in library')
else:
    print('index =', in_bisect(library, 0, len(library), myword))
end = time.time()
print(end-start)
# myword is not in library while 0.07   index 0.003  bisect 0.001
# apple 4450               while 0.003  index 0.001  bisect 0.001
# zoo 113707               while 0.07   index 0.005  bisect 0.001
# while，index和bisect没有对比就没有伤害

思路很简单，但要得出这个概率结论要重复多少次呢？脚本写好以后我先用了10次，100次，1000次，效果都不好，数字太漂浮，于是我都怀疑自己了。搜索之后发现别人用MATLAB写了个大体意思跟我一样的程序，他重复了100万次，好吧，我懂了！本来这种扔随机数进去的测试重复就应该趋向于无穷，但试过你就知道，100万次绝对让你的电脑卡到怀疑死机了。所以我狡猾地控制百分数只输出整数，10万次有点卡（我的破电脑等待结果大概需要4秒），但还可以接受。

Exercise 8：This exercise pertains to the so-called Birthday Paradox, which you can read about at http://en.wikipedia.org/wiki/Birthday_paradox. If there are 23 students in your class, what are the chances that two of you have the same birthday? You can estimate this probability by generating random samples of 23 birthdays and checking for matches. Hint: you can generate random birthdays with the randint function in the random module. You can download my solution from http://thinkpython2.com/code/birthday.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

import random
def chance(num):
    n = 0
    x = 100000 # 越大越好，但太大了运行慢到怀疑人生…… 1W小卡，10W卡，100W非常卡！
    for i in range(x):
        birth = []
        for i in range(num):
            birth.append(random.randint(1, 365))
        birth.sort()
        for i in range(num - 1):
            if birth[i] == birth[i+1]:
                n += 1
                break
    return n/x
num = 23
print('chance is', '{:.0%}'.format(chance(num)))
# chance is 51%  x = 10W 百分数显示小数将会是个测试噩梦！！！

验证出某些数学定理是一件非常酷的事，但我为什么要那么干呢？所以当Think Python的习题要我做那种事的时候，我会莫名其妙地产生一些弱弱的抗拒心理。有时，留存在我脑海的数学知识根本不足以让我理解那些符号到底要我做什么。我不知道为什么写这本书的人觉得读者都明白那些数学符号是要干些什么的，他们面向的到底是什么知识层面的读者呢？那些符号在中国的教育系统里，大概高中中等水平以上的学生会懂。作为一个大学生，理论上我应该全懂那些东西到底是什么意思。倒不是要你真的算出来，但你起码得知道他们要你做些什么。时间是把杀猪刀，中国的应试教育使得大家在离开学校多年以后，如果期间又长期不用，通常都不会记得那些东西，大概只会隐约记得曾经学过。还记得小学的时候，我的某个同学很抗拒学数学，他觉得生活中最简单的加减乘除就能解决几乎所有问题，当然这个所有问题只是他眼中、他当时所遇到的那些。

为什么要学数学？我不知道。有些时候我觉得数学真的很有趣。大概是因为我觉得其中的某些规律会让我惊叹不已。那些规律不是人类创造出来的，是大自然母亲孕育出来的，我们只是逐步知道了那些东西的存在，逐步开始利用那些规律做某些事。之所以某些时候我会有点害怕数学，是因为我是个吊儿郎当的人，即便我懂得某些规律，但是在不断重复的过程中，做着做着我就出错了。小学时计算之所以出错，倒不是因为我乘法表背得不好，而是因为我的字写得太丑，为了图快，字写着写着连我自己都不认得到底是什么。计算机不会因为正常重复而犯错误，如果真的崩了，必定是制定的规则有问题。还记得小学时候影响我最深的那个数学老师，非常看重数学的思维，而不是数学重复计算本身。我的运气非常好，小学、初中、高中，我都分别遇到了一个影响我一生的数学老师。在我印象之中，其他老师从来没有这么深刻地影响过我，虽然他们其中的某些对我来说很重要，我也非常喜欢。也有一些老师是我很不喜欢的，但不喜欢归不喜欢，我不会因为那个就故意搞砸自己那一门课的成绩，反而，我要拿出更优秀的成绩向他们示威。当然，有些时候，我不够强大，所以想示威也无能为力。我的学习不是为了跟老师较劲。

学生时代，为什么要学习？为什么要把题目解答正确？其实当时我完全没有考虑过这些问题，我也没有时间考虑除了用一种方法，还能不能用其它方法得出同样的答案。这里的发散应该包括除了那个参考答案以外，某道题是否还会存在其它情况，还会出现其它答案吗？很多时候，我们的时间就只够解答那道题，根本没有闲情考虑那道题如果改变了某些参数，会不会出现一些比较颠覆的结果。做作业时的我们，又或者考试时的我们，干掉这道题以后就直奔下一道。如果每次都胡思乱想，作业无论如何都做不完，考试就更别想可以在规定时间之内完成答题。

后来我才发现，如果人要真的有所得，要认真地学习研究，除了理解某个知识以外，还必须有一定的自主思考的空间与时间。我们不应该一直被别人牵着鼻子去发散，而应该学会主动地脑洞大开。很多时候，别人会用某个分数衡量我们，或许是通过考试，或许是通过讨论，但那个真的就代表我们吗？能定义我们的只有我们自己。

我们之所以要探寻，我们之所以要纠结，是因为我们想知道、想做得更好。

觉得自己虽然见过递归，但几乎不用，不逼着我我都不用，循环用得越来越遛。前两题我和参考答案得出的结论一致，最后一题，我觉得参考答案有问题。下面的都是我的脚本。下面要用到的words.txt在这里。

Exercise 7：This question is based on a Puzzler that was broadcast on the radio program Car Talk: Give me a word with three consecutive double letters. I’ll give you a couple of words that almost qualify, but don’t. For example, the word committee, c-o-m-m-i-t-t-e-e. It would be great except for the ‘i’ that sneaks in there. Or Mississippi: M-i-s-s-i-s-s-i-p-p-i. If you could take out those i’s it would work. But there is a word that has three consecutive pairs of letters and to the best of my knowledge this may be the only word. Of course there are probably 500 more but I can only think of one. What is the word? Write a program to find it. Solution: http://thinkpython2.com/code/cartalk1.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def double_letter(word):
    num = 0
    i = 0
    if len(word) >= 6:
        while i < len(word)-1:
            if word[i] == word[i+1]: 
                num = num + 1
                i = i + 2
            elif i > 2 and word[i-2] != word[i-3]:
                break
            else:
                i = i + 1
        if num == 3:
            print(word)
fin = open('words.txt')
n = 0
for line in fin:
    word = line.strip()
    double_letter(word)
# bookkeeper
# bookkeepers
# bookkeeping
# bookkeepings

Exercise 8: Here’s another Car Talk Puzzler: “I was driving on the highway the other day and I happened to notice my odometer. Like most odometers, it shows six digits, in whole miles only. So, if my car had 300,000 miles, for example, I’d see 3-0-0-0-0-0. “Now, what I saw that day was very interesting. I noticed that the last 4 digits were palindromic; that is, they read the same forward as backward. For example, 5-4-4-5 is a palindrome, so my odometer could have read 3-1-5-4-4-5. “One mile later, the last 5 numbers were palindromic. For example, it could have read 3-6-5-4-5-6. One mile after that, the middle 4 out of 6 numbers were palindromic. And you ready for this? One mile later, all 6 were palindromic! “The question is, what was on the odometer when I first looked?” Write a Python program that tests all the six-digit numbers and prints any numbers that satisfy these requirements. Solution: http://thinkpython2.com/code/cartalk2.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def is_palindrome(word):
    if word[::-1] == word:
        return True 
def test_palindrome(number):
    if is_palindrome(str(number)[2:]):
        if is_palindrome(str(number+1)[1:]):
            if is_palindrome(str(number+2)[1:1]):
                if is_palindrome(str(number+3)):
                    return True
for number in range(100000, 999999):
    if test_palindrome(number):
        print(number)
# 198888
# 199999

Exercise 9: Here’s another Car Talk Puzzler you can solve with a search: “Recently I had a visit with my mom and we realized that the two digits that make up my age when reversed resulted in her age. For example, if she’s 73, I’m 37. We wondered how often this has happened over the years but we got sidetracked with other topics and we never came up with an answer. “When I got home I figured out that the digits of our ages have been reversible six times so far. I also figured out that if we’re lucky it would happen again in a few years, and if we’re really lucky it would happen one more time after that. In other words, it would have happened 8 times over all. So the question is, how old am I now?” Write a Python program that searches for solutions to this Puzzler. Hint: you might find the string method zfill useful. Solution: http://thinkpython2.com/code/cartalk3.py.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

year = 99
meet = int(input('how many times have we met?(1-8): '))
print('mom born me at', '\t','my age', '\t',"mon's age")
for i in range(10, 80): # 假设你妈生你的最低年龄是10，最高年龄是80
    n = 0
    for age in range(1, year):
        if age < int(str(age).zfill(2)[::-1]) and int(str(age).zfill(2)[::-1]) - age == i:            
            # print(i, '\t\t', age, '\t\t', str(age).zfill(2)[::-1])             
            n = n + 1
            if n == meet:
                print(i, '\t\t', age, '\t\t', str(age).zfill(2)[::-1])
 
# how many times have we met?(1-8): 6
# mom born me at   my age          mon's age
# 18               57              75
# 27               58              85
# 36               59              95
 
# how many times have we met?(1-8): 8
# mom born me at   my age          mon's age
# 18               79              97
 
# mom born me at   my age          mon's age
# 18               2               20
# 18               13              31
# 18               24              42
# 18               35              53
# 18               46              64
# 18               57              75
# 18               68              86
# 18               79              97
# 27               3               30
# 27               14              41
# 27               25              52
# 27               36              63
# 27               47              74
# 27               58              85
# 27               69              96
# 36               4               40
# 36               15              51
# 36               26              62
# 36               37              73
# 36               48              84
# 36               59              95
# 45               5               50
# 45               16              61
# 45               27              72
# 45               38              83
# 45               49              94
# 54               6               60
# 54               17              71
# 54               28              82
# 54               39              93
# 63               7               70
# 63               18              81
# 63               29              92
# 72               8               80
# 72               19              91

昨天晚上，在做那些文字游戏的时候，我做到了好像怎么费劲就轻而易举地把题目做出来了，只需要几分钟到十几分钟。从写脚本到测试成功，整个过程没有状况，甚至写完脚本后，所有东西下面红色波浪线都没有。通常，我都会习惯忘记在句子的结束加上冒号。Python要求必须严格缩进，多了少了都不行，而且使用缩进必须用一样的方式，通常必须要求用4个空格。习惯了用VSCode以后，我会设置缩进为4个空格，当我在上一行回车之后，如果上面是冒号，下一行就会自动缩进4个空格。但如果某段代码不是我写的，而是从某个地方复制过来的，就可能会出现状况。所以为了避免这种无聊的出错，我把所有占位符都显示出来。比如空格，也比如tab。大概对其他人来说，写代码就应该是行云流水的。知道自己要实现的功能是什么，知道自己应该用什么方法，然后按照思路按部就班。调试这种东西没有个尽头，没有说用了某些方法测试就能一定保证调试完以后程序没有任何的bug。只能做到尽可能少bug，不可能做到完全没有bug。不知道从什么时候开始，我觉得不把话说死非常重要。

昨天我终于体验到云流水般写代码，是因为在行云流水之前我已经纠结过好几个小时。在行云流水之后，我也遇到了命令行的光标卡在那里，不显示程序有错误，但是程序也不进行下去。如果我进入了死循环，程序出不来，Python会提示我上面已经进行了超过994行，别浪浪费大家精力了。之前我已经见识过了。而昨晚我遇到的是光标停在那里，没有任何提示。脚本那里也没有任何红色波浪线，说明语法是对的，起码静态语法没问题。当我再次看到脚本的时候，发现原来是我在用while进行循环迭代的时候，没有设置改变条件的东西，于是while的循环就停在那里了。在我构想那个循环的时候，其实我是设定好增量条件的。我的脑子已经准备好了，但我的手指并没有把增量条件敲上去，所以就出现了之前死在了终端的状况。我不知道光标死在了终端我还能做些什么，反正我的处理方式是把终端关了。光标停在那里，输入什么都没有反应，又或许如果我在单独的CMD命令行里搞那个的话，我可以用某些什么方式从那里跳出来。只是我现在不知道该做些什么。因为我是在VScode的测试，所以我简单地把那个终端的窗口关掉，重开一个就好。

还记得，在大学里学习C语言的时候，其实我不怎么喜欢用while这个东西循环，我更喜欢用for。拿Python跟C语言比，我觉得后者需要我们在写代码的时候更加仔细严谨。比如花括号这种东西绝对不能省。也比如某个对象在使用之前必须先声明，不只要说明它存在，而且要确定好那是一个什么类型的东西。在循环控制方面，C语言一开始就必须得想好所有。相对而言，Python很自由。昨天我突然发现原来in这个东西可以让if这种语句也具备循环的功能。在实现某个功能的时候，我用了两个for嵌套，而参考答案只用了一个for和一个if，出来的结果完全是一样的。我在两个for里还得加个if做判断，相对参考答案而言，显然就有点臃肿了。

我明明知道做习题会让我死去活来，但是一定程度上，我却在享受那种征服未知的刺激。