优化会导致超时吗? [英] optimization causes timeout?

问题描述

我正在研究一个程序，该程序需要一个整数并查找该整数具有的连续和的组合数:

I am working on a program that takes an integer and finds the number of combinations of consecutive sums that the integer has:

数字13可以表示为连续正数的总和 整数6 +7.十四可以表示为2 + 3 + 4 + 5，也可以是和 连续的正整数.一些数字可以表示为 连续正整数的总和以一种以上的方式.为了 例如25是12 + 13，也是3 + 4 + 5 + 6 + 7.

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.

我研究了一下，发现它是奇数个数减一.因此，我编写了一个程序，用于查找奇数因子的数量，在某些情况下，我的答案仍然是错误的.有见识吗?

I researched and read that it's the number of odd factors minus one. So I wrote a program that finds the number of odd factors and my answer is still wrong in certain cases. Any insight?

代码似乎可以正常工作，但是由于超时而导致崩溃，这很可能是由于优化错误所致.

Code seems to work fine but there is a crash due to Timeout which is probably due to optimization error.

可能的输入大小的限制是 1至10 ^(12)

The constraints for possible input size is 1 to 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

然后，您可以分析如何用这些主要因素获取奇数因素.快速分析会告诉您:

You can then analyze how you could get odd factors with those prime factors. A quick analyze will tell you that :

• 奇数*奇数=奇数
• 奇数*偶数=偶数
• 偶数*偶数=偶数

考虑到这一点，让我们找到使用奇*奇得出的所有因素:

With that in mind, let's find all the factors we get with odd * odd :

• 1 * 1 = 1
• 3 * 1 = 3
• 5 * 1 = 5
• 5 * 3 = 15
• 5 * 5 = 25
• 5 * 5 * 3 = 75

一种无需写全部即可找到这些组合的快速方法是"加1方法":将每个主要奇数因子的出现次数加1，然后将它们相乘:

A quick way to find these combinations without writing them all is the "plus 1 method" : add 1 to the number of occurences of each prime odd factor, and multiply them together :

我们找到了1200 = 1 * 2^4 * 3^1 * 5^2，所以我们可以这样做:

We found that 1200 = 1 * 2^4 * 3^1 * 5^2, so we can do :

• (数量为3" +1)(数量为5" +1)= (1 + 1) ( 2 + 1) = 6

数字1200有6个奇数因子，如您所述，从该数字中减去1可得到1200具有的连续和的组合数:

• 6-1 = 5 <-呜呼！终于得到了结果！

现在，让我们看一下代码. 我们想要的是一张地图，键是主要因素，值是它们的出现次数:

Now, let's look at the code. What we want to have is a Map, the keys being the prime factors and the values being the number of their occurences :

/*
    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;
}

有了这一点，让我们尝试打印编号为 1200 的地图包含的内容:

With that, let's try to print what the map contains for number 1200 :

public static void main(String[] args) {
    int n = 1200;

    System.out.println(oddPrimeFactors(n));
}

$n : {3=1, 5=2}

好！现在，让我们用之前开发的方法完成程序:

Good ! Now let's finish the program with the method we developed before :

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可以处理的最大值来执行程序，并且程序花了不到一秒钟的时间才能进行，这对我来说似乎非常快.不过可能会更快，这取决于您找到此代码的最优化版本！

Finished ! feel free to ask if you did not understand something !

Note : I tried my program with the max value Integer can handle and it took less than one second for my program to proceed, which seems pretty fast to me. It could probably be faster though, it's up to you to find the most optimized version of this code !

这篇关于优化会导致超时吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！