首页 > 代码库 > 将一个正整数表示为连续自然数的和
将一个正整数表示为连续自然数的和
原文:将一个正整数表示为连续自然数的和
将一个正整数表示为连续自然数的和,比如给定整数15,那么根据题意,需要输出的连续自然数为1+2+3+4+5=4+5+6=7+8=15。题目中的连续自然数序列可以看做一个升序的有序数组,取数组前两个数为起始的区间的左右两个端点。对区间中的值进行累加,如果累加值小于给定的整数时,那么右端点向右移动,添加下一个数字,如果累加值大于给定的整数时,那么左端点向右移动,表示去掉最左端的最小值,如果值与给定整数相等,那么输出后,需要重新对定区间左右两个端点赋值,直到左端点的值小于 (number+1)/2。代码如下:
1 void printContinuous(int begin, int end, int value) 2 { 3 for(int i=begin; i!=end; i++) 4 cout<<i<<"+"; 5 cout<<end<<" = "<<value<<endl; 6 } 7 8 void findContinuous(int n) 9 {10 int begin=1, end = 2; //begin和end分别代表和为n的连续正数的区间11 int middle = (n+1)/2; //middle表示n的中间数,middle*2 >= n,所以控制begin<middle即可12 int sum = begin+end;13 14 while(begin < middle)15 {16 if(sum == n) //和与n相等,则打印17 {18 printContinuous(begin, end, n);19 //从begin+1开始重新计算sum的值20 begin++;21 end = begin+1;22 sum = begin+end;23 }24 else if(sum > n)//如果sum>n,那么begin右移,即减去最左边的数25 {26 sum-=begin;27 begin++;28 }29 else//如果sum<n,那么end右移,即添加一个数30 {31 end++;32 sum+=end;33 }34 }35 }
上面的解法可以满足题目的要求,我们现在试着用数学的方法来求解此题。题目中要求将给定整数表示为连续自然数的和,而连续自然数序列可以看做一个等差数列,那么题目可以重新描述为,求出和为给定整数值的自然数组成的等差数列。等差数列前n项和的公式为:a1*n+ n*(n-1)*d/2,其中a1表示首项值,n表示项数,d表示公差。根据公式,可以写出代码:
1 void findContinuous2(int n) 2 { 3 for(int i=1; i<(n+1)/2; i++) 4 { 5 for(int j=1; j<(n+1)/2; j++) 6 { 7 //表示以i开头,到i后面j项为止的等差数列和 8 int sum = i*j+(j*(j-1)/2); 9 if(sum == n)10 {11 printContinuous(i, i+j-1, n);12 }13 }14 }15 }
可以看出,数学对于一些算法还是比较重要的,不能说一定会提高程序的运行效率,但在解决一些问题是,数学上的知识会帮助我们更加清晰化的解法。
将一个正整数表示为连续自然数的和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。