【NOI-题解】1108 - 正整数N转换成一个二进制数1290 - 二进制转换十进制1386 - 小丽找半个回文数1405

文章目录

一、前言
二、问题
- 问题：1108 - 正整数N转换成一个二进制数
- 问题：1290 - 二进制转换十进制
- 问题：1386 - 小丽找半个回文数
- 问题：1405 - 小丽找潜在的素数？
三、感谢

一、前言

本章节主要对进制转换的题目进行讲解，包括《1108 - 正整数N转换成一个二进制数》《1290 - 二进制转换十进制》《1386 - 小丽找半个回文数》《1386 - 小丽找半个回文数》题目。

二、问题

问题：1108 - 正整数N转换成一个二进制数

类型：进制转换

题目描述：

输入一个不大于 32767 的整数 n ，将它转换成一个二进制数。

输入：

输入只有一行，包括一个整数（0 ≤ n ≤ 32767)。

输出：

输出只有一行。

样例1：

输入：

输出：

样例2：

输入：

输出：

在这里插入图片描述

1.分析问题

已知：一个不大于 32767 的整数 n。
未知：将它转换成一个二进制数。
关系：进制转换

2.定义变量

n; 用于存储待转换的整数。
v; 用于存储转换后的二进制位，每个元素代表一位，0 或 1。

	//二、定义变量（已知、未知、关系） int n;vector<int> v;

3.输入数据

从标准输入读取一个整数。

	//三、输入已知cin>>n;

4.数据计算

使用while(n)循环，当n不为0时执行循环体。
取n的当前最低位（n % 2），将其添加到vector的末尾。
将n右移一位，相当于除以2并向下取整，继续处理下一位。

//四、根据关系计算while(n){v.push_back(n%2);n/=2;}

5.输出结果

在转换完成后，先检查vector是否为空。若为空，则直接输出0。
否则，从vector的末尾开始遍历到开头，逐个输出vector中的元素，即得到了该整数的二进制表示。

//五、输出未知 if(v.empty()){cout<<0;}else{for(int i=v.size()-1;i>=0;i--){cout<<v[i];}}return 0;

完整代码如下：

#include<bits/stdc++.h> // 包含通用头文件，提供所有常用的标准库功能
using namespace std;    // 使用标准命名空间std，简化代码中的库函数调用int main() {            // 程序入口点// 一、分析问题// 目标：将一个不大于32767的十进制整数转换为二进制表示// 二、定义变量int n;               // 存储用户输入的整数vector<int> v;       // 使用vector来存储整数的二进制位，每个元素代表一位（0或1）// 三、输入cin >> n;            // 从标准输入读取一个整数n// 四、转换过程while(n) {           // 当n非零时执行循环v.push_back(n % 2); // 取n的当前最低位（n除以2的余数），加入到vector末尾n /= 2;           // n右移一位，即n除以2并向下取整，继续处理下一位}// 五、输出// 检查vector是否为空（理论上这里可以直接输出"0"，因为当n为0时，循环不会执行，直接进入此逻辑）if(v.empty()) {cout << 0;       // 如果vector为空（即输入的n为0），直接输出"0"} else {// 遍历vector，从最后一个元素开始向前遍历，输出二进制位for(int i = v.size() - 1; i >= 0; i--) {cout << v[i]; // 输出当前位}}// 结束程序return 0;            // 主函数正常结束，返回0
}

问题：1290 - 二进制转换十进制

类型：进制转换、字符串

题目描述：

请将一个 25 位以内的 2 进制正整数转换为 10 进制！

输入：

一个 25 位以内的二进制正整数。

输出：

该数对应的十进制。

样例：

输入：

111111111111111111111111

输出：

16777215

在这里插入图片描述

1.分析问题

已知：一个 25 位以内的 2 进制正整数;
未知：转换为 10 进制;
关系：二进制转十进制。

2.定义变量

s 用于存储输入的二进制。
res 初始化结果变量，用于存放转换后的十进制数值。

	//二、定义变量（已知、未知、关系）string s;int res=0;

3.输入数据

从标准输入读取一个二进制字符串。

	//三、输入已知cin>>s;

4.数据计算

使用一个循环遍历输入字符串s的每一个字符（从末位到首位）。
初始化一个变量t用于记录当前位的权重，初始为1（即2^0）。
将当前字符（‘0’或’1’）减去字符’0’得到其对应的整数值（0或1），然后乘以当前位的权重t，累加到结果res中。
在每次迭代后，将权重t乘以2，以便处理下一位的二进制位。

	//四、根据关系计算int t=1;for(int i=s.size()-1;i>=0;i--){res+=(s[i]-'0')*t;t*=2;}

5.输出结果

输出转换后的十进制数值。

//五、输出未知 cout<<res;

完整代码如下：

