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)    베이스 하 이 트 높이
  midPos = (0.75+1)/2  (7/8)     베이스 하 이 트 높이
그림 으로 아래 와 같이 표시 할 수 있다
//img.jbzj.com/file_images/article/201606/2016061511392912.jpg
//img.jbzj.com/file_images/article/201606/2016061511392913.jpg
//img.jbzj.com/file_images/article/201606/2016061511392914.jpg
우 리 는 연속 적 으로 제 귀 에서 발생 하 는 기 호 를 이 진 트 리 의 노드 로 볼 수 있다.뿌리 h 는 초기 값 입 니 다.바로 1/2 곳 의 기호 로 모든 부모 기호 에 두 개의 기호 가 생 겼 다.아래 그림 과 같다.
//img.jbzj.com/file_images/article/201606/2016061511392915.jpg
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);
 }
 }
}

5.코드 다운로드
http://xiazai.jb51.net/201606/yuanma/DrawRuler(jb51.net).rar
이상 이 바로 본문의 전체 내용 입 니 다.여러분 께 참고 가 될 수 있 기 를 바 랍 니 다.여러분 들 도 저 희 를 많이 응원 해 주시 기 바 랍 니 다.

좋은 웹페이지 즐겨찾기