院校机试刷题第四天：1911反转公约数、1702十六进制不进位加法

一、1911反转公约数

1.题目描述

2.解题思路

两个关键点：1.如何把数字反转，2.如何求最大公约数。

反转：用字符串形式存储，定义一个新的字符串倒序存储反转之后的字符串，将字符串按位转换位数字。

求最大公约数：欧几里得算法：

1. 给定两个整数 a 和 b，其中 a≥b。

2. 计算 amodb，得到余数 r。

3. 将 a 替换为 b，将 b 替换为 r。

4. 重复步骤2和3，直到 b 为0。

5. 此时的 a 就是最大公约数。

int gcd(int a, int b) {while (b != 0) {int r = a % b;a = b;b = r;}return a;
}

3.代码

#include <iostream>
#include <algorithm>
using namespace std;int strToNum(string str) {int num = 0;int length = str.length();int cnt = 1;for(int i = length - 1; i >= 0; i--) {num += (str[i] - '0') * cnt;cnt *= 10;}return num;
}int gcd(int a, int b) {while(b != 0) {int r = a % b;a = b;b = r;}return a;
}int main() {string str1, str2;cin >> str1 >> str2;//反转字符串reverse(str1.begin(), str1.end());reverse(str2.begin(), str2.end());//转为数字int num1 = strToNum(str1);int num2 = strToNum(str2);//求最大公约数if(num1 < num2) {swap(num1, num2);}int result = gcd(num1, num2);cout << result;return 0;
}

二、1702十六进制不进位加法

1.题目描述

2.解题思路

解题关键：1.如何实现十六进制加法，2.如何实现不进位

想要实现不进位的十六进制加法只能一位一位算，不能先转为十进制计算，再转回十六进制。

不进位的话结果的长度就是最长的那个计算数的长度，从较小的计算数开始逐位相加，遇到需要进位的结果就将其减去16，再将大于9的数字转为字母存放起来。

因为是逐位计算，所以用字符串存储数字显然要更加方便。

3.代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;//字母输入统一为大写
string tongYi(string str) {for(int i = 0; i < str.length(); i++) {if(str[i] >= 'a' && str[i] <= 'z') {str[i] -= 32;}}return str;
}int main() {string str1, str2;while(cin >> str1 >> str2) {//统一输入为大写str1 = tongYi(str1);str2 = tongYi(str2);int length = max(str1.length(), str2.length());str1 = string(length - str1.length(), '0') + str1;str2 = string(length - str2.length(), '0') + str2;string str3(length, 0);for(int i = length - 1; i >= 0; i--) {int temp1 = (str1[i] >= 'A') ? (str1[i] - 'A' + 10) : (str1[i] - '0');int temp2 = (str2[i] >= 'A') ? (str2[i] - 'A' + 10) : (str2[i] - '0');int tempResult = temp1 + temp2;//去除进位if(tempResult >= 16) {tempResult -= 16;}if(tempResult >= 10) {str3[i] = tempResult - 10 + 'A';}else {str3[i] = tempResult + '0';}}//输出for(int i = 0; i < str3.length(); i++) {cout << str3[i];}cout << endl;}return 0;
}