问题描述
晚上参加某公司的笔试题遇到如下一道题，本来打算在网上搜索，无奈全是英文，所以我将大概意思写出，各位有知道是什么问题的可以告诉我，比如说这是道费波那奇数列，我想了半天没想出这道题该如何求解。题目如下：给你一个数比如 6，从0开始，第n步可以走n个距离比如 第一步（0-->1) 走了1步
第二步（1-->3) 走了2步第三步（3-->6) 走了3步当然你也可以往负数那边走比如4的话（0，-1） （-1，1） （1，4）走1步 走2步 走三步
程序C/C++ 实现不能使用任何stl，所有实现自己写，要求给定数字N，求出其所走序列。表达能力有限，如果有疑问在此留言。楼下几个说简单的，你不妨写出代码，多试几个数字，就知道这个程序有多简单了。2015.9.21 19：59………………………………………………………………………………
问题解答
回答1：我想的解法效率有点低，但是至少是思路是可行的。我不会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)
回答2：可能是我没明白，不过我觉得这个可以直接暴搜。第一次假设一直往右走，然后用一个序列将其中的坐标全部存起来，到终点之后你想输出路径；第二次假设前n-1步往右走，最后一步往左走，终点后坐标逆向输出；第三次假设前n-2步往右走，第n-1步往左走，第n-2步往右走；第四次假设前n-2步往右走，最后两步往左走；……以此类推，一直到最后一轮都是往左走就可以了。就是每一步都有两个方向，全部跑一遍就好了。方案一共有2^n种。代码如下：
#include<stdio.h>#define N 20int path[N];void dfs(int k,int n){ if(k<=n)//走到第k步 {path[k] = path[k-1]+k;dfs(k+1,n);path[k] = path[k-1]-k;dfs(k+1,n); } else//走完n步 {for(int i=0; i<n; i++){ printf('(%d,%d)',path[i],path[i+1]);}printf('n');return ; } return ;}int main(){ int n; scanf('%d',&n); path[0]=0; dfs(1,n); return 0;}回答3：
上面有人说了, 查找状态 表示出来 是一个满二叉树. 那么数据结构就很明显了, 一个vector. 可以参考堆 的实现, 第一级 index为0, 第二级为1, 2... 查找显然是一个bsf, 找到后 向上很容易 逆推出路径(堆中的parent函数). over
Challenge accepted.#include <stdio.h>#include <stdlib.h>static int ensureCapacity(int **arr, int *capacity, int size){ if (size <= *capacity)return 0; *arr = (int*)realloc(*arr, (*capacity << 1) * sizeof(int)); if (*arr)*capacity <<= 1; ensureCapacity(arr, capacity, size); return *arr == NULL;}static int lChild(int n){ return (n << 1) + 1;}static int rChild(int n){ return (n << 1) + 2;}static int parent(int n){ return n == 0 ? n : (n - 1) >> 1;}static void printPath(int *arr, int i){ int p; if (i == 0)return; p = parent(i); printPath(arr, p); printf('(%d, %d)n', arr[p], arr[i]); }int searchPath(int N){ int *arr; int capacity, i, step, left, right, rc; capacity = 64; rc = 0; if ((arr = (int*)malloc(capacity * sizeof(int))) == NULL)goto err; left = right = step = 0; arr[0] = 0; while (1) {step++;if (ensureCapacity(&arr, &capacity, rChild(right) + 1)) goto err;for (i = left; i <= right; i++) { if (arr[i] == N) {printPath(arr, i);goto done; } arr[lChild(i)] = arr[i] - step; arr[rChild(i)] = arr[i] + step;}left = lChild(left);right = rChild(right); }err: rc = -1;done: if (arr)free(arr); return -1;}int main(void) { searchPath(100); return 0;}
结果:
(0, -1)(-1, -3)(-3, -6)(-6, -10)(-10, -5)(-5, 1)(1, 8)(8, 16)(16, 25)(25, 35)(35, 46)(46, 58)(58, 71)(71, 85)(85, 100)回答4：
//斐波那契数列int a = 0;//开始int b = 0;int c = 0;a = a + 1;//第一步b = c;//第一步的起点c = b + a;//第一步的终点//输出（b,c）a = a + 1;//第二步b = c;//第二步的起点c = b + a;//第二步的终点//输出（b,c）//第N步，重复执行上面的，这有什么困难的吗？while(a <= N){ a = a + 1;//第a步 b = c;//第a步的起点 c = b + a;//第a步的终点 //输出（b,c）}
我不会C++，你凑合看吧，大概就这意思。
