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

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

2024-07-07 21:39:49   215人阅读

题目描述：一个正整数有可能可以被表示为 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 ++;
    }
}

运行后的结果显示为：


联系
我们