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