C++程序练习-1338:Ugly Numbers-set的应用

描述
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n'th ugly number.

输入
Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.
输出
For each line, output the n’th ugly number .:Don’t deal with the line with n=0.
样例输入
1
2
9
0
样例输出
1
2
10

分析：
建立数据表，然后查找数据表，输出结果。

思路：
可以用C++中set，且它的元素唯一，有序。

//冰非寒([e-mail])
//260kB 0ms 1196 B G++
#include <cstdio>
#include <set>
using namespace std;
//global variables
const int N =1601;
set<unsigned long>uglynum;
//functions
void init();
void print(int);
//main function
int main(){
    int n;
    init();
    while(scanf("%d",&n) == 1&&n){
        print(n);
    }
    return 0;
}
//initialize ugly numbers
void init(){
    int j(1);
    pair<set<unsigned long>::iterator,bool> ptr;
    uglynum.insert(1);
    for(set<unsigned long>::iterator it = uglynum.begin();j < N;++ it){
        ptr = uglynum.insert(*it * 2);
        if(ptr.second == 1){
            j ++;
        }
        ptr = uglynum.insert(*it * 3);
        if(ptr.second == 1){
            j ++;
        }
        ptr = uglynum.insert(*it * 5);
        if(ptr.second == 1){
            j ++;
        }
    }
}
//print result
void print(int n){
    int j(1);
    for(set<unsigned long>::iterator it = uglynum.begin();j <= n && it != uglynum.end();++ it){
        if(j == n){
            printf("%u\n",*it);
        }
        j ++;
    }
}