淘課計畫 - HackMD

# 淘課計畫 ## week 3 --- ### 本周主題是進制轉換 ~~投影片全部都是暴雷請小心服用~~ ---- ## 題目連結 [vjudge](https://vjudge.net/contest/622292#overview) ---- ## 出處連結 [problem A][1] ([中文點我][6]) [problem B][4] ([中文點我][8]) [problem C][2] ([中文點我][7]) [problem D][3] [1]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1872 [2]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=889 [3]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1034 [4]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=960 [6]: https://zerojudge.tw/ShowProblem?problemid=a132 [7]: https://zerojudge.tw/ShowProblem?problemid=a134 [8]: https://zerojudge.tw/ShowProblem?problemid=e545 --- ## [problem A][1] [1]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1872 ---- #### 題意將數字從十進制轉二進制，輸出二進制中1的數量。 ---- #### 作法將十進制轉二進制的做法，可以透過直式除法具體可以用while實作，用陣列紀錄1的位置最後反過來輸出 ---- ```cpp= int n; while(n>0){ if(n%2==1){ arr[bit]=1; } n/=2; bit++; } ``` ---- #### 或是也可以寫成這樣 ###### ~~裝B用~~ ```cpp= int n; vector<int> ans; while(n>0){ if(n&1) ans.push_back(1); else ans.push_back(0); n>>=1; } reverse(ans.begin(),ans.end()); ``` --- ## [problem B][2] [2]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=960 ---- #### 題意將輸入的一串數字分別視為十進制與十六進制再分別計算轉二進制後 1 的數量 ---- #### 作法跟 problem A 很像，差別在一開始要分成十六進制與二進制處理 --- ## [problem C][2] [2]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=889 ---- #### 題意將數字從十進制轉費波納契進制 ---- #### 作法先做一個費波納契數的陣列再用迴圈從大往小逐一比對 n 是否有用到當前bit 一樣用陣列紀錄答案再輸出 ---- #### 製作費波納契數陣列 :::spoiler ```cpp= f[0]=1;f[1]=2; for(int i=2;i<40;i++){//只要到40就夠了 f[i]=f[i-1]+f[i-2]; } ``` ::: ---- #### 轉費波納契進制 :::spoiler ```cpp= for(int i=38;i>=0;i--){ if(n>=f[i]){ ans[i]=1;//ans為紀錄答案的陣列 n-=f[i]; i--;//應題目要求跳過一個位元 } } ``` ::: --- ## [problem D][3] [3]: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=1034 ---- #### 題意給一個 N 進制的數字 R，且 R 可以被 (N-1) 整除求符合條件的最小 N (2 ≤ N ≤ 62) 註: A 表示 10 、 B 表示 11 ... a 表示 36 、 b 表示 37 以此類推到 z ---- #### 公式推導假設一個N進位制的二位數表示R~1~R~2~ R~1~R~2~ :arrow_right: R~1~ * N + R~2~ = R~1~*(N-1) + R~1~ + R~2~ 因為 R~1~*(N-1) 可以被 (N-1) 整除所以 R~1~ + R~2~ 也必須可以被 (N-1) 整除 ---- #### 公式推導假設一個N進位制的三位數表示abc R~1~R~2~R~3~ = R~1~ * N^2 + R~2~ * N + R~3~ = (R~1~N(N-1) + R~1~N) + (R~2~(N-1) + R~2~) + R~3~ = (R~1~N(N-1) + R~1~(N-1) + R~1~) + (R~2~*(N-1) + b) + R~3~ = (R~1~N(N-1) + R~1~(N-1) + R~2~(N-1)) + R~1~ + R~2~ + R~3~ = (R~1~N + R~1~ + R~2~) * (N-1) + R~1~ + R~2~ + R~3~ 因為 (R~1~N + R~1~ + R~2~) 可以被 (N-1) 整除所以 R~1~ + R~2~ + R~3~ 也必須可以被 (N-1) 整除 ---- #### 小結 1 一個 N 進位制的 K 位數 R R 表示為 R~1~R~2~R~3~...R~K-1~R~K~ R~1~+R~2~+R~3~+...+R~K-1~+R~K~必須可以被 (N-1) 整除 ---- #### 小結 2 一個 N 進位制的 K 位數 R R 表示為 R~1~R~2~R~3~...R~K-1~R~K~ R 的最小進制至少是 R~1~ ~ R~K~中最大的數 + 1 例 : 3 至少是 4 進制、 A 至少是 11 進制 ---- #### 作法總結本題要判斷一個 N 進制的數字 R 是 N 進制需要符合兩個條件 1. R~1~+R~2~+R~3~+...+R~K-1~+R~K~必須可以被 (N-1) 整除 2. N > R~i~ ( i for all 1 ~ K ) ---- #### 作法總結 可以先用一個 *m* 變數紀錄R~1~到R~K~中最大的值 再用一個變數 *s* 紀錄R~1~+...+R~K~的值 最後再用迴圈跑 *m* 到 62 中，有沒有數可以整除 *s*