第五课：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
function hanoi($n,$f,$t,$s){
if ($n==1){
echo "move from ".$f." to ".$t.".<br/>";
}else{
hanoi($n-1,$f,$s,$t);
hanoi(1,$f,$t,$s);
hanoi($n-1,$s,$t,$f);
}
}
hanoi(2,'f','t','s')
?>
兔子的例子用php改写：（本身的计算很简单，但是发现服务器只能计算到35个月，然后就会超过php默认的30秒计算时间）
<?php
function tuzi($x){
if($x == 0 || $x == 1){
return 1;
}else{
return tuzi($x-1)+tuzi($x-2);
}
}
function testtuzi($n){
for ($i=0;$i<$n;$i++){
echo "兔子在".$i."月的数目是".tuzi($i)."<br/>";
}
}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);