#include <bits/stdc++.h> // 包含头文件，提供了所有常用的标准库功能
using namespace std;    // 使用标准命名空间std，简化代码中的库函数调用int main() {            // 程序入口点// 一、问题分析// 已知条件：一个长度不超过25位的二进制正整数// 目标：将此二进制数转换为十进制数// 二、变量定义string s;           // 存储二进制字符串int res = 0;        // 初始化转换结果为0// 三、输入二进制cin >> s;           // 从标准输入读取一个二进制// 四、二进制转十进制计算int t = 1;          // 初始化当前位的权重为2^0 = 1for(int i = s.size() - 1; i >= 0; i--) { // 从字符串末位开始遍历到首部// 将字符数字（'0'或'1'）转换为其对应的整数值（0或1），然后乘以其权重t，累加到res中res += (s[i] - '0') * t;// 每处理完一位，权重t翻倍，相当于下一位的权重（2^n）t *= 2;}// 五、输出十进制结果cout << res;         // 输出转换得到的十进制数return 0;            // 主函数正常结束，返回0
}

问题：1386 - 小丽找半个回文数

类型：进制转换

题目描述：

小丽同学在编程中学到了回文数的概念，如果一个数正过来读和反过来读是同一个数，那么这个数就是回文数；比如：2、5、8、66、121、686、12321 都是回文数，小丽发现，这样的数不算多。

于是小丽有个想法，如果这个数不是回文数，但这个数在 2 进制或者 16 进制下是回文数，就算这个整数是半个回文数，比如 417 并不是回文，但 417 对应的 16 进制数是 1A1 是回文数，因此 417 算半个回文数。

请你编程帮助小丽找符合条件的半个回文数。

输入：

第一行是一个整数 n（5≤n≤100）；第二行是 n 个整数（这些整数都是 [0,10^8] 之间的整数）；

输出：

所有符合条件的半个回文数，每行一个。

样例：

输入：

5
121 417 27 100 21

输出：

417
27
21

在这里插入图片描述

1.分析问题

已知：n个整数；
未知：找符合条件的半个回文数。
关系：这个数不是回文数，但这个数在 2 进制或者 16 进制下是回文数，就算这个整数是半个回文数

2.定义变量

	int n;string s,binary,hexa;

3.输入数据

程序接收用户输入的整数数量n。

	//三、输入已知cin>>n;

随后，对于每一个输入的整数s，程序先检查它是否为回文数，如果是则跳过（因为它不符合“半个回文数”的定义）。

	for(int i=0;i<n;i++){cin>>s;}

接着，将s分别转换为二进制和十六进制形式，并检查这两种形式是否为回文。只要其中任一是回文，就输出原始的整数s。

		if(checkHW(s)) continue;//四、根据关系计算binary=decbin(s);hexa=dechex(s);//五、输出未知 if(checkHW(binary)||checkHW(hexa)){cout<<s<<endl;}

4.数据计算

此函数通过创建字符串的逆序副本并比较两者是否相等来判断给定字符串是否为回文。

bool checkHW(string t){string re=t;reverse(re.begin(),re.end());return t==re;
}

将输入的十进制字符串转换为二进制。

string decbin(string dec){int ndec=0,t;char c;string bin;for(int i=0;i<dec.size();i++){ndec=ndec*10+(dec[i]-'0');}while(ndec){t=ndec%2;c=t+'0';bin=c+bin;ndec/=2;}return bin;
}

将输入的十进制字符串转换为十六进制字符串


string dechex(string  dec){int ndec=0,t;char c;string hex;for(int i=0;i<dec.size();i++){ndec=ndec*10+(dec[i]-'0');}while(ndec){t=ndec%16;if(t<=9){c=t+'0';}else{c=t-10+'A';}hex=c+hex;ndec/=16;}return hex;
}

5.输出结果

//五、输出未知 if(checkHW(binary)||checkHW(hexa)){cout<<s<<endl;}

完整代码如下：

