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

x33g5p2x  于2022-03-11 转载在 其他  
字(1.6k)|赞(0)|评价(0)|浏览(322)

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

另类加法

题目链接

题目描述

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

测试样例

  1. 1,2
  2. 返回:3

解题思路

不使用算数运算符,故需要通过位运算计算:

两个数字相加:

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

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

比如:1+3

二进制:00000001

二进制:00000011

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

00000010

00000010

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

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

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

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

  1. class UnusualAdd {
  2. public:
  3. int addAB(int A, int B) {
  4. // write code here
  5. //两个有一个为0就结束
  6. if(A == 0)
  7. return B;
  8. if(B == 0)
  9. return A;
  10. int a = A ^ B;//相加后二进制的取值(不考虑进位)
  11. int b = (A & B) << 1;
  12. return addAB(a,b);
  13. }
  14. };

走方格的方案数

题目链接

题目描述

请计算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)

解题代码

  1. //m行n列的二维数组
  2. #include<iostream>
  3. #include<vector>
  4. using namespace std;
  5. int main()
  6. {
  7. int n,m;
  8. while(cin>>n>>m)
  9. {
  10. //只能往右和往下走
  11. //动规问题:F(i,j):到达i,j位置的走法数
  12. //状态转移方程:F(i,j) = F(i-1,j)+F(i,j-1)
  13. //初始状态:F(0,0) = 0,F(0,i) = 1,(i= 1.2.3....n) F(i,0) = 1 (i= 1.2.3....m)
  14. vector< vector<int> > vv;
  15. vv.resize(m+1);
  16. //初始化
  17. for(int i = 0;i<m+1;i++)
  18. {
  19. vv[i].resize(n+1);
  20. vv[i][0] = 1;
  21. }
  22. for(int i = 0;i<n+1;i++)
  23. {
  24. vv[0][i] = 1;
  25. }
  26. vv[0][0] = 0;
  27. for(int i = 1;i <= m;i++)
  28. {
  29. for(int j = 1;j <= n;j++)
  30. {
  31. vv[i][j] = vv[i-1][j]+vv[i][j-1];
  32. }
  33. }
  34. cout<< vv[m][n]<<endl;
  35. }
  36. return 0;
  37. }

递归解题代码

  1. #include<iostream>
  2. using namespace std;
  3. int pathnum(int n,int m)
  4. {
  5. if(n == 0 || m == 0)
  6. return 1;
  7. return pathnum(m-1,n) + pathnum(m,n-1);
  8. }
  9. int main()
  10. {
  11. int n,m;
  12. while(cin>>n>>m)
  13. {
  14. cout<<pathnum(n,m)<<endl;
  15. }
  16. return 0;
  17. }

相关文章