java - 将整数表示为连续正整数之和

Question

我正在编写代码来计算整数可以表示为连续整数之和的方式的数量。例如

15=(7+8),(1+2+3+4+5),(4+5+6)。所以路数等于 3 乘 15。 现在输入大小可以<=10^12。我的程序在 10^7 之前都运行良好(我想是这样，但不确定，因为我没有在任何在线法官上检查过它。请随意检查代码)

但是一旦 i 给它 10^8 或更大的整数作为输入。它抛出许多运行时异常(它不显示什么运行时错误)。提前致谢。

import java.io.*;

//sum needs to contain atleast 2 elements
public class IntegerRepresentedAsSumOfConsecutivePositiveIntegers
{
    public static long count = 0;
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long num = Long.parseLong(br.readLine()); //Enter a number( <=10^12)
        driver(num);
        System.out.println("count = " + count);
    }

    public static void driver(long num)
    {
        long limit = num / 2;
        for(long i = 1 ; i <= limit ; i++)
        {
            func(i,num);
        }
    }

    public static void func(long i,long num)
    {
        if(i < num)
        {
            func(i + 1,num - i);
        }
        else if(i > num)
        {
            return;
        }
        else
        {
            count++;
        }
    }

}

Answer 1

当您的输入大小像您的情况一样大时，递归函数不适合。

java调用堆栈的最大深度约为8900次调用，有时只有在7700次调用后才会发生堆栈溢出，因此这实际上取决于您的程序输入大小。

尝试这个算法，我认为它可以解决您的问题:

它会正常工作直到10^9，之后将需要更多时间才能完成程序的运行。

    long sum = 0;
    int count = 0;
    long size;
    Scanner in = new Scanner(System.in);
    System.out.print("Enter a number <=10^12: ");
    long n = in.nextLong();
    if(n % 2 != 0){
        size = n / 2 + 1;
    }
    else{
        size = n / 2;
    }
    for(int i = 1; i <= size; i++){           
       for(int j = i; j <= size; j++){
            sum = sum + j;
            if(sum == n){
                sum = 0;
                count++;
                break;
            }
            else if(sum > n){
                 sum = 0;
                 break;
            }
        }
    }
    System.out.println(count);

输出:

Enter a number <=10^12: 15
3

Enter a number <=10^12: 1000000000
9
BUILD SUCCESSFUL (total time: 10 seconds)