只考加法的面试题---编程之美

http://blog.csdn.net/haykey/archive/2008/10/29/3175373.aspx

最近时日，从dangdang买了本MARA众高人写的《编程之美》，里面有这么一道题，其中并没有给出问题的解答。一时兴起，就在电脑前动了动手，特献丑与此。BTW,《编程之美》应该是每一位热爱编程技术的IT从业人员桌案边必备的好书。当我还在沉浸于找出问题的解决方案时，MARA的大侠找出了N个解，并且寻求最优解。他们把一个看似复杂的问题可以很快地简单化，找出数学模型，并编程实现。Keep fighting!!!

[question]
我们知道:1+2=3;
             4+5=9;
             2+3+4=9;
等式左边都是两个以上连续的自然数相加，那么是不是所有的整数都可以写成这种形式呢？
写一个程序，对于一个32位正整数，输出它所有的连续自然数之和的算式。

[analysis]
可以发现任意自然数序列其实是公差为1的等差数列，那么数列前N项和公式有a1*n +n*(n-1)/2 = sn，而这里sn = 输入的正整数input。通过分析a1只需在集合[1，input/2)中，把上式等效变形为n2+(2a1-1)n-2input = 0，n的取值为中学学得2a分之负b加减根号下b方减4ac，哈，如果n为一个正整数，那么符合条件输出。如何判断n为合法的正整数不是浮点数呢？看看我的solution吧。我算法的时间复杂度是O(N)线形级别的,不知哪位大虾的solution可以再快些。

#include

#include

using namespace std;

bool isPositiveInt(float num)

{

 return (num - (int)num)==0?true:false;

}

void outputResult(int a1,float n,int input)

{

  int loopCounter = 1;

  int a = a1;

  cout<

  

  while(loopCounter<(int)n)

  {

     cout<<"+"<

  }//while

  

  cout<<"="<

}

int main(int argc, char* argv[])

{

 unsigned int input,i;

 //input any positive numbers you want to calculate with

 cout<<"input any positive numbers you want to calculate with:"<

        cin>>input;

 //O(n)

 cout<

 

 float temp;

 for(i=1;i<=input/2;i++)

 {

    temp = sqrt(float(8*input+(i+i-1)*(i+i-1)));//b*b - 4ac

    temp = (1 + temp - i - i)/2;

    if(isPositiveInt(temp))

    {

       outputResult(i,temp,input);

    }

 }

 

 return 0;

}