晚上参加某公司的笔试题遇到如下一道题,本来打算在网上搜索,无奈全是英文,所以我将大概意思写出,各位有知道是什么问题的可以告诉我,比如说这是道费波那奇数列,我想了半天没想出这道题该如何求解。
题目如下:
给你一个数比如 6,从0开始,第n步可以走n个距离
比如 第一步(0-->1) 走了1步
1 2 3 4 5 6 7 8 |
|
程序C/C++ 实现不能使用任何stl,所有实现自己写,要求给定数字N,求出其所走序列。
表达能力有限,如果有疑问在此留言。
楼下几个说简单的,你不妨写出代码,多试几个数字,就知道这个程序有多简单了。
2015.9.21 19:59
………………………………………………………………………………
PHP中文网2017-04-17 12:07:43
我想的解法效率有点低,但是至少是思路是可行的。
我不会C/C++,我就把思想写给你吧。
你每一步有2个状态,向前或向后,你可以画一棵树,大概长这样。
其中第n级表示走第n步可能的所在位置。你会发现每一级左右两边的数都是相反的。比如第三级,-3,1和-1,3。所以对于第三级,你就只需要存1和3就可以了。
由于第n级能走n-1步,所以第n级所有的情况就是正负第n-1级所有情况加减n。
还是比如第三级,由于第二级有1和3,第三级就是1+3,1-3,3+3,3-3,就是4,-2,6,0,所有的情况就是-6,-4,-2,0,2,4,6。但是我们只存绝对值,也就是0,2,4,6。
你就一级一级往下算,算到每一级看看结果的绝对值是不是在里面。如果在的话,就等于找到结果了,然后往上逆推生成路径。
逆推的方法是,对于第n级的选中的数x,看第n-1级中的|x+n|或|x-n|那个数。
比如要找的数是4,在上面那个树中第三级有它,我们就算4+3和4-3,也就是7和1。第二级中有|1|,我们就选中第二级的1。然后算1+2,1-2,得3和-1。第1级中有|-1|,我们就选中第一级的-1(尽管我们只记录了绝对值,负值依然是存在于这一级里面的)。然后路径就出来了。
(0,-1)->(-1,1)->(1,4)
巴扎黑2017-04-17 12:07:43
可能是我没明白,不过我觉得这个可以直接暴搜。
第一次假设一直往右走,然后用一个序列将其中的坐标全部存起来,到终点之后你想输出路径;
第二次假设前n-1步往右走,最后一步往左走,终点后坐标逆向输出;
第三次假设前n-2步往右走,第n-1步往左走,第n-2步往右走;
第四次假设前n-2步往右走,最后两步往左走;
……
以此类推,一直到最后一轮都是往左走就可以了。
就是每一步都有两个方向,全部跑一遍就好了。方案一共有2^n种。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
PHP中文网2017-04-17 12:07:43
上面有人说了, 查找状态 表示出来 是一个满二叉树. 那么数据结构就很明显了, 一个vector
. 可以参考堆 的实现, 第一级 index为0, 第二级为1, 2... 查找显然是一个bsf, 找到后 向上很容易 逆推出路径(堆中的parent函数). over
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
|
结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
PHPz2017-04-17 12:07:43
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
我不会C++,你凑合看吧,大概就这意思。