c122 - 00443 - Humble Numbers
題目描述
題目要求找出第 n 個 Humble Number。Humble Number 定義為其質因數僅包含 2, 3, 5, 或 7 的正整數。輸入為多個 n 值，直到 n = 0 為止。對於每個 n，輸出對應的 Humble Number，並正確處理序數 (st, nd, rd, th)。
解題思路
程式碼使用深度優先搜尋 (DFS) 的方式產生 Humble Number。find 函數遞迴地將已知的 Humble Number 分別乘以 2, 3, 5, 7，並將新的 Humble Number 加入 ans 陣列中。為了避免重複，在加入新的 Humble Number 之前，會檢查它是否已經存在於 ans 陣列中。產生所有 Humble Number 後，對 ans 陣列進行排序，然後根據輸入的 n 值輸出對應的 Humble Number。序數的處理透過條件判斷來實現。
複雜度分析
- 時間複雜度: O(N log N)，其中 N 是要產生的 Humble Number 的數量。DFS 的時間複雜度取決於產生 Humble Number 的數量，而排序的時間複雜度為 O(N log N)。
- 空間複雜度: O(N)，主要用於儲存 Humble Number 的
ans陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long int ans[5843],it;
void find(long long int n){
if(n>2000000000||it>=5843)return;
for(int i=0;i<it;++i){
if(ans[i]==n)return;
}
ans[it]=n;
++it;
find(n*2);
find(n*3);
find(n*5);
find(n*7);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
find(1);
sort(ans,ans+it);
while(cin >> it){
if(it==0)break;
int l=it%100,m=it%10;
if(l==11||l==12||l==13)
cout << "The " << it << "th humble number is ";
else if(m==1)
cout << "The " << it << "st humble number is ";
else if(m==2)
cout << "The " << it << "nd humble number is ";
else if(m==3)
cout << "The " << it << "rd humble number is ";
else
cout << "The " << it << "th humble number is ";
cout << ans[it-1] << ".\n";
}
}