时间:2021-05-20
1.分而治之的概念
分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决
2.分而治之的优点和缺点
分而治之算法通常包括一个或者多个递归方法的调用,当这些调用将数据分隔成为独立的集合从而处理较小集合的时候,分而治之的策略将会有很高的效率,而在数据进行分解的时候,分而治之的策略可能会产生大量的重复计算,从而导致性能的降低。
3.画标尺程序的分析讲解
画标尺是分而治之的策略的一个简单应用,标尺是由长度为1英寸的单元构成的序列,每个单元的末端有最长的记号,每个寸单元的1/2英寸处的记号要比末端的短,在1/4处的记号比1/2的要短,1/8处比1/4处短,编写一个程序,在一条线上,用规则间隔来绘制标记,在特定位置有特定大小的记号。
分析:在一个直线上,我们可以首先将这条直线一分为二,然后对分出来的二个再进行拆分。直到满足一定的精度要求,比如以最小刻度为1/8英寸为例,drawRuler作为画标尺的第归函数,在drawRuler函数中用一段线段的两端(起点(startPos),终点(endPos)),和变量h作为参数,标记的基础高度为baseHeight,而标记的高度应该为h*baseHeight,则标尺的画法可以分析如下:
计算间隔(0.0,1.0)的中点:midPos = (startPost+endPos)/2;在中点1/2处画一个标记,高度为3*baseHeight
将中点分隔开的为两条直线,再使用第归函数drawRule,对应的起点,终点为(0.0,0.5)和(0.5,1.0),参数h-1,这样可以使高度相比短些
第归步骤2(h=2)
midPos = (0.0+0.5)/2 (1/4处),高度为 2*baseHeight
midPos = (0.5+1.0)/2 (3/4处)高度为 2*baseHeight
第归步骤(h=1)
分别在1/8处和7/8处标记,计算方法
midPos = (0.0+0.25)/2 (1/8) 高度为baseHeight
midPos = (0.75+1)/2 (7/8) 高度为baseHeight
用图示可以表示如下
我们可以将连续第归产生的记号看作二叉树的节点。树根h为初值。就是1/2处的记号,每个父记号都产生了两个子记号。如下图所示
4.可执行程序文件
5.代码下载
http://xiazai.jb51.net/201606/yuanma/DrawRuler(jb51.net).rar
以上就是本文的全部内容,希望能给大家一个参考,也希望大家多多支持。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
上两片第归算法学习:1)递归算法之分而治之策略2)递归算法之归并排序 上一篇学习中介绍了了递归算法在排序中的一个应用:归并排序,在排序算法中还有一种算法用到了
方法一:递归算法//////一列数的规则如下:1、1、2、3、5、8、13、21、34求第30位数是多少,用递归算法实现。(C#语言)/////////publ
本文实例讲述了C#递归实现回文判断算法,分享给大家供大家参考。具体实现方法如下:复制代码代码如下:staticvoidMain(string[]args){Da
算法中递归的一个典型应用就是遍历目标文件夹,并把该文件夹下的所有文件和文件夹打印或显示出来,还可以递归计算出目标文件夹的总大小。本文即以实例形式展示了C#递归实
本文实例讲述了C#递归方法实现无限级分类显示效果。分享给大家供大家参考,具体如下:运行效果如下图所示:具体代码如下:C#无限级分类递归显示示例span{floa