一类计算问题小结poj&hoj Set Definition ，Humble Numbers ，Ugly Numbers 因子构造法

/*这类问题都是给一些只能由某些特定因子乘积组成的数，然后求第n个数的大小。做法就是每次用所给的条件来构造因子，预处理出前N项的值，复杂度O(N)，查询复杂度O(1).*/Set Definition.code#include <stdio.h>#include <iostream>using namespace std;int a[10000000];int main(){    a[1]=1;    int n1=1,n2=1;    for(int i=2;i<=10000000;i++)    {        a[i]=min(2*a[n1]+1,3*a[n2]+1);        if(a[i]==2*a[n1]+1) n1++;        if(a[i]==3*a[n2]+1) n2++;    }    int x;    while(scanf("%d",&x)==1)    {        printf("%d\n",a[x]);    }    return 0;}Humble Numbers.code#include <stdio.h>#include <iostream>using namespace std;int a[6000];int main(){    a[1]=1;    int n2=1,n3=1,n5=1,n7=1;    for(int i=2; i<=5842; i++)    {        a[i]=min(min(a[n2]*2,a[n3]*3),min(a[n5]*5,a[n7]*7));        if(a[i]==a[n2]*2) n2++;        if(a[i]==a[n3]*3) n3++;        if(a[i]==a[n5]*5) n5++;        if(a[i]==a[n7]*7) n7++;    }    int n;    while(scanf("%d",&n)==1&&n)    {        if(n%10==1)        {            if(n%100!=11) printf("The %dst humble number is %d.\n",n,a[n]);            else printf("The %dth humble number is %d.\n",n,a[n]);        }        else if(n%10==2)        {            if(n%100!=12) printf("The %dnd humble number is %d.\n",n,a[n]);            else printf("The %dth humble number is %d.\n",n,a[n]);        }        else if(n%10==3)        {            if(n%100!=13) printf("The %drd humble number is %d.\n",n,a[n]);            else printf("The %dth humble number is %d.\n",n,a[n]);        }        else printf("The %dth humble number is %d.\n",n,a[n]);    }    return 0;}Ugly Number.code#include <iostream>using namespace std;int main(){    int number[1505];    int judge[3];    int i,j;    int n;    i=0;    number[0]=1;    while(i<=1500)    {    for( j=0;j<=i,number[j]*2<=number[i];j++);        judge[0]=number[j]*2;    for( j=0;j<=i,number[j]*3<=number[i];j++);        judge[1]=number[j]*3;    for( j=0;j<=i,number[j]*5<=number[i];j++);        judge[2]=number[j]*5;    number[i+1]=min(judge[0],min(judge[1],judge[2]));    i++;   }        cout <<"The 1500'th ugly number is " << number[1499] << "." << endl;    return 0;}