回顾mitx-6.00.1x-week2
@Date : 2018-07-18
@Author : lmingzhi (lmingzhi@gmail.com)
@Link :
@Version : ver1.0
[TOC]
2018.07.18
week 2-3 Simple Algorithms
3.1 Video So far ...
注意点：
- Strings are ‘immutable’, can not be modified.
s = 'hello'
s[0] = 'y' # → cause error
s = 'y' + s[1:] # assign 'yello' to s, s is a new object
for char in s:
if char == 'i' or char == 'u':
print('char is i or u')
3.2 Video Approximate solution
solution to find cube
- can use exhaustive enumueration (It is a good enough solution)
- start with a guess and incremently some small value
- e.g. |\text{guess}^3 - \text{cube}| <= \text{epsilon}
Observations - find square root
- step could be any small number
- if too small, takes a long time to find square root
- if too large, might skip over answer without getting close enough
- In general, will take x/step times through code to find solution
- 复杂度O(n) → need a more efficient way to do this
3.3 Video Bisection Search
二分查找：
- 适用于已排好序的序列
- 适用于查找某个区间的某个值
- 有递归的思维在其中
- 要求输入与输出单调变化才起作用（bisection search works when value of function varies monotonically with input）, 如求解0-1之间的均立方根，可以乘以一个1000的倍数（系数）后，再进行。
step:
- if not close enough, guess too big or too small (search 0 ~ x)
- if g ** 2 > x, then know g is too big, so now search 0 ~ g
- and if , for example, this now g is such that g ** 2 < x, then know too small, so now search next g(搜索区间next g ~ g)
- 算法复杂度 O(logn)
search space:
- first guess: N/2
- second guess: N/4
- gth guess: N/2^g
Observations:
- Bisection search radically reduce computation time - being smart about generating guess is important
- should work well on problems with 'ordering' property - value of function being solved varies monotonically with input value. (e.g. Here function is
g**2, which grows as g grows.)
2018-07-19
Exercise: guess my number
# week2-3 Exercise: guess my number
print('Please think of a number between 0 and 100!')
low = 0
high = 100
def guess_wrong_ans(ans):
global high, low, mid
if ans == 'c':
print('Game over. Your secret number was: %s' % mid)
return False
elif ans == 'h':
high = mid
elif ans == 'l':
low = mid
else:
print('Sorry, I did not understand your input.')
return True
status = True
while status:
mid = (low + high)//2
print('Is your secret number %s?' % mid)
ans = input("Enter 'h' to indicate the guess is too high. Enter 'l' to indicate the guess is too low. Enter 'c' to indicate I guessed correctly. ")
status = guess_wrong_ans(ans)
3.4 Video: Floats and Fractions
Seeking how machines store float!
3.4.1 十进制转二进制（整数）
for Decimal numbers:
302 = 3 * 10^2 + 0 * 10^1 + 2 * 10^0
for Binary number:
10011 = 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0
= 16 + 0 + 0 + 2 + 1
= 19
Internally, computer represents numbers(int or float) in binary!
十进制转二进制思路：
- x = 10011 (二进制，即十进制的19,
1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0) - x % 2 → 1 （最后一位）
- that gives us the last binary bit
- x // 2 → 右移一位，即
1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0- all the bits get shifted right
- 重复step2和step3, 再分别得到1，0，0，1（首位）
- 因此19的二进制表示为：10011
用二进制表示整数可以准确的储存
num = 19
if num < 0:
isNeg = True
num = abs(num)
else:
isNeg = False
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num % 2) + result
num = num // 2
if isNeg:
result = '-' + result
print(result)
3.4.2 处理分数 how to deal with fractions
e.g. 简单的3/8
3/8 = 0.375
= 3 * 10^(-1) + 7 * 10^(-2) + 5 * 10^(-3)
= (3 * 10^1 + 7 * 10^1 + 5 * 10^0) / 10^3
So if we multiply by a power of 2 big enough to convert into a whole number,
can then convert to binary, and then divide by the same power of 2
即先乘以2的幂次方，转化为整数（整数可以直接转为二进制），然后再除以2的幂次方（相当于向左移动二进制的小数点）
- 0.375 * (23) = 3 (decimal)
2.Convert 3 to binary (now 11)
3.Divide by 23 (shift right) to get 0.011 (binary)
x = 0.375
p = 0
while ((2**p)*x) % 1 != 0:
print('Remainder = ' + str((2**p)*x - int((2**p)*x)))
p += 1
num = int(x*(2**p))
result = ''
if num == 0:
result = '0'
while num > 0:
result = str(num%2) + result
num = num//2
for i in range(p - len(result)):
result = '0' + result
result = result[0:-p] + '.' + result[-p:]
print('The binary representation of the decimal ' + str(x) + ' is ' + str(result))
Remainder = 0.375
Remainder = 0.75
Remainder = 0.5
The binary representation of the decimal 0.375 is .011
# 二进制转十进制
binary = '0001100110011001100110011001100110011001100110011001101'
def binary2decima(binary):
decimal = 0
for digit in binary:
decimal= decimal*2 + int(digit)
return decimal
SOME IMPLICATIONS
- If there is no integer p such that x(2*p) is a whole number, then internal representation is always an approximation
- Suggest that testing equality of floats is not exact
- Use abs(x-y) < some small number, rather than x == y
- Why does print(0.1) return 0.1, if not exact?
- Because Python designers set it up this way to automatically round
以上解释了为什么小数是不精确的，比如0.1是找不到一个2**k的数与之相乘（k要求为整数），从而获得一个整数
3.5 Video: Newton-Raphson
General approximation algorithm to find roots of a polynomial in one variable
p(x) = a_nx^n + a_{n-1}x^{n-1} + ... + a_1x^n + a_0
- Want to find
rsuch thatp(r) = 0 - Newton showed that if g is an approximation to the root, then
g - p(g) / p’(g)is a better approximation; wherep’is derivative of p.
Simple case: cx^2 + k, 步骤：
- First derivative: 2cx
- Newton-Raphson says given a guess g for root; a better guess is
g – (g^2 – k)/2g - 循环迭代
g = g – (g^2 – k)/2g, 直至收敛
epsilon = 0.01
y = 24.0
guess = y/2.0
numGuesses = 0
while abs(guess*guess - y) >= epsilon:
numGuesses += 1
guess = guess - (((guess**2) - y)/(2*guess))
print('numGuesses = ' + str(numGuesses))
print('Square root of ' + str(y) + ' is about ' + str(guess))
迭代算法思维
Iterative algorithms
- Guess and check methods build on reusing the same code
- Use a looping construct to generate guesses, then check and continue
产生的guess算法有：
- Exhaustive enumeration
- Bisection search
- Newton-Raphson (for root finding)
思考题:
- 为什么说计算机储存整数（int）是精确的，而储存小数(float)则是不精确的? 大家可以思考讨论一下。
- Guess and Check methods中，产生guess的有：
- Exhaustive Enumeration 穷举法
- Bisection search 二分法
- Newton-Raphson 计算根（for root finding）
可以简述一下Guess and Check的流程关键要素吗？上述3种方法有什么特点？
