search

selfteaching-learning-notes / selfteaching-learning-notes.github.io

自学营学员学习笔记
https://selfteaching-learning-notes.github.io
15 stars 83 forks source link

1091050017-MIT-自学 MIT 原版书 #25

Open kagamiqyah opened 5 years ago

kagamiqyah commented 5 years ago

学员信息

学习笔记

Chapter 3: SOME SIMPLE NUMERICAL PROGRAMS 一些简单的数值程序

这一章非常有意思，列举了一些简单算法里举例说明如何应用到实际上。事实上，计算机的计算速度是惊人的，但是我们作为程序员需要告诉它具体实施步骤，还要按照它能理解的语言和方式来告诉。 拿找到一个数的平方根来举例子，如果让计算机来完成，需要怎样做呢？原来不是我想想的那种直接用公式算出，而是需要找到，有的数的平方根不是有理数，那么只需要找到最接近的近似值就可以了，按照这个思路，书里列出了几个方法有穷举法、二分法和牛顿-拉佛森法。本章在介绍完每个方法后，都会有一道练习，帮助理解。

  1. 穷举法： 利用循环语句枚举出所有可能性，直到得到正确答案或者尝试完所有值。 练习，要求用户输入一个整数，找出符合要求的这个数的根和幂。power的要求是0<power<6 
    
def g():
n = int(input("Enter a number: "))
for pwr in range(5, 0, -1):    # 满足power的要求
    root = 1
    while root**pwr <= n:   # 枚举出所有可能性
          if root**pwr == n:
             return (root, pwr)
          else:
            root += 1
raise Exception("Cannot be solved.")

print(g())

2. 二分法 bisection search：
    把待查找空间分为两部分，每一次循环迭代后，把符合的那部分再一分为二，直到找到近似值或准确值为止。这个方法是非常节省待查找空间的。
我用练习来熟悉了二分法：要求找出一个数的立方根，既可以是正数，也可以是负数

x = int(input('please enter a integer(positive or negative):')) epsilon = 0.01 numGusses = 0 low = 0.0 high = max(1.0,abs(x)) ans = (high + low)/2.0 while abs( ans 3 - abs(x)) >= epsilon: print('low =',low,'high =',high, 'ans =',ans) numGusses += 1 if ans 3 < abs(x): low = ans else: high = ans ans = (high + low)/2.0 print('numGuesses =', numGusses) if x > 0: print(ans, 'is close to cube root of ',x) if x < 0: print('-',ans,'is close to cube root of',x)

3. 二进制数和浮点数 binary and float。在编程语言里，非整数数值都是用*浮点数*表示的。并且为了数值的精度，都会用二进制来表示有效数字和指数。比如，0.625（5/8）会表示成数对（101，-11），代表
5 x 2 <sup>-3</sup> = 5/8=0.625
练习来了，如何把一个二进制的数转化成十进制呢？

user_input = int(input("enter a binary value"))

bits = list(str(user_input))

decimal = 0

counter = 0

for i in reversed(bits): decimal += 2*counter int(i) # 先把二进制数字倒序排列，然后序列上1或0都乘以相对应的2的指数 counter+=1

print ('The decimal value is: ', decimal)

4. 牛顿-拉佛森方法 Newton-Raphson search

书里说Newton-Raphson 的方法比二分法在找到一个数的近似平方根时更有效率，于是我写了代码求证一下。二分法是上面介绍过了，Newton-Raphson的方法书里已经介绍过了，那么只要比较一下迭代次数就可以了。

def Newton_Raphson_square_root(k):

Newton-Raphson for square root,find x such that x**2 - 24 is within epsilon of 0.01.

epsilon  = 0.01
x = k / 2.0
Guess = 0
while abs(x * x - k)>= epsilon:
    x = x- (((x ** 2) - k)/(2 * x))
    Guess += 1
print ( x,'is close to square root of', k)
print ('The number of guesses is',Guess)
return Guess

def Bisection_square_root(k):

Bisection for square root,find x such that x**2 - 24 is within epsilon of 0.01.

epsilon = 0.01
low = 0.0
high = k
x = float((low + high)/2)
guess = 0
while abs(x ** 2 - k) >= epsilon:
    if x ** 2 > k:
        high = x
    elif x ** 2 < k:
        low = x
    else:
        break
    x = (high + low) / 2
    guess += 1
print ( x,'is close to square root of', k)
print ('The number of guesses is',guess)
return guess

k = 24.0 nr = Newton_Raphson_square_root(k) bs = Bisection_square_root(k) if nr > bs: print('Bisction search is more efficient than Newton-Raphson search.') else: print('Newton-Raphson search is more efficient than Bisection search.') 


结果为：![屏幕快照 2019-07-18 下午5.29.21](http://ww4.sinaimg.cn/large/006tNc79ly1g5k98bq3prj30dc01ymx7.jpg)

确实如书中所说，**牛顿-拉佛森方法Newton-Raphson search 更有效率**。
kagamiqyah commented 5 years ago

学员信息

学习笔记

第四章讲函数、作用域，记得我第一次看这些概念的时候，脑子里完全是懵的，不知如何下手，但是反复地从不同的参考书和文章里看到和应用这些概念知识以后，反而能一字一句地读进去了，况且这本书写得非常明白。

  1. Function

    Through Finger exercise, I test myself whether I master this concept 'function'.

    Write a function isIn that accepts two strings as arguments and returns True if either string occurs anywhere in the other, and False otherwise.

    def isIn(string1,string2):
 if (string1 in string2) or (string2 in string1):
   result = True
 else:
   result = False
 return result

    Test result:

    屏幕快照 2019-07-31 上午11.32.51

  2. Scoping

    Only through read a simple code, I am able to know the result, but the code gets more complicated, I have no choice but to use my favorite tool : python tutor to get a result.

    sometimes, the actual and formal parameters have the same name,but actually they are not same variable, they are in the different scope.

    def f(x):  #global frame
   def g(): # f frame
       x = 'abc' #local frame
       print('x =', x) 
   def h(): # f frame
       z = x # z = 3 + 1
       print('z =', z)
   x = x + 1 
   print('x =', x) 
   h() 
   g() 
   print('x =', x) 
   return g 
x = 3 #global variable 
z = f(x) 
print('x =', x)
print('z =', z) 
z() # z==g z()==g()

    Python tutor:

    屏幕快照 2019-07-31 上午11.55.35

屏幕快照 2019-07-31 上午11.55.50

本章还有其他内容，比如递归和回文，但不是今天的重点。

每次看这些知识都会有新的体会，随着看的参考资料越来越多类，看待各种知识的角度越来越丰富，之前对我来说很难的知识点也不再困扰我了，这大概就是进步吧。

回头看我6月初期的打卡，有点陌生，甚至内容经常只是短短几句话。看来记录是管用的，不看不知道曾经的笨拙，当然现在也依然笨拙，只不过比之前强一点点而已。