首页 > 代码库 > java算法之超级丑数
java算法之超级丑数
问题描述：
写一个程序来找第 n 个超级丑数。
超级丑数的定义是正整数并且所有的质数因子都在所给定的一个大小为 k 的质数集合内。
比如给你 4 个质数的集合 [2, 7, 13, 19], 那么 [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] 是前 12 个超级丑数。
注意事项
1:永远都是超级丑数不管给的质数集合是什么。
2:给你的质数集合已经按照升序排列。
0 < k ≤ 100, 0 < n ≤ 10^6, 0 < primes[i] < 1000
样例 ：给出 n = 6 和质数集合 [2, 7, 13, 19]。
第 6 个超级丑数为 13，所以返回 13 作为结果。
代码：
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco; color: #931a68 } p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco; min-height: 15.0px } p.p3 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco } span.s1 { color: #000000 } span.s2 { color: #931a68 } span.s3 { color: #7e504f } span.s4 { color: #0326cc } span.s5 { text-decoration: underline; color: #7e504f } span.Apple-tab-span { white-space: pre }</style>package 超级丑数;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
System.out.println(3/2);
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
if(k<=0||k>100){
return;
}
int primes[] = new int[k];
for (int i = 0; i < primes.length; i++) {
primes[i] = sc.nextInt();
for (int j = 2; j < primes[i]/2+1; j++) {
if(primes[i]%j==0){
return;
}
}
}
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
for (int i = 2; i < Math.pow(10, 6); i++) {
if(isSuperUglyNumber(i,primes)){
list.add(i);
}
if(list.size()==n){
System.out.println(list.get(n-1));
break;
}
}
}
//递归思想判断是否为超级丑数
private static boolean isSuperUglyNumber(int i, int[] primes) {
if(i<primes[0])return false;
else{
for (int j = primes.length-1; j >= 0; j--) {
if(i==primes[j]){
return true;
}
else if(i>primes[j]&&i%primes[j]==0){
if(isSuperUglyNumber(i/primes[j],primes)){
return true;
}
}else{
continue;
}
}
return false;
}
}
//循环思想判断是否为超级丑数
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco; color: #931a68 } p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px Monaco } span.s1 { color: #000000 } span.s2 { color: #7e504f } span.s3 { color: #931a68 } span.s4 { color: #0326cc } span.s5 { text-decoration: underline; color: #7e504f } span.Apple-tab-span { white-space: pre }</style>public static boolean isSuperUglyNumber(int num ,int[] p){
for (int i = 0; i < p.length; i++) {
int j = 0;
while(true){
if(num % p[i] != 0 ){
break;
}else{
num = num/p[i];
continue;
}
}
if(num == 1){
return true;
}
}
return false;
}
}
采用了循环和递归两种思想，两个方法都可以正确判断到是否为满足条件超级丑数，这里就不放测试结果了，请自行测试
还有一些细节上的问题没有处理，不要在意这些哈。
转载请注明出处哦http://www.cnblogs.com/meng1314-shuai/p/7233403.html
java算法之超级丑数