DD9. 寻找丑数
描述
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。输入描述
整数N输出描述
第N个丑数示例1
输入:
6
输出:
6
C++14 解法, 执行用时: 2ms, 内存消耗: 224KB, 提交时间: 2019-01-17
#include <stdio.h>
int main()
{
int n;
int i,x=2; //auto add
int count=1;
scanf("%d",&n); //input N
if(1==n)
{
printf("1");
return 0;
}
while(1)
{
i = x;
do
{
if(i%2==0) //2
{
i=i/2;
}
else if(i%3==0) //3
{
i=i/3;
}
else if(i%5==0) //5
{
i=i/5;
}
else if(i==1) //choushu
{
count++;
break;
}
else
{
break;
}
}while(1);
if(count == n)
{
printf("%d",x);
return 0;
}
x++;
}
return 0;
}
C 解法, 执行用时: 2ms, 内存消耗: 256KB, 提交时间: 2019-03-25
#include<stdio.h>
int main()
{
int n;
int list[100];
while (scanf("%d", &n) != EOF)
{
list[0] = 1;
int i = 1;
int num = 1;
while(i < n)
{
while(1)
{
num += 1;
int m = num;
while((m % 2) == 0)
{
m /= 2;
}
while((m % 3) == 0)
{
m /= 3;
}
while((m % 5) == 0)
{
m /= 5;
}
if (m == 1)
{
i++;
break;
}
}
}
printf("%d\n", num);
}
}
C 解法, 执行用时: 2ms, 内存消耗: 304KB, 提交时间: 2021-09-24
#include <stdio.h>
int min(int a,int b,int c)
{
if(a<=b && a<=c)
return a;
if(b<=c && b<=a)
return b;
return c;
}
int GetUglyNumber_Solution(int index ) {
if(index==0)
return 0;
int sum=1,a2=0,a3=0,a5=0;
int arr[1501];
arr[0]=1;
while(sum!=index)
{
arr[sum]=min(arr[a2]*2,arr[a3]*3,arr[a5]*5);
if(arr[sum]==arr[a2]*2)
a2++;
if(arr[sum]==arr[a3]*3)
a3++;
if(arr[sum]==arr[a5]*5)
a5++;
sum++;
}
return arr[index-1];
}
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
printf("%d\n",GetUglyNumber_Solution(N));
}
return 0;
}
C++14 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2018-08-26
#include<bits/stdc++.h>
using namespace std;
int min(int a,int b,int c){
int min = (a<b)?a:b;
min = (min<c)?min:c;
return min;
}
int mc(int index){
if(index<=0)
return 0 ;
int result[index];
result[0]=1;
int m2=0,m3=0,m5=0;
for (int i=1;i<index;i++){
int min1 =min(result[m2]*2,result[m3]*3,result[m5]*5);
result[i]=min1;
if(result[m2]*2<=min1){
m2++;
}
if(result[m3]*3<=min1){
m3++;
}
if(result[m5]*5<=min1){
m5++;
}
}
return result[index-1];
}
int main(){
int a;
cin>>a;
int b = mc(a);
cout<<b<<endl;
return 0 ;
}
C 解法, 执行用时: 2ms, 内存消耗: 364KB, 提交时间: 2020-07-03
#include <stdio.h>
#include <stdlib.h>
int main(){
int n;
scanf("%d", &n);
// printf("%d\n", n);
int cnt = 0;
int i;
int temp;
for(i = 1; cnt < n; i++){
temp = i;
while(1){
if(temp%2 == 0){
temp /= 2;
}
else if(temp%3 == 0){
temp /= 3;
}
else if(temp%5 == 0){
temp /= 5;
}
else if(temp == 1){
cnt++;
// printf("i = %d, cnt = %d\n", i, cnt);
break;
}
else{
break;
}
}
}
printf("%d\n", i-1);
return 0;
}