《計算機科學及編程導論》部分筆記

* Computational thinking

* Understand code

* Understand abilities & limits

* Map problems into computation

圖靈兼容性：

在一種語言中能做的事，在另一種語言中也能做。

變數的類型是根據它現在綁定的值的類型而改變的，不要反覆無常地改變變數的類型。

y = 3*5 # y指向15y = x # y指向x的值（15）而不是xif x == y # 比較的是x的值和y的值，而不是x和y

線性複雜度：

執行循環的次數和輸入參數的大小直接相關。

防禦性編程：

在代碼中涵蓋所有可能路徑，確信對於所有可能的輸入都對應了代碼中的一個路徑，避免錯誤和無限循環的產生。

字元串是有序的字元序列。

建立函數：

分解（代碼結構化）和抽象（規避細節）

函數的目的：

尋找計算的共同模式

雞兔同籠問題：

def solve(numHeads,numLegs): for numRabbits in range(0,numHeads+1): numChicks = numHeads - numRabbits totLegs = 2 * numChicks + 4 * numRabbits if totLegs == numLegs: return(numRabbits,numChicks) return(None,None)def farm(): heads = int(raw_input(enter number of heads:)) legs = int(raw_input(enter number of legs:)) Rabbits,Chicks = solve(heads,legs) if Rabbits == None: print there is no solution. else: print number of Rabbits is,Rabbits print number of Chicks is,Chicks

遞歸（recursion）：

將一個問題進行分解，分解成一個簡單的同類問題或一系列可解決的基本步驟。

體現遞歸思想的兩個例子：

1、判斷一個英文字元串是否是迴文（即從左向右看和從右向左看是否完全一致）：

def isPalindrome(s): """Return True if s is a palindrome and False otherwise""" if len(s) <=1: return True else: return s[0] == s[-1] and isPalindrome(s[1:-1])

2、斐波那契數列（從第三項起，每一項都是前兩項的和。0，1，1，2，3，5，8，13…）：

def fib(x): """Return Fibonacci of x, where x is a non-negative int""" if x == 0 or x == 1: return 1 else: return fib(x-1) + fib(x-2)

64位存儲：

1位存儲符號（正或負）

11位存儲指數

52位存儲尾數

（浮點）數值 = 尾數 × 底數 ^ 指數 （附加正負號） 能表示17個數長的10進度精度

留意浮點數的比較

不應該去測試結果相等不相等，而應該去測試結果是不是足夠接近。

abs（a – b）< epsilon （abs：絕對值函數 epsilon：大於零的極小值)

brute-force algorithm 窮舉法

successive approximation 逐次逼近法

Bisection method 二分法

Newton』s method 牛頓法

python中的計算，一旦達到L的數量級（20億），就將停留在L。如：

>>> a = 2**1000>>> a10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376L>>> b = 2**999>>> b5357543035931336604742125245300009052807024058527668037218751941851755255624680612465991894078479290637973364587765734125935726428461570217992288787349287401967283887412115492710537302531185570938977091076523237491790970633699383779582771973038531457285598238843271083830214915826312193418602834034688L>>> a/b2L

二分法求平方根：

def squareRootBi(x, epsilon): """Return y s.t. y*y is within epsilon of x""" assert epsilon > 0, epsilon must be postive, not + str(epsilon) low = 0 high = max(x, 1) # x大於1時，x的平方大於x，所以在(0,x)取中值。而當x小於1時，x的平方小於x，要在(0,1)取中值。 guess = (low + high)/2.0 ctr = 1 while abs(guess**2 - x) > epsilon and ctr <= 100: #print low:, low, high:, high, guess:, guess if guess**2 < x: low = guess else: high = guess guess = (low + high)/2.0 ctr += 1 assert ctr <= 100, Iteration count exceeded print Bi method. Num. iterations:, ctr, Estimate:, guess return guess

牛頓法求平方根

def squareRootNR(x, epsilon): """Return y s.t. y*y is within epsilon of x""" assert epsilon > 0, epsilon must be postive, not + str(epsilon) x = float(x) guess = x/2.0 diff = guess**2 - x ctr = 1 while abs(diff) > epsilon and ctr <= 100: #print Error:, diff, guess:, guess guess = guess - diff/(2.0*guess) diff = guess**2 - x ctr += 1 assert ctr <= 100, Iteration count exceeded print NR method. Num. iterations:, ctr, Estimate:, guess return guess

assert（斷言）

用來檢測一個條件，如果條件為真，什麼都不做；反之則觸發一個帶可選錯誤信息的AssertionError，程序停止運行。

L1+L2 和L1.append(L2)的區別

L1+L2是把L2中的所有元素加到L1中，而L1.append(L2)是把L2作為一個整體加入到L1中。

列表綁定和數值綁定的區別

>>> L1 = [1,2,3]>>> L2 = L1 >>> L1[0] = 4>>> L1[4,2,3]>>> L2[4,2,3]>>> a = 1>>> b = a # b和1綁定後，原先a和1之間的綁定就中斷了>>> a = 2>>> b1

input和raw_input的區別

input接收數值（返回數值），表達式（返回計算後的數值），字元串（返回字元串）。raw_input接收用戶的任意輸入，以字元串的形式返回。

把實現和使用分離

大O符號（Big O notation）：

用於描述函數漸進行為的數學符號。通常是用另一種更簡單的函數來描述一個函數數量級的漸進上界。

