校园招聘

腾讯

腾讯公司

所属行业:互联网/电子商务 企业性质:私营/民营企业 企业规模:1000人以上

腾讯技术岗的笔试题目

时间:2016-11-29 编辑:光辉

  猴子摘香蕉,它可以一次摘1个,或者一次摘两个,总共摘了50个香蕉,请问共有多少中摘法?(腾讯2016年校招实习笔试题简答题的第二题。)

  解答过程如下:

  由于猴子一次只能摘1个或者两个,设猴子有m次摘了2个香蕉的情况,那么可以知(50-2m)次摘了一个香蕉的情况,其中 0≤ m≤ 25

  经分析,

  当m=0时,共有C050+0 = C050 种情况。

  当m=1时,共有C148+1 = C149 种情况。

  当m=2时,共有C246+2 = C248 种情况。

  当m=3时,共有C344+3 = C347 种情况。

  ……

  当m=24时,共有C242+24 = C2426 种情况。

  当m=25时,共有C250+25 = C2525 种情况。

  SUM = C050 +C149+C248+…+C2426+C2525解法二:

  设摘n个香蕉有f(n)中摘法,如f(50)表示50个香蕉的摘法,经分析,f(n)=f(n-1)+f(n-2)。(n≥3),且f(2)=2,f(1)=1.可用c++编程实现。

  代码一:

  #include

  using namespace std;

  long long f(int n)

  {

  if(n<0)

  return -1;

  else if(n==1)

  return 1;

  else if(n==2)

  return 2;

  return f(n-1)+f(n-2);

  }

  void main()

  {

  cout

  }

  代码一由于采用递归的办法进行计算,速度太慢(我i5的笔记本跑了5五分钟没跑出来)。出于效率考虑,现改进为代码二,采用非递归方法计算。

  代码二:

  #include

  using namespace std;

  long long f(int n)

  {

  long long a=1,b=2,c=0;

  if(n<1)

  return 0;

  else if(n==1)

  return 1;

  else if(n==2)

  return 2;

  else

  {

  for(int i=3;i<=n;i++)

  {

  c=a+b;

  a=b;

  b=c;

  }

  return c;

  }

  }

  void main()

  {

  cout<<"f(1)="

  cout<<"f(2)="

  for(int i=3;i<=50;i++)

  {

  cout<<"f("

您需要登录后才可以回帖登录|注册
发布

互联网/电子商务

私营/民营企业

1000人以上

http://www.qq.com/

公司地址

广东省 - 深圳市 - 南山区科技园飞亚达大厦3-10楼

扫码关注官方微信

及时获取"最新"校招信息