标题:JAVA每周一题(2)——曾经诺西的笔试题
只看楼主
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
结帖率:100%
已结贴  问题点数:100 回复次数:19 
JAVA每周一题(2)——曾经诺西的笔试题
求丑数:
    丑数是指那些因子只含2,3,5的数。2,3,4,5,6,8,9,10,12,15是最前面的丑数,请编写一个程序,打印出第1500个丑数。要求效率要高。
欢迎大家百度,只要能整理出尽可能快的程序就行。
 
 
 
搜索更多相关主题的帖子: 诺西 JAVA 笔试 
2010-06-25 16:23
书呆
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:55
专家分:188
注 册:2010-3-26
得分:10 
像素数筛法。。。

不过好像题目说法有点问题,应该是素因子吧。否则,8和12都还有4这个非素数因子

[ 本帖最后由 书呆 于 2010-6-26 01:04 编辑 ]

沉醉东风月下读。柴门闭,莫管客来无。
2010-06-26 00:57
lampeter123
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:54
帖 子:2508
专家分:6424
注 册:2009-1-30
得分:70 
程序代码:
import java.util.*;

public class Ex_2 {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
        int i=1;
        while(i<1000) {
            treeSet.add(2*i);
            treeSet.add(3*i);
            treeSet.add(5*i);
            i++;
        }
        Iterator it = treeSet.iterator();
        int n = 1;

        while(it.hasNext()) {
            System.out.println(it.next());
            if (n==1500)
            {
                break;
            }
            n++;
        }  
  
    }
}


[ 本帖最后由 lampeter123 于 2010-6-26 09:15 编辑 ]

你的优秀和我的人生无关!!!!
    
    我要过的,是属于我自己的生活~~~
2010-06-26 08:32
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
得分:0 
回复 2楼 书呆
8=2×2×2,12=2×2×3,所以没错
2010-06-26 09:13
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
得分:0 
回复 3楼 lampeter123
你的程序还需要改改,因为2×i不一定是正确的,假如I=7就错误了,因为14=2×7,7不是(2,3,5)其中的一个.所有的因子都必须只能由2,3,5组成
2010-06-26 09:18
lampeter123
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:54
帖 子:2508
专家分:6424
注 册:2009-1-30
得分:0 
以下是引用linjx0123在2010-6-26 09:18:11的发言:

你的程序还需要改改,因为2×i不一定是正确的,假如I=7就错误了,因为14=2×7,7不是(2,3,5)其中的一个.所有的因子都必须只能由2,3,5组成
import java.util.*;

public class Ex_2 {
    public static void main(String[] args) {
        TreeSet<Integer> treeSet = new TreeSet<Integer>();
        int i=1;
        while(i<1000) {
            if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) {
            treeSet.add(2*i);
            treeSet.add(3*i);
            treeSet.add(5*i);
            }
            i++;
        }
        Iterator it = treeSet.iterator();
        int n = 1;

        while(it.hasNext()) {
            System.out.println(it.next());
            if (n==1500)
            {
                break;
            }
            n++;
        }
        
            
           
   
    }
}
修改了一下,这次对了吧,不过效率不高,有待改进

你的优秀和我的人生无关!!!!
    
    我要过的,是属于我自己的生活~~~
2010-06-26 09:29
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
得分:0 
还是不对,因为假如i=14,i%2==0,但是14=2×7,treeSet.add(2*i);就是2×2×7,所以还是错误的。这道题目用
while(i%5==0){
     i=i/5;
}
while(i%3==0){
     i=i/3;
}
while(i%2==0){
    i=i/2;
}
这种方法解,虽然可以得到答案,但明显不是笔试的人想要的答案,这个效率最差了。
2010-06-26 10:01
lampeter123
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:54
帖 子:2508
专家分:6424
注 册:2009-1-30
得分:0 
以下是引用linjx0123在2010-6-26 10:01:56的发言:

还是不对,因为假如i=14,i%2==0,但是14=2×7,treeSet.add(2*i);就是2×2×7,所以还是错误的。这道题目用
while(i%5==0){
     i=i/5;
}
while(i%3==0){
     i=i/3;
}
while(i%2==0){
    i=i/2;
}
这种方法解,虽然可以得到答案,但明显不是笔试的人想要的答案,这个效率最差了。
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) //只包含2,3,5因子,已经没有7了

你的优秀和我的人生无关!!!!
    
    我要过的,是属于我自己的生活~~~
2010-06-26 10:28
ljwei
Rank: 3Rank: 3
等 级:论坛游侠
威 望:1
帖 子:46
专家分:192
注 册:2009-9-18
得分:10 
顶下
2010-06-26 11:09
linjx0123
Rank: 9Rank: 9Rank: 9
等 级:贵宾
威 望:14
帖 子:279
专家分:1362
注 册:2006-4-7
得分:0 
回复 8楼 lampeter123
if(i==1||(i%2==0)||(i%3==0)||(i%5==0)) //只包含2,3,5因子,已经没有7了

假如i=14或者22,33,55,那么if()的条件为true的。以14为例,这个时候treeset.add(2*i),3*i,5*i就是28,42,70.而28=2*2*7,42=2*3*7,70=5*2*7,都含有7,所以错误
2010-06-26 15:13



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-311244-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020333 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved