10
Tôi có vấn đề cần giải quyết. N số tự nhiên được đưa ra. Tôi cần phải tìm một danh sách các số tự nhiên mà tổng lên đến con số nhất định và đồng thời các phần tử nghịch đảo lên đến 1.Tất cả các số tự nhiên tổng hợp thành N và tổng số nghịch đảo tổng hợp lên một
a + b + c + ... = N
1/a + 1/b + 1/c + ... = 1
a, b, c không phải là duy nhất.
Tôi đã đưa ra mã sau trong Java. Nó hoạt động cho các trường hợp đơn giản, nhưng cực kỳ chậm đối với N > 1000.
Tôi có thể viết lại phương thức sao cho nó hoạt động nhanh ngay cả đối với hàng triệu? Có lẽ, tôi nên thả ra đệ quy hoặc cắt đứt một số chi nhánh với lừa toán học mà tôi bỏ lỡ?
SSCEE:
private final static double ONE = 1.00000001;
public List<Integer> search (int number) {
int bound = (int)Math.sqrt(number) + 1;
List<Integer> list = new ArrayList<Integer>(bound);
if (number == 1) {
list.add(1);
return list;
}
for (int i = 2; i <= bound; i++) {
list.clear();
if (simulate(number, i, list, 0.0)) break;
}
return list;
}
//TODO: how to reuse already calculated results?
private boolean search (int number, int n, List<Integer> list, double sum) {
if (sum > ONE) {
return false;
}
//would be larger anyway
double minSum = sum + 1.0/number;
if (minSum > ONE) {
return false;
}
if (n == 1) {
if (minSum < 0.99999999) {
return false;
}
list.add(number);
return true;
}
boolean success = false;
for (int i = 2; i < number; i++) {
if (number - i > 0) {
double tmpSum = sum + 1.0/i;
if (tmpSum > ONE) continue;
list.add(i);
success = search(number - i, n - 1, list, tmpSum);
if (!success) {
list.remove(list.size() - 1);
}
if (success) break;
}
}
return success;
}
Tôi nghĩ '1/a + 1/b + 1/c + ... = N' là lỗi đánh máy, phải là' = 1', phải không? –
Chỉ cần làm rõ, {a, b, ...} phải là số nguyên, phải không? Ngoài ra, bạn có cho phép cả số dương và số âm? – adrianp
Nên a, b, c, ... de dinstinct? – Thomash