回溯法（复习笔记一）-四、深度剖析

时间：2024-06-02 18:04:28

问题描述：        

找出从自然数1、2、……、n中任取r个数的所有组合。

问题的状态空间为  E={（x1，x2，...，xr）∣xi∈S ，i=1，2，...，r }        

其中： S={1，2，3，...，n}       约束集为：   x1<x2<... <xr

递归算法：
INPUT: n个数分别为{1，2，…n}，r。
OUTPUT: n个数的所有r组合。
    1.    for  k =1 to r
    2.         c[k] =0
    3.    end for
    4.    k =1
    5.    while k≥1
    6.          while c[k]≤n-1
    7.                 c[k] =c[k]+1
    8.                 if c为合法的  then得到一个r组合，输出c数组
    9.                 else if c是部分解 then k =k+1
   10.         end while
   11.         c[k] =0
   12.         k =k-1
   13.  end while
非递归算法：
INPUT: n个数分别为{1，2，…n}，r。
OUTPUT: n个数的所有r组合。
    1.    for  k =1 to r
    2.         c[k] =0
    3.    end for
    4.    k =1
    5.    while k≥1
    6.          while c[k]≤n-1
    7.                 c[k] =c[k]+1
    8.                 if c为合法的  then得到一个r组合，输出c数组
    9.                 else if c是部分解 then k =k+1
   10.         end while
   11.         c[k] =0
   12.         k =k-1
   13.  end while

相关文章