《编程之美》读书笔记:“只考加法的面试题”_求职面试_非技术区_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 非技术区 > 求职面试 > 《编程之美》读书笔记:“只考加法的面试题”

《编程之美》读书笔记:“只考加法的面试题”

 2010/12/2 10:22:42    程序员俱乐部  我要评论(0)
  • 摘要:最近时日,从dangdang买了本MARA众高人写的《编程之美》,里面有这么一道题,其中并没有给出问题的解答。一时兴起,就在电脑前动了动手,特献丑与此。BTW,《编程之美》应该是每一位热爱编程技术的IT从业人员桌案边必备的好书。当我还在沉浸于找出问题的解决方案时,MARA的大侠找出了N个解,并且寻求最优解。他们把一个看似复杂的问题可以很快地简单化,找出数学模型,并编程实现。Keepfighting!!![question]我们知道:1+2=3;4+5=9;2+3+4=9
  • 标签:编程之美 面试题

最近时日,从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可以再快些。

[answer-programme]
#include "stdafx.h"
#include <math.h>
#include <iostream.h>

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(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;
}

本文出自:http://blog.csdn.net/haykey/archive/2008/10/29/3175373.aspx

发表评论
用户名: 匿名