例如6、8都是丑数,我们把只包含因子2、3和5的数

2019-09-20 13:31栏目:大奖888官网登录
TAG:

丑数(Ugly Numbers, UVa 136)

丑数,什么是丑数

主题素材陈诉:

把只饱含因子2、3和5的数称作丑数(Ugly Number)。举例6、8都是丑数,但14不是,因为它满含因子7。
不足为奇上大家把1看作是率先个丑数。求按从小到大的相继的第N个丑数。

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

输出:
恐怕有多组测量检验数据,对于每组数据,
输出第N个丑数。

样例输入:

3 

 

样例输出:

3 

标题陈诉

小编们把只含有因子2、3和5的数称作丑数(Ugly Number)。求按从小到大的逐一的第1500个丑数。譬喻6、8都以丑数,但14不是,因为它蕴涵因子7。习于旧贯上大家把1当做第叁个丑数。

主题材料:我们把只包涵因子2、3和5的数称作丑数(Ugly Number)。比如6、8都以丑数,但14不是,因为它饱含因子7。习贯上我们把1看成是首先个丑数。求按从小到大的依次的第1500个丑数。

思路1:遍历

思路2: 依照丑数的定义,丑数应该是另多少个丑数乘以2、3要么5的结果(1除了)。由此我们能够创设五个数组,里面的数字是排好序的丑数。里面包车型地铁每二个丑数是前面包车型地铁丑数乘以2、3恐怕5获取的。那根本正是确认保障数组里的丑数是稳步的了。大家倘使数组中曾经有好七个丑数,排好序后存在数组中。大家把现成的最大丑数记做M。今后大家来生成下三个丑数,该丑数分明是如今某叁个丑数乘以2、3或许5的结果。大家第一思量把已有个别种种丑数乘以2。在乘以2的时候,能赢得若干个结果小于或等于M的。由于大家是依据顺序生成的,小于或然等于M确定已经在数组中了,大家不需另行思虑;大家还有大概会拿走若干个大于M的结果,但我们只必要首先个大于M的结果,因为大家盼望丑数是按从小到北周序生成的,其余更加大的结果大家随后再说。我们把获得的率先个乘以2后大于M的结果,记为M2。相同大家把已部分每贰个丑数乘以3和5,能获取第4个大于M的结果M3和M5。那么下一个丑数应该是M2、M3和M5四个数的蝇头者。

 1 #include <stdio.h>
 2 #include "stdafx.h"
 3 
 4 int IsUgly(int number)
 5 {
 6     while(number % 2 == 0)
 7         number /= 2;
 8     while(number % 3 ==0)
 9         number /= 3;
10     while(number % 5 ==0)
11         number /= 5;
12 
13 
14     return (number == 1) ? true : false;
15 }
16 
17 int GetUglyNumber_Solution1(int index)
18 {
19     if(index <= 0)
20         return 0;
21 
22     int number = 0;
23     int uglyFound = 0;
24     while(uglyFound < index)
25     {
26         ++ number;
27 
28         if(IsUgly(number))
29         {
30             ++ uglyFound;
31         }
32     }
33 
34     return number;
35 }
36 
37 
38 int Min(int number1, int number2, int number3);
39  
40  int GetUglyNumber_Solution2(int index)
41 {
42     if(index <= 0)
43         return 0;
44  
45     int *pUglyNumbers = new int[index];
46     pUglyNumbers[0] = 1;
47     int nextUglyIndex = 1;
48  
49     int *pMultiply2 = pUglyNumbers;
50     int *pMultiply3 = pUglyNumbers;
51     int *pMultiply5 = pUglyNumbers;
52  
53     while(nextUglyIndex < index)
54     {
55         int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
56         pUglyNumbers[nextUglyIndex] = min;
57  
58         while(*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
59             ++pMultiply2;
60         while(*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
61             ++pMultiply3;
62         while(*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
63             ++pMultiply5;
64  
65         ++nextUglyIndex;
66     }
67  
68     int ugly = pUglyNumbers[nextUglyIndex - 1];
69     delete[] pUglyNumbers;
70     return ugly;
71 }
72  
73  int Min(int number1, int number2, int number3)
74  {
75      int min = (number1 < number2) ? number1 : number2;
76      min = (min < number3)? min : number3;
77      
78      return min;
79  }
80  
81 int main()
82 {
83     int index = 10;
84     printf("solution1 %dn", GetUglyNumber_Solution1(index));
85     printf("solution2 %dn", GetUglyNumber_Solution2(index));
86     printf("n");
87     
88     index = 30;
89     printf("solution1 %dn", GetUglyNumber_Solution1(index));
90     printf("solution2 %dn", GetUglyNumber_Solution2(index));
91     printf("n");
92     
93     index = 1500;
94     printf("solution1 %dn", GetUglyNumber_Solution1(index));
95     printf("solution2 %dn", GetUglyNumber_Solution2(index));
96     printf("n");
97     
98     return 0;
99 }

图片 1

标题:大家把只富含因子2、3和5的数称作丑数(Ugly Number)。举例6、8都以丑数,但14不是,因为它含有因子7。习贯上大家...

解题思路:

  最简便易行的思路是,从1到大数,每一个数都检查测验一回是还是不是是丑数,检查评定方法能够虚构

int ugly(int number){
    if(number%2 == 0){
        return ugly(number/2);
    }else if(number%3 == 0){
        return ugly(number/3);
    }else if(number%5 == 0){
        return ugly(number/5);
    }else
        return number==1?true:false;
}

 

  可是这种思路,会浪费多量的时光,最后就能够晚点。

  大家着想八个数组,数组存款和储蓄的是当下的丑数,今后的种种丑数,都以用事先的数组的要素相乘的来的。接下来就是哪些获取后边的丑数并有限支撑它是寸步不移的。

  能够想到,数组的首先个因素是1,1与2 3 5独家相乘,能够赢得几个值,那四个值里面细小的,分明就是下二个丑数的最大值,接着max2的下标后移,继续相比。

void mkUglyNumber(){
    gArr[top++] = 1;
    int *max2 = gArr;
    int *max3 = gArr;
    int *max5 = gArr;
    while(top < 1500){
        int min = getMin(*max2*2,*max3*3,*max5*5);
        gArr[top] = min;
        while(*max2*2 <= gArr[top])
            ++max2;
        while(*max3*3 <= gArr[top])
            ++max3;
        while(*max5*5 <= gArr[top])
            ++max5;
        ++top;
    }
}

 

  比如,眼下的数组成分只是1,那么与2 3 5 相乘获得2 3 5,分明赢得的最小值是2。数组成分变为1 2。

  下标那回变为2 1 1,继续与2 3 5相乘,获得4 3 5,寻觅在那之中极小的,再放进数组,成分变为1 2 3。

  继续,直到找到1500个丑数之后,每一次进行读取丑数就可以

算法实现

  1. 本子1:错误版本
//#define LOCAL#include<iostream>#include<cstdio>#include<queue>/*输出第1500个丑数*/using namespace std;typedef long long LL;const int coeff[3]={2,3,5};int main(){    #ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    #endif    priority_queue<LL,vector<LL>,greater<LL> > pq;//!1    pq.push;//初始化得有1个1.    for(int i=1;;i++){        //每次循环都从pq中取出一个丑数,根据这个丑数计算出新的丑数,并注入。        LL ugly=pq.top();        pq.pop();        if{cout<<ugly;break;}        else{            //通过这个取出的丑数,计算新的丑数,并入队            for(int i=0;i<3;i++){                LL x=ugly*coeff[i];                pq.push;            }        }    }}

上述思路是透过每一次从优先队列pq中收获八个丑数,然后经过这一个丑数总计出新的丑数,对于随便的丑数x,他的2,3,5倍也都以丑数,通过如此的章程,能够把具备的丑数一网打尽。
而是那个地点并未设想周详的是,差别的变通方法大概会生成同贰个丑数,所以中间确定有不知凡两次重复了,比如235=325=532=...,所以须要八个数据结构来记录丑数是或不是早已冒出过了,set集结挺适合的,那么修改代码后如下。

//#define LOCAL#include<iostream>#include<cstdio>#include<queue>#include<set>/*输出第1500个丑数*/using namespace std;typedef long long LL;const int coeff[3]={2,3,5};int main(){    #ifdef LOCAL    freopen("data.in","r",stdin);    freopen("data.out","w",stdout);    #endif    priority_queue<LL,vector<LL>,greater<LL> > pq;//!1    set<LL> s;    pq.push;//初始化得有1个1.    s.insert;    for(int i=1;;i++){        //每次循环都从pq中取出一个丑数,根据这个丑数计算出新的丑数,并注入。        LL ugly=pq.top();        pq.pop();        if{cout<<ugly;break;}        else{            //通过这个取出的丑数,计算新的丑数,并入队            for(int i=0;i<3;i++){                LL x=ugly*coeff[i];                if(!s.count{                    s.insert;                    pq.push;                }            }        }    }    return 0;}

成套代码:

#include <stdio.h>
#define MAXSIZE 1500
void mkUglyNumber();
int getMin(int max2,int max3,int max5);
int gArr[MAXSIZE];
int top;
int main(){
    int n;
    top = 0;
    mkUglyNumber();
    while(scanf("%d",&n)!=EOF && n>=1 && n<=1500){
        printf("%dn",gArr[n-1]);
    }
    return 0;
}
void mkUglyNumber(){
    gArr[top++] = 1;
    int *max2 = gArr;
    int *max3 = gArr;
    int *max5 = gArr;
    while(top < 1500){
        int min = getMin(*max2*2,*max3*3,*max5*5);
        gArr[top] = min;
        while(*max2*2 <= gArr[top])
            ++max2;
        while(*max3*3 <= gArr[top])
            ++max3;
        while(*max5*5 <= gArr[top])
            ++max5;
        ++top;
    }
}
int getMin(int max2,int max3,int max5){
    int min = max2<max3?max2:max3;
    return min<max5?min:max5;
}
/**************************************************************
    Problem: 1214
    User: xhalo
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:920 kb
****************************************************************/

 

把只蕴涵因子2、3和5的数称作丑数(Ugly Number)。举例6、8都是丑数,但14不是,因为它包涵因子7。 习于旧贯上大家把1当作是率先个...

版权声明:本文由大奖888-www.88pt88.com-大奖888官网登录发布于大奖888官网登录,转载请注明出处:例如6、8都是丑数,我们把只包含因子2、3和5的数