一著名软件公司的java笔试算法题！
一著名软件公司的java笔试算法题！
算法程序题：
该公司笔试题就1个，要求在10分钟内作完。
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
问题点数：10、回复次数：123Top
1 楼buyaowen（失业中，请勿打扰）回复于 2006-10-09 09:28:32 得分 0
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
=======================================================================
412345???Top
2 楼haisenmai（我应该做得到）回复于 2006-10-09 09:36:43 得分 0
10minutes not enoughTop
3 楼zsh6709（世界上没有后悔药吃的！！！）回复于 2006-10-09 10:19:39 得分 0
10分钟够的
用数组来做，我觉得
可能有点笨吧！！
如果需要我就把代码写出来Top
4 楼arbiter（同济流氓）回复于 2006-10-09 10:34:39 得分 0
有一个思路是建一个6个结点的图，每个结点代表一个数字，然后标记上两两结点的关系（是否有向），随后深度遍历，或广度遍历图，找出结点的所有走向路径，就是最后的所有排列了，如果没有准备10分钟肯定不够。Top
5 楼Rayuu（）回复于 2006-10-09 10:44:52 得分 0
学习！谁能给出个参考代码？Top
6 楼javaliu2006（）回复于 2006-10-09 10:45:10 得分 0
zsh6709(世界上没有后悔药吃的！！！)
你把代码写出来贴后面，让大家看看Top
7 楼twomao（2毛）回复于 2006-10-09 11:05:48 得分 0
先得到所有的排列组合,再用正则表达式去掉不匹配的数字..Top
8 楼likespring1（）回复于 2006-10-09 11:06:06 得分 5
int[] position1 = new int{1、2、2、3、4、5};
int[] position2 = new int{1、2、2、3、4、5};
int[] position3 = new int{1、2、2、3、4、5};
int[] position4 = new int{1、2、2、3、4、5};
int[] position5 = new int{1、2、2、3、4、5};
String tempstring = null;
int index= -1;
for (int i1=0;i1<6;i1++){
for (int i2=0;i2<6;i2++){
if (i2==i1)
break;
for (int i3=0;i3<6;i3++){
if (i3==i1 || i3==i2 )
break;
if (i3==2)
break;
for (int i4=0;i4<6;i4++){
if (i4==i1 || i4==i2 || i4==i3)
break;
for (int i5=0;i5<6;i5++){
if (i5==i1 || i5==i2 || i5==i3 || i5==i4 )
break;
tempstring =""+position1[i1]+position2[i2]+position3[i3]+position4[i4]+position4[i4];
if ((index=tempstring.indexof("3")) ){
if (tempstring.subString(index+1,index+2).equals("5"))
break;
}
if ((index=tempstring.indexof("5")) ){
if (tempstring.subString(index+1,index+2).equals("3"))
break;
}
System.err.println(position1[i1]+position2[i2]+position3[i3]+position4[i4]+position4[i4])
}
}
}
}
}Top
9 楼alienyang（）回复于 2006-10-09 11:10:31 得分 0
学习Top
10 楼netstu（孤心）回复于 2006-10-09 11:16:36 得分 0
不错Top
11 楼ChDw（米）回复于 2006-10-09 11:16:41 得分 5
private int[] num = new int[]{1,2,2,3,4,5};
private boolean[] selected = null;
public static void main(String[] args) throws Exception {
new Test().test();
}
private void test() {
selected = new boolean[num.length];
List<Integer> result = new ArrayList<Integer>();
next(result);
}
private void next(List<Integer> result) {
if(result.size() == num.length)
printResult(result);
else {
for(int i = 0; i < num.length; i++) {
if(!selected[i]) {
selected[i] = true;
result.add(num[i]);
next(result);
result.remove(result.size() - 1);
selected[i] = false;
}
}
}
}
private void printResult(List<Integer> result) {
if(result.get(2).intValue() != 4) {
for(int i = 1; i < result.size(); i++)
if(result.get(i - 1).intValue() == 3 && result.get(i).intValue() == 5)
return;
for(int i = 0; i < result.size(); i++)
System.out.print(result.get(i));
System.out.println();
}
}
Top
12 楼inorro（）回复于 2006-10-09 11:32:04 得分 0
强Top
13 楼likespring1（）回复于 2006-10-09 11:42:09 得分 0
楼上不对！
如果有两个2你怎么处理Top
14 楼ChDw（米）回复于 2006-10-09 12:01:28 得分 0
所以我使用selected数组，这个selected表示这个元素是否已经选择过而并不使用list中是否contains方法Top
15 楼ChDw（米）回复于 2006-10-09 12:02:19 得分 0
去除重复是有点问题Top
16 楼javaliu2006（）回复于 2006-10-09 12:05:17 得分 0
一软件公司笔试题
编程能力测试
1． 将40个随机数据写入数据库，并按时间编排好，
2． 将上述数据在另一台计算机中实时浏览，
3．数据库可以是任意形式的数据库，浏览界面可以自由设定。
Top
17 楼wei_x1980（牛,這不是一個"強"字能說清的）回复于 2006-10-09 12:22:38 得分 0
学习中Top
18 楼do_the_best（近我者赤）回复于 2006-10-09 13:24:37 得分 0
作为笔试题有点难，算法上出现考虑不周的地方的概率比较大。
要是上机考就比较好了。Top
19 楼solid210（）回复于 2006-10-09 14:42:52 得分 0
哪来的两个4呢?如果两个4可以,那6个4可以不?
要是可以,对6位循环输入就成了,仅仅判断第三位不等于4,3和5不相邻就可以了.
public class Test03 {
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int i = 1 ; i <= 5 ; i++){
for(int j = 1 ; j <= 5 ; j++){
if(i==5&&j==3)
continue ;
if(i==3&&j==5)
continue ;
for(int k = 1 ; k <= 5 ; k++){
if(k==5&&j==3)
continue ;
if(k==3)
continue ;
for(int m = 1 ; m <= 5 ; m++){
if(k==5&&m==3)
continue ;
for(int n = 1 ; n <= 5 ; n++){
if(m==5&&n==3)
continue ;
if(m==3&&n==5)
continue ;
for(int p = 1 ; p <= 5 ; p++){
if(p==5&&n==3)
continue ;
if(p==3&&n==5)
continue ;
System.out.println(i+""+j+""+k+""+m+""+n+""+p) ;
}
}
}
}
}
}
}
}
以上代码满足:"4"不能在第三位，"3"与"5"不能相连.但是没有去除重复
最后一个数字是555555,哈哈Top
20 楼wangyan8576（一米宽的信仰）回复于 2006-10-09 14:44:33 得分 0
以前好象在一本C的书上看过，那是用递归实现的，怎么做的就忘了，当时没怎么理解
Top
21 楼yyfhz（火山）回复于 2006-10-09 14:52:39 得分 0
写个思路
int soruce_value[] = {1,2,2,3,4,5}
如果没有重复值的话，直接一个6重循环就可以了，但是数组有重复元素。
这就可能出现数字的重复。
对于这道题目，我们可以把它看做先拼不重复的五位数，然后再对每一种拼法，在第一个"2"后面再插入第2个"2"。
---------------------------------------------------
这当然只是针对这道题目的做法。一般的，对于一个长度为n的数组a={ai, i=1,2,...n}，假设它包含m个不同的元素，我们可以把它看做是下列2个数组的联合:
A={ai,i=1,...,m}-- 代表a中各个不同的元素
B={bi,i=1,...,m}-- 代表A[i]出现的次数。
那么拼接的方式可以是：
step 1.利用m个不同的元素，拼接出数据B=a1',a2',...am'
step 2.
While B的长度<n {
(for i=1; i<=m; i++) {
如果bi>1，在B的最后一个ai后，再插入一个ai，bi=bi-1
}
}
为了实现这种做法，应当会使用到嵌套函数的调用。Top
22 楼FreeSeagull（蓝天，白云，松花江）回复于 2006-10-09 15:01:21 得分 0
《TAOCP》第一章讲有讲这个。叫做Permutation.
具体算法基本的有三种,参看
http://www.cut-the-knot.org/do_you_know/AllPerm.shtmlTop
23 楼jk88811（你的就是我的，我的还是我的~!）回复于 2006-10-09 15:07:40 得分 0
汗, 搬出<TAOCP>来了...Top
24 楼shuyanbo（楚国壮士）回复于 2006-10-09 16:07:01 得分 0
这个题目出的好像不太严谨,
题目如下：用 [1、2、2、3、4、5这六个数字] ，用java写一个main函数，打印出所有不同的排列，如：[512234、412345] 等，要求："4"不能在第三位，"3"与"5"不能相连。
如果是全排列, 应该是数字不能有重复, 我猜想题目应该是: 用1-6六个数字, 写函数打印所有全排列,要求是: 4不能在第三位,3与5不能相连.
这个用图的遍历应该很简单吧,遍历的过程中加上条件即可.Top
25 楼fdlm_dark（）回复于 2006-10-09 16:16:17 得分 0
http://community.csdn.net/Expert/topic/5068/5068524.xml?temp=.2967188
发两个怎么。。。Top
26 楼joylisten（浩渺）回复于 2006-10-09 16:17:42 得分 0
10分钟我写不出来，半小时将将够Top
27 楼wuhuiITren（乌龟）回复于 2006-10-09 19:00:00 得分 0
顶Top
28 楼fifadxj（坦克车）回复于 2006-10-09 19:22:13 得分 0
哎。。用了1个半小时。。
package test;
import java.util.ArrayList;
import java.util.List;
import javax.swing.JFrame;
public class test extends JFrame {
public static void main(String[] arsg) {
List results = new ArrayList();
String[] nums = new String[]{"1","2","2","3","4","5"};
boolean[] used = new boolean[]{false,false,false,false,false,false};
String cur = "";
int i1,i2,i3,i4,i5,i6=0;
for (i1 = 0; i1 < nums.length; i1++) {
if (used[i1] == true) continue;
used[i1] = true;
for (i2 = 0; i2 < nums.length; i2++) {
if (used[i2] == true) continue;
used[i2] = true;
for (i3 = 0; i3 < nums.length; i3++) {
if (used[i3] == true) continue;
used[i3] = true;
for (i4 = 0; i4 < nums.length; i4++) {
if (used[i4] == true) continue;
used[i4] = true;
for (i5 = 0; i5 < nums.length; i5++) {
if (used[i5] == true) continue;
used[i5] = true;
for (i6 = 0; i6 < nums.length; i6++) {
if (used[i6] == true) {
continue;
}
used[i6] = true;
cur = nums[i1]+nums[i2]+nums[i3]+nums[i4]+nums[i5]+nums[i6];
if (check(cur) == true) {
if (!results.contains(cur)) {
System.out.println(cur);
results.add(cur);
}
}
used[i6] = false;
}used[i5] = false;
}used[i4] = false;
}used[i3] = false;
}used[i2] = false;
}used[i1] = false;
}
System.out.println("count: "+results.size());
}
public static boolean check(String s) {
if (s.substring(2,3).equals("4")) return false;
if (s.substring(0,2).equals("35") || s.substring(0,2).equals("53")) return false;
if (s.substring(1,3).equals("35") || s.substring(1,3).equals("53")) return false;
if (s.substring(2,4).equals("35") || s.substring(2,4).equals("53")) return false;
if (s.substring(3,5).equals("35") || s.substring(3,5).equals("53")) return false;
if (s.substring(4,6).equals("35") || s.substring(4,6).equals("53")) return false;
return true;
}
}
Top
29 楼fifadxj（坦克车）回复于 2006-10-09 19:22:42 得分 0
198种Top
30 楼changchunren520（）回复于 2006-10-09 21:54:20 得分 0
帮顶下。请问各位大侠 for循环怎样才能运用自如。我能看懂。但是却写不出来。。Top
31 楼z_love（）回复于 2006-10-09 22:03:25 得分 0
顶以下
太强了
什么时候能达到你这种程度呀！
你学了多长时间了！
羡慕呀！
该学习！！！！Top
32 楼maque83（）回复于 2006-10-09 22:48:45 得分 0
头晕Top
33 楼zhuixun5506（>> narsil）回复于 2006-10-09 23:16:55 得分 0
markTop
34 楼arbiter（同济流氓）回复于 2006-10-10 10:39:47 得分 0
看见大家循环套循环，圈圈套圈圈的写法，我实在是忍无可忍了，6个数字还好，给你一百个数字，是不是准备百环大作战了？
我来实现一下我之前讲的基本思路：
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];
private int[][] a = new int[n][n];
private String result = "";
private TreeSet set = new TreeSet();
public static void main(String[] args) {
new TestQuestion().start();
}
private void start() {
// Initial the map a[][]
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;
}
}
}
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
// Begin to depth search.
for (int i = 0; i < n; i++) {
this.depthFirstSearch(i);
}
// Print result treeset.
Iterator it = set.iterator();
while (it.hasNext()) {
String string = (String) it.next();
// "4" can not be the third position.
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) {
// Filt the duplicate value.
set.add(result);
}
for(int j = 0; j < n; j++) {
if (a[startIndex][j] == 1 && visited[j] == false) {
depthFirstSearch(j);
} else {
continue;
}
}
// restore the result value and visited value after listing a node.
result = result.substring(0, result.length() -1);
visited[startIndex] = false;
}
}
可以结贴了。Top
35 楼mahaixing（猪的克星）回复于 2006-10-10 11:59:17 得分 0
不就是一个排列组合嘛，搞那么复杂干吗！
package com.mahaixing;
public class Permute {
private int[] temp;
private boolean[] used;
private int[] array;
public int count = 0;
private void printArray() {
for (int i = 0; i < temp.length; i++) {
System.out.print(temp[i]);
}
System.out.println();
}
private void permuteInternal(int pos) {
if (pos == array.length) {
count ++;
printArray();
return;
}
for (int i = 0; i < array.length; i++) {
if (used[i])
continue;
used[i] = true;
if ((pos == 3) && (array[i] == 4)) {
used[i] = false;
continue;
}
if (pos > 0) {
if ((temp[pos - 1] == 5) && (array[i] == 3)) {
used[i] = false;
continue;
}
if ((temp[pos - 1] == 3) && (array[i] == 5)) {
used[i] = false;
continue;
}
}
temp[pos] = array[i];
permuteInternal(pos+1);
used[i] = false;
}
}
public void permute(int[] array) {
this.temp = new int[array.length];
this.used = new boolean[array.length];
this.array = array;
permuteInternal(0);
}
public static void main(String args[]) {
int[] numbers = {1, 2, 3, 4, 5, 6};
Permute ng = new Permute();
ng.permute(numbers);
System.out.println("共有：" + ng.count + " 种排列");
}
}Top
36 楼arbiter（同济流氓）回复于 2006-10-10 13:57:14 得分 0
你写的不复杂？而且还算错了。重复结果算进去干吗？重写吧Top
37 楼horse_h（小马）回复于 2006-10-10 16:25:04 得分 0
学习Top
38 楼zhuang_zi（庄子）回复于 2006-10-10 16:50:04 得分 0
import java.util.ArrayList;
import java.util.Iterator;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
Test test = new Test();
int[] data = { 1, 2, 2, 3, 4, 5 };
ArrayList result = new ArrayList();
int startPoint = 0;
test.returnArrange(data, startPoint, result);
Iterator it = result.iterator();
System.out.println("ArraySizeBefore=" + result.size());
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
test.printArray(dataMe);
}
result = test.filter(result);
it = result.iterator();
System.out.println("ArraySizeAfterFitler=" + result.size());
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
test.printArray(dataMe);
}
}
public ArrayList getResult(int[] data) {
ArrayList result = new ArrayList();
int startPoint = 0;
returnArrange(data, startPoint, result);
result = filter(result);
return result;
}
private ArrayList filter(ArrayList result) {
ArrayList resultList = new ArrayList();
Iterator it = result.iterator();
while (it.hasNext()) {
int[] dataMe = (int[]) it.next();
if (isOK(dataMe)) {
resultList.add(dataMe);
}
}
return resultList;
}
private boolean isOK(int[] data) {
return data[2] != 4 && checkConnection(data);
}
private boolean checkConnection(int[] data) {
boolean result = true;
for (int i = 0; i < data.length - 1; i++) {
if ((data[i] == 3 && data[i + 1] == 5)
|| (data[i] == 5 && data[i + 1] == 3))
return false;
}
return result;
}
private void printArray(int[] data) {
String s = "";
for (int i = 0; i < data.length; i++) {
s += ","+data[i] ;
}
System.out.println(s.substring(1));
}
private void returnArrange(int[] data, int startPoint, ArrayList resultList) {
int currentStart = startPoint;
if (isDESC(data, startPoint)) {
resultList.add(copyArray(data));
return;
} else {
returnArrange(data, startPoint + 1, resultList);
for (int index = data.length - 1; index > startPoint; index--) {
if (data[index] > data[startPoint]) {
int anotherStartPoint = startPoint + 1;
exchangeData(data, index, startPoint);
ascArrayByFrom(data, anotherStartPoint);
returnArrange(data, anotherStartPoint, resultList);
}
}
}
}
private void exchangeData(int[] data, int positionA, int positionB) {
int temp = data[positionA];
data[positionA] = data[positionB];
data[positionB] = temp;
}
private int findSmallerPositionBeforeCurrent(int[] data, int current,
int end) {
int i = -1;
int currentNum = data[current];
for (int index = end; index >= current; index--) {
if (data[index] > currentNum) {
return index;
}
}
return i;
}
private int[] copyArray(int[] data) {
int[] copy = new int[data.length];
for (int i = 0; i < data.length; i++) {
copy[i] = data[i];
}
return copy;
}
private boolean isDESC(int[] data, int index) {
for (int i = index; i < data.length; i++) {
int tempMax = data[i];
for (int j = i + 1; j < data.length; j++) {
if (data[j] > tempMax) {
return false;
}
}
}
return true;
}
private void ascArrayByFrom(int[] data, int index) {
for (int i = index; i < data.length; i++) {
int tempMin = data[i];
for (int j = i + 1; j < data.length; j++) {
if (data[j] < tempMin) {
tempMin = data[j];
data[j] = data[i];
data[i] = tempMin;
}
}
}
}
}
Top
39 楼zhuang_zi（庄子）回复于 2006-10-10 16:50:45 得分 0
试试我这个,不对找我Top
40 楼zhuang_zi（庄子）回复于 2006-10-10 16:52:19 得分 0
核心都在returnArrange(),其余都是辅助.Top
41 楼xulipeng（）回复于 2006-10-10 17:04:48 得分 0
我好象还没看明白题目
"写一个main函数" 是不是意味着不能用递归,更不能定义其它的类啊?Top
42 楼zhaoyiguo（）回复于 2006-10-10 17:57:41 得分 0
arbiter(同济流氓)的那个思路才是王道~!!!
支持~!!!
... ...
...
有点羞于启齿...
... 可不可以把思路再讲解得详细一些?!
虽然看懂了,但是还没有开窍.
请务必帮忙.
弄清这道问题,将对我帮助很大.
有劳Top
43 楼arbiter（同济流氓）回复于 2006-10-10 18:13:58 得分 0
总算遇到知音了，哪里不清楚的，你可以说出来，我针对你的问题再回答。否则无的放式。
我可以再多说点：
3，5不能相连：实际要求这个连通图的结点3，5之间不能连通, 可在构造图结构时就满足改条件，然后再遍历图。
代码中请注意这几行：
// 3 and 5 can not be the neighbor.
a[3][5] = 0;
a[5][3] = 0;
只要这样定义图，根本不用在代码中写IF ELSE语句。
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一
性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。
只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。
关于图形数据结构建议先看看数据结构的书，主要是将如何利用二维数组描述图结构，再看看图的深度遍历实现原理。最后再应用到这个问题上来，自然就不难明白了。Top
44 楼jacklondon（jacklondon）回复于 2006-10-10 18:26:19 得分 0
应该用递归。Top
45 楼Areslp（努力ING）回复于 2006-10-11 00:12:37 得分 0
markTop
46 楼zsh6709（世界上没有后悔药吃的！！！）回复于 2006-10-11 10:37:04 得分 0
都强啊
本来我以为10分钟可以搞定的， 结果编写出来后n多错误，看来一个小时也未必能搞定，关键是思想。
我觉得
arbiter(同济流氓)
的思想很好，以前学数据结构时没发现有那么大用处，现在总算知道一点了，看来数据结构不能丢~~~~~~~~~Top
47 楼tongor（秦唐人）回复于 2006-10-11 11:22:14 得分 0
可以用数学排列组合的算法实现Top
48 楼jacklondon（jacklondon）回复于 2006-10-11 12:33:42 得分 0
我说说我的思路，递归。
n 个数字求不重复的全排列。
第一个数字可以为这 n 个中的一个，拿出一个，求剩下 n-1 个全排列，拼接在第一个后面。将第一个数字轮换，重复以上操作。
Top
49 楼zhl0369（T_stone）回复于 2006-10-11 14:24:16 得分 0
半个小时
不过好像算法不怎么样，以前学的算法都忘光了！！
public class Temp {
public static void main(String[] args) {
// TODO Auto-generated method stub
int count =0;
int[] a={1,2,2,3,4,5};
for(int i0=0;i0<6;i0++)
for(int i1=0;i1<6;i1++)
for(int i2=0;i2<6;i2++)
for(int i3=0;i3<6;i3++)
for(int i4=0;i4<6;i4++)
for(int i5=0;i5<6;i5++)
if(check(i0,i1,i2,i3,i4,i5)){
System.out.println(""+a[i0]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]);
count++;
}
System.out.println("总计："+count);
}
public static boolean check (int i0,int i1,int i2,int i3,int i4,int i5){
if (i0==i1||i0==i2||i0==i3||i0==i4||i0==i5||i1==i2||i1==i3||i1==i4||i1==i5||i2==i3||i2==i4||i2==i5||i3==i4||i3==i5||i4==i5)
return false;
if(i2==4)
return false;
if ((i0==3&&i1==5)||(i1==3&&i2==5)||(i2==3&&i3==5)||(i3==3&&i4==5)||(i4==3&&i5==5))
return false;
if ((i0==5&&i1==3)||(i1==5&&i2==3)||(i2==5&&i3==3)||(i3==5&&i4==3)||(i4==5&&i5==3))
return false;
int[] b = {i0,i1,i2,i3,i4,i5};
int start=0;
int end=0;
for (int i=0;i<6;i++){
if (b[i]==1)
start = i;
if(b[i]==2)
end =i;
}
if(start<end)
return false;
return true;
}
}
Top
50 楼eric0et（战鸦十四号）回复于 2006-10-11 14:52:09 得分 0
题目如下：用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
-----------------------
1、2、2、3、4、5 6个数字能组出412345？
Top
51 楼liuzhiyuan（）回复于 2006-10-11 17:19:45 得分 0
需要考虑一下,关注可读性强的答案,呵呵Top
52 楼mahaixing（猪的克星）回复于 2006-10-17 10:58:46 得分 0
to: arbiter(同济流氓)
刚才运行了一下你的程序，好像你的有重复吧。
头3个结果：
122345
122543
123245
最后3个结果
543122
543212
543221Top
53 楼arbiter（同济流氓）回复于 2006-10-17 15:00:43 得分 0
好几个算法都算出参考答案是 198 了。
你给头三个，最后三个，哪两个重了？Top
54 楼vulner（猪猪）回复于 2006-10-17 15:30:22 得分 0
笨笨的硬写一个:结果好像有198个.
public static void main(String args[]) {
int[] a = new int[6];
int[] b = new int[6];
int total = 0;
outer:for (int i = 122345; i <= 543221; i++) {
for (int k = 0; k < b.length; k++) {
b[k] = 0;
}
a[0] = i / 100000;
a[1] = i / 10000 - i / 100000 * 10;
a[2] = i / 1000 - i / 10000 * 10;
a[3] = i / 100 - i / 1000 * 10;
a[4] = i / 10 - i / 100 * 10;
a[5] = i / 1 - i / 10 * 10;
if (a[2] == 4)
continue outer;
for (int j = 0; j < a.length; j++) {
if (a[j] > 5)
continue outer;
if (a[j] == 3) {
if (j != 5 && a[j + 1] == 5)
continue outer;
if (j != 0 && a[j - 1] == 5)
continue outer;
}
switch (a[j]) {
case 1:
b[1]++;
break;
case 2:
b[2]++;
break;
case 3:
b[3]++;
break;
case 4:
b[4]++;
break;
case 5:
b[5]++;
break;
}
}
if (b[0] == 0 && b[1] == 1 && b[2] == 2 && b[3] == 1 && b[4] == 1 &&
b[5] == 1) {
total++;
System.out.println(i);
}
}
System.out.println("total=" + total);
}Top
55 楼seeing2000（飞扬的秋）回复于 2006-10-17 15:56:24 得分 0
各位看下我的程序，应该没问题了：
/**
* (c) 2006 Siemens AG
*
* Project Corba 3GPP North-Bound Interface Agent
* Subproject test
* File proTest.java
* Created on Oct 17, 2006 by CN1SY082. (TODO check user name)
*
* History:
* Date(Y.M.D) User Reason (plus CR, LM, Fault number)
*
*/
package test1;
import java.awt.List;
public class proTest {
private static int[] num = new int[]{1,2,2,3,4,5};
private static int MAX = num.length;
private static boolean state[] = new boolean[MAX + 1];
private static int item[] = new int[MAX + 1];
static List numList = new List();
public static void proNum(){
String tempNum = "";//store the num String
int tempIndex = 0;
DoPermutation(1);
removeNum(numList);
}
public static void DoPermutation(int pos) {
String tt = "";
if (pos > MAX) {
for (int j = 1; j <= MAX; j++){
tt = tt.concat(String.valueOf(num[item[j]-1]));
}
boolean reComp = compareBefor(tt,numList);
if(reComp == true){
System.out.println("there is the same elements : " + tt);
}else{
numList.add(tt);
}
return;
}
for (int i = 1; i <= MAX; i++) {
if (!state[i]) {
state[i] = true;
item[pos] = i;
DoPermutation(pos + 1);
state[i] = false;
}
}
}
public static boolean compareBefor(String temNum,List temList){
boolean bol = false;//if return false , then there are no same String , if return true , then there is the same String
for(int i = 0; i < temList.countItems(); i++){
String getList = temList.getItem(i);
if(getList.equalsIgnoreCase(temNum)){
bol = true;
}else{
bol = false;
}
}
return bol;
}
public static void removeNum(List listnum){
int i = 0;
for(;i< listnum.countItems(); i++){
String sdd = listnum.getItem(i);
if(String.valueOf(sdd.charAt(3)).equals("4")){
listnum.remove(i);
break;
}else if(sdd.contains("35")||sdd.contains("53")){
listnum.remove(i);
break;
}else{
continue;
}
}
if(i<listnum.countItems()){
removeNum(listnum);
}else{
numList = listnum;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
proNum();
for(int i = 0 ; i < numList.countItems(); i++){
System.out.println(numList.getItem(i));
}
}
}
/* EOF */Top
56 楼seeing2000（飞扬的秋）回复于 2006-10-17 16:06:02 得分 0
你们确定只有１９８个？我算的是３86个Top
57 楼mahaixing（猪的克星）回复于 2006-10-17 16:56:38 得分 0
to: arbiter(同济流氓)
抱歉，我弄错了。怪我没看清他的题目，没有考虑到重复的情况。结果应该是198个。Top
58 楼yanxiantong（）回复于 2006-10-17 18:51:10 得分 0
vulner(猪猪) 我想对你说一个字"牛"！你的编程思想！简直是．．．．Top
59 楼salia（）回复于 2006-10-17 20:38:59 得分 0
package yan;
public class RroTest {
static int [] v={1,2,2,3,4,5};
static void check4(int i){
if(v[i]==4){
//continue;
}
}
static void check35(int i, int j){
if((v[i]==3 & v[j]==5)||(v[i]==5 & v[j]==3) ){
}
}
public static void main(String[] args) {
for(int k1=0; k1<6; k1++){
int b1=v[k1];
for(int k2=0; k2<6; k2++){
if((v[k1]==3 & v[k2]==5)||(v[k1]==5 & v[k2]==3) ){
continue;
}
int b2=v[k2];
for(int k3=0; k3<6; k3++){
if(v[k3]==4){
continue;
}
if((v[k2]==3 & v[k3]==5)||(v[k2]==5 & v[k3]==3) ){
continue;
}
int b3=v[k3];
for(int k4=0; k4<6; k4++){
if((v[k3]==3 & v[k4]==5)||(v[k3]==5 & v[k4]==3) ){
continue;
}
int b4=v[k4];
for(int k5=0; k5<6; k5++){
if((v[k4]==3 & v[k5]==5)||(v[k4]==5 & v[k5]==3) ){
continue;
}
int b5=v[k5];
for(int k6=0; k6<6; k6++){
if((v[k5]==3 & v[k6]==5)||(v[k5]==5 & v[k6]==3) ){
continue;
}
int b6=v[k6];
System.out.println(""+b1+b2+b3+b4+b5+b6);
}
}
}
}
}
}
}
}
Top
60 楼blue_sky2008（IT->egg）回复于 2006-10-17 20:46:48 得分 0
都这么强啊
Top
61 楼salia（）回复于 2006-10-17 20:47:43 得分 0
不好意思...重新发过:
按题目要求..我算到结果有:29358种...用了半个钟
package yan;
public class RroTest {
static int [] v={1,2,2,3,4,5};
public static void main(String[] args) {
int nunber=0;
for(int k1=0; k1<6; k1++){
int b1=v[k1];
for(int k2=0; k2<6; k2++){
if((v[k1]==3 & v[k2]==5)||(v[k1]==5 & v[k2]==3) ){continue;}
int b2=v[k2];
for(int k3=0; k3<6; k3++){
if(v[k3]==4){ continue;}
if((v[k2]==3 & v[k3]==5)||(v[k2]==5 & v[k3]==3) ){continue;}
int b3=v[k3];
for(int k4=0; k4<6; k4++){
if((v[k3]==3 & v[k4]==5)||(v[k3]==5 & v[k4]==3) ){continue;}
int b4=v[k4];
for(int k5=0; k5<6; k5++){
if((v[k4]==3 & v[k5]==5)||(v[k4]==5 & v[k5]==3) ){continue;}
int b5=v[k5];
for(int k6=0; k6<6; k6++){
if((v[k5]==3 & v[k6]==5)||(v[k5]==5 & v[k6]==3) ){continue;}
int b6=v[k6];
nunber++;
System.out.println(""+nunber+" :"+b1+b2+b3+b4+b5+b6);
}
}
}
}
}
}
}
}
Top
62 楼kymair（日向雏田）回复于 2006-10-17 21:21:41 得分 0
这下大家认识到数据结构课程的重要性了吧……
Top
63 楼green2008（开始8年抗战！）回复于 2006-10-17 21:25:36 得分 0
UPTop
64 楼zhangyuwei_（咸鱼）回复于 2006-10-18 01:24:21 得分 0
public class test
{
public static boolean boo(int i,int j)
{
if(i==2 && j==4 || i==4 && j==2)
return true;
return false;
}
public static void main(String[] args)
{
String str;
int[] arr1={1,2,3,4,5};
int[] arr2={1,2,3,4,5};
int[] arr3={1,2,3,4,5};
int[] arr4={1,2,3,4,5};
int[] arr5={1,2,3,4,5};
for(int i1=0;i1<5;i1++)
{
for(int i2=0;i2<5;i2++)
{
if(boo(i1,i2))
continue;
for(int i3=0;i3<5;i3++)
{
if(boo(i2,i3) || i3==3)
continue;
for(int i4=0;i4<5;i4++)
{
if(boo(i3,i4))
continue;
for(int i5=0;i5<5;i5++)
{
if(boo(i4,i5))
continue;
str=arr1[i1]+""+arr2[i2]+""+arr3[i3]+""+arr4[i4]+""+arr5[i5];
System.out.println(str);
}
}
}
}
}
}
}
1780个结果，无重复
Top
65 楼flyineagle（纸上得来终觉浅，绝知此事要躬行）回复于 2006-10-18 01:51:02 得分 0
学习~~~~Top
66 楼vulner（猪猪）回复于 2006-10-18 13:33:33 得分 0
to:yanxiantong()
见笑，见笑:P，数据结构纯属是重修的补考过的，基本没什么概念，得系统的学习下了。Top
67 楼ak_2005（★★★★★）回复于 2006-10-18 13:53:10 得分 0
MARK FIRSTTop
68 楼lgh2008（ar_guang）回复于 2006-10-18 14:29:33 得分 0
to: arbiter(同济流氓) 、
mahaixing(猪的克星)、
seeing2000(飞扬的秋)、
fifadxj(坦克车)、
vulner(猪猪)
请教一下，
你们的结果都不超过 300 个， 但我觉得结果应该会超过 400 个 ， 因为6个数的所有排列是： 720 个( 6 * 5 * 4 * 3 * 2 * 1 = 720 ) , 去除少量不符合要求的（ 应该不会超过 1/3 )， 应该会超过 400 个 。
不知我的分析对否， 请指正。
Top
69 楼arbiter（同济流氓）回复于 2006-10-18 14:37:11 得分 0
不要想当然，跑程序，看结果，再思考Top
70 楼lgh2008（ar_guang）回复于 2006-10-18 15:24:49 得分 0
to: arbiter(同济流氓)
我跑过上面的程序 ，我很佩服你们算法，但我总觉得结果会超过 198 个。Top
71 楼pirateRocy（海盗罗西）回复于 2006-10-18 16:59:02 得分 0
to: arbiter(同济流氓)
想法不错，但是，个人认为，如果不是利用set来去处重复项，
就十全十美了。Top
72 楼cecoo（小风）回复于 2006-10-18 20:32:06 得分 0
到底谁强啊？？？
Top
73 楼zanbije（）回复于 2006-10-18 21:05:51 得分 0
大家都好强.学习.Top
74 楼guzuoshantou（孤小小）回复于 2006-10-19 00:19:48 得分 0
下面是我以前所能研究出的最精简的序列算法(当然只是对于我来说,肯定还有比这更好的多的算法).我利用了递归算法,一个缺点是不能执行太多个数的序列,否则递归太深会抛出异常,但可以把递归改成for循环,就会避免这个问题,但因为我对递归比较着迷,所以就没去改.至于楼主说的那些不满足的条件,可以加个validate方法,在打印时验证一下即可.本人较懒所以没去做,只是研究算法而已,那些附加条件没什么技术含量.(在这提一点,千万别认为用一大堆for循环算出答案也算是种算法,那跟逐个打印出来没什么两样,试想一下,给你N个数的序列,你该怎么办)
public class TestMain {
public TestMain() {
}
public static void main(String[] args) {
TestMain testmain = new TestMain();
char[] c=new char[]{'1','2','3','4','5'};
testmain.start(c);
System.out.println(testmain.count(c.length));
}
public void start(char[] c){
start(c,c.length,this.count(c.length),1);
}
private void start(char[] c,int size,int count,int n){
if(n>count) return;
int f1=n%size;
int f2=f1-1;
if(f2<0) f2=size-1;
char temp = c[f1];
c[f1] = c[f2];
c[f2] = temp;
System.out.println(c);
start(c,size,count,++n);
}
private int count(int n){
if(n==1) return 1;
return n*count(--n);
}
}Top
75 楼guzuoshantou（孤小小）回复于 2006-10-19 00:37:50 得分 0
在这里面 arbiter(同济流氓) 图构的思想是最好的,向往之!用图构思路非常清析,但用来解决这道题有点大材小用,效率不够好.(欢迎拍砖,被拍得越惨,就学到越多)Top
76 楼jy02209334（失意中......）回复于 2006-10-19 09:53:58 得分 0
public class Test
{
public static void main(String[] args)
{
int[] a = {1,2,2,3,4,5};
int sum = 0;
for(int i = 0 ; i < a.length ; i++ )
{
for(int j = 0 ; j < a.length ; j++ )
{
if(j == i||i == 3 && j == 5 || j == 3 && i == 5 )continue;
for(int k = 0 ; k < a.length ; k++ )
{
if(k == i || k == j || k == 4 || j == 3 && k == 5 || k == 3 && j == 5)continue;
for(int t = 0 ; t < a.length ; t++)
{
if(t == i || t == j || t == k || k == 3 && t == 5 || t == 3 && k == 5)continue;
for(int s = 0 ; s < a.length ; s++ )
{
if(s == i || s == j || s == k || s == t || s == 3 && t == 5 || t == 3 && s == 5)continue;
for(int n = 0 ; n < a.length ; n++ )
{
if(n == i || n == j || n == k || n == t || n == s || s == 3 && n == 5 || n == 3&& s == 5)continue;
System.out.println("第"+ sum++ +"种:"+i+j+k+t+s+n);
}
}
}
}
}
}
}
}
我用的笨办法,为什么结果有395个?请问哪有问题吗Top
77 楼arbiter（同济流氓）回复于 2006-10-19 10:22:08 得分 0
pirateRocy(海盗罗西):
实际上基于图的算法好处在于，只要你能定义好满足题目要求的图结构，遍历的结果就是你要的结果，不用任何对遍历结果做任何处理。包括本题中的：4不能在第三位置，3，5不能相连，唯一
性要求，其实都可以在体现在构造的图形结构里，然后直接遍历图取得自己要的结果。而不用再次处理结果集。
只是说这里实际上对其它要求要体现在图结构里有困难（理论上是可以的），但起码3，5不能相接是很好构造的，就是上面的代码段来解释的。
所以不想用TREESET，可以把心思花在构造唯一性的图上，我这里用TREESET只是偷懒的做法，有兴趣的，可以把符合题目要求的图构造出来，然后直接深度遍历图求解。理论上确实存在你说的十全十美的解法。
TO:guzuoshantou(孤小小)
图的深度遍历原理也是递归，好处在于它首先构造了模型，再处理模型，模型代码和处理模型的代码是松耦合的，自然思路就很清晰，至于说到效率，其实并不低，你可以比较一下，我没跑过你的程序，但是我比较过的其它算法，这是最快的。Top
78 楼laoxing521（想做程序员的农民）回复于 2006-10-19 10:34:17 得分 0
数学不好，只能靠边看
顶一个Top
79 楼lgh2008（ar_guang）回复于 2006-10-19 11:51:37 得分 0
再 to: arbiter(同济流氓)
如果我没有看错的话， 你的结果没有包含排列：
532412
253241
531242
531422
412532
453212
453221
453122
241253
242531
253124
421253
221534
212534
425321
415322
253412
153242
532142
142532
215342
245321
425312
122534
当然，我只列举了一部分。
Top
80 楼lgh2008（ar_guang）回复于 2006-10-19 13:04:54 得分 0
不好意思，看错了，有一个条件没有考虑。Top
81 楼kumao（）回复于 2007-01-10 16:41:26 得分 0
做了一下，10分钟太难了，不过觉得自己这个思路比较简单，仅供大家参考。
因为是数字数列实际上如果不考虑重复情况，6个数就有6×5×4×3×2×1＝720种情况，程序就是要编写出这个数列，然后重复不重复就很好解决了。我是用字符串解决的。
我谈一下我自己的思路，假设3个字符，1，2，3
传递 1，2，3 数组
取出 1
传递 2，3 数组
取出 2
传递 3 数组
得到 123
返回
取出 3
传递 2 数组
得到132
返回
返回
取出 2
传递 1，3 数组
取出 1
传递 3 数组
得到 213
返回
取出 3
传递 1 数组
得到 231
返回
返回
取出 3
传递 1，2 数组
取出 1
传递 2 数组
得到 312
返回
取出 2
传递 1 数组
得到 321
返回
返回
即依次在数组中抽取一个元素，然后将抽取后的数组传递下去，进行下一次抽取，直到剩下一个元素
现在考虑4个 元素 1，2，3，4
应该是这样的结果
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
所以根据这个思路必须使用递归函数。根据这个思路写了以下一段程序
关键是2点，一个是递归的时候，每递归一次，传递一个新数组，数组元素去掉1个
第二是必须把丢掉的数组元素也一并传递进去，否则字符串就少了。
package Test;
public class PrintListTest1 {
//计算总共有多数符合条件的列表
private static int i=0;
//结果字符串
String resultstr="" ;
//将数组转换成字符串 也可以合并成一个数组什么的
private String getList(int[] a){
String result="";
for(int len=0;len<a.length;len++)
result=result+a[len];
return result;
}
//判断是否符合条件这个对程序意义不大的
private boolean isValidStr(String str){
if (str.charAt(2)=='4')
return false;
if (str.indexOf("35")>-1)
return false;
if (str.indexOf("53")>-1)
return false;
return true;
}
/*
传递去除元素的数组，好像数组没有直接方法可以删除一个元素
只能再造一个数组
*/
private int[] DelArray(int[] a,int pos){
if (pos>a.length-1) return a;
int len=a.length-1;
int[] newArray=new int[len];
for(int i=0;i<len+1;i++){
if (i<pos) newArray[i]=a[i];
if (i>pos) newArray[i-1]=a[i];
}
return newArray;
}
void GetList(String prestr,int[] a){
/*
prestr 就是被抽取得数组元素， 为了简便使用字符串
大家也可以使用 数组什么的
*/
/*
这个是符合题目的一段，但是觉得打印出
完整数列才是题目的意义，符合条件什么的就很简单了
判断是否符合条件，判断是否重复
if (a.length<2){
String result;
result=prestr+getList(a);
if(isValidStr(result)){
//if(true){
if (resultstr.indexOf(result)==-1){