Design an algorithm to find the kth number such that the only prime factors are 3,5 and 7
方法一:
a[i]=min{a[s1]*3,a[s2]*5,a[s3]*7};
s1<i,s2<i,s3<i && a[s1]*3>a[i-1],a[s2]*3>a[i-1],a[s3]*7>a[i-1]
时间复杂度O(n^2)
#include<stdio.h> int min(int a,int b,int c)
{
int smallest = a<b?a:b;
smallest = smallest<c?smallest:c;
return smallest;
} int func(int k)
{
int m3=;
int m5=;
int m7=;
int *p = new int[k+];
p[]=;
for(int i=;i<=k;i++)
{
for(int j=;j<i;j++)
{
if(p[j]*>p[i-])
{
m7=p[j]*;
break;
}
}
for(int j=;j<i;j++)
{
if(p[j]*>p[i-])
{
m5=p[j]*;
break;
}
}
for(int j=;j<i;j++)
{
if(p[j]*>p[i-])
{
m3=p[j]*;
break;
}
}
p[i]=min(m3,m5,m7);
}
int r = p[k];
delete[] p;
p = NULL;
return r;
} int main()
{
int k=;
printf("%dth:%d\n",k,func(k));
return ;
}
方法二：
将1填入输出数组的第一位，然后准备三个队列Q3,Q5,Q7,分别压入1*3,1*5,1*7
第i位就是三个队列的队首元素中最小的，然后将该元素从队列取出：
如果是从Q3取出,则将该数分别乘以3,5,7，再将三个数分别插入到Q3,Q5,Q7队尾
如果是从Q5取出,则将该数分别乘以5,7，再将两个数分别插入到Q5,Q7队尾
如果是从Q7取出,则将该数乘以7，再将结果插入到Q7队尾
直到取出第K+1位（1不算）
时间复杂度O(n)
#include<iostream>
#include<deque> using namespace std; int func(int k)
{
deque<int>Q3;
deque<int>Q5;
deque<int>Q7;
int pi=;
Q3.push_back();
Q5.push_back();
Q7.push_back();
for(int i=;i<k+;i++)
{
if(Q3.front()<Q5.front() && Q3.front()<Q7.front())
{
pi=Q3.front();
Q3.pop_front();
Q3.push_back(*pi);
Q5.push_back(*pi);
Q7.push_back(*pi);
}
else if(Q5.front()<Q3.front() && Q5.front()<Q7.front())
{
pi=Q5.front();
Q5.pop_front();
Q5.push_back(*pi);
Q7.push_back(*pi);
}
else if(Q7.front()<Q3.front() && Q7.front()<Q5.front())
{
pi=Q7.front();
Q7.pop_front();
Q7.push_back(*pi);
}
else
{
cout<<"error"<<endl;
}
}
return pi;
} int main()
{
for(int k=;k<;k++)
{
cout<<k<<"th:"<<func(k)<<endl;
}
return ;
}