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

时间：2010-09-24 来源：wsnhyjj

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 <cmath> #include <iostream> 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<<a1;      while(loopCounter<(int)n)   {    cout<<"+"<<a1+loopCounter++;   }//while      cout<<"="<<input<<endl; }
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:"<<endl;    cin>>input;
//O(n) cout<<endl<<"the possible data groups are"<<endl; 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; }

相关阅读更多 +