hdu1058

#include<iostream> #include<string> using namespace std; int const N = 4; int map[N] = {2,3,5,7}; int findMin(int arr[], bool flag[], int len) { int min = arr[0]; int i=0; for(i=0; i<len; i++) if(arr[i] < min) min = arr[i]; for(i=0; i<len; i++) { if(min == arr[i]) flag[i] = true; else flag[i] = false; } return min; } void initHumble(int maxN, int humble[]) { humble[1] = 1; int pos[N] = {1,1,1,1}; int arr[N]; bool flag[N]; for(int i=2; i<=maxN; i++) { for(int j=0; j<N; j++) arr[j] = humble[pos[j]]*map[j]; int min = findMin(arr, flag, N); humble[i] = min; for(int j=0; j<N; j++) if(flag[j]) //相同的最小丑数在这里会被过滤掉 pos[j]++; } } void outPut(int humble[]) { int n; while(cin>>n && n) { string str = "th"; if(n%10==1 && n%100!=11) str = "st"; else if(n%10==2 && n%100!=12) str = "nd"; else if(n%10==3 && n%100!=13) str = "rd"; cout<<"The "<<n<<str<<" humble number is "<<humble[n]<<"."<<endl; } } int main() { const int SIZE = 6000; int humble[SIZE]; initHumble(5842, humble); outPut(humble); return 0; }