本笔记的教材为 MIT Open Course :Introduction to Computer Science and Programming,by Prof. Eric Grimson, John Guttag.

像计算机科学家一样思考。

用语言来 描述 我们想让计算机做什么,描述整个的过程。

第一课 ~ 第三课

高级语言 / 低级语言

低级语言:汇编语言,通过简单的操作,把数据从内存的某个位置移动到另一个位置。类似这样的操作。

高级语言:功能更复杂。

通用语言 / 专用语言

解释型语言 / 编译型语言

解释型语言:

源码被检查之后,交给解释器,然后给出输出。基本上是在运行时直接进行操作。

解释型语言比较容易调试,因为还能看到源代码。

编译型语言:

有一个中间步骤,源码需要先送给一个检查器或编译器,或两者合一,产生出来的是对象代码,object code。

这个步骤会进行两个重要的操作:一是帮助检查代码错误,二是在实际运行之前,经常会转换为更高效的指令序列。

编译型语言执行起来更快。


Python 是通用的,高级语言,解释型语言。

Python 语法

语法

语法是指在该语言中,什么才是 合法 的表达。

“cat dog boy” 就不是合法的表达。

语义

static semantics

什么 样的程序是 有意义 的,什么样的表达是有意义的。

有时候语法正确,却没有任何语义:”My desk is Suson”

虽然从语法上讲是合法的,但不具有任何语义,通常没人给桌子起名字。

静态语义帮助我们判断哪些表达式、代码具有的意义。

full semantics

这个程序是 做什么 的?如果运行某程序,它会实现什么?

数据类型

Python 会自动进行数据类型的检查,如果不符合要求会给出提示。

数字

  • 整形:5
  • 浮点:3.14

字符串

布尔

True / False

类型转换

把一种类型的数据转换为其它类型。

str()int()

数据类型是动态的

在 Python 中,数据类型是 动态 的。可能该变量一开始是数字,接下来就可以变成字符串。但仍然建议不要随意修改数据类型,以避免更多的错误产生。

A = 3
A = 'string'

操作符

操作符用来连接操作对象。

  • +
  • -
  • *
  • /

+

用来连接数字时,会进行数学运算;连接字符串时,Python 把两个字符串整合到一起。

str(5) + 'abc'

先把数字转换为字符串,再与其它字符串连接。

为了把不同类型的数据连接到一起,通常需要进行类型转换。

-

只能连接数字,进行减法数学运算。

*

连接数字时,进行乘法运算。

连接字符串和数字:如果是 字符串 * 整形数字N,则字符串被重复 N 次。其它连接均会返回 “类型错误”。

操作符连接不同类型对象的行为,称为 过载,即 overloaded,因为有点超出操作符本身的能力范围了。

/

只能连接数字,进行除法运算。

操作符的优先级

( ) > ** > *,/ > +-

变量

用变量来保存数据。

var = ‘what the hell?’

通过赋值语句,把变量与值 绑定 到一起。

关于变量使用的 场合:只要变量值在当前位置是合法的,如数据类型可以在当前环境使用,该变量就可以放在这儿。

变量名

尽量起有意义的变量名,便于代码的理解。如 firstnamelastname,比 AB 好很多。

表达式

把操作对象用操作符组合在一起就形成了表达式。

在 shell 中直接键入表达式,Python 会自动进行对应的操作,如运算、连接字符串等,然后直接输出结果。而在脚本中的表达式则不会自动输出,必须显式使用 print() 语句来实现输出。

比较表达式

4 > 2"abc" == "abc""z" > "a" 返回的值为 True

3 <= 2"z" > "za" 返回 False

赋值表达式

A = 3*5
B = 20
C = B
B = 3
print("B is ",B,", C is ",C)
B is  3 , C is  20

变量名 C 会指向具体的值 20,而不是指向变量 B。因此,虽然 B 变成了 3,但 C 仍然是 20。

赋值,可以理解为把变量名与某处的值链接起来,或把变量名指向值。

