原题:
用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求: "4 "不能在第三位, "3 "与 "5 "不能相连. 然后发现很少Java程序员知道递归回溯法解决该问题。思想基本都被严重的‘OO’化了。本题给的是数字,一堆人都在操作字符串。总而言之是缺少算法知识,这对Java社区来说是个很大的缺陷,也是C/C++程序员谈到Java就面露不屑表情的原因之一。学Java学到基本算法都不知道实在是一种悲哀。再回头看这题,假如换成数学问题,就问多少方案呢?显然是个排列问题,可以先计算所有的情况,然后去除不满足条件的。
1。不加任何约束,则一共P6/P2=360种(因为2重复了,所以除以P2)
2。4在第三位的情况有:P5/P2=60种(去掉4,其他数字的全排列)
3。3,5相连的情况有:P5*P2/P2=120(把3,5看成一个整体,全排列,然后乘以P2是3,5这个整体的排列,除以2的重复)
4。4即在第三位,而且3,5又相连。
4.1)考虑3,5在第一二位,则有P2×(P3/P2)=6.
4.2)3,5不在头两位。
4.2.1)左边全是2的情况,(P2×P2)=4
4.2.2)左边是1,2的情况 (P2×P2×P2)= 8
5。根据容斥原理:总共:360-(60+120)+(6+4+8)=198种。
回到程序解答上,其实就是一个搜索问题,搜索所有的可行解,搜索空间就是所有排列,这类问题一般都可用回溯法解决。
回溯法的算法框架一般都是:void backtrace(int steps[],int depeth)
{
if(depth>=LIMIT){sloved();} constructCondicates();
foreach condicates do{
steps[depth]=condicates[i];
backtrace(depth++);
}
}关键在于构造可行解。本题的相应Java算法如下:
/**
* @author yvon
*
*/
public class TestGen {
int constructCondicates(int steps[], int[] used, int level, int[] condicates) {
int cn = 0;
boolean has2 = false;
for (int j = 0; j < 5; j++) {
if (used[j] == 0) {
if (level > 0) {
if ((j == 2 && steps[level - 1] == 5)
|| (j == 4 && steps[level - 1] == 3)
|| (j == 3 && level == 2)) {// 三五不相连,四不能在第三位
continue;
}
}
if (j == 1) {
if (!has2) {
has2 = true;
} else {// 可行解里只能一次包含2.相同的位置(排除重复)
continue;
}
}
condicates[cn++] = j + 1;
// 如果是2的话,还可以使用一次,前提是可行解没使用
} else if (j == 1 && !has2 && used[j] == 1) {
condicates[cn++] = j + 1;
has2 = true;
}
}
return cn;
} void doGen(int steps[], int used[], int level, int[] total) {
if (level == 6) {
for (int i = 0; i < 6; i++) {
System.out.print(steps[i] + " ");
}
System.out.println();
total[0]++;
return;
}
int condicates[] = new int[6];
int cn = constructCondicates(steps, used, level, condicates);
for (int k = 0; k < cn; k++) {
int todo = condicates[k];
steps[level] = todo;
used[todo - 1]++;
doGen(steps, used, level + 1, total);
used[todo - 1]--;
}
}
public static void main(String[] args) {
int[] steps = new int[6];
int[] used = new int[6];
int total[] = new int[1];
new TestGen().doGen(steps, used, 0, total);
System.out.println("Totally:" + total[0]);
}}运行结果:1 2 2 3 4 5
1 2 2 5 4 3
1 2 3 2 4 5
1 2 3 2 5 4
1 2 3 4 2 5
1 2 3 4 5 2
1 2 5 2 3 4
1 2 5 2 4 3
1 2 5 4 2 3
1 2 5 4 3 2
1 3 2 2 4 5
1 3 2 2 5 4
1 3 2 4 2 5
1 3 2 4 5 2
1 3 2 5 2 4
1 3 2 5 4 2
1 4 2 3 2 5
1 4 2 5 2 3
1 4 3 2 2 5
1 4 3 2 5 2
1 4 5 2 2 3
1 4 5 2 3 2
1 5 2 2 3 4
1 5 2 2 4 3
1 5 2 3 2 4
1 5 2 3 4 2
1 5 2 4 2 3
1 5 2 4 3 2
2 1 2 3 4 5
2 1 2 5 4 3
2 1 3 2 4 5
2 1 3 2 5 4
2 1 3 4 2 5
2 1 3 4 5 2
2 1 5 2 3 4
2 1 5 2 4 3
2 1 5 4 2 3
2 1 5 4 3 2
2 2 1 3 4 5
2 2 1 5 4 3
2 2 3 1 4 5
2 2 3 1 5 4
2 2 3 4 1 5
2 2 3 4 5 1
2 2 5 1 3 4
2 2 5 1 4 3
2 2 5 4 1 3
2 2 5 4 3 1
2 3 1 2 4 5
2 3 1 2 5 4
2 3 1 4 2 5
2 3 1 4 5 2
2 3 1 5 2 4
2 3 1 5 4 2
2 3 2 1 4 5
2 3 2 1 5 4
2 3 2 4 1 5
2 3 2 4 5 1
2 3 2 5 1 4
2 3 2 5 4 1
2 4 1 3 2 5
2 4 1 5 2 3
2 4 2 3 1 5
2 4 2 5 1 3
2 4 3 1 2 5
2 4 3 1 5 2
2 4 3 2 1 5
2 4 3 2 5 1
2 4 5 1 2 3
2 4 5 1 3 2
2 4 5 2 1 3
2 4 5 2 3 1
2 5 1 2 3 4
2 5 1 2 4 3
2 5 1 3 2 4
2 5 1 3 4 2
2 5 1 4 2 3
2 5 1 4 3 2
2 5 2 1 3 4
2 5 2 1 4 3
2 5 2 3 1 4
2 5 2 3 4 1
2 5 2 4 1 3
2 5 2 4 3 1
3 1 2 2 4 5
3 1 2 2 5 4
3 1 2 4 2 5
3 1 2 4 5 2
3 1 2 5 2 4
3 1 2 5 4 2
3 1 5 2 2 4
3 1 5 2 4 2
3 1 5 4 2 2
3 2 1 2 4 5
3 2 1 2 5 4
3 2 1 4 2 5
3 2 1 4 5 2
3 2 1 5 2 4
3 2 1 5 4 2
3 2 2 1 4 5
3 2 2 1 5 4
3 2 2 4 1 5
3 2 2 4 5 1
3 2 2 5 1 4
3 2 2 5 4 1
3 2 5 1 2 4
3 2 5 1 4 2
3 2 5 2 1 4
3 2 5 2 4 1
3 2 5 4 1 2
3 2 5 4 2 1
3 4 1 2 2 5
3 4 1 2 5 2
3 4 1 5 2 2
3 4 2 1 2 5
3 4 2 1 5 2
3 4 2 2 1 5
3 4 2 2 5 1
3 4 2 5 1 2
3 4 2 5 2 1
3 4 5 1 2 2
3 4 5 2 1 2
3 4 5 2 2 1
4 1 2 3 2 5
4 1 2 5 2 3
4 1 3 2 2 5
4 1 3 2 5 2
4 1 5 2 2 3
4 1 5 2 3 2
4 2 1 3 2 5
4 2 1 5 2 3
4 2 2 3 1 5
4 2 2 5 1 3
4 2 3 1 2 5
4 2 3 1 5 2
4 2 3 2 1 5
4 2 3 2 5 1
4 2 5 1 2 3
4 2 5 1 3 2
4 2 5 2 1 3
4 2 5 2 3 1
4 3 1 2 2 5
4 3 1 2 5 2
4 3 1 5 2 2
4 3 2 1 2 5
4 3 2 1 5 2
4 3 2 2 1 5
4 3 2 2 5 1
4 3 2 5 1 2
4 3 2 5 2 1
4 5 1 2 2 3
4 5 1 2 3 2
4 5 1 3 2 2
4 5 2 1 2 3
4 5 2 1 3 2
4 5 2 2 1 3
4 5 2 2 3 1
4 5 2 3 1 2
4 5 2 3 2 1
5 1 2 2 3 4
5 1 2 2 4 3
5 1 2 3 2 4
5 1 2 3 4 2
5 1 2 4 2 3
5 1 2 4 3 2
5 1 3 2 2 4
5 1 3 2 4 2
5 1 3 4 2 2
5 2 1 2 3 4
5 2 1 2 4 3
5 2 1 3 2 4
5 2 1 3 4 2
5 2 1 4 2 3
5 2 1 4 3 2
5 2 2 1 3 4
5 2 2 1 4 3
5 2 2 3 1 4
5 2 2 3 4 1
5 2 2 4 1 3
5 2 2 4 3 1
5 2 3 1 2 4
5 2 3 1 4 2
5 2 3 2 1 4
5 2 3 2 4 1
5 2 3 4 1 2
5 2 3 4 2 1
5 4 1 2 2 3
5 4 1 2 3 2
5 4 1 3 2 2
5 4 2 1 2 3
5 4 2 1 3 2
5 4 2 2 1 3
5 4 2 2 3 1
5 4 2 3 1 2
5 4 2 3 2 1
5 4 3 1 2 2
5 4 3 2 1 2
5 4 3 2 2 1
Totally:198
用1、2、2、3、4、5这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234、412345等,要求: "4 "不能在第三位, "3 "与 "5 "不能相连. 然后发现很少Java程序员知道递归回溯法解决该问题。思想基本都被严重的‘OO’化了。本题给的是数字,一堆人都在操作字符串。总而言之是缺少算法知识,这对Java社区来说是个很大的缺陷,也是C/C++程序员谈到Java就面露不屑表情的原因之一。学Java学到基本算法都不知道实在是一种悲哀。再回头看这题,假如换成数学问题,就问多少方案呢?显然是个排列问题,可以先计算所有的情况,然后去除不满足条件的。
1。不加任何约束,则一共P6/P2=360种(因为2重复了,所以除以P2)
2。4在第三位的情况有:P5/P2=60种(去掉4,其他数字的全排列)
3。3,5相连的情况有:P5*P2/P2=120(把3,5看成一个整体,全排列,然后乘以P2是3,5这个整体的排列,除以2的重复)
4。4即在第三位,而且3,5又相连。
4.1)考虑3,5在第一二位,则有P2×(P3/P2)=6.
4.2)3,5不在头两位。
4.2.1)左边全是2的情况,(P2×P2)=4
4.2.2)左边是1,2的情况 (P2×P2×P2)= 8
5。根据容斥原理:总共:360-(60+120)+(6+4+8)=198种。
回到程序解答上,其实就是一个搜索问题,搜索所有的可行解,搜索空间就是所有排列,这类问题一般都可用回溯法解决。
回溯法的算法框架一般都是:void backtrace(int steps[],int depeth)
{
if(depth>=LIMIT){sloved();} constructCondicates();
foreach condicates do{
steps[depth]=condicates[i];
backtrace(depth++);
}
}关键在于构造可行解。本题的相应Java算法如下:
/**
* @author yvon
*
*/
public class TestGen {
int constructCondicates(int steps[], int[] used, int level, int[] condicates) {
int cn = 0;
boolean has2 = false;
for (int j = 0; j < 5; j++) {
if (used[j] == 0) {
if (level > 0) {
if ((j == 2 && steps[level - 1] == 5)
|| (j == 4 && steps[level - 1] == 3)
|| (j == 3 && level == 2)) {// 三五不相连,四不能在第三位
continue;
}
}
if (j == 1) {
if (!has2) {
has2 = true;
} else {// 可行解里只能一次包含2.相同的位置(排除重复)
continue;
}
}
condicates[cn++] = j + 1;
// 如果是2的话,还可以使用一次,前提是可行解没使用
} else if (j == 1 && !has2 && used[j] == 1) {
condicates[cn++] = j + 1;
has2 = true;
}
}
return cn;
} void doGen(int steps[], int used[], int level, int[] total) {
if (level == 6) {
for (int i = 0; i < 6; i++) {
System.out.print(steps[i] + " ");
}
System.out.println();
total[0]++;
return;
}
int condicates[] = new int[6];
int cn = constructCondicates(steps, used, level, condicates);
for (int k = 0; k < cn; k++) {
int todo = condicates[k];
steps[level] = todo;
used[todo - 1]++;
doGen(steps, used, level + 1, total);
used[todo - 1]--;
}
}
public static void main(String[] args) {
int[] steps = new int[6];
int[] used = new int[6];
int total[] = new int[1];
new TestGen().doGen(steps, used, 0, total);
System.out.println("Totally:" + total[0]);
}}运行结果:1 2 2 3 4 5
1 2 2 5 4 3
1 2 3 2 4 5
1 2 3 2 5 4
1 2 3 4 2 5
1 2 3 4 5 2
1 2 5 2 3 4
1 2 5 2 4 3
1 2 5 4 2 3
1 2 5 4 3 2
1 3 2 2 4 5
1 3 2 2 5 4
1 3 2 4 2 5
1 3 2 4 5 2
1 3 2 5 2 4
1 3 2 5 4 2
1 4 2 3 2 5
1 4 2 5 2 3
1 4 3 2 2 5
1 4 3 2 5 2
1 4 5 2 2 3
1 4 5 2 3 2
1 5 2 2 3 4
1 5 2 2 4 3
1 5 2 3 2 4
1 5 2 3 4 2
1 5 2 4 2 3
1 5 2 4 3 2
2 1 2 3 4 5
2 1 2 5 4 3
2 1 3 2 4 5
2 1 3 2 5 4
2 1 3 4 2 5
2 1 3 4 5 2
2 1 5 2 3 4
2 1 5 2 4 3
2 1 5 4 2 3
2 1 5 4 3 2
2 2 1 3 4 5
2 2 1 5 4 3
2 2 3 1 4 5
2 2 3 1 5 4
2 2 3 4 1 5
2 2 3 4 5 1
2 2 5 1 3 4
2 2 5 1 4 3
2 2 5 4 1 3
2 2 5 4 3 1
2 3 1 2 4 5
2 3 1 2 5 4
2 3 1 4 2 5
2 3 1 4 5 2
2 3 1 5 2 4
2 3 1 5 4 2
2 3 2 1 4 5
2 3 2 1 5 4
2 3 2 4 1 5
2 3 2 4 5 1
2 3 2 5 1 4
2 3 2 5 4 1
2 4 1 3 2 5
2 4 1 5 2 3
2 4 2 3 1 5
2 4 2 5 1 3
2 4 3 1 2 5
2 4 3 1 5 2
2 4 3 2 1 5
2 4 3 2 5 1
2 4 5 1 2 3
2 4 5 1 3 2
2 4 5 2 1 3
2 4 5 2 3 1
2 5 1 2 3 4
2 5 1 2 4 3
2 5 1 3 2 4
2 5 1 3 4 2
2 5 1 4 2 3
2 5 1 4 3 2
2 5 2 1 3 4
2 5 2 1 4 3
2 5 2 3 1 4
2 5 2 3 4 1
2 5 2 4 1 3
2 5 2 4 3 1
3 1 2 2 4 5
3 1 2 2 5 4
3 1 2 4 2 5
3 1 2 4 5 2
3 1 2 5 2 4
3 1 2 5 4 2
3 1 5 2 2 4
3 1 5 2 4 2
3 1 5 4 2 2
3 2 1 2 4 5
3 2 1 2 5 4
3 2 1 4 2 5
3 2 1 4 5 2
3 2 1 5 2 4
3 2 1 5 4 2
3 2 2 1 4 5
3 2 2 1 5 4
3 2 2 4 1 5
3 2 2 4 5 1
3 2 2 5 1 4
3 2 2 5 4 1
3 2 5 1 2 4
3 2 5 1 4 2
3 2 5 2 1 4
3 2 5 2 4 1
3 2 5 4 1 2
3 2 5 4 2 1
3 4 1 2 2 5
3 4 1 2 5 2
3 4 1 5 2 2
3 4 2 1 2 5
3 4 2 1 5 2
3 4 2 2 1 5
3 4 2 2 5 1
3 4 2 5 1 2
3 4 2 5 2 1
3 4 5 1 2 2
3 4 5 2 1 2
3 4 5 2 2 1
4 1 2 3 2 5
4 1 2 5 2 3
4 1 3 2 2 5
4 1 3 2 5 2
4 1 5 2 2 3
4 1 5 2 3 2
4 2 1 3 2 5
4 2 1 5 2 3
4 2 2 3 1 5
4 2 2 5 1 3
4 2 3 1 2 5
4 2 3 1 5 2
4 2 3 2 1 5
4 2 3 2 5 1
4 2 5 1 2 3
4 2 5 1 3 2
4 2 5 2 1 3
4 2 5 2 3 1
4 3 1 2 2 5
4 3 1 2 5 2
4 3 1 5 2 2
4 3 2 1 2 5
4 3 2 1 5 2
4 3 2 2 1 5
4 3 2 2 5 1
4 3 2 5 1 2
4 3 2 5 2 1
4 5 1 2 2 3
4 5 1 2 3 2
4 5 1 3 2 2
4 5 2 1 2 3
4 5 2 1 3 2
4 5 2 2 1 3
4 5 2 2 3 1
4 5 2 3 1 2
4 5 2 3 2 1
5 1 2 2 3 4
5 1 2 2 4 3
5 1 2 3 2 4
5 1 2 3 4 2
5 1 2 4 2 3
5 1 2 4 3 2
5 1 3 2 2 4
5 1 3 2 4 2
5 1 3 4 2 2
5 2 1 2 3 4
5 2 1 2 4 3
5 2 1 3 2 4
5 2 1 3 4 2
5 2 1 4 2 3
5 2 1 4 3 2
5 2 2 1 3 4
5 2 2 1 4 3
5 2 2 3 1 4
5 2 2 3 4 1
5 2 2 4 1 3
5 2 2 4 3 1
5 2 3 1 2 4
5 2 3 1 4 2
5 2 3 2 1 4
5 2 3 2 4 1
5 2 3 4 1 2
5 2 3 4 2 1
5 4 1 2 2 3
5 4 1 2 3 2
5 4 1 3 2 2
5 4 2 1 2 3
5 4 2 1 3 2
5 4 2 2 1 3
5 4 2 2 3 1
5 4 2 3 1 2
5 4 2 3 2 1
5 4 3 1 2 2
5 4 3 2 1 2
5 4 3 2 2 1
Totally:198
http://topic.csdn.net/u/20070114/14/1170e023-e8f0-4331-8bd8-516c6f1e40da.html?10672
int[] src = {1, 2, 2, 3, 4, 5};
int x = g(src, new int[src.length], 0);
System.out.println(x);
} private static int g(int[] src, int[] result, int index) {
if (index >= src.length) {
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]);
System.out.print(" ");
}
System.out.println();
return 1;
}
int x = 0;
for (int i = 0; i < result.length; i++) {
if (src[i] == 0) {
continue;
}
if (index == 2 && src[i] == 4) {
continue;
}
if (index > 0 && result[index - 1] + src[i] == 8) {
continue;
}
if (i == 2 && src[1] > 0) {
continue;
}
result[index] = src[i];
src[i] = 0;
x += g(src, result, index + 1);
src[i] = result[index];
}
return x;
}
现在没几个程序员关心算法的
要是和他们说起来
很多人不屑一顾
觉得什么都有现成的 没必要重新造轮子
其实主要是现在的环境和一部分人的误导
没错,以前的底层基本够用了,也实在懒得去研究那些底层枯燥的东西,实用性太低我做项目从来只管应用,API足够用了,如果API不够用,只能说明设计有问题。别跟我说没技术含量,能赚钱就行,管他什么技术含量
是啊,相比楼主的来说,看着就舒服,很干净。楼主代码中有 N 层的嵌套 if,时间一长估计会晕掉的。
也是C/C++程序员谈到Java就面露不屑表情的原因之一。学Java学到基本算法都不知道实在是一种悲哀。这个,你上各大OJ看看,JAVA大神比比皆是,这个和语言没有关系。