如f(x)∈O(n^2)，其中，x是一個特定問題的輸入，n是對x規模大小的一個估算。

常見的幾種演算法複雜度：

O(n) 常數級

O(logn) 對數級

O(Len(s)) 線性級

O(n^2) 平方級

O(2^n) 指數級

數組的兩種存儲方式：

1. 鏈表（linked list）：內存上某一點指向下一個元素的值

2. 順序表（Sequential List）：內存上某一點指向數組起點

選擇排序/單元排序（Selection Sort） 和 冒泡排序（Bubble Sort）

查找某一元素是否在數組中的兩種方式：

1. 直接查找 O(n)

2. 排序後再進行查找 O(n*logn+logn)

當只進行一次查找時，直接查找的速度更快。而當要進行多次查找時，直接查找所需的時間為k*n，而排序後在進行查找所需的時間為n*logn+k*logn。此時排序後再進行查找的速度更快。

分治演算法（divide and conquer algorithm）

1. Split the problem into several sub-problems of the same type.

2. solve independently.

3. combine solutions.

適合用分治演算法解決的問題：最好是能夠簡單將問題進行分解，並且合併的過程不是非常的複雜（比線性方案小）。

分治演算法的一個應用：

歸併排序（merge sort）（馮.諾依曼於1945年發明）

1. divide list in half.

2. continue until we have singleton lists.

3. merge of the sub-lists.

def merge(left,right): """Assumes left and right are sorted lists,return a new sorted list containing the same elementsas (left + right) would contain.""" result = [] i,j = 0,0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1 while (i < len(left)): result.append(left[i]) i = i + 1 while (j < len(right)): result.append(right[j]) j = j + 1 return resultdef mergesort(L): """Return a new sort list containing the same elements as L""" print L if len(L) < 2: return L[:] else: middle = len(L)/2 left = mergesort(L[:middle]) right = mergesort(L[middle:]) together = merge(left,right) print merged, together return together

哈希演算法

1. 將輸入映射成一組數字。

2. 用空間換時間。

3. 哈希演算法是Python中用來實現字典的技術。

4. 好的哈希函數難以創立。

使用異常處理的兩個例子：

1、獲得一個特定類型的輸入

def readVal(valType, requestMsg, errorMsg): while True: val = raw_input(requestMsg) try: val = valType(val) return val except: print(errorMsg)print readVal(int, Enter int: , Not an int.)

2、打開一個文件&求中位數

def getGrades(fname): try: gradesFile = open(fname, r) except IOError: print Could not open, fnmae raise GetGradesError grades = [] for line in gradesFile: grades.append(float(line)) return gradestry: grades = getGrades(q1grades.txt) grades.sort() median = grades[len(grades)/2] print Median grade is, medianexcept GetGradesError: print Whoops

斷言和異常的區別

1. 斷言是一些測試條件，如果輸入滿足這些條件，剩下的代碼就會運行。如果不滿足，就會拋出一個錯誤，然後立即停止操作。

2. 異常和異常處理做的是，這裡有些我們預期的異常情況，並且這些情況我能嘗試處理。使用異常時，代碼能夠正常運行，並且在程序出現錯誤時會告知你。

測試和調試

測試：將輸入輸出跟程序的規格說明書進行對比

• Testing and Reasoning（推測）
• Validation（認證）is a process
• Designed to uncover problems and increase confidence that our program does what we think it』s intent to do.
• Unit testing（單元測試）& Integration testing（集成測試）
• Test suite（測試集）：small enough & big enough to give us some confidence

調試：查明為什麼程序不運行或者不按預期運行

• 功能方面的調試（Function） & 性能方面的調試（Performance）
• 調試的目的並不是去消除一個bug，而是去得到一個沒有bug的程序
• 最好的兩個調試工具
  • Print statement
  • Reading
• 做系統化地調試
  • Reduce search space
  • Localize the source of the problem
  • Study the text (how could it have produced this result & is it part of a family & how to fix it)
• 實驗必須要有反駁我們假設的可能
• 怎樣設計實驗
  • Find simplest input that will the bug
  • Find the part of the program that is most likely at fault (Binary search)
• 一些可能出錯的地方
  • Reversed order of arguments
  • Spelling
  • Initialization
  • Object vs Value equality
  • Aliasing(重名)
  • Side-function
• 一些建議
  • Keep record of what you tried
  • Reconsidering assumptions
  • Debug the code,not the comment
  • Get help-Explain
  • Walk away
  • Code should not always grow
  • Make sure that you can revert:save old version

Optimization problems(最優選擇問題)

• 特徵
  • A function to maximize/minimize
  • A set of comstraints(約束)
• 應用：
  • Shortest path
  • Traveling sales person(TSP)
  • Bin packing
  • Sequence alignment(調整)
  • Knapsack(背包)
• Problem reduction
  當你有一個從沒碰過的問題要處理，首先要做的一件事就是問問自己這是不是一個別人已經解決了的問題。
• 0/1背包問題
  • Greedy algorithm：每一步都最大化你的價值，對未來不做安排
  • Local optimal decisions：局部最優策略並不會保證全局最優
• Dynamic programing（動態編程）
  • Overlapping sub-problems(重疊子問題)
  • Optimal sub-structure（最優子結構）:Global optimal solution can be constructed from optimal solutions to sub-problem.
• Memoization（默記法）

  We record a value the first time it』s computerd,then look it up the subsequent times we need it.

• Decision tree（決策樹）

推薦閱讀：