题意:给出丑数的定义,只含有2,3,5,7这四个素数因子的数称为素数。求第n个丑数。
可以先观察几个丑数得出规律
1:dp[1]
2:min(1*2,1*3,1*5,1*7)
3:min(2*2,1*3,1*5,1*7)
4:min(2*2,2*3,1*5,1*7)
5:min(3*2,2*3,1*5,1*7)
6:min(3*2,2*3,2*5,1*7)
7:min(4*2,3*3,2*5,1*7)
8:min(4*2,3*3,2*5,2*7)
9:min(5*2,3*3,2*5,2*7)
然后ppt里面的方程也就好理解了
dp[i]=min(dp[p1]*2,dp[p2]*3,dp[p3]*5,dp[p4]*7)
如果选中了哪一个数,对应的伪指针移动1 注意上面的6的情况,如果有两个或两个以上的数和它相等,对应的伪指针都移动1
然后就是输出的问题了
1是first
2是second
3是third
4是fourth
----
11是eleventh
12是twelfth
13是thirteenth -----
这一题也是学习的---感觉它的转移方程有一点点不一样---用已经算出来的丑数去推出新的丑数--- 另外输出的时候看了半天(为什么要判断这么多次----5555)原来是因为序数词的后缀不一样(===5555555)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=+; int dp[maxn]; int min(int a,int b,int c,int d)
{
a=a<b?a:b;
b=c<d?c:d;
return a<b?a:b;
} int main()
{
int n,i,p1,p2,p3,p4,dp1,dp2,dp3,dp4;
dp[]=;
p1=p2=p3=p4=;
for(i=;i<=;i++)
{
dp1=*dp[p1];
dp2=*dp[p2];
dp3=*dp[p3];
dp4=*dp[p4];
dp[i]=min(dp1,dp2,dp3,dp4);
if(dp[i]==dp1) p1++;
if(dp[i]==dp2) p2++;
if(dp[i]==dp3) p3++;
if(dp[i]==dp4) p4++;
}
while(scanf("%d",&n)!=EOF&&n)
{
if(n%==&&n%!=)
printf("The %dst humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %dnd humble number is %d.\n",n,dp[n]);
else if(n%==&&n%!=)
printf("The %drd humble number is %d.\n",n,dp[n]);
else
printf("The %dth humble number is %d.\n",n,dp[n]);
}
return ;
}