HDOJ1058——找丑数

问题描述

定义:如果一个数的因子只有2,3,5,7,那么它就是一个丑数。
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … 是一个丑数数列
现在给出一个正整数n，求出第n个丑数。

问题分析

这道题丑数最大为2000000000。如果用暴力求解，判断1到2000000000中每一个数字是不是丑数，若是丑数，则添加到数组中，显然超时。
因为每一个丑数的因数只有2,3,5,7,所以第n个丑数肯定是由它前面的n-1个丑数中的某一个数乘以{2,3,5,7}中的一个数得到。那么问题的关键就是怎么寻找到这样的数。
设第n个丑数为M，那么第n+1个数肯定比M大。我们遍历前面的n个数，将每个数乘以2，并找出大于M的最小数字。同样，可以找出乘以3的，乘以5的和乘以7的。那么第n+1个丑数肯定是这四个数中的最小值。
定义四个指针p_2,p_3,p_5,p_7,分别指向当前状态应该更新的丑数。
则得到状态转移方程$dp[n] = min(dp[p_2],dp[p_3],dp[p_5],dp[p_7])$
每次更新后，将相应的指针向右移动一个位置。更新后面的丑数。

代码实现

#include<stdio.h>
int dp[5850];
int min(int a,int b,int c,int d)
{
  int min = 2e9;
  if(a < min) min = a;
  if(b < min) min = b;
  if(c < min) min = c;
  if(d < min) min = d;
  return min;
}
void pre()
{
  dp[1] = 1;
  int i = 1,j = 1,k = 1,l = 1;
  for(int m = 2;m<=5842;m++)
  {
    dp[m] = min(dp[i] * 2,dp[j] * 3,dp[k] * 5,dp[l] * 7);
    if(dp[m] == dp[i] * 2) i++;
    if(dp[m] == dp[j] * 3) j++;
    if(dp[m] == dp[k] * 5) k++;
    if(dp[m] == dp[l] * 7) l++;
    /*注意，这里不是else if.因为有可能出现两个指针对应的状态更新之后相等的情况。这个时候两个指针都要移动的.*/
  }
}
int main()
{
  int n;
  pre();
  while(scanf("%d",&n) != EOF && n != 0)
  {
    printf("The %d",n);
    if(n % 10 == 1 && n % 100 != 11)  printf("st");
    else if(n % 10 == 2 && n % 100 != 12) printf("nd");
    else if(n % 10 == 3 && n % 100 != 13) printf("rd");
    else printf("th");
    printf(" humble number is %d.\n",dp[n]);
  }
  return 0;
}