def ugly(n):
res = [1]
if n <=1 :
return max(n,0)
else:
index2, index3, index5 = 0,0,0
i = 0
while i < n:
i += 1
res.append(min(res[index2]*2,res[index3]*3,res[index5]*5))
if res[i] == res[index2]*2:
index2 += 1
if res[i] == res[index3]*3:
index3 += 1
if res[i] == res[index5]*5:
index5 += 1
return res[n-1]
用python写的
public class Main { public static void main(String args[]){ Scanner scanner = new Scanner(System.in); while (scanner.hasNext()){ int n = scanner.nextInt(); System.out.println(getTarget(n)); } } public static int getTarget(int n){ int[] arr = new int[n]; arr[0] = 1; int t1 = 0; int t2 = 0; int t3 = 0; int nextNum = 1; while (nextNum < n){ arr[nextNum] = Math.min((Math.min(arr[t1]*2,arr[t2]*3)),arr[t3]*5); if(arr[t1]*2 <= arr[nextNum]) t1++; if(arr[t2]*3 <= arr[nextNum]) t2++; if(arr[t3]*5 <= arr[nextNum]) t3++; nextNum++; } return arr[n - 1]; } }
#include<iostream> #include<algorithm> using namespace std; const int maxn=10010; int main() { int n; while(cin>>n) { int res[maxn]={0}; res[0]=1; int index2=0,index3=0,index5=0; int i=0; while(i<n) { i+=1; res[i]=min(res[index2]*2,min(res[index3]*3,res[index5]*5)); if(res[i]==res[index2]*2) { index2++; } if(res[i]==res[index3]*3) { index3++; } if(res[i]==res[index5]*5) { index5++; } } cout<<res[n-1]<<endl; } }
#include <bits/stdc++.h> using namespace std; int F(int n){ int a[n+1]; a[1] = 1; int i=1, j=1, k=1, cnt=2; while(cnt<=n){ a[cnt] = min(min(2*a[i], 3*a[j]), 5*a[k]); if(a[cnt] == 2*a[i]) i++; if(a[cnt] == 3*a[j]) j++; if(a[cnt] == 5*a[k]) k++; cnt++; } return a[n]; } int main(){ int n; scanf("%d", &n); printf("%d\n", F(n)); return 0; }
My solution:
def ugly_num(n, k=10000):
ugly_array = [2, 3, 5]
if n == 1:
return 1
else:
latest_array = ugly_array
while len(ugly_array) < k:
new_array = []
for i in latest_array:
for j in [2, 3, 5]:
if i * j not in new_array:
new_array.append(i * j)
ugly_array.extend(new_array)
latest_array = new_array
ugly_array = sorted(ugly_array)
return ugly_array[n - 2]
import java.util.Scanner; /* * 查找第n个丑数 */ public class ted { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 题目要求查找的第n个丑数 int n = sc.nextInt(); // 已找到0个丑数 int count = 0; // 从1开始查找 int start = 1; // 当求得的丑数个数小于n;就不断start++,判断start是不是丑数。 while (count < n) { int s = start; // 如果能被2/3/5整除,就一直除 while ((s % 2) == 0 || s % 3 == 0 || s % 5 == 0) { if (s % 2 == 0) { s = s / 2; } else if (s % 3 == 0) { s = s / 3; } else if (s % 5 == 0) { s = s / 5; } } // s==1,说明能被2/3/5除尽,说明是丑数。 if (s == 1) count++;// 第count个丑数 start++; } // 因为:循环末尾start++,用于下一轮计算,结果(start - 1); System.out.println(start - 1); System.out.println("ok"); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * @author wylu */ public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); System.out.println(getUglyNumber(n)); } private static int getUglyNumber(int n) { if (n < 1) return 0; int[] arr = new int[n]; arr[0] = 1; int t2 = 0, t3 = 0, t5 = 0; for (int i = 1; i < n; i++) { int m2 = arr[t2] * 2, m3 = arr[t3] * 3, m5 = arr[t5] * 5; arr[i] = Math.min(Math.min(m2, m3), m5); while (arr[t2] * 2 <= arr[i]) t2++; while (arr[t3] * 3 <= arr[i]) t3++; while (arr[t5] * 5 <= arr[i]) t5++; } return arr[n - 1]; } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 已找到0个丑数 int count = 0; // 从1开始查找 int start = 1; // 当求得的丑数个数小于n;就不断start++,判断start是不是丑数。 while (count < n) { int s = start; // 如果能被2、3、5整除,就一直除 while (s % 2 == 0 || s % 3 == 0 || s % 5 == 0) { if (s % 2 == 0) { s = s / 2; } else if (s % 3 == 0) { s = s / 3; } else if (s % 5 == 0) { s = s / 5; } } // s==1,说明能被2/3/5除尽,说明是丑数。 if (s == 1) { // 第count个丑数 count++; } start++; } System.out.println(start - 1); } }
#include<iostream> #include<stdio.h> using namespace std; int main() { int N,i,t = 1; cin >> N; bool f = 1; for ( int j = 1; j <=N;) { i = t; f = 1; while (f) { f = 0; if (i % 2 == 0) { i /= 2; f = 1; } else if (i % 3 == 0) { i /= 3; f = 1; } else if (i % 5 == 0) { i /= 5; f = 1; } else { break; } if (i == 1) { break; } } if (i==1) { j++; } t++; } cout << t-1 << endl; system("pause"); return 0; }
#include<iostream> #include<vector> using namespace std; #include<algorithm> int main() { int N; while(cin>>N) { if(N<7) return N; vector<int>res(N); res[0]=1; int t2=0; int t3=0; int t5=0; for(int i=1;i<N;++i) { res[i]=min(res[t2]*2,min(res[t3]*3,res[t5]*5)); if(res[i] == res[t2]*2) t2++; if(res[i] == res[t3]*3) t3++; if(res[i] == res[t5]*5) t5++; } printf("%d\n",res[N-1]); } return 0; }
import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); System.out.print(GetUglyNumber(sc.nextInt())); sc.close(); } public static int GetUglyNumber(int index) { if(index<=6) return index; int[] arr=new int[index]; arr[0]=1; int t2=0,t3=0,t5=0; for(int i=1;i<index;i++){ arr[i]=(Math.min(arr[t2]*2,Math.min(arr[t5]*5,arr[t3]*3))); if(arr[i]==arr[t2]*2) t2++; if(arr[i]==arr[t3]*3) t3++; if(arr[i]==arr[t5]*5) t5++; } return arr[index-1]; } }