丑数 有关问题

丑数 问题

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ

题目描述：http://ac.jobdu.com/problem.php?cid=1039&pid=17

把只包含因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含因子7。
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
输入：
输入包括一个整数N(1<=N<=1500)。
输出：
可能有多组测试数据，对于每组数据，
输出第N个丑数。
样例输入：
3
样例输出：

3

代码已AC：

思想：本质就是2 ，3 ，5 的乘积的组合，不过要顺序组合，那么我们的操作就是：每次都将2,3,5乘以一个已经是丑数的数，再比较大小，小的进入数组，然后在比较；

例如：1是丑数，那么下一个比较 2 * 1、3 * 1和5*1，那么得到的是2，2进入数组，下面比较的是2*2、3*1 和5*1( 注意因为后面的3*1和5*1的大小并不确定，所以还要继续进行比较 )得到3进入数组，再比较 2 * 2、3 * 2和5*1.。。。。。  基本算法就是：2 * c2 、3*c3 、5 * c5，ci 是数组的下标，每次都选择后都ci++一个。。。直到N个丑数。。

#include <stdio.h>#include <math.h>long long int min( long long int n1, long long int n2, long long int n3 ){    long long int t = n1 < n2 ? n1 : n2;    return t < n3 ? t : n3; }int main(){    long long int ug[1500];    int c2 = 0, c3 = 0, c5 = 0, N;        ug[0] = 1;    N = 1;        while( N < 1500 )    {           ug[N] = min( ug[c2] * 2, ug[c3] * 3, ug[c5] * 5 );            if( ug[N] == ug[c2] * 2 )   // 因为可能数相等，所以不能else if            {               c2++;           }                      if( ug[N] == ug[c3] * 3 )           {               c3++;           }                      if( ug[N++] == ug[c5] * 5 )           {               c5++;           }               }    while( scanf("%d", &N) != EOF )    {           printf("%lld\n", ug[N-1]);    }        return 0;}

查看更多 下一篇