首页 > ACM题库 > 九度OJ > 九度-1214-丑数[数学]
2014
02-14

九度-1214-丑数[数学]

题目描述:
把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
输入:
输入包括一个整数N(1<=N<=1500)。
输出:
可能有多组测试数据,对于每组数据,
输出第N个丑数。
样例输入:
3
样例输出:
3
#include <stdio.h>
#include <stdlib.h>
int min( int a, int b, int c ){
        int min;
        min = (a<b)? a:b;
        min = (min<c)? min:c;
        return min;
}
int getUglyNumber( int len ){
        int *uglyNums = (int*)malloc( len*sizeof(int) );
        uglyNums[0] = 1;
        int next = 1;
        int *p2 = uglyNums;
        int *p3 = uglyNums;
        int *p5 = uglyNums;
        while( next<len ){
                uglyNums[next] = min(*p2*2, *p3*3, *p5*5 );
                while( uglyNums[next] >= *p2*2) p2++;
                while( uglyNums[next] >= *p3*3) p3++;
                while( uglyNums[next] >= *p5*5) p5++;
                next++;
        }
        int res = uglyNums[len-1];
        free(uglyNums);
        return res;
}
int main(){
    int n;
        while( scanf("%d",&n) != EOF ){
                printf("%d\n",getUglyNumber(n) );
        }
    return 0;
}

 

 


  1. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  2. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c