九度OJ 1214：丑数（整除）

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：2180

解决：942

题目描述：: 把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。

习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

输入：: 输入包括一个整数N(1<=N<=1500)。

输出：: 可能有多组测试数据，对于每组数据，

输出第N个丑数。

样例输入：

样例输出：

思路：

常规思路，反复消因子2 3 5，如果最后剩下1，就是丑数，但最后发现超时了。见代码2。

优化的思路跟素数筛法有点类似，参考的别人的代码写的，很巧，学习了！见代码1。

代码1：

#include <stdio.h>

#include <stdlib.h>

int min(int a, int b, int c)

{

    int r;

    r = a<b ? a : b;

    r = r<c ? r : c;

    return r;

}

int main()

{

    int n, count;

    while(scanf("%d", &n) != EOF)

    {

        int *nums = (int *)malloc(n*sizeof(int));

        nums[0] = 1;

        count=1;

        int *p2 = nums;

        int *p3 = nums;

        int *p5 = nums;

        while (count < n)

        {

            nums[count] = min(*p2*2, *p3*3, *p5*5);

            while (nums[count] >= *p2*2)

                p2++;

            while (nums[count] >= *p3*3)

                p3++;

            while (nums[count] >= *p5*5)

                p5++;

            count ++;

        }

        printf("%d\n", nums[count-1]);

        free(nums);

    }

    return 0;

}

/**************************************************************

    Problem: 1214

    User: liangrx06

    Language: C

    Result: Accepted

    Time:20 ms

    Memory:912 kb

****************************************************************/

代码2（原来的超时代码）：

#include <stdio.h>

int main()

{

    int n, m, tmp, count;

    while(scanf("%d", &n) != EOF)

    {

        count=1;

        m=1;

        while (count != n)

        {

            m++;

            tmp = m;

            while (tmp % 2 == 0)

                tmp /= 2;

            while (tmp % 3 == 0)

                tmp /= 3;

            while (tmp % 5 == 0)

                tmp /= 5;

            if (tmp == 1)

                count ++;

        }

        printf("%d\n", m);

    }

    return 0;

}

/**************************************************************

    Problem: 1214

    User: liangrx06

    Language: C

    Result: Time Limit Exceed

****************************************************************/

巴特西

九度OJ 1214：丑数（整除）

最新文章

热门文章

巴特西

九度OJ 1214：丑数 （整除）

最新文章

热门文章

九度OJ 1214：丑数（整除）