问题:“巴比伦人使用有规律的数字来计时。在数学中,“正则数”被定义为是60的某个幂的因数(60,3600等)。等价地,我们可以说一个正则数是一个只有2,3和5的素因子的数。前10个常规数字是:1,2,3,4,5,6,8,9,10,12.你的任务是找到第n个正规数。”我的教授要求我们专门使用优先级队列来解决这个问题,我们将测试的最大数字不超过 n = 300。我很无知。编辑:我显然不是要求完整的代码,我只是需要指针让我开始。
n = 300
0s0u357o1#
不知道为什么要使用PriorityQueue,但解决这个问题的一个非常丑陋的蛮力方法是这样的。
import java.util.Arrays;import java.util.List;import java.util.PriorityQueue;import java.util.stream.Collectors;public class Driver { public static void main(String[] args) { Driver driver = new Driver(); System.out.println(driver.getRegularNumber(30) .toString()); } public PriorityQueue<Integer> getRegularNumber(int n) { PriorityQueue<Integer> regularNumbers = new PriorityQueue<>(); int count = 0; int current = 1; List<Integer> pf; List<Integer> apf = Arrays.asList(2, 3, 5); while (count < n) { // Get the prime factors of the current number. // If it is a subset of the allowed prime factors then add it to the Queue. pf = primeFactors(current); if (apf.containsAll(pf)) { regularNumbers.add(current); count++; } current++; } return regularNumbers; } public static List<Integer> primeFactors(int n) { List<Integer> factors = new ArrayList<>(); for (int i = 2; i < n; i++) { while (n % i == 0) { factors.add(i); n = n / i; } } if (n > 2) { factors.add(n); } factors = factors.stream() .distinct() .collect(Collectors.toList()); return factors; }}
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.stream.Collectors;
public class Driver {
public static void main(String[] args) {
Driver driver = new Driver();
System.out.println(driver.getRegularNumber(30)
.toString());
}
public PriorityQueue<Integer> getRegularNumber(int n) {
PriorityQueue<Integer> regularNumbers = new PriorityQueue<>();
int count = 0;
int current = 1;
List<Integer> pf;
List<Integer> apf = Arrays.asList(2, 3, 5);
while (count < n) {
// Get the prime factors of the current number.
// If it is a subset of the allowed prime factors then add it to the Queue.
pf = primeFactors(current);
if (apf.containsAll(pf)) {
regularNumbers.add(current);
count++;
current++;
return regularNumbers;
public static List<Integer> primeFactors(int n) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i < n; i++) {
while (n % i == 0) {
factors.add(i);
n = n / i;
if (n > 2) {
factors.add(n);
factors = factors.stream()
.distinct()
.collect(Collectors.toList());
return factors;
这将产生[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]作为输出。
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
1条答案
按热度按时间0s0u357o1#
不知道为什么要使用PriorityQueue,但解决这个问题的一个非常丑陋的蛮力方法是这样的。
这将产生
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
作为输出。