首页 > 代码库 > 百度之星—一个整数拆分成连续的正整数之和的个人解决方法

百度之星—一个整数拆分成连续的正整数之和的个人解决方法

题目描述:一个正整数有可能可以被表示为 n(n>=2) 个连续正整数之和,如:

15=1+2+3+4+5
15=4+5+6
15=7+8

请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。

 

为了解决这个问题,我声明了一个类用来实现。具体声明如下所示:

class CNumber
{
private:
    int split_number;  
    int result_number;   //用来保存拆分的序列的个数。

public:
    void set_number(int split_number);
    int  get_number() const;

    void number_dispose();
    void show_result(int begin , int end);

    void class_interface();

public:
    CNumber(int split_number = 15);
    ~CNumber(void);
};

 

解决方法

 

1、要想解决这个问题,比较直观一点的方法就是穷举法,从1到这个数值的一半,逐渐相加,直到找出等于数值的序列。要想实现这种想法,只用两个for循环语句就可以实现了,但是其时间复杂度接近于O(n3)。

具体解决问题的成员函数代码为:

void CNumber::number_dispose()
{
    int temp = split_number / 2;

    for(int i = 1 ; i <= temp ; i++)
    {
        int result = i;
        for(int j = i + 1 ; j<= temp + 1 ; j++)
        {
            result += j;
            if(split_number == result)
            {
                show_result(i , j);  //用来输出结果
                result_number++;
            }
            else if(result > split_number)
            {
                break;
            }
        }
    }
}

2、由于是连续整数之和,那么也就是说,这一串数值构成等差数列,运用等差数列的求和公式(begin + end)*(end – begin + 1)/2,通过begin的值来求出end的值,如果end的值是整数的话,那么这个整数就可以拆分成begin到end之间的连续整数,如果不能,则继续。另外begin的取值范围是1到数值的一半。运用这种方法,其时间复杂度为O(n)。具体的实现代码为:

void CNumber::number_dispose()
{
    int temp = split_number / 2;

    for(int i = 1 ; i <= temp ; i++)
    {
        double result = 8 * split_number + 4 * i * i - 4 * i + 1;
        double first_judge = sqrt((double)result);
        if((int)first_judge != first_judge)
            continue;

        int end = ((int)first_judge - 1)/ 2;//上面的运算,其实就是求一元二次方程的解。
        show_result(i , end);
        result_number ++;
    }
}

运行后的结果显示为: