<h2 class="text-center">CPE 檢定加強計畫（四）</h2> <h3 class="text-center">進制轉換與 CPE 考前須知</h3> <style> :root{ --r-main-font-size: 30px; } .reveal .slides { text-align: left; } /* .ul-left { display: block !important; margin:0 0 0 0.5em !important; } */ .hint { color: #191919; } details[open] { margin-top: 1.5em; } details[open] .hint { color: inherit; } details[open] .hint::after { content: "："; } </style> ---- ### Table of Contents - 不同的進位制 - 實作進位制轉換 - 基本題型講解 - CPE 考前須知 ---- 一般來說 日常用到的都是十進位 對資工系 常用的是二進位與十六進位 ---- 但是在 CPE 的題目中 各種奇奇怪怪的進位制都有可能出現 --- <h2 class="text-center">不同的進位制</h2> ---- ### 十進制 - 每一位數字: $0$ ~ $9$ - 每數到十就進一位 (即寫到下一格) - 可以以十的指數去拆解 $2506=2\times 10^3+5\times 10^2+0\times 10^1+6\times 10^0$ ---- ### 二進制 - 每一位數字: $0$ ~ $1$ - 每數到二就進一位 (即寫到下一格) - 可以以二的指數去拆解 $(1011)_2=1\times 2^3+0\times 2^2+1\times 2^1+1\times 2^0$ ---- ### 十六進制 - 每一位數字: $0$~$F$ - $A$~$F$ 分別是 $10$~$15$ - 每數到十六就進一位 (即寫到下一格) - 可以以十六的指數去拆解 $1F0A=1\times 16^3+15\times 16^2+0\times 16^1+10\times 16^0$ ---- ### n 進制 (一般化) - 每一位數字: $0$ ~ $n-1$ - 每數到 $n$ 就進一位 (即寫到下一格) - 可以以 $n$ 的指數去拆解 設一序列 $a_3a_2a_1a_0$ 為 $n$ 進制數字 $a_3a_2a_1a_0=a_3\times b^3+a_2\times b^2+a_1\times b^1+a_0\times b^0$ --- <h3 class="text-center"> 實作進位制轉換 </h3> ---- ### 十進位 ⮕ 二進位 ```cpp string d_to_b(int n){ string ret; while(n){ ret.push_back('0' + n % 2); n >>= 1; // n = n / 2 } reverse(ret.begin(), ret.end()); // 顛倒 return ret; } ``` ---- ### 十進位 ⬅ 二進位 ```cpp int b_to_d(string s){ int ret = 0; for(int i = s.length() - 1, exp = 1; i >= 0; i--, exp *= 2) ret += exp * (s[i] - '0'); return ret; } ``` <p class="text-center">or</p> ```cpp int b_to_d(string s) { int ret = 0; for (int i = 0; i < s.length(); i++) ret = ret * 2 + (s[i] - '0'); return ret; } ``` ---- ### 十進位 ⮕ 十六進位 ```cpp string mp = "0123456789ABCDEF"; string d_to_h(int n){ string ret; while(n){ ret.push_back(mp[n % 16]); n /= 16; } reverse(ret.begin(), ret.end()); // 顛倒 return ret; } ``` ---- ### 十進位 ⬅ 十六進位 ```cpp int h_to_d(string s){ int ret = 0; for(int i = 0; i < s.length(); i++){ if(s[i] >= '0' && s[i] <= '9') ret = ret * 16 + (s[i] - '0'); else if(s[i] >= 'A' && s[i] <= 'F') ret = ret * 16 + (s[i] - 'A' + 10); } return ret; } ``` --- <h2 class="text-center"> 基本題型講解 </h2> ---- ### [10931 - Parity](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1872) 將數字從十進制轉二進制 輸出二進制中 $1$ 的數量 :::spoiler <font color="#191919">提示</font> 這個可以用來計算二進位 $1$ 的數量 ```cpp __builtin_popcount(); ``` ::: ---- <h3 class="text-left"><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=960"> 10019 - Funny Encryption Method </a></h3> 給一個數字 $n$ 將其視為十進位 $a_1$ 與十六進位 $a_2$ 求 $b_1$ 與 $b_2$ - $b_1$ 為 $a_1$ 的二進位中 $1$ 的數量 - $b_2$ 為 $a_2$ 的二進位中 $1$ 的數量 ---- <h3 class="text-left"><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=13&page=show_problem&problem=1042"> 10101 - Bangla Numbers </a></h3> 將數字轉換成指定單位的格式 |單位|數值| |---|---| Kuti|10,000,000| Lakh|100,000| Hajar|1,000| Shata|100| :::spoiler <font color="#191919">提示</font> 1. 注意輸出格式 2. 建議使用遞迴 ::: ---- <h3 class="text-left"><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=889"> 00948 - Fibonaccimal Base </a></h3> 把費氏數列當作一種 base 來求他的數字拆解 可以想成費氏數列的哪幾項加起來會是該數 $0$ 代表不取該數字、$1$ 代表取該數字 ---- <h3 class="text-left"><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1034"> 10093 - An Easy Problem! </a></h3> 給一個 $N$ 進制的數字 $R$，且 $(N-1)|R$ 求符合條件的最小 $N$ $(2 \leq N \leq 62)$ 根據題意: 'A'$=10$ 、 'B'$=11$、'a'$=36$ 、 'b'$=37$ 以此類推到 'z'，共 $62$ 種符號 這題超難，需要[推導](https://hackmd.io/@CPE-GOGO/SJQdKfk20)一下 --- <h2 class="text-center"> CPE 考前須知 </h2> ---- <h3 class="text-left"> 考前準備 </h3> - 帶學生證與其他證件(身分證) - 考場可以帶水、文具用品 - 睡飽 ---- <h3 class="text-left"> 考試須知 </h3> - 在開始前有 $1$ 小時的測試時間 介面上有什麼按鈕都按按看 習慣一下 原則上有字典、查 standard library 等等功能 - 不可使用手機 - 可以中途舉手上廁所 - 在開始一段時間後可以提早離開 ---- <h3 class="text-left"> 考完查資料 </h3> 可以上官網查歷屆考試看成績 CPE 官網[連結](https://cpe.cse.nsysu.edu.tw/history.php) --- 以上是本章內容 <a href="https://github.com/ShanCisgood/cpp_for_uva" style="color: #191919">答案在這裡</a>