【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; // 程序結束
}