快捷導(dǎo)航

C#遞歸算法之分而治之策略

更新時(shí)間：2016年06月15日 11:39:26 作者：張玉彬

分而治之的策略主要是將大量復(fù)雜的問題分成多個(gè)子問題，解決各個(gè)子問題，從而解決原問題，下面就讓我們看看具體如何實(shí)現(xiàn)。

1.分而治之的概念

　　分而治之是一種使用遞歸解決問題的算法，主要的技巧是將一個(gè)大的復(fù)雜的問題劃分為多個(gè)子問題，而這些子問題可以作為終止條件，或者在一個(gè)遞歸步驟中得到解決，所有子問題的解決結(jié)合起來就構(gòu)成了對(duì)原問題的解決

2.分而治之的優(yōu)點(diǎn)和缺點(diǎn)

　　分而治之算法通常包括一個(gè)或者多個(gè)遞歸方法的調(diào)用，當(dāng)這些調(diào)用將數(shù)據(jù)分隔成為獨(dú)立的集合從而處理較小集合的時(shí)候，分而治之的策略將會(huì)有很高的效率，而在數(shù)據(jù)進(jìn)行分解的時(shí)候，分而治之的策略可能會(huì)產(chǎn)生大量的重復(fù)計(jì)算，從而導(dǎo)致性能的降低。

3.畫標(biāo)尺程序的分析講解

　　畫標(biāo)尺是分而治之的策略的一個(gè)簡(jiǎn)單應(yīng)用，標(biāo)尺是由長(zhǎng)度為1英寸的單元構(gòu)成的序列，每個(gè)單元的末端有最長(zhǎng)的記號(hào)，每個(gè)寸單元的1/2英寸處的記號(hào)要比末端的短，在1/4處的記號(hào)比1/2的要短，1/8處比1/4處短，編寫一個(gè)程序，在一條線上，用規(guī)則間隔來繪制標(biāo)記，在特定位置有特定大小的記號(hào)。

　　分析：在一個(gè)直線上，我們可以首先將這條直線一分為二,然后對(duì)分出來的二個(gè)再進(jìn)行拆分。直到滿足一定的精度要求，比如以最小刻度為1/8英寸為例，drawRuler作為畫標(biāo)尺的第歸函數(shù)，在drawRuler函數(shù)中用一段線段的兩端(起點(diǎn)（startPos），終點(diǎn)(endPos))，和變量h作為參數(shù),標(biāo)記的基礎(chǔ)高度為baseHeight，而標(biāo)記的高度應(yīng)該為h*baseHeight,則標(biāo)尺的畫法可以分析如下：

　　計(jì)算間隔（0.0，1.0）的中點(diǎn)：midPos = (startPost+endPos)/2;在中點(diǎn)1/2處畫一個(gè)標(biāo)記，高度為3*baseHeight

　　將中點(diǎn)分隔開的為兩條直線，再使用第歸函數(shù)drawRule，對(duì)應(yīng)的起點(diǎn)，終點(diǎn)為（0.0，0.5）和(0.5,1.0)，參數(shù)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處標(biāo)記，計(jì)算方法

　　midPos = (0.0+0.25)/2 (1/8) 高度為baseHeight

　　midPos = (0.75+1)/2 (7/8) 高度為baseHeight

　　用圖示可以表示如下

　　我們可以將連續(xù)第歸產(chǎn)生的記號(hào)看作二叉樹的節(jié)點(diǎn)。樹根h為初值。就是1/2處的記號(hào)，每個(gè)父記號(hào)都產(chǎn)生了兩個(gè)子記號(hào)。如下圖所示

4.可執(zhí)行程序文件

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);
 }
 }
}

5.代碼下載
http://xiazai.jb51.net/201606/yuanma/DrawRuler(jb51.net).rar

以上就是本文的全部?jī)?nèi)容，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: