【ICS_32A】Lecture2Week3

Exception

try:
    the_file= file_path.open("r")
    line_count=0
    for line in the_file:
        line_count += 1
        return line_count
except OSError:
    print("That file should not be opened")
except ValueError:
    print("That file did not contain text")
finally:
    if the_file!=None:
        the_file.close()
  1. finally无论try有无出现问题,都会执行
  2. except下只会在try中出现问题时执行
  3. except (Exception):
  4. assert(Boolean Experssion)
    • 如果True,就执行下一行,如果False,就会停止并traceback一个"AssertionError"
    • 如果表达式内本来就会出bug,那么就会返回bug信息,而不会有AssertionError
  5. nested list of interger有且只有int和nested list of interger

【ICS_32A】Lecture1Week3

文件File

  1. open(path,mode)
  2. type(open(path,mode))=>class '_io.TextIOwrapper
  3. open.mode=mode
  4. opne.write(str),会返回buffer里所有字符串的长度
  5. open.close()
  6. write之后并不会直接写入文件,而是先存在buffer中,然后在close之前将buffer写入文件中。
  7. 与print不同,write没有ending,如果要换行,必须要/n。
  8. Path(path)
  9. Path.is_file()
  10. Path.is_dir()
  11. Path.open(mode) => open(path,mode)
  12. Path.iterdir(),迭代器,C列表
  13. list(Path.iterdir())
  14. for i in Path.iterdir()
  15. Path.name =>文件名,不带扩展名
  16. Path.suffix =>扩展名

模块module

  1. import math || math.sqrt(9)
  2. from math import sqrt || sqrt(9)
  3. from math import * || 会导致大量重名

TIPS:

  1. 查标准库

【CLRS】15-动态规划DynamicProgramming

动态规划Dynammic Programming

  1. 四步骤:
    1. 刻划一个最优解的结构特征
    2. 递归的定义最优解的值
    3. 计算最优解的值,通常采用自底向上的方法
    4. 利用计算出的信息构造一个最优解
  2. 动态规划方法是付出额外的内存空间来节省计算时间,是典型的以空间换时间的例子。当然其节省时间的效果是很明显的
  3. 动态规划有两种等价的实现方法:
    1. 带备忘的自顶向下法 top-down with memoization
    2. 自底向上法 bottom-up method
      两者的渐进时间相同

子问题图

  1. 子问题图是一个有向图,每个顶点唯一对应一个子问题
  2. 若求子问题x的最优解时需要直接用到子问题y的最优解,那么在子问题图中就会有一条从子问题x的顶点到子问题y的有向边。
  3. 子问题图 G=(V,E)的规模可以确定动态规划算法的运行时间:
    • 每个子问题只求解一次,一次算法运行时间等于每个子问题求解时间之和
    • 通常,一个子问题的求解时间与子问题图中对应顶点的出度成正比
    • 通常,动态规划算法的运行时间与顶点和边的数量线性关系

钢材切割问题

矩阵链乘法问题

动态规划原理

1. 最优子结构

  1. 问题是否适合应用动态规划算法,看是否具有最优子结构性质
  2. 发觉最优子结构的通用模式:
    1. 会做出一个选择。做出这次选择会产生一个或多个待解的子问题
    2. 假定已经知道哪种选择才会得到最优解
    3. 给定可获得最优解的选择后,我们可以确定这次选择会产生哪些子问题,以及如何最好的刻划子问题空间。
    4. 利用剪切-粘贴 Cut-and-paste:利用反证法证明每个子问题的解就是它本身的最优解
      1. 假定子问题的解不是其自身的最优解
      2. 剪切掉这些非最优解
      3. 将最优解粘贴进去
      4. 得到一个更优的解
      5. 与假设矛盾,因为你现在已经有了一个最优解
  3. 保持子问题尽可能简单,只在必要时才扩展他
  4. 对于不同问题,最优子结构的不同体现在两个方面:
    1. 原问题的最优解中涉及多少个子问题
    2. 在确定最优解使用哪些子问题时,我们需要考虑多少中选择
  5. 可以用子问题的总数和每个子问题需要考虑多少选择的乘积来粗略分析算法的运行时间
  6. 子问题图也可用来做类似的分析:图中每个顶点对应一个子问题,而选择对应子问题顶点的边
  7. 在动态规划方法中,我们通常自底向上的使用最优子结构

【ICS_32A】Lecture2Week2

