泰波拿契數 (Tribonacci Number) 即把費波拿契數 (Fibonacci Number) 的概念推廣至三個數。
T0 = 0, T1 = T2 = 1, Tn = Tn-1 + Tn-2 + Tn-3
请你写一个算法,输入n,输出第n个Tribonacci数mod 2009的结果。
这个题目是众多名企的笔试面试题,据我所知,2009年微软海笔就出了这个题。另外据说google也出国这个题目。这个题目的好,好在于它有很好的区分度。
这个题目有三种解法。你采用什么算法,你的水平就一目了然了。
首先看第一种解法,也是最简单,最容易想到的。
递归法:代码如下:
#include <iostream>
#include <fstream>
#include <cstdlib>
using namespace std;
#define THRESHOLD 2009
#define DEAL(x) ((x) < THRESHOLD ? (x) : (x) % THRESHOLD)
int tribonacci_v1(int n)
{
if (n <= 2)
return n == 0 ? 0 : 1;
else
{
int k =
tribonacci_v1(n - 1) + tribonacci_v1(n - 2) + tribonacci_v1(n - 3);
return DEAL(k);
}
}
采用递归的方法需要大量的重复计算。
经过测试,在ubuntu + gcc -o + p4 2.4GHz的机器上,100都需要算好久。
如果你采用这种算法的话,毫无疑问。你是不可能PASS笔试的。
算法二:采用递推的方法:
这种方法也很简单,头文件定义的宏已经在上面代码有了,函数代码如下:
int tribonacci_v2(int n)
{
int res[] = {0,1,1,2};
for (int i = 3;i <= n;i++)
{
res[3] = res[2] + res[1] + res[0];
res[3] = DEAL(res[3]);
res[0] = res[1];
res[1] = res[2];
res[2] = res[3];
}
return n <= 2 ? res[n] : res[2];
}
采用递推的算法消除了很多重复计算,其时间复杂度是线性的,只扫描一遍O(n).
经测试,一百万以内的数字可以瞬间得到答案。1千万的话也能在1秒内得到解。但是超过1千万就不行了。
在笔试的时候,由于时间有限,其实能写到这个算法就应该可以勉强过笔试了。
第三种解法,矩阵法:
我们首先对算式做一个预处理:
Tn = Tn-1 + Tn-2 + Tn-3
Tn+1 = Tn + Tn-1 + Tn-2
=Tn-1 + Tn-2 + Tn-3 + Tn-1 + Tn-2
= 2Tn-1 +2Tn-1 + Tn-2
Tn+2 = Tn+1 + Tn + Tn-1
= 4Tn-1 +3Tn-1 + 2Tn-2
根据上面的变形,我们可以写成矩阵乘法的方式:
[Tn+2, [ 4 , 3 , 2 ; [Tn-1,
Tn+1, = 2 , 2 , 1; * Tn-2,
Tn] 1, 1 , 1] Tn-3];
我们分别令三个矩阵为 C B A,则有 Cn+2 = B * An-1
因此Cn+5 = B * Cn+2 = B * B * An-1
依此类推 Cn + k = B ^ ([(k + 1) / 3]) * An-1 其中[]为向上取整
于是我们成功将模型转化为矩阵连乘了,而矩阵连乘是符合结合律的,因此我们可以二分求解.
算法复杂度转化为O(logn),具体代码如下:
code写得有点烂,多包涵:
void MatrixMul(int res[][3],const int m1[][3],const int m2[][3])
{
int tmp[3][3];
memset (tmp, 0, sizeof(tmp));
for (int i = 0;i < 3;i++)
{
for (int j = 0;j < 3;j++)
{
for (int k = 0;k < 3;k++)
{
tmp[i][j] += m1[i][k] * m2[k][j];
}
tmp[i][j] = DEAL(tmp[i][j]);
}
}
memcpy(res, tmp, sizeof(int) * 9);
}
int tribonacci_v3(int n)
{
if (n <= 2)
return n == 0 ? 0 : 1;
int matrix[3][3] = {
4 , 3, 2,
2 , 2, 1,
1 , 1, 1};
int res[3][3] = {
1 , 0 , 0,
0 , 1 , 0,
0 , 0 , 1};
int pow = n / 3;
int index = 2 - n % 3;
while (pow != 0)
{
if (pow & 1)
MatrixMul(res, res, matrix);
MatrixMul(matrix,matrix,matrix);
pow >>= 1;
}
return DEAL(res[index][0] + res[index][1]);
}
第三种方法是最完美的,但是代码量比较大,而且容易写错。在面试的时候倒是可以拿出来show一把自己的算法功底。
转自:http://ctperson.blog.ccidnet.com/blog-htm-do-showone-type-blog-itemid-1764393-uid-282150.html
分享到:
相关推荐
100家IT名企笔试面试题 百度笔试题,中兴笔试题,腾讯笔试题,华为笔试题,联想笔试题
名企笔试面试题1、给出一个查分运放,如何相位补偿,并画补偿后的波特图。(凹凸) 2、画差放的两个输入管。(凹凸) 3、画电流偏置的产生电路,并解释。(凹凸) 4、说明mos一半工作在什么区。(凹凸的题目和面试)...
四大、华为、欧莱雅、联通等名企的笔试面试真题四大、华为、欧莱雅、联通等名企的笔试面试真题四大、华为、欧莱雅、联通等名企的笔试面试真题四大、华为、欧莱雅、联通等名企的笔试面试真题四大、华为、欧莱雅、联通...
本资料包“计算机专业各名企笔试面试题及面试技巧”正是针对这一需求,提供了丰富的备考资源。 首先,关于笔试部分,IT企业通常会设计涵盖算法、数据结构、操作系统、计算机网络、数据库、编程语言等多个领域的题目...
fpga,半导体笔试面试题,包括FPGA工程师面试题和答案,中兴通讯校园招聘硬件类笔试题和答案,嵌入式硬件工程师招聘笔试题及答案,最全的硬件工程师笔试试题集,华为笔试真题,典型岗位笔试题,半导体名企模拟面试...
《牛客网_2018名企校招笔试真题精选技术篇》是一份针对学生和求职者的重要参考资料,它汇聚了2018年度众多知名企业的校园招聘笔试题目,旨在帮助准备参加校招的技术人才提升自己的技能水平,顺利通过筛选。...
有华为、微软、神州、金蝶、谷歌等等太多了不一一列举了,大家自己研究吧。大家给点鼓励!
2019年工作面试真题之最新名企笔试题:1000亿条记录中查询内容(腾讯笔试题),华为校招笔试题(字符集合),京东校园招聘笔试真题(快速排序),类似跳表数据结构,查找元素的复杂度(腾讯笔试题),连通图的最大...
"名企笔试面试题总结" 以下是对给定文件信息的详细分析和知识点总结: 标题:名企笔试面试题 描述:本资源提供了多家名企(华为、阿卡、TCL、索尼、微软、百度、大唐)的笔试面试题,涵盖C++、数据结构等相关知识...
这些面试试题是各个名企的面试题哦,都有详细的分析,非常棒的,如果你正在找工作,千万不要错过这套试题哦~~~
这份名为“2018名企校招笔试真题精选技术篇.pdf.zip”的压缩包文件,内含一个名为“2018名企校招笔试真题精选技术篇.pdf”的文档,是博主在春招期间购买于牛客网并经过个人复习标注的资源。这个文档主要针对的是算法...
"互联网名企面试笔试题"这个主题涵盖了一系列旨在测试应聘者技术能力、逻辑思维、问题解决技巧以及行业理解的题目。这些题目通常涉及到编程语言、算法与数据结构、操作系统、网络、数据库等多个IT领域的专业知识。 ...
这些资料汇集了2016年IT名企的笔试真题和答案,涵盖了美团、人人网、阿里巴巴、百度以及360等知名企业的工程师面试环节,对于应聘者来说是宝贵的复习资源。这些企业对工程师的技术要求高,尤其重视前端工程师和后端...
14. **微软面试题**: - 金条问题:将金条切成1/7、2/7和4/7三段。 - 飞鸟问题:鸟飞了15英里,因为鸟的速度比火车快,一直在飞。 - 传感器问题:至少需要2个,分别放在黑白交界处。 - 时针分针重叠:一天中时针...
该文本汇总了常见C++面试中遇到的各种坑,涵盖基础知识比较全面
名企笔试面试手册,不用我多说,绝对物有所有值(包括大型国有企业,外资企业的笔试和面试题目).
《100家名企笔试面试题目》是一个涵盖了软件、硬件和通信领域的综合资源,主要集中在软件类的面试和笔试问题。这份文档旨在为求职者提供一个全面了解企业招聘过程中的常见技术问题的平台,帮助他们更好地准备和提升...
硬件工程师面试笔试资料电子...东芝(中国)toshiba硬件工程师面试题,华为,百度,索尼,戴尔软硬件工程师面试题,逻辑工程师,算法工程师,硬件工程师面试题(北京数码视讯科技股份有限公司招聘笔试真题)等500个资料。
《程序员最常见的笔试面试题合集》是一份涵盖了程序员在求职过程中可能会遇到的各类笔试和面试问题的综合资源。这份合集旨在帮助程序员提升技术素养,准备面试,以便在竞争激烈的IT行业中脱颖而出。以下是对这份合集...