用1,2,3,4,5组成不重复5位数,4不能在第三位,3与5不能相连.各位都有什么好的方法？？
先写出我认为最简单，最容易看懂的方法吧，那位都更有效率的方法，可以交流交流哈..
//对第一题增加难度，用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，--------------------编程问答-------------------- 输出结果：
//如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
public class Test3
{
public static void main(String[] args)
{
int number = 0;
int count = 0;
String numberStr;
for (int a = 1; a <= 5; a++)
{
for (int b = 1; b <= 5; b++)
{
for (int c = 1; c <= 5; c++)
{
for (int d = 1; d <= 5; d++)
{
for (int e = 1; e <= 5; e++)
{
// 打印出所有不重复的数字
if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
{
number = a * 10000 + b * 1000 + c * 100 + d * 10 + e;
numberStr = String.valueOf(number);
// 4不能再第3位， "3"与"5"不能相连
if (numberStr.indexOf("4") != 2 && numberStr.indexOf("35") == -1 && numberStr.indexOf("53") == -1)
{
count++;
System.out.println(numberStr);
}
}
}
}
}
}
}
System.out.println("count=" + count);
}
}
12345--------------------编程问答--------------------
12543
13245
13254
14325
14523
15234
15243
21345
21543
23145
23154
24315
24513
25134
25143
31245
31254
31524
31542
32145
32154
32514
32541
34125
34152
34215
34251
34512
34521
41325
41523
42315
42513
43125
43152
43215
43251
45123
45132
45213
45231
51234
51243
51324
51342
52134
52143
52314
52341
54123
54132
54213
54231
54312
54321
count=56
--------------------编程问答--------------------
--------------------编程问答--------------------
好吧 为什么有人和你几乎同时发表该帖子呢
--------------------编程问答--------------------
你用了多长时间，，，，从Main，开始到结束。？？
--------------------编程问答--------------------
//对第一题增加难度，用1、2、2、3、4、5这六个数字，用java写一个main函数，打印出所有不同的排列，
//如：512234、412345等，要求："4"不能在第三位，"3"与"5"不能相连。
public class Test3
{
public static void main(String[] args)
{
int number = 0;
int count = 0;
String numberStr;
for (int a = 1; a <= 5; a++)
{
for (int b = 1; b <= 5; b++)
{
int c=1;
while(c<=5){
for (int d = 1; d <= 5; d++)
{
for (int e = 1; e <= 5; e++)
{
// 打印出所有不重复的数字
if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
{
number = a * 10000 + b * 1000 + c * 100 + d * 10 + e;
numberStr = String.valueOf(number);
// 4不能再第3位， "3"与"5"不能相连
if (numberStr.indexOf("35") == -1 && numberStr.indexOf("53") == -1)
{
count++;
System.out.println(numberStr);
}
}
}
}
c++;
if(c==4) c++;
}
}
}
System.out.println("count=" + count);
}
}
减了一些循环 你看一下 --------------------编程问答-------------------- 想了想35和53应该还可以去掉一些循环语句 --------------------编程问答--------------------
到底5个数还是6个数…… --------------------编程问答-------------------- 其实还可以优化！ --------------------编程问答-------------------- 先回复下，一会详细看下。蛮有意思 --------------------编程问答-------------------- package com.lh.test;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Demo
{
public static void main(String[] args)
{
long start = System.currentTimeMillis();
Test1();
long end = System.currentTimeMillis();
System.out.println("你的运行时间：" + (long)(end - start));
start = System.currentTimeMillis();
System.out.println("开始时间：" + System.currentTimeMillis());
Test();
System.out.println("结束时候用时：" + (long)(System.currentTimeMillis() - start));
}
public static void Test1()
{
int number = 0;
int count = 0;
String numberStr;
for (int a = 1; a <= 5; a++)
{
for (int b = 1; b <= 5; b++)
{
int c=1;
while(c<=5){
for (int d = 1; d <= 5; d++)
{
for (int e = 1; e <= 5; e++)
{
// 打印出所有不重复的数字
if (a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e)
{
number = a * 10000 + b * 1000 + c * 100 + d * 10 + e;
numberStr = String.valueOf(number);
// 4不能再第3位， "3"与"5"不能相连
if (numberStr.indexOf("35") == -1 && numberStr.indexOf("53") == -1)
{
count++;
System.out.println(numberStr);
}
}
}
}
c++;
if(c==4) c++;
}
}
}
System.out.println("count=" + count);
}
public static void Test()
{
int number = 0;
int count = 0;
String numberStr;
for (int a = 1; a <= 5; a++)
{
for (int b = 1; b <= 5; b++)
{
int c=1;
if(a == b)
{
continue;
}
while(c<=5){
for (int d = 1; d <= 5; d++)
{
if(a == d || b == d)
{
continue;
}
for (int e = 1; e <= 5; e++)
{
if(a == e || b == e || d == e)
{
continue;
}
// 打印出所有不重复的数字
if (a != c && b != c && c != d && c != e)
{
number = a * 10000 + b * 1000 + c * 100 + d * 10 + e;
numberStr = String.valueOf(number);
// 4不能再第3位， "3"与"5"不能相连
if (numberStr.indexOf("35") == -1 && numberStr.indexOf("53") == -1)
{
count++;
System.out.println(numberStr);
}
}
}
}
c++;
if(c==4) c++;
}
}
}
System.out.println("count=" + count);
}
}
--------------------编程问答-------------------- Test是我改写你的。
Test是你的。 --------------------编程问答--------------------
学习了
--------------------编程问答--------------------
#2 
--------------------编程问答--------------------
我用递归来实现吧，这样看起来简单一些，分成每一小步，而且扩展性强，如下：
--------------------编程问答--------------------
public static int n = 0;
public static void main(String[] args) {
List<String> list = new LinkedList<String>(Arrays.asList("1","2","3","4","5"));
listAll(list, "");
System.out.println(n);
}
public static void listAll(List<String> list, String strNum) {
if (list.isEmpty()) {
n++;
System.out.println(strNum);
}
for (int i = 0; i < list.size(); i++) {
int len = strNum.length();
List<String> tmp = new LinkedList<String>(list);
String c = tmp.remove(i);
if (len == 2 && c.charAt(0) == '4' // 第三个位置不能为4
|| (len > 0 && c.charAt(0) == '3' && strNum.charAt(strNum.length() - 1) == '5') // 3和5不相连
|| (len > 0 && c.charAt(0) == '5' && strNum.charAt(strNum.length() - 1) == '3')) {
continue;
}
listAll(tmp, strNum + c);
}
}
5个数，也有6个数的那个题目
--------------------编程问答--------------------
恩，看过了 --------------------编程问答--------------------
研究研究，貌似挺好看的
--------------------编程问答--------------------
++ --------------------编程问答-------------------- 四五层for循环，要是数据量大的话，这个效率就可想而知了。如果排列的数据是1,2,2,3,4,5,6,7,8,9,那岂不是要用10个for循环。 --------------------编程问答--------------------
似乎题目本身就具有这样的要求，而且这个问题的复杂度似乎达到f（n^n）的恐怖规模 --------------------编程问答-------------------- 说到底是个排列问题。
工具类： http://blog.csdn.net/raistlic/article/details/7844812
import java.util.Arrays;
import java.util.List;
/**
*
* @author raistlic
* @date Dec 29, 2012
*/
public class NumberPuzzle {
public static void main(String[] args) {
int total = 0;
StringBuilder builder = new StringBuilder();
for(List<String> p : Permutation.of(Arrays.asList("1", "2", "3", "4", "5"))) {
builder.delete(0, builder.length());
for(String i : p)
builder.append(i);
String s = builder.toString();
if( s.charAt(3) != '4' && !s.contains("35") && !s.contains("53") ) {
System.out.println(s);
total++;
}
}
System.out.println("total : " + total);
}
}
结果：
run:
13254
13425
13452
14325
14523
15234
15423
15432
23154
23415
23451
24315
24513
25134
25413
25431
31254
31425
31452
31524
32154
32415
32451
32514
34125
34152
34215
34251
34512
34521
41325
41523
42315
42513
43125
43152
43215
43251
45123
45132
45213
45231
51234
51324
51423
51432
52134
52314
52413
52431
54123
54132
54213
54231
54312
54321
total : 56
BUILD SUCCESSFUL (total time: 0 seconds)
--------------------编程问答--------------------
好像应该是 charAt(2) != '4'，写错了，结果：
run:
12345
12543
13245
13254
14325
14523
15234
15243
21345
21543
23145
23154
24315
24513
25134
25143
31245
31254
31524
31542
32145
32154
32514
32541
34125
34152
34215
34251
34512
34521
41325
41523
42315
42513
43125
43152
43215
43251
45123
45132
45213
45231
51234
51243
51324
51342
52134
52143
52314
52341
54123
54132
54213
54231
54312
54321
total : 56
BUILD SUCCESSFUL (total time: 0 seconds)
--------------------编程问答-------------------- 如果不用排列算法，直接用多重循环穷举的话，数位多了应该会比较慢，——递归更要不得，栈会溢出的。
比如 1 2 3 4 5 6 7 8 9 组成不重复的 9 位数，4不能在第三位，35不能相邻，用排列算法穷举耗时 2 秒：
run:
total : 250560
BUILD SUCCESSFUL (total time: 2 seconds)
当然如果从数学角度分析，大概有更快的可以直接计算出个数的方法…………
--------------------编程问答--------------------
弱弱的问一下问什么栈会溢出的
递归写出来应该看起来更加舒服吧 --------------------编程问答-------------------- 看来楼主是学生呀 --------------------编程问答--------------------
如果递归的层数太多，栈就会溢出的。
其实从效率上讲循环和递归可能差不多，有的语言像PHP这种递归的效率可能还更低一些。
递归的代码写起来可能稍微显得优雅，可是其实原则上能比较容易写成循环的就不要写成递归，只有像quick sort这种才写递归。个人看法说错勿怪。 --------------------编程问答-------------------- 弱弱的问一下，为什么要把for（int c=1，c<=5,c++)改成while循环呢，请各位指教一下
--------------------编程问答--------------------
+_+. --------------------编程问答--------------------
看起来简洁多了，学习。。。 --------------------编程问答--------------------
package pkgname;--------------------编程问答--------------------
public class PermutationMain {
/**
* <method description>
*
* @param args
*/
static int total = 0;
static int pos = 0;
static int[] flags = { 0, 0, 0, 0, 0 }; // 0-not used,1-used
static int[] numbers = { 1, 2, 3, 4, 5 };
public static void main(String[] args) {
for (int i = 0; i < 5; i++) {
total = makeNumber(i, pos, total, "");
}
}
public static int makeNumber(int useNum, int pos, int total, String prefix) {
flags[useNum] = 1; // mark it used
try {
prefix = prefix + numbers[useNum];
// filter out unvalid result
if (((pos == 3 && numbers[useNum] == 4))
|| ((prefix.length() >= 2) && ((prefix.endsWith("35") || prefix.endsWith("53"))))) {
return total;
}
if (pos == 4) {
System.out.print(prefix + " ");
if (++total % 5 == 0) {
System.out.println();
}
return total;
}
for (int i = 0; i < 5; i++) {
if (flags[i] != 1) {
total = makeNumber(i, pos + 1, total, prefix);
}
}
return total;
} finally {
flags[useNum] = 0;
}
}
}
递归速度比循环快很多 --------------------编程问答-------------------- 今天刚看了贴子，我是这样做的，看能否减少循环时间和判断次数。从运行结果看是一样的。
public class test4 {
public static void main(String args[]){
String strTemp=null;
int count=0;
for(int a=1;a<=5;a++){
for(int b=1;b<=5;b++){
if (a==b) continue;
for(int c=1;c<=5;c++){
if (4==c) continue;
if (c==b || c==a) continue;
for(int d=1;d<=5;d++){
if(d==c || d==b || d==a) continue;
for(int e=1;e<=5;e++){
if(e==d || e==c || e==b || e==a) continue;
//if(a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e){
int numTemp=a*10000+b*1000+c*100+d*10+e;
//debug:System.out.println(numTemp);
strTemp=String.valueOf(numTemp);
//@条件符合)
if ((strTemp.indexOf("53")==-1)&&(strTemp.indexOf("35")==-1)){
//打印
System.out.println(strTemp);
count++;
}
}
}
}
}
}
System.out.println("count:"+count);
}
}
--------------------编程问答--------------------
这个结论你是从哪里得来的？
http://stackoverflow.com/questions/2651112/is-recursion-ever-faster-than-looping --------------------编程问答--------------------
学习了，原来差不多。只是之前做排序，觉得递归挺快的。 --------------------编程问答--------------------
我开始也以为递归快，后来有一次在PHP里用递归，效率惨不忍睹，然后就去搜索关于递归效率的文章，发现不是这么回事…… --------------------编程问答--------------------
递归是逻辑上清晰，效率不见得高。
--------------------编程问答--------------------
不对吧..为什么没有 12344 呢. --------------------编程问答--------------------
--------------------编程问答--------------------
--------------------编程问答--------------------
补充：Java , Java SE
