Uva 443 Humble Numbers

題目來源：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=384

這一題在luckycat上有中文翻譯，剛開始看完題目的時候，是用遞迴寫的，但一直跑無窮迴圈@@，最後用了BFS的方法寫，把要處理的元素放入queue中，當queue裡面沒有元素的時候，就會跳出迴圈，這次也學會了一些vector小技巧

因為只要找質因數只有2 3 5 7的數字，那就把2 3 5 7一直乘一直乘就好了吧(?)
但是也不知道要怎麼乘才不會亂掉，最後想到把要乘得數字放入queue中，然後每次都從queue中拿出元素(以下稱t)，讓t和 2 3 5 7 相乘，乘出來的元素在放入queue中，還有vector中，但如果t之前有放過了(因為2*5==5*2會有元素重複問題)，就不用再放了，最後將vector由小到大排序，程式就大致完成了

因為不知道元素總共有幾個，所以用vector儲存
要先宣告函示庫 #include<vector>
vector宣告方式是 vector <int> a;
放入元素m至vector a中則為 a.push_back(m)

如果要將vector內的元素由小排到大排序
要先宣告函示庫 #include<algorithm>
利用裡面的sort()函式，可以上C++ 的reference上面找使用方法這裡用最簡單的形式 sort(a.begin(),a.end());//從第一個元素由小到大排到最後一個元素

最後是，因為5*2==2*5 所以有時候得到的數字會重複，重複的數字就不需要在放入queue和vector中了，這時候我就必須要會判斷，10是否已經出現在vector中

	vector <long long int> a;
	vector <long long int>::iterator it;
	it = find (a.begin(), a.end(),10);//重vector的頭到尾尋找10是否存在
	if (it == a.end()){
	//沒找到重複元素
	}

view raw 112.cpp hosted with ❤ by GitHub

程式碼：

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstdio>
	#include <queue>
	using namespace std;
	int main(){
	vector <long long int> a;
	vector <long long int>::iterator it;
	int b[4] = {2,3,5,7};
	long long int num,t;
	a.push_back(1);
	queue <long long int> Q;
	Q.push(1);
	while(!Q.empty()){
	num = Q.front();
	Q.pop();
	for(int i=0;i<4;i++){
	t= num;
	t*=b[i];
	if(t<=2000000000){
	//如果t已經在a裡面的話，就不用再加入a了
	it = find (a.begin(), a.end(),t);
	if (it == a.end()) {
	a.push_back(t);
	Q.push(t);
	}
	}
	else break;
	}
	}
	sort(a.begin(),a.end());//將vector內元素由小排到大
	int x;
	while(cin>>x && x){
	if(x%100==11 || x%100==13 || x%100==12) printf("The %dth humble number is %d.\n",x,a.at(x-1));
	else if(x%10==1) printf("The %dst humble number is %d.\n",x,a.at(x-1));
	else if(x%10==2) printf("The %dnd humble number is %d.\n",x,a.at(x-1));
	else if(x%10==3) printf("The %drd humble number is %d.\n",x,a.at(x-1));
	else printf("The %dth humble number is %d.\n",x,a.at(x-1));
	}
	}

view raw uva443.cpp hosted with ❤ by GitHub