象棋中马的跳法

【题目】

请同学们自行搜索或者想象一个象棋的棋盘，然后把整个棋盘放入第一象限，棋盘的最左下 角是(0,0)位置。

那么整个棋盘就是横坐标上9条线、纵坐标上10条线的一个区域。

给你三个 参数，x，y，k，返回如果“马”从(0,0)位置出发，必须走k步，最后落在(x,y)上的方法数 有多少种？

 

暴力递归

思路：

定义一个8*9的棋盘，然后边界限制，不能跳的超出棋盘

当step 步数到0的时候，i，j 的位置也到达了 目标位置 a，b的时候，表示为一种有效方法

然后调递归不断的尝试，一共8个位置。

 

int process(int i, int j, int step,int a,int b)
{
    if (i < 0 || i > 8 || j < 0 || j > 9)
    {
        return 0;
    }
    if (step == 0)
    {
        return (i == a && j == b) ? 1 : 0;
    }
    return process(i - 1, j - 2, step - 1, a, b)
        + process(i - 2, j - 1, step - 1, a, b)
        + process(i - 2, j + 1, step - 1, a, b)
        + process(i - 1, j + 2, step - 1, a, b)
        + process(i + 1, j - 2, step - 1, a, b)
        + process(i + 2, j - 1, step - 1, a, b)
        + process(i + 2, j + 1, step - 1, a, b)
        + process(i + 1, j + 2, step - 1, a, b);
}

 

机器人达到指定位置方法数

【题目】 假设有排成一行的 N 个位置，记为 1~N，N 一定大于或等于 2。开始时机器人在其中的 M 位 置上(M 一定是 1~N 中的一个)，机器人可以往左走或者往右走，如果机器人来到 1 位置， 那 么下一步只能往右来到 2 位置;如果机器人来到 N 位置，那么下一步只能往左来到 N-1 位置。 规定机器人必须走 K 步，最终能来到 P 位置(P 也一定是 1~N 中的一个)的方法有多少种。给 定四个参数 N、M、K、P，返回方法数。

【举例】 N=5,M=2,K=3,P=3 上面的参数代表所有位置为 1 2 3 4 5。机器人最开始在 2 位置上，必须经过 3 步，最后到 达 3 位置。走的方法只有如下 3 种: 1)从2到1，从1到2，从2到3 2)从2到3，从3到2，从2到3 3)从2到3，从3到4，从4到3 所以返回方法数 3。 N=3,M=1,K=3,P=3 上面的参数代表所有位置为 1 2 3。机器人最开始在 1 位置上，必须经过 3 步，最后到达 3 位置。怎么走也不可能，所以返回方法数 0。

 

暴力递归

int walk(int n, int cur, int rest, int p)
{
    if (rest == 0)
    {
        return cur == p ? 1 : 0;
    }
    if (cur == 1)
    {
        return walk(n, 2, rest - 1, p);
    }
    if (cur == n)
    {
        return walk(n, n - 1, rest - 1, p);
    }
    return walk(n, n + 1, rest - 1, p) + walk(n, n - 1, rest - 1, p);
}

int f(int n, int start, int end, int k, int p)
{
    if (n < 2 || k<1 || start>n || p<1 || p>n)
    {
        return 0;
    }
    return walk(n, start, k, p);
}

 

 

换钱的最少货币数

【题目】 给定数组 arr，arr 中所有的值都为正数且不重复。每个值代表一种面值的货币，每种面值 的货币可以使用任意张，再给定一个整数 aim，代表要找的钱数，求组成 aim 的最少货币 数。

【举例】 arr=[5,2,3]，aim=20。 4 张 5 元可以组成 20 元，其他的找钱方案都要使用更多张的货币，所以返回 4。 arr=[5,2,3]，aim=0。 不用任何货币就可以组成 0 元，返回 0。 arr=[3,5]，aim=2。 根本无法组成 2 元，钱不能找开的情况下默认返回-1。

 

暴力递归

int process(int array[], int index, int aim,int len)
{
    if (index == len)
    {
        return aim == 0 ? 1 : 0;
    }
    int ways = 0;
    for (int zhang = 0; zhang*array[index] <= aim; zhang++)
    {
        ways += process(array, index + 1, aim - zhang * array[index],len);
    }
    return ways;
}

 

 

Bob的生存概率

【题目】 给定五个参数n,m,i,j,k。表示在一个N*M的区域，Bob处在(i,j)点，每次Bob等概率的向上、 下、左、右四个方向移动一步，Bob必须走K步。如果走完之后，Bob还停留在这个区域上， 就算Bob存活，否则就算Bob死亡。请求解Bob的生存概率，返回字符串表示分数的方式。

 

暴力递归

int process(int i, int j, int n, int m, int k)
{
    if (n < 0 || i == n || m < 0 || j == m)
    {
        return 0;
    }
    if (k == 0)
    {
        return 1;
    }
    int live = process(i, j, n - 1, m, k - 1)
        + process(i, j, n + 1, m, k - 1)
        + process(i, j, n, m + 1, k - 1)
        + process(i, j, n, m - 1, k - 1);
    return live;
}