C#递归算法之分而治之策略_C#

C#递归算法之分而治之策略

2021-11-25 14:49张玉彬 C#

分而治之的策略主要是将大量复杂的问题分成多个子问题，解决各个子问题，从而解决原问题，下面就让我们看看具体如何实现。

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

　　用图示可以表示如下

C#递归算法之分而治之策略

　　我们可以将连续第归产生的记号看作二叉树的节点。树根h为初值。就是1/2处的记号，每个父记号都产生了两个子记号。如下图所示

C#递归算法之分而治之策略

4.可执行程序文件

				?

									using system;

									using system.collections.generic;

									using system.componentmodel;

									using system.data;

									using system.drawing;

									using system.text;

									using system.windows.forms;

									namespace drawruler

									{

									 public partial class form1 : form

									 {

									 public form1()

									 {

									 initializecomponent();

									 }

									 private void form1_load(object sender, eventargs e)

									 {

									 }

									 void drawruler(float startpos, float endpos, int h)

									 {

									 float baseheight =4;

									 if (h > 0)

									 {

									 float midpos = (startpos + endpos) / 2;

									 float height = h * baseheight;

									 drawmark(midpos, height);

									 drawruler(startpos, midpos, h - 1);

									 drawruler(midpos, endpos, h - 1);

									 }

									 }

									 void drawmark(float pos, float height)

									 {

									 using (graphics g = this.creategraphics())

									 {

									 float xoffset = 100 + pos;

									 float yoffset = 100-height;

									 solidbrush brusuh = new solidbrush(color.black);

									 pen p = new pen(brusuh, 1);

									 g.drawline(p, xoffset, yoffset, xoffset, 100);

									 }

									 }

									 private void form1_paint(object sender, painteventargs e)

									 {

									 #region 首先画一条直线

									 using (graphics g = e.graphics)

									 {

									 float xoffset = 100;

									 float yoffset = 100;

									 int len = 300;

									 solidbrush brusuh = new solidbrush(color.black);

									 pen p = new pen(brusuh, 2);

									 g.drawline(p, xoffset, yoffset, xoffset + len, yoffset);

									 }

									 #endregion

									 drawruler(0, 300, 3);

									 }

									 }

									}