这是我在论坛上回的一个帖子，感觉很有意思就在这里保存下来，以免丢失！ 原贴地址： http://community.csdn.net/Expert/topic/3964/3964967.xml?temp=.7246057 提问（我稍加更改）： 做一函数，比如 向函数传入一个6函数计算出5行， 每二个一对，一行3对，一行中必须出现{1,2,3,4,5,6}； 两行中不能有相同的一对！ 向函数传入一个 12 则输出11行等等... //例:如6则输出这样内容,每组必须无重复
//则函数计算出5行，每行３对，2个一对，无重复的组合 1-2,3-4,5-6
2-4,3-5,1-6
3-2,4-6,1-5
4-5,3-1,2-6
5-2,1-4,3-6 我的解答： 给搂主一个提议：这是我精心为你设计的一个算法，如果有什么不对的地方，给我发消息！ 具体算法步骤：
输入num（偶数）时，
用(x,y)模式表示x-y
弄一个邻居表TA，如下是（1,2,3,4,…,i,i+1,…num）的所有二位组合：
p1----> (1,2),(1,3),(1,4)…,(1, num)
p2----> (2,3),(2,4)…(2, num)
p3----> (3,4),…,(3, num)
…
pi---->(i,i+1),…,(i,num)
…
p(num-1)----> (num-1,num)
寻找一组的步骤如下： 初始化：定义集合SA,用来存储已经被包含的x,y，初始化SA＝{},
注意：未处理(x1,y1)：表示(x1,y1)没有被尝试地包含在SA中，所谓尝试，是因为即使被包含进去，也可能被回滚掉！ 第1步，取p1中第一个未处理(1,y1)，SA ={1,y1}； 第2步，如果2在SA中，进入第3步，
否则如果p2存在未处理(2,y2)，取p2中第一个未处理(2,y2)，SA =SA+{2,y2}；
否则如果p2不存在未处理(2,y2)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； 第3步，如果3在SA中，进入第４步，
否则如果p3存在未处理(3,y3)，取p3中第一个未处理(3,y3)，SA =SA+{3,y3}；
否则如果p3不存在未处理(3,y3)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； … 第i步，如果i在SA中，进入第i+1步，
否则如果pi存在未处理(i,yi)，取pi中第一个未处理(i,yi)，SA =SA+{i,yi}；
否则如果pi不存在未处理(i,yi)，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； …
第num-1步，如果num-1在SA中，进入第num步,
否则如果p(num-1)存在未处理((num-1),y(num-1))，取p(num-1)中第一个未处理((num-1),y(num-1))，SA =SA+{(num-1),y(num-1)}；
否则如果p(num-1)不存在未处理((num-1),y(num-1))，去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步； 第num步，如果SA还未全包括{1,2,3,4, …,i,i+1,…num},去掉最后加入SA的两个数，然后返回到最后加入元素到SA的那一步；
否则，假设SA={x1,y1,x2,y2,…},则从邻居表中删除(x1,y1),(x2,y2),…；然后到初始化重新开始寻找下一组，直到邻居表中没有元素！ 再给你一个例子：
当为6时，
邻居表，
p1----> (1,2),(1,3),(1,4),(1,5),(1,6)
p2----> (2,3),(2,4),(2,5),(2,6)
p3----> (3,4),(3,5),(3,6)
p4----> (4,5),(4,6)
p5----> (5,6) 找第1组过程：
第1步，p1取（1，2），SA={1,2}；
第2步, 2在SA中，转下一步；
第3步，p3取 (3，4)，SA={1,2,3,4}；
第4步，4在SA中，转下一步；
第5步，p5取 (5，6)，SA={1,2,3,4,5,6}；
第6步，得到第一组(1,2),(3,4),(5,6），
从邻居表中删除(1,2),(3,4),(5,6），邻居表变为
p1----> (1,3),(1,4),(1,5),(1,6)
p2----> (2,3),(2,4),(2,5),(2,6)
p3----> (3,5),(3,6)
p4----> (4,5),(4,6) 找第2组过程：
第1步，p1取（1，3），SA={1,3}；
第2步, p2取 (2，4)，SA={1,3,2,4}；
第3步，3在SA中，转下一步；
第4步，4在SA中，转下一步；
第5步，p5不存在未处理(5,y5)，去掉最后加入SA的两个数,SA={1,3}；然后返回到最后加入元素到SA的第2步,
第2步, p2取 (2，5)，SA={1,3,2,5}；
第3步，3在SA中，转下一步；
第4步，p2取 (4，6), SA={1,3,2,5,4,6}；
第5步，5在SA中，转下一步
第6步，得到第二组(1,3),(2,5),(4,6），
从邻居表中删除(1,3),(2,5),(4,6），邻居表变为
p1----> (1,4),(1,5),(1,6)
p2----> (2,3),(2,4)(2,6)
p3----> (3,5),(3,6)
p4----> (4,5) 找第3组过程：
…
找第4组过程：
…
找第5组过程：
…
p1----> (1,6)
p2----> (2,3)
p3---->
p4----> (4,5) 可以找到5组为
(1,2),(3,4),(5,6）
(1,3),(2,5),(4,6）
(1,4),(2,6),(3,5）
(1,5),(2,4),(3,6）
(1,6),(2,3),(4,5） 结果正确吧？
|
本类阅读TOP10