语句

Python 可以解释的合法的命令。

常见的有赋值语句、print() 等。

代码的组织方式

基本要素

数据 操作符 命令
数字
字符串
布尔
+ - * /
and, or
赋值
输入/输出
条件结构
循环结构

代码的运行顺序

线性程序

Straight Line Program

程序代码按顺序 逐行 执行。

分支程序

基于某些测试的结果,指令的运行顺序是可以 变化 的。

测试通常是针对变量的值进行的。

条件结构

在测试条件结构时,一定要把 所有可能 都测试到。

条件的构成

测试条件 最终会归结为 一个布尔值

条件可以是 一个简单的表达式,如 a<z,其结果要么 True,要么 False

也可以是 多个表达式andornot 连接而成的 布尔组合

条件结构常见的语法

if ...
if <some test>:
	block of instructions
	..........
	........

无需像其它语言一样用 endif 之类的来关闭。

if ... else ...
if <some test>:
	block of instructions
	..........
	........
else:
	block of instructions
	..........
	........
elif
if ... : ...
elif ... : ...
else : ...

或:

if <some test>:
	block of instructions
	..........
	........
elif <tests>:
	block of instructions
	..........
	........
elif <tests>:
	block of instructions
	..........
	........
嵌套
if <some test>:
	if <tests>:
		block of instructions
		..........
		........
	else:
		block of instructions
		..........
		........
else:
	block of instructions
	..........
	........

循环结构

循环,loop,也叫 迭代,iteration。

循环结构分析

组成循环的要素
  • 选择用于 计数 的变量:循环中,必须有个变量的值随着每次循环会发生 变化,次数必须是 有限 的,否则会成为死循环;
  • 初始化 变量:变量须提前在 循环外 初始化;
  • 结束循环 的测试:需要有一个用于结束循环的测试,通常测试变量值;
  • 组建循环内代码块:修改变量;
  • 循环结束后做什么

在设计一个循环时,必须确认循环会 中止,而且一定会返回一个 合理的 答案。

流程图

流程图是构建完善的循环结构的合适工具。

防御性编程

Defensive programming,是防御式设计的一种具体体现,它是为了保证,对程序的不可预见的使用,不会造成程序功能上的损坏。它可以被看作是为了减少或消除墨菲定律效力的想法。防御式编程主要用于可能被滥用,恶作剧或无意地造成灾难性影响的程序上。

  • 确保分析了所有可能的执行路径
  • 确保每条路径都有合理的输出
  • 所有可能的输入都有对应的路径,不会造成错误或死循环
  • 不要指望用户能给你期望的输入,要把用户当傻子,会犯错

以上的编程原则可以称为 穷举法,exhaustive enumeration,即考虑所有的可能性。

while 循环

满足条件就 一直 循环

.....
while <test>:
	block of code
	......
	......

如:

## 计算两个不同大小的数之间所有因数
x = 10
i = 1
while(i<x):
    if x%i == 0:
        print( 'divisor ',i)
    i = i+1

for 循环

就给定的条件 有限 地循环

for <var> in <some collection>:
	block of code
	......
	......

如 :

## 另一种列出两数之间因数的方法
x = 10
for i in range(1,x):
    if x%i == 0:
        print('divisor ',i)

元组

tuple,元组,泛指 有限 个元素所组成的 序列,是复合数据结构的一种。它是 不可修改 的。

元组的创建

元组由三部分组成:边界符、分隔符和元素。通常采用的边界符是小括号 ( ),分隔符是逗号 ,

foo=(1,2,3,4,5)
索引

用索引来访问元组中每个位置的元素,索引从 0 开始。因此索引只能访问 单个 的元素。

>>>foo[1] # 第 2 个元素
2

>>>foo[-1] # 最后一个元素
5

##### 切片

用切片来访问指定 索引范围 的元素。

在切片操作中,不包含区间范围的最后一个元素,这是 Python 的风格。

