我正在开发一个程序，它接受一个整数并找出该整数具有的连续和的组合数:
The number 13 can be expressed as a sum of consecutive positive
integers 6 + 7. Fourteen can be expressed as 2 + 3 + 4 + 5, also a sum
of consecutive positive integers. Some numbers can be expressed as a
sum of consecutive positive integers in more than one way. For
example, 25 is 12 + 13 and is also 3 + 4 + 5 + 6 + 7.
我研究并读到它是奇数因子的数量减一。所以我写了一个程序来计算奇数因子的数量，但在某些情况下我的答案仍然是错误的。有什么见解吗？
代码似乎工作正常，但由于超时而发生崩溃，这可能是由于优化错误。
可能的输入大小的约束是
1 到 10^(12)
static int consecutive(long num) {
while (num % 2 == 0) num /= 2; // 1st opt.
return consecutiveHelper(num)-1;
}
public static int consecutiveHelper(long num) {
long factorNumber = 1;
int count = 0;
while(factorNumber <= num / 2) { // 2nd opt.
if(num % factorNumber == 0) {
count++;
}
factorNumber += 2; // 3rd opt.
}
if (num % 2 != 0) {
count++;
}
return count;
}
让我们尝试找到一个伪优化的方法来解决您的问题:
您需要做的是将您的数字分解为质因数。
例如，如果您取1200:
1200 = 2*2*2*2*3*5*5 = 1 * 2^4 * 3^1 * 5^2
然后您可以分析如何使用这些素因子得到奇数因子。快速分析会告诉您:
- 奇数 * 奇数 = 奇数
- 奇数 * 偶数 = 偶数
- 甚至 * 甚至 = 甚至
考虑到这一点，让我们找出我们用 odd * odd 得到的所有因数:
- 1 * 1 = 1
- 3 * 1 = 3
- 5 * 1 = 5
- 5 * 3 = 15
- 5 * 5 = 25
- 5 * 5 * 3 = 75
“加 1 法”是一种无需全部写出即可快速找到这些组合的方法:将每个素数奇数因子的出现次数加 1，然后将它们相乘 :
我们发现 1200 = 1 * 2^4 * 3^1 * 5^2，所以我们可以这样做:
- ("3 的个数"+ 1) ("5 的个数"+ 1) =
(1 + 1) ( 2 + 1) = 6
数字 1200 有 6 个奇数因子，正如您所说，从该数字中减去 1 以获得 1200 的连续和的组合数:
现在，让我们看一下代码。 我们想要的是一个 Map，键是主要因素，值是它们出现的次数:
/*
If number is odd,
find the number in the keys and add 1 to its value.
If the number is not in the keys, add it with value = 1.
*/
public static void addValue(Map<Integer, Integer> factors, int i) {
if(i % 2 != 0) {
int count = factors.containsKey(i) ? factors.get(i) : 0;
factors.put(i, ++count);
}
}
/*
Classic algorithm to find prime numbers
*/
public static Map<Integer, Integer> oddPrimeFactors(int number) {
int n = number;
Map<Integer, Integer> factors = new HashMap<>();
for (int i = 2; i <= n / i; i++) {
while (n % i == 0) {
addValue(factors, i);
n /= i;
}
}
if(n > 1) addValue(factors, n);
return factors;
}
这样，让我们尝试打印 map 包含的数字 1200 的内容:
public static void main(String[] args) {
int n = 1200;
System.out.println(oddPrimeFactors(n));
}
$n : {3=1, 5=2}
很好!现在让我们用我们之前开发的方法来完成这个程序:
public static int combinations = 1;
public static void main(String[] args) {
int n = 1200;
oddPrimeFactors(n).forEach((key, value) -> combinations *= (value + 1));
combinations--;
System.out.println(combinations);
}
$combinations = 5
完成的 !如果您有不明白的地方，请随时提问!
注意:我用 Integer 可以处理的最大值尝试了我的程序，我的程序只用了不到一秒钟的时间就可以继续，这对我来说似乎相当快。不过它可能会更快，这取决于您找到此代码的最优化版本!