一道java面试题,算法,求大家帮忙解答!

07-11-20 python
1-100中,
求:5个不同数的和小于100的不重复组合的个数.

求效率比较高的算法。

多层for循环法首先排除,效率太差。

先谢谢大家了!

[该贴被python于2007-11-20 15:11修改过]

[该贴被python于2007-11-20 15:12修改过]

3
moby
2007-11-21 17:00
用for循环效率也不差
public static void main(String[] args) {
//假设a<b<c<d<e,所以a<18,b<24,c<32,d<49,e<96
for(int a=1;a<18;a++){
for(int b =a+1;b<24;b++){
for (int c=b+1;c<32;c++){
for(int d=c+1;d<49;d++){
for(int e=d+1;e<96;e++){
if (a+b+c+d+e<100){
System.out.println(a+" "+b+" "+c+" "+d+" "+e);
}else{
break;
}
}
}
}
}
}


}

[该贴被moby于2007-11-21 17:06修改过]

ttt
2007-11-22 20:00
moby兄的算法不错,在下再来优化一下:

public static void main(String[] args) {

int a, b, c, d, e;
int tmp[4];

for(a=1; a<18; a++){
tmp[0] = (100 - a - 1 - (1+1) - (1+1+1)) / 4;

for(b =a+1; b<=tmp[0]; b++){
tmp[1] = (100 - a - b - 1 - (1+1)) / 3;

for (c=b+1; c<=tmp[1]; c++){
tmp[2] = (100 - a - b - c - 1) /2;

for(d=c+1; d<=tmp[2]; d++){
tmp[3] = (100 - a - b - c - d);

for(e=d+1; e<=tmp[3]; e++){
if (a+b+c+d+e<100){
System.out.println(a+" "+b+" "+c+" "+d+" "+e);
}else{
break;
}
}
}
}
}
}


}

ttt
2007-11-24 14:13
不好意思,刚才将自己发布的代码复制netbean6中RUN一下,原来有语法错误,原来JAVA不能
int tmp[4];
这样定义数组,这是C的定义(在下以前一直是C和汇编,没想到JAVA不是这样的)。
所以改为
int[] tmp = new int[4];
就OK了。
以下为全代码,在下在netbean6中RUN过了,没问题:

/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/

package test;

/**
*
* @author root
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here

int a, b, c, d, e;
int[] tmp = new int[4];

for(a=1; a<18; a++){
tmp[0] = (100 - a - 1 - (1+1) - (1+1+1)) / 4;

for(b =a+1; b<=tmp[0]; b++){
tmp[1] = (100 - a - b - 1 - (1+1)) / 3;

for (c=b+1; c<=tmp[1]; c++){
tmp[2] = (100 - a - b - c - 1) /2;

for(d=c+1; d<=tmp[2]; d++){
tmp[3] = (100 - a - b - c - d);

for(e=d+1; e<=tmp[3]; e++){
if (a+b+c+d+e<100){
System.out.println(a+" "+b+" "+c+" "+d+" "+e);
}else{
break;
}
}
}
}
}
}
}

}

sifeng618435
2007-11-27 11:13
请问楼上的2位,有什么可以提高算法的书啊~
谢谢啊

ghostv1
2008-03-13 17:28
97+95+93+...+1

猜你喜欢