c++ - 一道简单到无法下手的笔试题

Question

晚上参加某公司的笔试题遇到如下一道题，本来打算在网上搜索，无奈全是英文，所以我将大概意思写出，各位有知道是什么问题的可以告诉我，比如说这是道费波那奇数列，我想了半天没想出这道题该如何求解。
题目如下：
给你一个数比如 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
………………………………………………………………………………

Answer 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)

Answer 2

可能是我没明白，不过我觉得这个可以直接暴搜。
第一次假设一直往右走，然后用一个序列将其中的坐标全部存起来，到终点之后你想输出路径；
第二次假设前n-1步往右走，最后一步往左走，终点后坐标逆向输出；
第三次假设前n-2步往右走，第n-1步往左走，第n-2步往右走；
第四次假设前n-2步往右走，最后两步往左走；
……
以此类推，一直到最后一轮都是往左走就可以了。
就是每一步都有两个方向，全部跑一遍就好了。方案一共有2^n种。
代码如下：

#include<stdio.h>
#define N 20
int 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;
}

Answer 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)

Answer 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++，你凑合看吧，大概就这意思。