[ACM] UVa 136 Ugly Numbers

題目136
set有自動排序加上過濾重複，回頭看這題就比較舒服了!!

想法步驟 :
1.因為ugly number 一定是由2或 3或 5組成，所以可以分解成 2^n * 3^m * 5^o 。

2.所以利用set的自動排序+加過濾重複字，我們就可以每一迴圈加入一組數字

3.重要的是每個number都是由2,3,5...等的次方所組成，利用迭代器在每次迴圈指向下一個un數字，分別插入 un乘上2,3,5後的數值，來表示之後的數列。

4.這樣有個問題，就是要讓迴圈跑超過1500次，才能找第1500位un數字。(超醜版本)

5.因為迭代器是跟著key值，並不會因為出現較小的數字改變排序而影響他指到的數字。

6.所以修正一下，每次迴圈把第一個數字踢掉，讓迭代器一直指向begin()，就可以確保每次都是指向最小的位數!!

正確版本:

1. #include <iostream>
2. #include <iterator>
3. #include <set>
4. using namespace std;
6. int main()
7. {
8.     long s = 1;
9.     set<long long> ugly_Number(&s, &s+1);   //初始化範圍:起始位置&S,結尾位置 &S+1 
10.     set<long long>::iterator p;
12.     for (int i=0; i<1500 ; i++)
13.     {
14.         p = ugly_Number.begin();
15.         ugly_Number.insert(*p * 2);
16.         ugly_Number.insert(*p * 3);
17.         ugly_Number.insert(*p * 5);
18.         ugly_Number.erase(*p);
19.     }
20.     cout << "The 1500\'th ugly number is " << *p << '.' << endl;
21. }

超醜版本:

1. #include <iostream>
2. #include <iterator>
3. #include <set>
4. #include <algorithm>
5. using namespace std;
7. //輸出串流 轉接器
8. ostream_iterator<long, char> out(cout," ");
10. int main()
11. {
12.     long s = 1;
13.     set<long long> ugly_Number(&s, &s+1);
14.  //  copy (ugly_Number.begin(), ugly_Number.end(), out);
15.     set<long long>::iterator p;
16.     set<long long>::iterator tmp;
18.     p = ugly_Number.begin();
19.     for (int i=0; i<2000 ; i++)
20.     {
21.         tmp = p;
22.         ugly_Number.insert(*tmp * 2);
23.         ugly_Number.insert(*tmp * 3);
24.         ugly_Number.insert(*tmp * 5);
25. //        ugly_Number.insert(*tmp * 6);
26. //        ugly_Number.insert(*tmp * 10);
27. //        ugly_Number.insert(*tmp * 15);
28.         ++p;
29. //        copy (ugly_Number.begin(), ugly_Number.end(), out);
30. //        cout << endl;
31. //        cout << *p << endl;
32. //        system("pause");
33.     }
34. ////    copy (ugly_Number.begin(), ++ugly_Number.begin(), out);
35.     set<long long>::iterator oo = ugly_Number.begin();
36.     for (int i=1; i < 1500 ; i++)
37.         oo++;
38.     cout << "The 1500\'th ugly number is " << *oo << '.' << endl;
39. }