Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1525052
  • 博文数量: 164
  • 博客积分: 2993
  • 博客等级: 少校
  • 技术积分: 1718
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-24 11:42
文章分类

全部博文(164)

文章存档

2014年(1)

2013年(36)

2012年(90)

2011年(37)

分类: C/C++

2012-04-20 15:23:07

题目:输入一个正数n,输出所有和为n的连续正数序列,例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6、7-8。

思路1:我们用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1,big初始化为2,如果从small到big的序列的和大于n的话,我们向右移动small,相当于从序列中去掉较小的数字。如果从small到big的序列的和小于n的话,我们向右移动big,相当于向序列中添加big的下一个数字,一直到small等于(1+n)/2,因为序列中至少要有两个数字。

 

  1. void FindContinuousSequence(int n)  
  2. {  
  3.     assert(n >= 3);  
  4.   
  5.     int small = 1;   
  6.     int big = 2;  
  7.     int mid = (1+n)/2;  
  8.     int sum = small+big;  
  9.     while(small < mid)  
  10.     {  
  11.         if(sum == n)  
  12.         {  
  13.             cout << small << "-" << big << endl;  
  14.             sum -= small;  
  15.             small++;  
  16.         }  
  17.         else if(sum > n)  
  18.         {  
  19.             sum -= small;  
  20.             small++;  
  21.         }  
  22.         else  
  23.         {  
  24.             big++;  
  25.             sum += big;  
  26.         }  
  27.     }  
  28. }  

 

思路2:按照等差数列计算,连续数列有i个数,首数为x,和为n=(2x+i-1)*i/2,解得x=(2n/i-i+1)/2,注意x>0且i为整数,可得i的取值范围为[2, sqrt(2*n)],又x为整数,故2n/i为整数,且(2n/i-i+1)/2为整数。

 

  1. void FindContinuousSequence(int n)  
  2. {  
  3.     assert(n >= 3);  
  4.       
  5.     for(int i=2; i<=sqrt(2*n); i++)  
  6.     {  
  7.         if((2*n)%i == 0)  
  8.         {  
  9.             int temp = 2*n/i-i+1;  
  10.             if(temp%2 == 0)  
  11.             {  
  12.                 cout << temp/2 << "-" << temp/2+i-1 << endl;  
  13.             }  
  14.         }  
  15.     }  
  16. }  


扩展题目1:某些数n并不能表示为一系列连续的自然数之和,例如4、8、32就不行,那么这样的数有什么规律呢?能否证明你的结论?

思路:2的整数次幂不能表示为一系列连续的自然数之和,如上思路2所示,若要2n/i为整数,则i必为偶数,而当i为偶数时,2n/i-i为偶数,2n/i-i+1为奇数,此时(2n/i-i+1)/2就不可能为整数了,即不存在连续自然数之和了,故命题得证。


扩展题目2:在64位正整数范围内,子序列数目最多的是哪一个?能否用数学知识推导出来可怜求思路可怜


(转载)

阅读(1314) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~