丑数(栈和队列)

丑数(栈和队列)

时间: 1ms        内存:1000M

描述:

题目:我们把只包含因子235的数称作丑数(Ugly Number)。例如68都是丑数,但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。输入一个数n,判断它是否是丑数。

输入:

输入n:

6

输出:

输出:

YES

示例输入:

8

示例输出:

YES

提示:

参考答案(内存最优[752]):

#include <stdio.h>     
#include <stdlib.h>
#include<string.h>
#define  maxsize 100   
typedef struct node     
{     
    int data;     
    struct node *next;     
}lnode;     
typedef lnode *link; 
link front=NULL; 
link rear=NULL;
void addqueue(int ch) 
{ 
    link s; 
    s=(link)malloc(sizeof(lnode)); 
    s->data=ch; 
    s->next=NULL; 
    if(rear==NULL) 
        front=s; 
    else
        rear->next=s; 
    rear=s; 
}  
int outqueue() 
{ 
    link top; 
    int temp;
    if(front!=NULL) 
    {
		top=front;
		front=front->next;
		temp=top->data; 
        free(top); 
        return temp; 
    } 
    else
        return -1; 
}
int main()     
{        
	int flag=0,n;
	scanf("%d",&n);
	while(n%2==0)
	{
		addqueue(2);
		n/=2;
	}
	while(n%3==0)
	{
		addqueue(n%3);
		n/=3;
	}
	while(n%5==0)
	{
		addqueue(n%5);
		n/=5;
	}
	addqueue(n);
	while(front!=NULL)
	{
		n=outqueue();
		if(n!=2&&n!=3&&n!=5&&n!=1&&n!=0)
			flag=1;
	}
	if(flag)
		printf("NO\n");
	else
		printf("YES\n");
    return 0;     
} 

参考答案(时间最优[0]):

#include <stdio.h>     
#include <stdlib.h>
#include<string.h>
#define  maxsize 100   
typedef struct node     
{     
    int data;     
    struct node *next;     
}lnode;     
typedef lnode *link; 
link front=NULL; 
link rear=NULL;
void addqueue(int ch) 
{ 
    link s; 
    s=(link)malloc(sizeof(lnode)); 
    s->data=ch; 
    s->next=NULL; 
    if(rear==NULL) 
        front=s; 
    else
        rear->next=s; 
    rear=s; 
}  
int outqueue() 
{ 
    link top; 
    int temp;
    if(front!=NULL) 
    {
		top=front;
		front=front->next;
		temp=top->data; 
        free(top); 
        return temp; 
    } 
    else
        return -1; 
}
int main()     
{        
	int flag=0,n;
	scanf("%d",&n);
	while(n%2==0)
	{
		addqueue(2);
		n/=2;
	}
	while(n%3==0)
	{
		addqueue(n%3);
		n/=3;
	}
	while(n%5==0)
	{
		addqueue(n%5);
		n/=5;
	}
	addqueue(n);
	while(front!=NULL)
	{
		n=outqueue();
		if(n!=2&&n!=3&&n!=5&&n!=1&&n!=0)
			flag=1;
	}
	if(flag)
		printf("NO\n");
	else
		printf("YES\n");
    return 0;     
} 

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注