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

The solution I think of is a bit inefficient, but at least the idea is feasible.
I don’t know C/C++, so I’ll just write my thoughts to you.

You have 2 states for each step, forward or backward. You can draw a tree, which looks like this.

The nth level represents the possible location of the nth step. You will find that the numbers on the left and right sides of each level are opposite. For example, the third level, -3,1 and -1,3. So for the third level, you only need to save 1 and 3.

Since level n can take n-1 steps, all situations at level n are plus or minus all situations at level n-1 plus or minus n.
For example, the third level, since the second level has 1 and 3, the third level is 1+3, 1-3, 3+3, 3-3, which is 4, -2, 6, 0, all The situation is -6, -4, -2, 0, 2, 4, 6. But we only store the absolute values, which are 0, 2, 4, and 6.

You just count down one level at a time, and see if the absolute value of the result is in it at each level. If it is there, it means that the result is found, and then the path is generated by working backwards.
The method of reverse reasoning is that for the selected number x at the nth level, look at the number |x+n| or |x-n| in the n-1th level.
For example, the number we are looking for is 4, and it is found at the third level of the tree above. We calculate 4+3 and 4-3, which is 7 and 1. If there is |1| in the second level, we select 1 in the second level. Then calculate 1+2, 1-2, and get 3 and -1. There is |-1| in level 1, so we select -1 in level 1 (although we only record the absolute value, negative values ​​still exist in this level). Then the path came out.
(0,-1)->(-1,1)->(1,4)

Answer 2

Maybe I don’t understand it, but I think this can be searched directly.
For the first time, assume that you go all the way to the right, and then use a sequence to store all the coordinates. After reaching the end point, you want to output the path;
For the second time, assume that you go right for the first n-1 steps and the last step Go left, and the coordinates after the end point are output in reverse;
The third time assumes that the first n-2 steps go to the right, the n-1 step goes to the left, and the n-2 step goes to the right;
the fourth time Assume that the first n-2 steps go to the right, and the last two steps go to the left;
...
and so on, until the last round, just go left.
Every step has two directions, just run them all. There are 2^n options in total.
The code is as follows:

#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

Someone said above that the search state is represented by a full binary tree. Then the data structure is obvious, a vector. You can refer to the implementation of the heap. The first level index is 0, and the second level is 1, 2 ... The search is obviously a bsf. After finding it, it is easy to reverse the path (parent function in the heap). 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;
}

Result:

(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）
}

I don’t know C++, so you just have to read it, that’s about it.