列表List

  1. append
  2. extend
  3. +=
  4. list(xx)
    list(range(10))
    list(1,2,3)
    list("Boo")
  5. 剪切slice:
    x[1:3]
    list[start:end+1:step=1]
    x[4:-2]
    x[-5:8
    x[-5:-1]
    x[:-5]
    x[4:]
    x[len(x)+1:]

Type Annotation

def len_at_least(s:str,min_length:int) -> bool:
    return len(s)>=min_length
  • 但是这并不是强制的,你仍然可以传(1,"xx")进去,当然会出错
  • 元组tuple: (int,str)
  • 列表List: List[int]
  • When all else fails, you can use a string litera
  • None

    • 所有方法都会返回一个值,只不过没写的都是返回None
    • type(None) => Nonetype

File

  1. file.seek(0),回到第一行

Tips:

  1. Even though Python does not check types until run-time, THAT DOES NOT mean you shouldn't think about them until run time. That also doesn't mean you shouldn't still want to say something about them in your program.

【ICS_32A】Lecture1Week2

方法 function

  1. 方法参数不能多给也不能少给,因为这两种情况都会出错
    givemefive() takes xx positional arguments but xxx was given
  2. 调用方法出错的Traceback顺序:
    1. 什么地方调用了该出错的方法
    2. 该出错的方法在哪里出错
    3. 出了什么错
  3. 局部变量和全局变量 Scope={local variables, global variables}
  4. 不要随便用全局变量
  5. 你可以在方法中写方法
    def read_and_sum_numbers():
    def read_number():
    return int(input("Enter a number, or 0 to stop"))
    total=0
    while TRUE:
    number = read)umber()
    if number==0:return total
    total+=number
  6. 调用方法时,会优先找同一层级的方法。也就是说,如果A方法中有local方法B,但是同时也存在和A同级的方法B,那么在A中调用方法B时,会优先调用local方法B。

    模块 module

  7. _name_=_main_
  8. 可以在module里写全局语句,他们将在module开始的时候就执行
  9. 如果模块本身有全局变量,且在部分方法中使用了该全局变量,那么这些方法将在引用该模块时出错。
  10. 方法中方法也是同理

其他

  1. 从project1开始在方法开头写docstring,来抽象的介绍方法
    """
    Takes an argument of any numeric type and returns its square,.
    """
  2. 课后可以用这个笔记和32a网上的笔记进行比较,查漏补缺
  3. 不能用type(1,2),只能x=1,2 => type(x)
  4. x,y,z="Boo" => x="B",y="o",z="o"

【ICS_32A】Lecture2Week1

条件与循环

if 语句

if value > 0:
    print("Positive")
elif value<0:
    print("Negative")
else:
    print("Zero")

python使用空格作为语句成分间隔符
用缩进(indention)体现各个成分块

循环

while

    while num<10:
        print(num)
        num+=1 ##没有++
    else:
        print("xxx")

在while后面可以加else,只有在while的条件不成立时才会执行
这样可以区分循环完全完成的情况和中间有break的情况,因为如果是break出来的话,是不会执行else下的命令的

格式化字符串

    print(f"Hello, (name)")

range函数

    range(6)==range(0,6,1)
    range(1,2**1024)
    r = range(10)
    r[0]==0
    r[1]==1
    r[-1]==9
    r[-10] WRONG

类似于list, 但不同于string

方法

Python自带方法

  1. print
  2. 方法本身就是一个对象,其type为function,名字为方法名
    type(getsize())
    <function getsize at ........>

【ICS_32A】Introduction to Python

变量类型转换

  1. Assignment is not expression, it is statement
  2. Expression returns a result
  3. Statement does not return reuslt
  4. 可以给int对象赋float值,将其转换成float对象,类似于重载

    10/03更新,如果将一个方法名赋值为int,其类型也会变成int,且原方法无法调用
    boo=13
    =====int=======
    boo=13.5
    =====变成float========

  5. 命名规范:
    1. 用小写字母、数字、下划线
    2. 开头必须用小写字母
    3. 用下划线作空格来代替大写字母
      studentId=>student_id

逻辑运算

  1. 逻辑运算式可以连写
    2<4<8
    True
    x=3
    0<x<5
    True
    y=4
    z=5
    x<y<z
    True
  2. or 包容性或
  3. ^ 排斥性或
  4. and

布尔值

  1. True
  2. False
  3. 布尔值可以进行算术运算
    True4
    4
    True此时作为int对象进行运算*

基础IO

Print

  1. print(var1, var2, var3 ,...,[sep=" "],[end="\n"])
    print(1,2,3)
    1 2 3
  2. 可以设置sep来设置间隔符,sep可以是任何字符串
  3. 可以设置end,end默认是转行,但通过end="",可以让其直接连在上次输出后面输出

    Input

  4. var = input()
  5. var将是个str
  6. 这是一个赋值过程,所以不会输出任何东西

String

  1. "Hello"

  2. " ' " ——如果要用单引号,就用双引号来括整个str

  3. 转义符

    \' => '
    \n 换行
    \t tab
    \\ => \
    \非法 => \\   但仍然只占一个字符长度
  4. 转义符将视为一个字符,字符长度为1

  5. \后必须要是合法字母,否则将视为错误

  6. 字符串相加可以连接两字符串

  7. "boo"*3 => "boobooboo"

  8. "Hello"=="Hello" => True

  9. "Hello"!="Hello" => False

  10. function和method的区别:

    function不需要一个对象,例如len(list)
    method必须是运用在一个对象上的,例如list.sort()

  11. str.upper()变大写

  12. str.isupper()判断是否全是大写字母,如果没有字母也算False

  13. str.upper().isupper()是允许的,但是无聊

  14. str.strip()去除除了单词之间的空格

  15. 强制类型转换

    int("3")
    bool("True")
    float("3.75")
    int("boo") WRONG
    
    age = int(input("Enter your Age:"))