主题:关于 排列&组合——深搜解法
近几天在坛子上见人讨论关于排列和组合的求法,我贴出我的程序,请大家过目
在M$中任选K个字母。
排列:
DECLARE SUB dfs (d!)
CLS
CONST maxn = 100
DIM SHARED a(maxn), used(maxn), l, k, m$
INPUT m$, k
l = LEN(m$)
CALL dfs(1)
SUB dfs (d)
IF d - 1 = k THEN
FOR i = 1 TO k: PRINT MID$(m$, a(i), 1); : NEXT i
PRINT
ELSE FOR i = 1 TO l
IF used(i) = 0 THEN
used(i) = 1
a(d) = i
dfs (d + 1)
used(i) = 0
END IF
NEXT i
END IF
END SUB
组合:
DECLARE SUB dfs (d!)
CLS
CONST maxn = 100
DIM SHARED a(maxn), used(maxn), l, k, m$
INPUT m$, k
l = LEN(m$)
CALL dfs(1)
SUB dfs (d)
IF d - 1 = k THEN
FOR i = 1 TO k: PRINT MID$(m$, a(i), 1); : NEXT i
PRINT
ELSE FOR i = a(d - 1) + 1 TO l '细心的人也许已经发现,组合和排列只在这一处改动了1个数
IF used(i) = 0 THEN
used(i) = 1
a(d) = i
dfs (d + 1)
used(i) = 0
END IF
NEXT i
END IF
END SUB
算法为DFS,深度优先搜索。
欢迎发表意见或建议,新手有不明白也欢迎提问。
在M$中任选K个字母。
排列:
DECLARE SUB dfs (d!)
CLS
CONST maxn = 100
DIM SHARED a(maxn), used(maxn), l, k, m$
INPUT m$, k
l = LEN(m$)
CALL dfs(1)
SUB dfs (d)
IF d - 1 = k THEN
FOR i = 1 TO k: PRINT MID$(m$, a(i), 1); : NEXT i
ELSE FOR i = 1 TO l
IF used(i) = 0 THEN
used(i) = 1
a(d) = i
dfs (d + 1)
used(i) = 0
END IF
NEXT i
END IF
END SUB
组合:
DECLARE SUB dfs (d!)
CLS
CONST maxn = 100
DIM SHARED a(maxn), used(maxn), l, k, m$
INPUT m$, k
l = LEN(m$)
CALL dfs(1)
SUB dfs (d)
IF d - 1 = k THEN
FOR i = 1 TO k: PRINT MID$(m$, a(i), 1); : NEXT i
ELSE FOR i = a(d - 1) + 1 TO l '细心的人也许已经发现,组合和排列只在这一处改动了1个数
IF used(i) = 0 THEN
used(i) = 1
a(d) = i
dfs (d + 1)
used(i) = 0
END IF
NEXT i
END IF
END SUB
算法为DFS,深度优先搜索。
欢迎发表意见或建议,新手有不明白也欢迎提问。