Java题目训练——另类加法和走方格的方案数

深藏阁楼爱情的钟 2023-09-30 20:38 10阅读 0赞

### 一、另类加法 ###

1.  题目描述：

给定两个int A和B。编写一个函数返回A+B的值，但不得使用+或其他算数运算符。

测试样例：

> 1,2  
> 返回：3

**题目详解：**

利用与运算符（&）和异或运算符（^）完成，于运算找到需要进位的位，异或运算相当于做加法，每次再加上进位，直至没有进位。

import java.util.*;
     
    public class UnusualAdd {
        public int addAB(int A, int B) {
            // write code here
            int xor,and;
            while(B != 0){
                xor = A ^ B;
                and = A & B;
                A = xor;
                B = and << 1;
            }
            return A;
        }
    }

### 二、走方格的方案数 ###

1.  题目描述：

请计算n\*m的棋盘格子（n为横向的格子数，m为竖向的格子数）从棋盘左上角出发沿着边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。

注：沿棋盘格之间的边缘线行走

1.  数据范围：

1.  输入描述：输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

1.  输出描述：输出一行结果

补充说明：

> 示例1  
> 输入：  
> 2 2  
> 输出：  
> 6

**题目详解：**

动态规划法，每一步都等于上一步的可能性相加，上一步也就是当前格子的左格子和上格子，在此之前需要先将格子初始化好，需要添加额外的一行和一列用来存放初始值，从格子左上开始，遍历至右下即所有可能性。

import java.util.Scanner;
     
    public class Main {
        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int[][] grid=new int[n+1][m+1];
     
            for (int i = 0; i < n + 1; i++) {
                grid[i][0] = 1;
            }
     
            for (int i = 0; i < m + 1; i++) {
                grid[0][i] = 1;
            }
     
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    grid[i][j] = grid[i-1][j]+grid[i][j-1];
                }
            }
     
            System.out.println(grid[n][m]);
        }
    }

如有建议或想法，欢迎一起学习讨论~