频道栏目
IT货架 > > 正文
【笔记】StanfordOpenCourse—CS106A:ProgrammingMethodology—002 Problem solving in Karel Decomposition The Idea of an algorithm
网友分享于:Jun 12, 2018 11:57:39 PM    来源: IT货架   

Problem solving in Karel

Decomposition

The Idea of an algorithm

 

1. 翻山越岭的Karl

    Karl爬山,不管是百步梯还是千步梯,类似图1

image

图 1

这个范例主要学习问题分解成一个个简单的模块,化繁为简,逐步求精。

思路

1> Karel来到山脚下(爬山当然要先到山边,没有自驾车,没有景区bus,没有。。。,只有2条腿;)。

2> 开始爬山,就是上楼梯,下楼梯;

3> 离开(爬山结束,该干嘛干嘛去,反正不能堵了山门干收费的勾当)。

 

1>和3>好说,Karel够单一,认准一个方向(east)直走,碰到墙就停下。

2>应该可以再分为3步:上山、登顶、下山。

上山:只要前面有楼梯(墙)就上,也就是左转 –> 移动 –> 右转 –> 移动;如此循环,就登顶了。

登顶:好不容易爬上来,会当临决定,总要做些啥,不管是插旗还是撒尿都可以表达到此一游,Karel只能放个方块表示。

下山:应该类似上山,只要前面为空(悬崖,别抬杠),就前进 –> 右转 –> 前进 –> 左转,如此循环,直到下到山脚。

 

分析到这里,似乎一切都ok,敲代码验证就完事儿了。但是,假设山是名山,修得特标准,上下都是一级级的台阶,但人就不同了,形形色色,四面八方,借问Karel一句:施主从何而来,又向何而去? Karel当然说:俺从西边来,向东边去。至于来有多近,去有多远。Karel就不操心了,按照指令走就是。这时,在看看上面的算法,似乎都ok,对应图1,下山也没问题,但要是环境变为11格,希望Karel走的更远,Karel就会撞地上了。悲催!

 

所以,下山的步骤就需要修改下:前面的问题就在于Karel不晓得自己是否已下到山脚,所以下山的条件是脚下是空的才能下,

下山:前进 –> 脚下是否为空(是 –> 右转 –> 前进 –> 左转 –> 看前面还有路否?(是 –> 前进)) 如此循环。

 

代码:

 

 

2. “种树”的Karel

    春寒料峭,Stanford校园里的树都光秃秃的(啥,怎没有冬青树),Karel从西向东闲逛。路见秃树,就想把其装饰下,装饰前后的效果如图2、3.

 

image

图 2

 

image

图 3

 

Karel不知道树有多高,多远。只确定有足够的方块装饰每棵树。

 

算法分析:

Karel要做的就是找到树,装饰它。

找树简单,就好比碰到墙就停下。

装饰树:爬树 –> 放树叶 –> 下树。

爬树:左转 –> 只要右边有树(墙)就前进 –> 右转。

放树叶:按图3所示放4个方块 –> 前进 –> 右转。

放4个方块:放1个方块 –> 前进 –> 左转 (循环4次)。

下树:类似上树,只要没碰到地就一直前进。

 

代码:

 

PS:这个代码里假定只有4棵树,所以Karel的包里有20个方块,如果编辑方块的数量多于20,就会出错,因为Karel不能区别墙和树。

 

3. 闯迷宫的Karel

  无它,右手法则,盲人摸象般,贴着右手的墙走,不通就左转。

 

代码:

广告服务联系QQ:1134687142 | 网站地图

版权所有: IT货架- 内容来自互联网,仅供用于技术学习,请遵循相关法律法规. 京ICP备11030978号-1