Notice: Undefined index: HTTP_USER_AGENT in /var/www/html/cuijunwei/wp-content/plugins/crayon-syntax-highlighter/util/crayon_util.class.php on line 793
Notice: Undefined index: HTTP_USER_AGENT in /var/www/html/cuijunwei/wp-content/plugins/crayon-syntax-highlighter/util/crayon_util.class.php on line 793
第五课: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模组
123456789101112 <?phpfunction 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秒计算时间)
12345678910111213 <?phpfunction 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);