Я работаю над задачей из учебника Java, в которой требуется найти первые 10 чисел с 50 десятичными цифрами, которые делятся на 2 или 3. Вот мой код:
import java.math.*;
public class Divisible {
public static void main(String[] args) {
BigDecimal numbers = new BigDecimal("0.00000000000000000000000000000000000000000000000000");
BigDecimal number2 = new BigDecimal("2.0");
BigDecimal number3 = new BigDecimal("3.0");
BigDecimal increment = new BigDecimal("0.00000000000000000000000000000000000000000000000001");
int count = 0;
while (count < 10) {
boolean isDivisibleBy2 = isDivisible(numbers, number2);
boolean isDivisibleBy3 = isDivisible(numbers, number3);
if (isDivisibleBy2 || isDivisibleBy3) {
System.out.println(numbers);
count++;
} else {
System.out.println("No divisor.");
}
numbers = numbers.add(increment);
}
}
private static boolean isDivisible(BigDecimal number, BigDecimal divisor) {
BigDecimal remainder = number.remainder(divisor);
return remainder.compareTo(BigDecimal.ZERO) == 0;
}
}
Но этот код выполняется в бесконечном цикле с надписью «Нет делителя».
Я думаю, проблема в методе isDivisible
, который проверяет делимость с помощью метода remainder
.
Буду признателен за любые советы по моему нынешнему подходу.
@ Сорен, это хорошая мысль. Что мы подразумеваем под делимостью на нецелые числа? Теперь, когда я думаю об этом, я понимаю, что неправильно понял вопрос. Я думаю, что под «числами с 50 десятичными цифрами» в книге подразумевались «целые числа с 50 цифрами», а не «числа с 50 цифрами после десятичного разделителя».
@Osmium Даже если ваш алгоритм завершится в результате тепловой смерти Вселенной (это не так — это 1,4x10^51 операций), он никогда не даст результат, не являющийся целым числом. Он печатает 0, 2, 3, 4, 6, 8, 9, 10, 12, 14. Просто делает это очень медленно. Остаток от деления десятичной дроби на целое число никогда не равен 0 (эта часть: remainder.compareTo(BigDecimal.ZERO)
)
Вместо того, чтобы сразу переходить к кодированию, не обдумав проблему должным образом, мне следует сначала потратить время на ее понимание. Урок выучен.
Я предлагаю вам использовать BigInteger
, а не BigDecimal
.
числа, делящиеся на 2 – начните с наименьшего четного (например, 10000...00
), а затем в цикле прибавляйте 2; аналогично для числа, делящегося на 3, только начальное число немного сложнее (например, 10000...02
) — это почти проще сделать на бумаге
@Майкл, почему ты так говоришь? Забывая о том, что это очень медленно, numbers
в конечном итоге достигнет десятичной дроби, равной целому числу, и в этом случае remainder.compareTo(BigDecimal.ZERO)
действительно будет 0
. Смысл использования compareTo
вместо equals
в том, что он игнорирует масштаб и просто смотрит на значение своих операндов.
@DawoodibnKareem «числа в конечном итоге достигнут десятичной дроби, равной целому числу», я знаю и уже говорил это. Я сказал, что его алгоритм печатает 0, 2, 3 и т. д. (теоретически, а не на практике).
У вас нет бесконечного цикла. Ваш прирост настолько мал, что делению требуется много-много-много итераций, чтобы наконец найти число, делящееся на 2 или 3. Если я изменю приращение на 0,01, я получу результаты почти сразу. При значении 0,00001 поиск результатов занимает секунды. Я не знаю, сколько времени потребуется, чтобы найти первый результат (2) с вашим приращением, но это не секунды, даже не часы и, вероятно, даже не недели — вполне может пройти больше года. (Печать сообщения и здесь не помогает.)
Пройдет 2e50 циклов, прежде чем numbers
превратится в 2.0
, что является первым числом, для которого цикл завершится. Предполагая, что поиск результата по адресу .00001 (1e5) занимает 1 секунду, и учитывая, что это алгоритм O(n)
, мы можем линейно расширить это время: потребуется 2e50/1e5
= 6335000000000000000000000000000000 ВЕКА, прежде чем этот код будет напечатан. «Вполне может пройти больше года», — говорите вы. Хм... да. Вы немного недооценили, там. Предполагаемая тепловая смерть Вселенной составляет ~1e100 лет, так что, я думаю, мы можем сказать: по крайней мере, сама Вселенная не мешает вам делать это буквально.
Вау, я был вааааааааа ;)
Я понимаю, что проблему надо решать написанием программы, ведь именно этим и хочется практиковаться…
Но подход проверки того, что остаток деления равен 0, проблематичен, когда вы ищете только 2 и 3 в качестве делителей.
Хорошо известно, что каждое четное число делится на 2, поэтому вам просто нужно проверить, является ли последняя цифра числа четной.
А число делится на 3, если сумма цифр делится на три (или если оно равно 3, 6 или 9). Хорошо, мы можем обсудить, является ли деление на 3 и проверка остатка быстрее, чем получение цифр числа и их суммирование (многократное количество раз), а затем проверка, равно ли это 3, 6 или 9.
Метод «грубой силы» требуется только для делителя 7 (пока мы остаемся между 2 и 9).
Это моменты, которые следует учитывать. Спасибо.
Как определить делимость нецелых чисел?