MIT600SC笔记REC3&7


REC3

忍受印度英语(所有的rec都是在复习之前的小程序,如果不打算学习python可以不看,所以后面笔记不记这个了)

第七课:Debugging

python(也包括其他语言)中的浮点数,2进制,2进制无法精确显示小数,默认情况下输入0.1电脑得到0.10000000000000001,一个17位的近似数,大部分情况下使用小数都是安全的。无法比较两个浮点数。两数相减,只要结果足够小,就可以认为两数足够接近或者相等。

bugs更应该被称为mistakes

Debugging的目标:不是快速的消除一个bug,而是向bug-free的程序前进。

debug是成为一个好程序员最重要的部分,系统和有效率地思考。

debugger-用来找到bug的工具,但是不建议使用。大多数程序员用print来debug。

print的本质是在找程序里面歪的地方,好debugger的关键是有系统的搜索。

Search for bugs using binary search. 二分法找bug

不是他为什么没有产生我想要的结果,而是How could it have done it have done.

study available data— program text — test results

Form hypothesis (consistent with data) –> design& run repeatable experiment

Potential to refute hypothesis

Find smaller input on which program fails

No such thing as the bug. 发现一个bug还有其他的。

写一段跟程序无关的代码,让debug更容易。Use a test harness. 看起来麻烦但实际上帮助省力。

MIT600SC笔记5&6


第五课:Python中的对象

python中用于收集数据的三种结构:tuples, lists, dictionaries. 前两者是ordered sequences of objects

divisors = divisors+(i,)   //括号中是只有一个元素的数组

slice-subsequence of tuple or list

tuples –  immutable; list – mutable   //看起来list更像array

append is a method; append(L, e) –> L.append(e)–> mutates L,  i.e. , side effect 。 append一个list会直接把原有的list本身包含到目标list当中,而+号会创建新list包含原有list的元素。

Alias– one object with multiple names

Dictionary – 元素无序;For dicts, the keys can be any immutable types.  //类似于php的key=>value数组

第六课:递归

为什么要用dict而不是list?python内置关联检索的时间是恒定的。

Divide & conquer:1) 小问题比原来的问题容易解决 2)小问题的解决方案可以轻易的被整合来解决原有问题。

Recursion 1)way of describing problems. 2) way of designing solutions

Basecase :direct answer

Recurtive(inductive) case : reduce to a simpler version of a same problem plus some other simple operations

河内寺庙的例子用php改写如下(假设10次)://回文的例子我不确定怎么写,因为php没有string模组

兔子的例子用php改写:(本身的计算很简单,但是发现服务器只能计算到35个月,然后就会超过php默认的30秒计算时间)

testtuzi(12);

上面的例子虚拟主机只能运行到35个月,然后就会超时,v2ex上的人对这个解决方案嗤之以鼻,因为效率很低。

有材料说这个违反了合成效益法则:

合成效益法则(Compound interest rule):在求解一个问题的同一实例的时候,切勿在不同的递归调用中做重复性的工作。

luoyou1014给出了循环的解决方案:

<?php
function tuzi($x){
$sum = 0;
$first=0;
$second=1;
for($i=0;$i<$x;$i++){
$sum = $first + $second;
$first = $second;
$second = $sum;
}
return $sum;
}

function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo “兔子在”.$i.”月的数目是”.tuzi($i).”<br/>”;
}
}
testtuzi(60);

kuye给出了改动最小的方案:

function tuzi($x){
static $result=array();
if(isset($result[$x])){
return $result[$x];
}
if($x == 0 || $x == 1){
$r= 1;
}else{
$r= tuzi($x-1)+tuzi($x-2);
}
$result[$x]=$r;
return $r;
}
function testtuzi($n){
for ($i=0;$i<=$n;$i++){
echo “兔子在”.$i.”月的数目是”.tuzi($i).”<br/>”;
}
}
testtuzi(60);

MIT600SC笔记4&rec2


第四课:程序的机器解释

两分法并不能找到所有数的平方根,比如这些平方根在0和x之外(例如x=0.5),high=max(x,1.0)

让代码正常工作(debug)比写代码难

debug的主要问题在于他们很懒,给debugger的第一个建议就是不要懒  //没有注释或者代码写不明白

尽量让程序变短

Decomposition: Create structure; modules-self contained, reusable

Abstraction: Suppresses detail

Function组成:Name,Parameters,Body

写function常见的一个错误就是不return value

Invoking:1)The formal parameter, x, is bound to the value of the actual parameter – x, upon entry, a new scope is created. Scope is a mapping from names to objects. //其实就是变量的范围问题

assert 前面值是真的话就继续,假的话就停止。

Stack frames:Main(SCOPE) –call–> F(SCOPE) –call–> g(SCOPE)    内存占用,让function不再active就可以不占用stack

Non-Scalar value: can be decomposed,可以装载多个元素, 例如string,一些操作如slicing

Rec 2: 循环,元组(tuples),字符串,函数

//tuples应该相当于php的array

MIT600SC笔记rec1&3


REC1:编码概念介绍(复述)

这节课主要内容是回顾前两节内容。

第三课:解决问题

如何知道返回平方根的程序一定会停止(返回值)。

Decrementing Function:1)map set of program variables to an integer, 2) Starts with a non-negative value, 3) while <= 0, loop terminates, 4) Decreased each interation

abs(x) – ans3 //三次方

Exhaustive Enumeration

Brute force– is often exactly the right way to solve a problem.  //举例来说我的CPU是E3-1230 V2, 主频3.3GHZ,每秒可运行33亿次运算,足够使用穷举解决绝大多数算术问题

range(x,y) = (x, x+1,…,y-1) //python的range

python的缩进,break

寻找某个数的平方根 -> Approximation

Find a y s.t. y*y=x+-E //加或者减伊普西龙, s.t.=such that

Specification of the problem //上述的方法会导致25的平方根找到4.9989998就停止

如何预料穷举所需的时间,以平方根计算为例: 1)start point到actual result的距离 2) 伊普西龙的值 3)递增的步值

Bisection Search: 1)cut search space in half each iteration //选一个随机的start point,判定值太大或者太小,以此一次消灭一半的潜在范围,然后再腰斩剩下的一半值,依此类推。如何得知space里面有多少值->起点和终点&&切割每份的大小。二分法很适合找quick answers. 很奇怪没有2)