Course: MIT 6.0001 Introduction to Computer Science and Programming in Python
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-0001-introduction-to-computer-science-and-programming-in-python-fall-2016/lecture-slides-code/
2/21/2018 Start
NO.1-1 RANDOM ALGORITHM
import random print(random.randint(16,277))
NO.1-2 SQUARE ROOT ALGORITHM
NO.1-3 BASIC MACHINE STRUCTURE
NO.1-4 SCALAR OBJECTS
int float bool NonType
use type() to see the type of an object
type(3.14) Out[4]: float type(true) Traceback (most recent call last): File "<ipython-input-5-83ab3fb73e0b>", line 1, in <module> type(true) NameError: name 'true' is not defined type(True) Out[6]: bool
NO.1-5 TYPE CONVERSION
float(3) → 3.0
int(3.9) → 3
NO.1-6 PRINT TO CONSOLE
print(3+2)
NO.1-7 REMAINDER and POWER
i%j #reminder i**j #i to the power of j
NO.2-1 NUANCES in PRINTING
x = 1 print(x) x_str = str(x) print("my fav num is", x, ".", "x =", x) #逗号自动前后加空格 print("my fav num is " + x_str + ". " + "x = " + x_str)#可以混合使用逗号和加号
OUTPUT:
my fav num is 1 . x = 1
my fav num is 1. x = 1
NO.2-2 LOGIC OPERATION
==
!=
and
or
NO.2-3 IF
if <condition>: <expression> <expression> if <condition>: <expression> <expression> ... else: <expression> <expression> ... if <condition>: <expression> <expression> ... elif <condition>: <expression> <expression> ... else: <expression> <expression> ...
NO.2-4 INPUT and LOOPS (FOR/WHILE)
while <condition>: <expression> <expression> ... # more complicated with while loop n = 0 while n < 5: print(n) n = n+1 # shortcut with for loop for n in range(5): print(n)
NO.2-5 RANGE
range(start,stop,step) for i in range(7, 10): for i in range(5, 11, 2):#包括5，不包括11
NO.2-6 BREAK
mysum = 0 for i in range(5, 11, 2): mysum += i if mysum == 5: break print(mysum)
NO.3-1 STRING (len, index, slice, for loop)
s = "abc" len(s)
s[0] evaluates to "a" s[1] evaluates to "b" s[2] evaluates to "c" s[3] trying to index out of bounds, error s[-1] evaluates to "c" s[-2] evaluates to "b" s[-3] evaluates to "a"
s = "abcdefgh"
[start:stop:step]#包括start 不包括stop
s[3:6] evaluates to "def", same as s[3:6:1] s[3:6:2] evaluates to "df" s[::] evaluates to "abcdefgh", same as s[0:len(s):1] s[::-1] evaluates to "hgfedbca", same as s[-1:-(len(s)+1):-1] #string逆序 s[4:1:-2] evaluates to "ec"
s = "abcdefgh" for char in s:#更好 if char == 'i' or char == 'u':#更好 print("There is an i or u")#更好 for index in range(len(s)):#不好 if s[index] == 'i' or s[index] == 'u':#不好 print("There is an i or u")#不好
NO.3-2 ABSOLUTE VALUE
abs()
NO.3-3 BISECTION SEARCH
cube = 27
epsilon = 0.01 num_guesses = 0 low = 0 high = cube guess = (high + low)/2.0 while abs(guess**3 - cube) >= epsilon: if guess**3 < cube : low = guess else: high = guess guess = (high + low)/2.0 num_guesses += 1 print 'num_guesses =', num_guesses print guess, 'is close to the cube root of', cube
#没考虑cube是负数，没考虑abs(cube)<1的情况
2/21/2018
NO.4 FUNCTION
#write function def is_even( i ): """ Input: i, a positive int Returns True if i is even, otherwise False """ print("inside is_even") return i%2 == 0 #invoke function is_even(3)
NO.5-1 TUPLE (immuable)
te = () t = (2,"mit",3) t[0] evaluates to 2 (2,"mit",3) + (5,6) evaluates to (2,"mit",3,5,6) t[1:2] slice tuple, evaluates to ("mit",) t[1:3] slice tuple, evaluates to ("mit",3) len(t) evaluates to 3 t[1] = 4 gives error, can’t modify object
#方便交换操作
#方便函数输出多个量
#有逗号的是tuple ('aaa',) 没逗号的是string('aaa')
NO.5-2 LIST (mutable)
a_list = [] L = [2, 'a', 4, [1,2]] len(L) evaluates to 4 L[0] evaluates to 2 L[2]+1 evaluates to 5 L[3] evaluates to [1,2], another list! L[4] gives an error i = 2 L[i-1] evaluates to ‘a’ since L[1]='a' above
NO.5-3 LIST:APPEND/REMOVE/DEL/POP
L = [2,1,3] L.append(5) #aliases, side effect of append
L1 = [2,1,3]
L1.extend([0,6]) mutated L1 to [2,1,3,0,6]
L = [2,1,3,6,3,7,0] # do below in order L.remove(2) mutates L = [1,3,6,3,7,0] L.remove(3) mutates L = [1,6,3,7,0] del(L[1]) mutates L = [1,3,7,0] L.pop() returns 0 and mutates L = [1,3,7]
NO.5-4 LISTS to STRINGS
s = "I<3 cs" s is a string list(s) returns ['I','<','3',' ','c','s'] s.split('<') returns ['I', '3 cs'] L = ['a','b','c'] L is a list ''.join(L) returns "abc" '_'.join(L) returns "a_b_c"
NO.5-5 SORT and REVERSE LIST
L=[9,6,0,3] sorted(L) returns sorted list, does not mutate L L.sort() mutates L=[0,3,6,9] L.reverse() mutates L=[9,6,3,0]
NO.5-6 ALIASES and CLONE
#extend函数也是这个性质
2/23/2018
NO.6-1 ITERATIVE vs. RECURSION
NO.6-2 STRING LOWER
s = s.lower()
NO.6-3 PALINDROME CHECKING with RECRUSION
def isPalindrome(s): def toChars(s): s = s.lower() ans = '' for c in s: if c in 'abcdefghijklmnopqrstuvwxyz': ans = ans + c return ans def isPal(s): if len(s) <= 1: return True else: return s[0] == s[-1] and isPal(s[1:-1]) return isPal(toChars(s))
NO.6-4 LIST: INDEX
def get_grade(student, name_list, grade_list, course_list): i = name_list.index(student) grade = grade_list[i] course = course_list[i] return (course, grade)
NO.6-5 DICTIONARY
my_dict = {} grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'} grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'} grades['John']# evaluates to 'A+' grades['Sylvan']# gives a KeyError grades['Sylvan'] = 'A' #add an entry 'John' in grades # returns True, test if key in dicSonary 'Daniel' in grades # returns False del(grades['Ana']) # delete entry #存储no order #只能存放 immutable variables #variables 不能 identical
grades = {'Ana':'B', 'John':'A+', 'Denise':'A', 'Katy':'A'}
grades.keys() # returns ['Denise','Katy','John','Ana']
grades.values() # returns ['A', 'A', 'A+', 'B']
NO.6-6 VALUES in DICTIONARY and MAX in LIST
def most_common_words(freqs): values = freqs.values() best = max(values) words = [] for k in freqs: if freqs[k] == best: words.append(k) return (words, best)
2/25/2018
#write file input_text = 'hello world anyone here?' first_file = open('first_file.txt','w') first_file.write(input_text) first_file.close() #append file append_file = ' What a pity!' first_file = open('first_file.txt','a') first_file.write(append_file) first_file.close() #read file -> output a string first_file = open('first_file.txt','r') content = first_file.read() first_file.close() print(content) #readline file -> output a small string first_file = open('first_file.txt','r') content1 = first_file.readline() content2 = first_file.readline() first_file.close() print(' ' + content1,content2) #readlines file -> output a list first_file = open('first_file.txt','r') content = first_file.readlines() first_file.close() print(content) #Class defination class Calculator: def __init__(self,nam,res): self.name = nam self.result = res def add(self,x,y): self.result = x + y #if this line is "result = x + y", "result" is only a local variable. So we need "self.result = x + y" here. print(self.name,'is now equal to',self.result) def minus(self,x,y): self.result = x - y print(self.name,'is now equal to',self.result) Calc = Calculator('Good Calc',0) Calc.add(1,2) Calc.minus(Calc.result,2) # LIST INDEX/COUNT/INSERT a = [1,3,2,4,5,6,5,6,5,6] a.insert(2,7) print(a,a.index(7),a.count(5)) a.sort(reverse=True) print(a) a.reverse() print(a) # MULTIDIMENSIONAL LIST a = [ [1,2,3], [4,5,6], [7,8,9] ] print(a[2][2])
2/26/2018
NO.7-1 BLACK TESTING
test the boundary of input
test the extremely large value 2**64
test the extremely small value 1/2**64
test both rational and irrational input
test values < 1
NO.7-2 GLASS BOX TESTING
go through all the possible paths in code
NO.7-3 COMMON EXCEPTION
快捷键：Ctrl + 1 注释/反注释
NO.7-4 EXCEPTION HANDLER
try: a = int(input("Tell me one number:")) b = int(input("Tell me another number:")) print(a/b) except: print("Bug in user input.") #or try: a = int(input("Tell me one number: ")) b = int(input("Tell me another number: ")) print("a/b = ", a/b) print("a+b = ", a+b) except ValueError: print("Could not convert to a number.") except ZeroDivisionError: print("Can't divide by zero") except: print("Something went very wrong.")
NO.7-5 RAISING an EXCEPTION
def get_ratios(L1, L2): """ Assumes: L1 and L2 are lists of equal length of numbers Returns: a list containing L1[i]/L2[i] """ ratios = [] for index in range(len(L1)): try: ratios.append(L1[index]/L2[index]) except ZeroDivisionError: ratios.append(float('nan')) #nan = not a number except: raise ValueError('get_ratios called with bad arg') return ratios
NO.7-6 SUM and an EXAMPLE of EXCEPTION APPLICATION
def avg(grades): try: return sum(grades)/len(grades) except ZeroDivisionError: print('warning: no grades data') return 0.0 #optional line
NO.7-7 ASSERTION
def avg(grades): assert len(grades) != 0, 'no grades data' #raises an AssertionError if it is given an empty list for grades return sum(grades)/len(grades)
NO.7-8 ROUND
round(35/3,1) -> 11.7
NO.8-1 CLASS DEFINATION
class Coordinate(object): def __init__(self, x, y): self.x = x self.y = y def distance(self, other): x_diff_sq = (self.x-other.x)**2 y_diff_sq = (self.y-other.y)**2 return (x_diff_sq + y_diff_sq)**0.5
def __str__(self):
return "<"+str(self.x)+","+str(self.y)+">"
c = Coordinate(3,4)
print(isinstance(c, Coordinate)) #use isinstance() to check if an object is a Coordinate. OUTPUT is "True"
NO.8-2 SPECIAL OPERATORS in CLASS
__add__(self, other) self + other __sub__(self, other) self - other __eq__(self, other) self == other __lt__(self, other) self < other __len__(self) len(self) __str__(self) print self
#... and others
NO.8-3 CLASS GETTERS and SETTERS
class Animal(object): def __init__(self, age): self.age = age self.name = None def get_age(self): return self.age def get_name(self): return self.name def set_age(self, newage): self.age = newage def set_name(self, newname=""): #DEFAULT ARGUMENTS self.name = newname def __str__(self): return "animal:"+str(self.name)+":"+str(self.age) a = Animal(3) a.age a.get_age()
2/27/2018
NO.9-1 INHERTIANCE and RANDOM LIB
class Student(Person): def __init__(self, name, age, major=None): Person.__init__(self, name, age) self.major = major def change_major(self, major): self.major = major def speak(self): r = random.random() if r < 0.25: print("i have homework") elif 0.25 <= r < 0.5: print("i need sleep") elif 0.5 <= r < 0.75: print("i should eat") else: print("i am watching tv") def __str__(self): return "student:"+str(self.name)+":"+str(self.age)+":"+str(self.major)
NO.9-2 END= in PRINT
print(line, end=' ') #为末尾end传递一个空字符串，这样print函数不会在字符串末尾添加一个换行符，而是添加一个空字符串。这个只有3版本有用。2.*版本不支持
NO.9-3 CLASS VARIABLES vs. INSTANCE VARIABLES
class Rabbit(Animal): tag = 1 #class variable def __init__(self, age, parent1=None, parent2=None): Animal.__init__(self, age) self.parent1 = parent1 self.parent2 = parent2 self.rid = Rabbit.tag # instance variable Rabbit.tag += 1 # incrementing class variable changes it for all instances that may reference it. def get_rid(self): return str(self.rid).zfill(3) def get_parent1(self): return self.parent1 def get_parent2(self): return self.parent2 def __add__(self, other): # returning object of same type as this class return Rabbit(0, self, other) def __eq__(self, other): parents_same = self.parent1.rid == other.parent1.rid #转移符，相当于接着下一行 and self.parent2.rid == other.parent2.rid parents_opposite = self.parent2.rid == other.parent1.rid and self.parent1.rid == other.parent2.rid return parents_same or parents_opposite
NO.9-4 STRING ZFILL FUNCTION
str(1).zfill(3) # -> '001'
NO.10-1 TIMING a PROGRAM
t0 = time.clock() c_to_f(100000) t1 = time.clock() - t0 Print("t =", t, ":", t1, "s,”)
NO.10-2 COUNTING OPERATIONS
2/28/2018
NO.11-1 BOOST BISECTION SEARCH
#PLAN A: O(nlog(n)) <- have to copy a list in every loop def bisect_search1(L, e): if L == []: return False elif len(L) == 1: return L[0] == e else: half = len(L)//2 if L[half] > e: return bisect_search1( L[:half], e) else: return bisect_search1( L[half:], e) #PLAN B: O(log(n)) <- avoid copying the list def bisect_search2(L, e): def bisect_search_helper(L, e, low, high): if high == low: return L[low] == e mid = (low + high)//2 if L[mid] == e: return True elif L[mid] > e: if low == mid: #nothing left to search return False else: return bisect_search_helper(L, e, low, mid - 1) else: return bisect_search_helper(L, e, mid + 1, high) if len(L) == 0: return False else: return bisect_search_helper(L, e, 0, len(L) - 1)
NO.11-2 GET ALL SUBSETS (RECURSION)
def genSubsets(L): res = [] if len(L) == 0: return [[]] #list of empty list smaller = genSubsets(L[:-1]) # all subsets without last element extra = L[-1:] # create a list of just last element new = [] for small in smaller: new.append(small+extra) # for all smaller solutions, add one with last element return smaller+new # combine those with last element and those without
NO.11-3 LIST, APPEND, EXTEND, ADD
new = [] new.append([1,2]+[3]) #->[[],[1,2,3]] new = [] new.extend([1,2]+[3]) #->[1,2,3] new = [0] new.append([1,2]+[3]) #->[0,[1,2,3]] new = [0] new.extend([1,2]+[3]) #->[0,1,2,3]
NO.11-4 COMPLEXITY of ITERATIVE and RECURSIVE FIBONACCI
#O(n), iterative def fib_iter(n): if n == 0: return 0 O(1) elif n == 1: return 1 else: fib_ii = 1 for i in range(n-1): tmp = fib_i fib_i = fib_ii fib_ii = tmp + fib_ii return fib_ii #O(2^n), recursive def fib_recur(n): """ assumes n an int >= 0 """ if n == 0: return 0 elif n == 1: return 1 else: return fib_recur(n-1) + fib_recur(n-2)
3/1/2018
文件操作READ READLINE READLINES SEEK TELL（偶然看到https://www.bilibili.com/read/cv254612，学习一下）
a = open('text.txt','w') b = '1wsdfsaf 2werqxcscsdgsf ' a.write(b) a.close() a = open('text.txt','r') c = a.read(20) print(c) a.seek(2,0) d = a.readline() print(d) #read()读全部，read(size)读特定长度 ， readline()读一行， readline(size) 相当于read(size)但不会读超过这一行的内容， readlines()相当于read()但返回的是一个list，readlines(size)读入lines直到这一行读完超过size #seek(x,y) y表示基点，y=0从头开始，y=1从当前位置，y=2从结尾，x表示往后移动的比特数 #tell() 返回当前字节
DEEPCOPY （偶然看到https://www.cnblogs.com/xueli/p/4952063.html，学习一下）
# without importation x = [1, 2, 3, ['a', 'b']] y = x[:] y.append('haha') y[3].append('c') print(x)#->[1, 2, 3, ['a', 'b', 'c']] # shallow copy import copy x = [1, 2, 3, ['a', 'b']] y = copy.copy(x) y.append('haha') y[3].append('c') print(x)#->[1, 2, 3, ['a', 'b', 'c']] # deep copy import copy x = [1, 2, 3, ['a', 'b']] y = copy.deepcopy(x) y.append('haha') y[3].append('c') print(x)#->[1, 2, 3, ['a', 'b']]
NO.11-5 SHUFFLE
random.shuffle(L) # 打乱顺序
NO.11-6 SORT ALGORITHM
#1) MONKEY SORT #2) BUBBLE SORT O(n^2) def bubble_sort(L): swap = False while not swap: swap = True #竟然还有这种操作 for j in range(1, len(L)): #此处是否还可以优化？因为每次冒泡循环结束，下个循环可以不考虑上个循环的最后一个元素了吧？ if L[j-1] > L[j]: swap = False #竟然还有这种操作，有助于提前结束循环 temp = L[j] L[j] = L[j-1] L[j-1] = temp #3) SELECTION SORT O(n^2) def selection_sort(L): suffixSt = 0 while suffixSt != len(L): for i in range(suffixSt, len(L)): if L[i] < L[suffixSt]: L[suffixSt], L[i] = L[i], L[suffixSt] suffixSt += 1 #4) MERGE SORT def merge(left, right): result = [] i,j = 0,0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 while (i < len(left)): result.append(left[i]) i += 1 while (j < len(right)): result.append(right[j]) j += 1 return result def merge_sort(L): if len(L) < 2: return L[:] else: middle = len(L)//2 left = merge_sort(L[:middle]) right = merge_sort(L[middle:]) return merge(left, right)
完结撒花✿✿ヽ(°▽°)ノ✿（后续仍会加入Python 基础函数，如果有的话）
总结来说，MIT 6.0001这门课首先很新（2016年），相比别的MIT open courseware课要新。第二，这门课内容相对简单，并未执着于介绍Python具体的函数，而是更像一门基础课，简单介绍算法思想和Python语法。对于进一步的，应该要学Introduction to algorithm了。