返回首页
当前位置: 主页 > 编程语言 > C#教程 >

遍历组合算法的模块化

时间:2014-05-29 00:07来源:电脑教程学习网 www.etwiki.cn 编辑:admin

在日常的需求设计中,遍历组合是一个常见的问题。

  例如:现在有N个不同的数。要求在其中找到M个数,使得M个数之和为指定的S,求所有满足条件的组合。

  这是一个很明显的遍历组合的问题。一般采用递推算法,求出满足条件的解。

  这类问题一般都采用一个数组P,来存放解。遍历整个组合空间,来找出解(有可能是所有解、也可能是一个解,根据题目要求来定)

  由于这类问题解法是固定的,故在此把该算法模块化。留待日后查阅用。

  

 

  上图是该算法的算法流程图

  下面贴出该算法的伪代码,用的是VB2005

  Public Sub Traversal()
    Dim P() As Integer, K As Integer, IsGroup As Boolean

    InitData()                        注:初始化数组代码块

    K = P.GetUpperBound(0)

    Do
      If IsMatch() Then                  注:判别是否满足条件的代码块
        OutputAnswer()                 注:输出解的代码块
      End If

      IsGroup = False

      Do
        Delta(K)                     注:P(K)自增加值的代码块
        Do
          If Overflow(K) Then             注:判断P(K)是否越界的代码块
            K = K - 1
            Exit Do
          Else
            If K < P.GetUpperBound(0) Then
              K = K + 1
              SetP(K)                注:依据条件设置P(K)值的代码块
            Else
              IsGroup = True
              Exit Do
            End If

          End If
        Loop
      Loop Until (K < 0 Or IsGroup = True)

    Loop Until K < 0

    SomeEndCode()                      注:求解结束的代码块

  End Sub

 

  举例说明:有1、4、7、2、5、6、9、8、7、5十个数,求四个数之和为20的所有组合。

  分别阐述各个代码块的实现

  初始化数组代码块:

    Dim N() As Integer={1,4,7,2,5,6,9,8,7,5}

    Redim P(3)

    P(0)=0:P(1)=1:P(2)=2:P(3)=3

  判别是否满足条件的代码块:

    N(P(0))+N(P(1))+N(P(2))+N(P(3))=20

  输出解的代码块:

    Debug.Print N(P(0)) & "," & N(P(1)) & "," & N(P(2)) & "," & N(P(3))

  P(K)自增加值的代码块:

    P(K)=P(K)+1

  判断P(K)是否越界的代码块

    P(K)>K+6

  依据条件设置P(K)值的代码块:

    P(K)=P(K-1)+1

  求解结束的代码块

    本题没必要设置这段代码

 

  故本题的代码如下:

  Public Sub Traversal()
    Dim P() As Integer, K As Integer, IsGroup As Boolean

    Dim N() As Integer={1,4,7,2,5,6,9,8,7,5}

    Redim P(3)

    P(0)=0:P(1)=1:P(2)=2:P(3)=3

    K = P.GetUpperBound(0)

    Do
      If N(P(0))+N(P(1))+N(P(2))+N(P(3))=20 Then       
        Debug.Print N(P(0)) & "," & N(P(1)) & "," & N(P(2)) & "," & N(P(3))

      End If

      IsGroup = False

      Do
        P(K)=P(K)+1
        Do
          If P(K)>K+6 Then  
            K = K - 1
            Exit Do
          Else
            If K < P.GetUpperBound(0) Then
              K = K + 1
              P(K)=P(K-1)+1
            Else
              IsGroup = True
              Exit Do
            End If

          End If
        Loop
      Loop Until (K < 0 Or IsGroup = True)

    Loop Until K < 0

  End Sub

 

 

 

  把这类问题模块化,以后碰到类似的问题。直接修改各个代码块的代码。

  著文以记之。

------分隔线----------------------------
标签(Tag):遍历组合算法
------分隔线----------------------------
推荐内容
猜你感兴趣