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);



发表评论

电子邮件地址不会被公开。 必填项已用*标注