爱悠闲 > 面试题:输入一个正整数n,输出所有的连续正整数之和等于n的序列

面试题:输入一个正整数n,输出所有的连续正整数之和等于n的序列

分类: 面试专栏  |  作者: key_15 相关  |  发布日期 : 2014-07-08  |  热度 : 59°

先说下题目: 如果你输入的数字是15 那么输出为1 2 3 4 5 、4 5 6  、 7  8

这个题目在剑指offer中有一个做法,但是不是最好的做法,面试官说复杂度过高:

剑指offer上面的解法是首先设置两个值i=1和j=2,一个表示开头的正整数,一个表示结尾的正整数。当正整数的和大于15的时候i向后移动,当和15的时候j向后移动。等的时候输出一个,到后继续找。

仔细琢磨结合网上的代码找到了一个时间复杂度为O(n的1/2次方)的方法

以15为例 我们假设最大正整数个数为x则这些正整数的中间数字为15/x 那么既然是最长则x前面的数字有x/2个到1 => 15/x = x/2; =>x=sqrt(15*2).

如果是n的话 x = sqrt(2n);

我们只需要根据这个长度x来找就可以了,下面是代码(来自网上):

#include <stdio.h>
#include <math.h>
int main()

 int m=0,
  n=0,
  start=0,
  end=0,
  flag=0; 
 //m为输入的数,n为正整数序列个数,start为显示的开始正整数,end为显示的结束正整数,
 //flag表示有无符合条件的序列存在,0(默认)没有,1有 
 float temp=0.0; 
 printf("please input a Integer:"); 
 scanf("%d",&m);
 printf("\n");
 n=(int) (sqrt((double)m)*sqrt((double)2));
 //求出可能的最大的序列个数
 while(n>=2)
 {
  temp=(float)m/n-(float)(n-1)/2;
  //求开始数
  if(temp==(int) temp)
  { 
   //判断是不是正整数,即有没有符合符合条件的序列存在
   for(flag=1,start=(int) temp,end=start+n;start<end;start++)
   {     
    //flag标志置1,有符合符合条件的序列存在,得出开始整数start和结束整数end 
    printf("%d",start); 
    printf(" ");
   } 
   printf("\n"); 
  } 
  n--; 
 }
 if(flag==0)    
  //没有符合符合条件的序列存在,则输出"none" 
  printf("none");
}

 

仔细一看也是很简单的。当时受到剑指offer这本书的干扰,自己以为很好了,结果被鄙视了