笔试强训每日一题(十二)

另类加法

题目链接

题目描述

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

测试样例

1,2
返回：3

解题思路

不使用算数运算符，故需要通过位运算计算：

两个数字相加：

1、求取数字相加后当前二进制位的取值(不考虑进位)

2、求取数字相加后进位的数值

比如：1+3

二进制：00000001

二进制：00000011

数字相加后当前二进制位的取值(不考虑进位)：00000010，相加后进位的数值：00000010，再将这两个相加：

00000010

00000010

数字相加后当前二进制位的取值(不考虑进位)：00000000，相加后进位的数值：00000100

直到两个值有一个为0时就结束

相加后二进制的取值：异或，相同则为0，不同则为1

相加后进位的数值：相与并左移，全为1时才为1，进位是进到上一个高位，左移一位即可到那个高位

class UnusualAdd {
public:
    int addAB(int A, int B) {
        // write code here
        //两个有一个为0就结束
        if(A == 0)
            return B;
        if(B == 0)
        	return A;
    	int a = A ^ B;//相加后二进制的取值(不考虑进位)
    	int b = (A & B) << 1;
    	return addAB(a,b);
    }
};

走方格的方案数

题目链接

题目描述

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

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

本题含有多组样例输入。

数据范围： 1 <= n,m <= 8

输入描述

每组样例输入两个正整数n和m，用空格隔开。(1≤n,m≤8)

输出描述

每组样例输出一行结果

解题思路

只能往右和往下走
动规问题：F(i,j):到达i,j位置的走法数
状态转移方程：F(i,j) = F(i-1,j)+F(i,j-1)
初始状态:F(0,0) = 0,F(0,i) = 1,(i= 1.2.3…n) F(i,0) = 1 (i= 1.2.3…m)

解题代码

//m行n列的二维数组
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        //只能往右和往下走
        //动规问题：F(i,j):到达i,j位置的走法数
        //状态转移方程：F(i,j) = F(i-1,j)+F(i,j-1)
        //初始状态:F(0,0) = 0,F(0,i) = 1,(i= 1.2.3....n) F(i,0) = 1 (i= 1.2.3....m)
        vector< vector<int> > vv;
        vv.resize(m+1);
        //初始化
        for(int i = 0;i<m+1;i++)
        {
            vv[i].resize(n+1);
            vv[i][0] = 1;
        }
        for(int i = 0;i<n+1;i++)
        {
            vv[0][i] = 1;
        }
        vv[0][0] = 0;
        for(int i = 1;i <= m;i++)
        {
            for(int j = 1;j <= n;j++)
            {
                vv[i][j] = vv[i-1][j]+vv[i][j-1];
            }
        }
        cout<< vv[m][n]<<endl;
    }
    return 0;
}

递归解题代码

#include<iostream>
using namespace std;

int pathnum(int n,int m)
{
    if(n == 0 || m == 0)
    	return 1;
    return pathnum(m-1,n) + pathnum(m,n-1);
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        cout<<pathnum(n,m)<<endl;
    }
    return 0;
}