java笔试之计算n x m的棋盘格子

请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

方法一使用递归，出口条件：如果一直向右或者一直向下，必然只有一种方法；

递归方法：在(n,m)处，要么是从(n-1,m)往右，要么是从(n,m-1)往下。

方法二使用循环遍历，原理和方法一类似，不过要注意数组的边界问题，数组初始化时，应当为(n+1)*(m+1)。

package test;

import java.util.Scanner;

public class exam05 {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {

            int n = scanner.nextInt();

            int m = scanner.nextInt();

            // System.out.println(get1(n, m));

            System.out.println(get2(n + 1, m + 1));

        }

    }

    private static int get1(int n, int m) {

        // 方法1:递归

        int sum = 0;

        if (n > 0 && m > 0)

            return sum = get1(n - 1, m) + get1(n, m - 1);

        else {

            return 1;

        }

    }

    private static int get2(int n, int m) {

        // 方法2:循环遍历

        int[][] a = new int[n][m];

        for (int i = 0; i < n; i++) {

            a[i][0] = 1;

        }

        for (int j = 0; j < m; j++) {

            a[0][j] = 1;

        }

        for (int i = 0; i < n - 1; i++) {

            for (int j = 0; j < m - 1; j++) {

                // 该点必然经过所有左侧点和上侧点经过的路

                a[i + 1][j + 1] = a[i + 1][j] + a[i][j + 1];

            }

        }

        return a[n - 1][m - 1];

    }

}

巴特西

java笔试之计算n x m的棋盘格子

最新文章

热门文章