首页 > 代码库 > 百度之星—一个整数拆分成连续的正整数之和的个人解决方法
百度之星—一个整数拆分成连续的正整数之和的个人解决方法
题目描述:一个正整数有可能可以被表示为 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 ++; } }
运行后的结果显示为:
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。