学步园

题目：一个数的素数因子是只有有2,3,5,7，叫做humble number，前20个 humble number为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27...
求第n个humble number；
分析：打表，开一个数组HumbleNumber[6000][5],HumbleNumber[i][0],存humble number，HumbleNumber[i][1,2,3,4]存HumbleNumber[i][0]*2,3 ,5,7的值，
HumbleNumber[i]是比Humblenumber[i-1][0]大的一个数，从HumbleNumber[1~i][1~4]都搜一遍 找出来了，复杂度O（N^2）

#include<iostream>
#include<cstdio>
using namespace std;
long long BumbleNumber[6000][5];
int prime[5]={0,2,3,5,7};
int main()
{
	int N;
    for(int i=1;i<=10;i++)
		BumbleNumber[i][0]=i;
	for(int i=1;i<=10;i++)
		for(int j=1;j<=4;j++)
			BumbleNumber[i][j]=BumbleNumber[i][0]*prime[j];

	for(int i=11;i<=5842;i++)
	{
		int temp=BumbleNumber[i-1][0],ans=2000000001;
	    for(int j=1;j<=i-1;j++)
		{
			for(int k=1;k<=4;k++)
				if(BumbleNumber[j][k]>temp && BumbleNumber[j][k]<ans)
					ans=BumbleNumber[j][k];
		}
		BumbleNumber[i][0]=ans;
		for(int k=1;k<=4;k++)
		{
			if(BumbleNumber[i][0]*prime[k]>2000000001)
				BumbleNumber[i][k]=2000000001;
			else
			    BumbleNumber[i][k]=BumbleNumber[i][0]*prime[k];
		}
	}
	 while(cin>>N)
    {
        if(N==0)
		   { break; }
        if(N%10==1&&N%100!=11)
        {
            cout<<"The "<<N<<"st humble number is "<<BumbleNumber[N][0]<<"."<<endl;
            continue;
        }
        if(N%10==2&&N%100!=12)
        {
            cout<<"The "<<N<<"nd humble number is "<<BumbleNumber[N][0]<<"."<<endl;
            continue;
        }
        if(N%10==3&&N%100!=13)
        {
            cout<<"The "<<N<<"rd humble number is "<<BumbleNumber[N][0]<<"."<<endl;
            continue;
        }
        cout<<"The "<<N<<"th humble number is "<<BumbleNumber[N][0]<<"."<<endl;
    }
}

问题分析：参考了网上的算法技巧，这种打表技巧，很巧妙，是递增的顺序，所以时间复杂度为O(N).......很巧妙！！！转载的别人的代码

#include <iostream>
#include <cstring>
using namespace std;
int min(int a,int b){
   if(a<b) return a;
   else return b;
}
int main(void){
   long D[5843];
   memset(D,0,sizeof(D));
   D[1]=1;
   int i,i1=1,i2=1,i3=1,i4=1;
   int t1,t2,t3,t4;
   for(i=2;i<5843;i++){
      t1=D[i1]*2;
      t2=D[i2]*3;
      t3=D[i3]*5;
      t4=D[i4]*7;
      D[i]=min(min(t1,t2),min(t3,t4));
      if(D[i]==t1) i1++;
      if(D[i]==t2) i2++;
      if(D[i]==t3) i3++;
      if(D[i]==t4) i4++;
   }
   int n;
   cin>>n;
   while(n){
      if(n%10==1&&n%100!=11){
         cout<<"The "<<n<<"st humble number is "<<D[n]<<"."<<endl;
      }
      else if(n%10==2&&n%100!=12){
         cout<<"The "<<n<<"nd humble number is "<<D[n]<<"."<<endl;
      }
      else if(n%10==3&&n%100!=13){
         cout<<"The "<<n<<"rd humble number is "<<D[n]<<"."<<endl;
      }else{
         cout<<"The "<<n<<"th humble number is "<<D[n]<<"."<<endl;
      }
      cin>>n;
   }
   system("pause");
   return 0;
}