>>>foo[1:3]
(2,3)

>>>foo[:3] # 读取前 3 个元素
(1,2,3)

foo[1:3] 是从第 1 个元素开始提取,到第 3 个前面的截止。即提取第 1、2 个元素。

如果尝试读取索引之外的元素,会返回索引错误消息。

字符串的索引和切片

字符串中的每个字符可以类似于元组中的元素一样被索引或切片。

>>> bar= 'what the fuck'
>>> bar[0]
'w'
>>> bar[:6]
'what t'
sumDigits = 0
for c in str(1952):
    sumDigits += int(c)
print (sumDigits)

第 4 课 :通过函数分解和抽象,递归介绍

函数

把所有代码都放在一起来运行不利于运行、调试、升级,需要把这些代码进行分解、抽象成为函数。

  • 把代码拆分成多个模块
  • 忽略细节:对于某一段代码,只需要知道给它什么输入,它会有什么输出
  • 创建新的要素

关键字

def

def 在 Python 中用于标识一个函数的开始,后面接着函数名称。

def sqrt(x):
return

return 意味着到此处停止程序的运行,同时返回随后跟随的变量。

return None 中的 None 是个特殊的值,意味着没有任何值可以返回。但 None 仍然可以用来与其它变量进行比较。

函数的调用

要调用一个函数,需要知道函数的名称和参数,如 abs(55)

调用函数时,传入的参数与函数参数进行本地绑定,local binding,即只在函数内部生效。

本地绑定不影响全局绑定。本地和全局是针对函数和 Python 解释器来讲的。本地指函数内部,全局指整个解释器环境。

穷举算法

brute-force algorithm

农夫养猪和鸡,头加起来有 20 个,脚加起来有 56 个,计算猪和鸡各有多少。

可通过枚举所有的可能性来计算:

0 只鸡,20 只猪,算一下是否对的上?

1 只鸡,19 只猪,是否正确?

2 只鸡,18 只猪?

……

写个程序来实现上面的循环:

def solve(numLegs, numHeads):
    for numChicks in range(0, numHeads + 1):
        numPigs = numHeads - numChicks
        totLegs = 4*numPigs + 2*numChicks
        if totLegs == numLegs:
            return (numPigs, numChicks)
    return (None, None)



def barnYard():
    heads = int(input('Enter number of heads: '))
    legs = int(input('Enter number of legs: '))
    pigs, chickens = solve(legs, heads)
    if pigs == None:
        print ('There is no solution')
    else:
        print( 'Number of pigs:', pigs)
        print( 'Number of chickens:', chickens)

递归

recursion

在尝试用程序解决一个问题时,除了循环,有时候还需要用另一种思路来考虑问题,递归。简单地说,递归就是函数 自己调用自己

递归函数的优点是定义简单,逻辑清晰。理论上,所有的递归函数都可以写成循环的方式,但循环的逻辑不如递归清晰。

递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法。

递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解,容易编程。但递归是用栈机制实现的(c++),每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。

循环其缺点就是不容易理解,编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加,没什么额外开销。空间上没有什么增加。

第 5 课:浮点数字,连续细化,查找根

浮点数字

在 Python 中,浮点数字遵循 IEEE 754 标准。

按标准规定,浮点数由三部分组成:符号、尾数、阶

mantissa,尾数,也称有效位。exponent,阶,即指数。

这三部分合在一起来表示计算机中的浮点数。

  • 尾数 :1 ≤ 尾数 < 2
  • 阶 :-1022 ~ 1023

在 CPython 中,浮点数总是 64 位的。

浮点数的结构:

符号 尾数  
单精度 1 位 8 位 23 位
双精度 1 位 11 位 52 位

Python 默认的是十进制 17 位小数的精度,前 16 位是准确的,第 17 位开始不准确。

范例

1/8 = 0.125

用十进制表示:1.25 * 10-1

用二进制表示:1.0 * 10-3 ,即 0.001