#include<bits/stdc++.h> // 包含常用头文件，简化代码，但非标准，建议具体指定所需头文件
using namespace std; // 使用std命名空间，允许直接使用std内的函数和对象，但可能引起命名冲突// 检查字符串是否为回文
bool checkHW(string t){string re = t; // 复制字符串treverse(re.begin(), re.end()); // 反转字符串return t == re; // 比较原字符串与反转后的字符串是否相等
}// 十进制字符串转二进制字符串
string decbin(string dec){int ndec = 0; // 初始化十进制数值for(int i=0; i<dec.size(); i++){ // 遍历输入字符串ndec = ndec * 10 + (dec[i] - '0'); // 将字符数字转换为整数并累加}string bin; // 初始化二进制字符串while(ndec){ // 当十进制数不为0时bin = (ndec % 2 ? '1' : '0') + bin; // 将余数添加到二进制字符串前部ndec /= 2; // 整除2进行下一轮}return bin; // 返回二进制字符串
}// 十进制字符串转十六进制字符串
string dechex(string dec){int ndec = 0; // 初始化十进制数值for(int i=0; i<dec.size(); i++){ // 遍历输入字符串ndec = ndec * 10 + (dec[i] - '0'); // 将字符数字转换为整数并累加}string hex; // 初始化十六进制字符串const char* digits = "0123456789ABCDEF"; // 十六进制字符表while(ndec){ // 当十进制数不为0时hex = digits[ndec % 16] + hex; // 添加对应的十六进制字符到字符串前部ndec /= 16; // 整除16进行下一轮}return hex; // 返回十六进制字符串
}int main(){// 主函数开始int n; // 定义整数n存储输入的整数数量cin >> n; // 读取整数nfor(int i=0; i<n; i++){ // 循环处理n个整数string s; // 存储当前输入的整数字符串cin >> s; // 读取一个整数// 如果该整数本身就是回文，则跳过if(checkHW(s)) continue;// 转换并检查二进制和十六进制形式string binary = decbin(s); string hexa = dechex(s);// 如果二进制或十六进制形式是回文，则输出原整数if(checkHW(binary) || checkHW(hexa)){cout << s << endl; // 输出整数}}// 主函数结束return 0; // 程序正常退出
}

问题：1405 - 小丽找潜在的素数？

类型：进制转换

题目描述：

小丽同学在编程中学到了二进制数的概念，她发现，有些二进制数，如果转为 10 进制，就是素数，小丽把这些数称为潜在的素数；比如 2 进制 1101011，转为 10 进制后为 107 ，就是素数。

请编程帮小丽找出，哪些二进制数转为 10 进制后，是素数，计算出这样的数有多少个？

输入：

第一行是一个整数（10≤n≤100）。

接下来 n 行，每行是一个 30 位以内的 2 进制数

输出：

一个整数代表所有转为 10 进制后是素数的 2 进制数的个数。

样例：

输入：

输出：

在这里插入图片描述

1.分析问题

已知：n个 30 位以内的 2 进制数；
未知：输出所有转为 10 进制后是素数的 2 进制数的个数。
关系：进制转换。

2.定义变量

	//二、定义变量（已知、未知、关系）int n,c=0,t;string s;

3.输入数据

首先读取一个整数n，表示有n个二进制数需要处理。
接下来进行n次循环，每次循环读取一个二进制字符串s。

	//三、输入已知cin>>n;for(int i=0;i<n;i++){cin>>s;}

4.数据计算

将二进制字符串b转换为十进制整数。它从字符串的末尾开始遍历，累积每一位的值（通过减去字符’0’得到数字）并乘以当前的基数（初始为1，每次循环乘以2）。

int bindec(string b){int dec=0,q=1;for(int i=b.size()-1;i>=0;i--){dec+=(b[i]-'0')*q;q*=2;}return dec;}

判断一个整数p是否为素数。

bool isPrime(int p){if(p<=3) return p>1;for(int i=2;i*i<=p;i++){if(p%i==0) return false;}return true;
}

调用bindec将其转换为十进制数t，再用isPrime判断t是否为素数。如果是，则计数器c加1。

	//四、根据关系计算t=bindec(s);if(isPrime(t)) ++c;

5.输出结果

循环结束后，输出计数器c的值，即转换后是素数的二进制数的个数。

	//五、输出未知 cout<<c;

完整代码如下：

#include<bits/stdc++.h> // 包含所有常用头文件
using namespace std;    // 使用std命名空间，简化代码中标准库的使用// 函数：将二进制字符串转换为十进制整数
int bindec(string b){int dec = 0, q = 1; // 初始化十进制数为0，权重为1（2的0次幂）for(int i = b.size() - 1; i >= 0; i--){ // 从字符串末尾开始遍历dec += (b[i] - '0') * q;           // 将当前位的二进制值加到十进制数上q *= 2;                             // 权重翻倍，对应二进制位的移动}return dec; // 返回转换后的十进制数
}// 函数：判断一个整数是否为素数
bool isPrime(int p){if(p <= 3) return p > 1; // 处理p为1, 2, 3的情况，其中2和3是素数for(int i = 2; i * i <= p; i++){ if(p % i == 0 ) return false; }return true; // 所有可能的因子都检查过了，p是素数
}int main(){// 主函数开始int n, count = 0; // n表示二进制数的个数，count用于统计素数的个数string binary;    // 用于存储输入的二进制字符串// 输入二进制数的个数ncin >> n;// 循环读取n个二进制数，并检查它们转换为十进制后是否为素数for(int i = 0; i < n; i++){cin >> binary; // 输入一个二进制数int decimal = bindec(binary); // 转换为十进制if(isPrime(decimal)) ++count; // 如果是素数，计数器加1}// 输出统计结果cout << count << endl; // 输出转换后为素数的二进制数的数量return 0; // 程序结束
}