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

显示全部楼层 · 2011-5-7 01:45:08

1-100中,
求:5个不同数的和小于100的不重复组合的个数.
先谢谢大家了！

千问 · 2011-5-7 01:45:08

我没说清楚，应该是：求效率比较高的算法。
多层for循环,效率太差,就不用考虑了!

千问 · 2011-5-7 01:45:08

大家快动脑筋！

千问 · 2011-5-7 01:45:08

分段查找，自己试试，

千问 · 2011-5-7 01:45:08

原帖由 python1981 于 2007-11-20 15:15 发表
大家快动脑筋！
呵呵

千问 · 2011-5-7 01:45:08

class Search
{

public static void main(String[] args)

{

for(int i=1;i复制代码

从上面这堆数里，很难看出或总结出规律的吧？

附：JS源码

最大值

复制代码

千问 · 2011-5-7 01:45:08

原帖由 lastwinner 于 2007-11-26 00:07 发表

1、是不难想象，但严谨的数学推理应有证据支持2、应是手误，应为F(84)=99，后一处也应改为85（题目说的是小于100，不包括等于）

我用javascript得出一个结果：
第一列表示5个数的和，第二列表示满足 ...
谢谢楼上的指正，F(75)不是笔误，是当时算错了

上次本来是把公式在草稿上写出来了的，后来发帖子的时候才发现草稿纸被倒垃圾的给收走了。
设出现次数为F(n),即下列：
1
1
2
3
5
7
10
13
18
23
30
37
47
57
70
...
不难看出的是，从第三项开始，每一项的值就是其前一项与前面一中间项的和。
具体数学证明当然可以通过数学归纳法证明，这里我不写了，下面把该数列的计算公式写出来：
数列F(n):
F(1) = 1;
当n>=1时，
F(2n) = F(2n-1) +F(n);
F(2n+1) = F(2n) + F(n+1);
由此也不难写出函数F(n)的算法（java代码）：
public static int F(int n)

{

if( n < 1 )

{

System.out.println("Error! Argument [n] cannot be lower than 1 .&quot

;

return -1;

}

if( n==1 )

{

return 1;

}

else

{

if( n%2 == 0)

{

returnF(n-1) + F(n/2) ;

}

else

{

returnF(n-1) + F(n/2+1) ;

}

}

}
然后本主题的问题就是求F(1) + ... + F(84) 的和了。循环一下就可以了。
[ 本帖最后由 bhan2008 于 2007-12-1 17:45 编辑 ]