Design an algorithm to find the kth number such that the only prime factors - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Design an algorithm to find the kth number such that the only prime factors

Design an algorithm to find the kth number such that the only prime factors# JobHunting - 待字闺中

c*e2012-03-31 07:03

1 楼

Design an algorithm to find the kth number such that the only prime factors
are 3, 5 and 7.

w*x2012-03-31 07:03

2 楼

迭代法:
//Find the nth number which is composed by factor 2, 3 and 5
void PrintSerials(int n)
{
assert(n > 0);
vector vec;
vec.push_back(1);
int nI2 = 0;
int nI3 = 0;
int nI5 = 0;
int nCount = 1;
while(nCount < n)
{
int nTmp2 = vec[nI2]*2;
int nTmp3 = vec[nI3]*3;
int nTmp5 = vec[nI5]*5;
int nMin = min(min(nTmp2, nTmp3), nTmp5);
if (vec.back() != nMin)
{
vec.push_back(nMin);
nCount++;
}
if (nMin == nTmp2)
nI2++;
else if (nMin == nTmp3)
nI3++;
else nI5++;
}
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
cout<}

c*t2012-03-31 07:03

3 楼

ding

【在 c**********e 的大作中提到】

: Design an algorithm to find the kth number such that the only prime factors
: are 3, 5 and 7.

l*e2012-03-31 07:03

4 楼

wwwyhx 的解法还是很牛的，简化了一下
static List getNth235(int k){
int i2 = 0, i3 = 0, i5 = 0;
List list = new ArrayList();
list.add(1);
while(list.size() < k){
int n2 = list.get(i2)*2;
int n3 = list.get(i3)*3;
int n5 = list.get(i5)*5;
int tmp = Math.min(Math.min(n2, n3), n5);
list.add(tmp);
if(tmp == n2) i2++;
if(tmp == n3) i3++;
if(tmp == n5) i5++;
}
return list;
}

c*e2012-03-31 07:03

5 楼

Good solutions. Thank you both.

w*o2012-03-31 07:03

6 楼

wwwyhx,
没有完全看懂，能否讲讲你的idea?
你用了三个index, nI2, nI3, nI5,然后不断的调整这些index,到底每个index都指示的
是什么？
careercup 150题的哪本书上，是用了3个queue,你的做法和careercup的做法是如何等
效的？
其实这两个我都没有完全弄明白。
谢谢！

【在 w****x 的大作中提到】

: 迭代法:
: //Find the nth number which is composed by factor 2, 3 and 5
: void PrintSerials(int n)
: {
: assert(n > 0);
: vector vec;
: vec.push_back(1);
: int nI2 = 0;
: int nI3 = 0;
: int nI5 = 0;

w*o2012-03-31 07:03

7 楼

好像不对的。我试了一下 2, 3, 5 的情况，是错的。

【在 w****x 的大作中提到】