• 软件测试技术
  • 软件测试博客
  • 软件测试视频
  • 开源软件测试技术
  • 软件测试论坛
  • 软件测试沙龙
  • 软件测试资料下载
  • 软件测试杂志
  • 软件测试人才招聘
    暂时没有公告

字号: | 推荐给好友 上一篇 | 下一篇

Adobe的一道笔试题

发布: 2010-7-08 10:46 | 作者: 不详 | 来源: 领测测试网采编 | 查看: 84次 | 进入软件测试论坛讨论

领测软件测试网

  Adobe的一道笔试题   软件测试

  {f(n), f(n-1), f(n-1), f(n-2)} ={1, 1, 1,0}n-1

  (注:{f(n+1), f(n), f(n), f(n-1)}表示一个矩阵。在矩阵中第一行第一列是f(n+1),第一行第二列是f(n),第二行第一列是f(n),第二行第二列是f(n-1)。)

  有了这个公式,要求得f(n),我们只需要求得矩阵{1, 1, 1,0}的n-1次方,因为矩阵{1, 1, 1,0}的n-1次方的结果的第一行第一列就是f(n)。这个数学公式用数学归纳法不难证明。感兴趣的朋友不妨自己证明一下。

  现在的问题转换为求矩阵{1, 1, 1, 0}的乘方。如果简单第从0开始循环,n次方将需要n次运算,并不比前面的方法要快。但我们可以考虑乘方的如下性质:

  / an/2*an/2 n为偶数时

  an=

  \ a(n-1)/2*a(n-1)/2 n为奇数时

  要求得n次方,我们先求得n/2次方,再把n/2的结果平方一下。如果把求n次方的问题看成一个大问题,把求n/2看成一个较小的问题。这种把大问题分解成一个或多个小问题的思路我们称之为分治法。这样求n次方就只需要logn次运算了。

  实现这种方式时,首先需要定义一个2×2的矩阵,并且定义好矩阵的乘法以及乘方运算。当这些运算定义好了之后,剩下的事情就变得非常简单。完整的实现代码如下所示。

  #include

  ///////////////////////////////////////////////////////////////////////

  // A 2 by 2 matrix

  ///////////////////////////////////////////////////////////////////////

  struct Matrix2By2

  {

  Matrix2By2

  (

  long long m00 = 0,

  long long m01 = 0,

  long long m10 = 0,

  long long m11 = 0

  )

  :m_00(m00), m_01(m01), m_10(m10), m_11(m11)

延伸阅读

文章来源于领测软件测试网 https://www.ltesting.net/

TAG: Adobe 笔试

41/41234>

关于领测软件测试网 | 领测软件测试网合作伙伴 | 广告服务 | 投稿指南 | 联系我们 | 网站地图 | 友情链接
版权所有(C) 2003-2010 TestAge(领测软件测试网)|领测国际科技(北京)有限公司|软件测试工程师培训网 All Rights Reserved
北京市海淀区中关村南大街9号北京理工科技大厦1402室 京ICP备10010545号-5
技术支持和业务联系:info@testage.com.cn 电话:010-51297073

软件测试 | 领测国际ISTQBISTQB官网TMMiTMMi认证国际软件测试工程师认证领测软件测试网