Posted on 2010-03-07 18:05
Initiate 阅读(557)
评论(0) 编辑 收藏 引用 所属分类:
模拟
水题开路了，若x是丑数，则2x,3x,5x都是丑数，本想直接开数组，再数一次
结果发现丑数十分稀疏，空间完全不够，只好对 2x,3x,5x 数列的大小进行判断
把最小的放入a[]
1 #include<iostream>
2 using namespace std;
3 int a[1550];
4 int min(int x,int y,int z)
5 {
6 int t;
7 t= x<y ? x:y;
8 t= t<z ? t:z;
9 return t;
10 }
11 int main()
12 {
13 a[1]=1;
14 int i,x=1,y=1,z=1;
15 for(i=2;i<=1500;i++)
16 {
17 a[i]=min(2*a[x],3*a[y],5*a[z]);
18 if(2*a[x]==a[i])x++;
19 if(3*a[y]==a[i])y++;
20 if(5*a[z]==a[i])z++;
21 }
22 while(cin>>i&&i)
23 cout<<a[i]<<endl;
24 }
25