検索

ホームページ  >  に質問  >  本文

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

晚上参加某公司的笔试题遇到如下一道题,本来打算在网上搜索,无奈全是英文,所以我将大概意思写出,各位有知道是什么问题的可以告诉我,比如说这是道费波那奇数列,我想了半天没想出这道题该如何求解。
题目如下:
给你一个数比如 6,从0开始,第n步可以走n个距离
比如 第一步(0-->1) 走了1步

1

2

3

4

5

6

7

8

<code>第二步(1-->3) 走了2步

第三步(3-->6)  走了3步

 

当然你也可以往负数那边走

比如4的话

(0,-1) (-1,1) (1,4)

走1步      走2步    走三步

</code>

程序C/C++ 实现不能使用任何stl,所有实现自己写,要求给定数字N,求出其所走序列。
表达能力有限,如果有疑问在此留言。
楼下几个说简单的,你不妨写出代码,多试几个数字,就知道这个程序有多简单了。
2015.9.21 19:59
………………………………………………………………………………

ringa_leeringa_lee2808日前770

全員に返信(4)返信します

  • PHP中文网

    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)

    返事
    0
  • 巴扎黑

    巴扎黑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

    <code>#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;

    }

    </code>

    返事
    0
  • PHP中文网

    PHP中文网2017-04-17 12:07:43

    上面有人说了, 查找状态 表示出来 是一个满二叉树. 那么数据结构就很明显了, 一个vector. 可以参考堆 的实现, 第一级 index为0, 第二级为1, 2... 查找显然是一个bsf, 找到后 向上很容易 逆推出路径(堆中的parent函数). over

    Challenge accepted.

    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

    <code>#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;

    }

    </code>

    结果:

    1

    2

    3

    4

    5

    6

    7

    8

    9

    10

    11

    12

    13

    14

    15

    <code>(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)</code>

    返事
    0
  • PHPz

    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

    <code>//斐波那契数列

     

    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)

    }

    </code>

    我不会C++,你凑合看吧,大概就这意思。

    返事
    0
  • キャンセル返事