题目如下:用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求:"4"不能在第三位,"3"与"5"不能相连。
基本思路:
1 把问题归结为图结构的遍历问题。实际上6个数字就是六个结点,把六个结点连接成无向连通图,对于每一个结点求这个图形的遍历路径,所有结点的遍历路径就是最后对这6个数字的排列组合结果集。
2 显然这个结果集还未达到题目的要求。从以下几个方面考虑:
1. 3,5不能相连:实际要求这个连通图的结点3,5之间不能连通, 可在构造图结构时就满足改条件,然后再遍历图。
2. 不能有重复: 考虑到有两个2,明显会存在重复结果,可以把结果集放在TreeSet中过滤重复结果
3. 4不能在第三位: 仍旧在结果集中去除满足此条件的结果。
采用二维数组定义图结构,最后的代码是:
import java.util.Iterator;
import java.util.TreeSet;
public class TestQuestion {
private String[] b = new String[]{"1", "2", "2", "3", "4", "5"};
private int n = b.length;
private boolean[] visited = new boolean[n];
visited =falsh;
private int[][] a = new int[n][n];
private String result = "";
private TreeSet TreeSet = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
a[i][j] = 0;
} else {
a[i][j] = 1;
}
}
}a[3][5] = 0;
a[5][3] = 0;
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
if (string.indexOf("4") != 2) {
System.out.println(string);
}
}
}
private void depthFirstSearch(int startIndex) {
visited[startIndex] = true;
result = result + b[startIndex];
if (result.length() == n) {
TreeSet .add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
result = result.substring(0, result.length() -1);
visited[startIndex] = false;
}
}
分享到:
相关推荐
马的遍历问题马的遍历问题马的遍历问题马的遍历问题马的遍历问题
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
使用MATLAB解决城市遍历问题的源代码。适用于试图使用MATLAB解决此类问题的用户。
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
国际象棋马的遍历问题 简化算法 棋盘自画
二叉树遍历问题 ⼀、⼆叉树的重要性 很多经典算法如 回溯、⼴度优先遍历、分治、动态规划等通常需要转化为树的问题,⽽树的题⽬难免涉及到递归的问题,因此掌握树的三 种遍历框架是必须的。 先序遍历:根,左,右 ...
个人的课程设计,由于GitHub登不上了,又怕辛辛苦苦写的代码丢了,想了想放在这吧,完美解决马的遍历问题,并有个人认为美到炸的动态演示界面,Qt写的,比较满意的一个程序,展示完满足感爆棚。
二叉树遍历问题-二叉树遍历问题
马的遍历问题,实现遍历,在棋盘中
1.设计一个文件保存地图信息,地图中标明各个城市之间是否有路及它们的距离。 2.利用图形展示地图信息。 3.手工输入起始城市 4.用红线标出从起始城市开始遍历所有城市的最短路径
二叉树遍历问题 问题描述 ---- > 给定一棵二叉树的先序遍历和中序遍历序列,求其后序遍历序列。 输入格式 ---- > 输入数据有两行,为两个字符串,其长度n均小于等于26。第一行为先序遍历序列,第二行为中序遍历...
数据结构 马的遍历问题 在中国象棋中马从棋盘任何位置起都能遍历棋盘中的所有位置
C语言程序一种是递归算法,另一种是利用站的迭代算法
数据结构课程设计《马的遍历问题》.pdf
图算法之骑士遍历问题,骑士遍历问题,或者象棋中马的遍历问题
有关于马的遍历问题的详细代码和设计文档,设计思路,用到的数据结构以及对于所定义的函数之间的联系
在一个8×8的国际象棋的棋盘上,马的走法是日字形的走法,从任意指定的方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的路径。
二叉树遍历问题 //二叉树的结构定义 typedef struct csNode { char data; struct csNode*lchild; struct csNode*rchild; } Csnode,*tree; //二叉树的建立 void CreatTree(tree *T) { char ch; cin>>ch; ...
二叉树的遍历问题,有较好的参考价值
该资源是用Java编写的简单的马的遍历问题,希望能提供给需要的人参看。