【題目鏈接】

ybt 1820：【00NOIP提高組】進(jìn)制轉(zhuǎn)換
洛谷 P1017 [NOIP2000 提高組] 進(jìn)制轉(zhuǎn)換
注意：兩OJ上題目?jī)?nèi)容相同，輸入輸出要求不同

【題目考點(diǎn)】

1.數(shù)制

【解題思路】

在題目描述下，對(duì)負(fù)數(shù)r進(jìn)制數(shù)字n，各位為$d_n{d}_{n?1}...d_1{d}_0$，按位權(quán)展開為：
$n=d_n?r^n+d_{n?1}?r^{n?1}+...+d_1?r^1+d_0?r^0$
其中$d_0,d_1,...,d_n$必須都為正數(shù)
除去最后一項(xiàng)，其余項(xiàng)加和一定是r的倍數(shù)：
$d_n?r^n+d_{n?1}?r^{n?1}+...+d_1?r^1=r?(d_n?r^{n?1}+d_{n?1}?r^{n?2}+...+d_1?r^0)$，簡(jiǎn)記為$r?q$
即$n=r?q+d_0?n?d_0=r?q$
其中$0\le d_0<|r|$
n需要減一個(gè)非負(fù)數(shù)$d_0$，使其是r的整數(shù)倍。
$d_0$即為r在可能為負(fù)數(shù)情況下廣義的“n對(duì)r取模”的值。該值無(wú)法在c++中通過(guò)n%r得到。

方法1：

枚舉從0到|r|-1的所有值，看哪一個(gè)滿足n減去它后是r的整數(shù)倍。

int mod(int a, int b)//求a對(duì)b取模的值，在a，b為負(fù)數(shù)條件下依然適用 {for(int r = 0; r < abs(b); ++r){if((a-r)%b == 0)return r;} }

方法2：

先求$n/r=x$，那么有：$n=r?x+m$，此時(shí)一定有$|m|<|r|$
m的值可能是正的也可能是負(fù)的。
根據(jù)上文結(jié)論：n需要減一個(gè)非負(fù)數(shù)，使其是r的整數(shù)倍。，所以必須讓$m\ge 0$
如果$m<0$，則公式化為：$n=r?(x+1)+m?r$。
$m?r$一定是非負(fù)數(shù)。
根據(jù)該原理，mod函數(shù)可以設(shè)計(jì)為：可以直接求商，再求余數(shù)，如果余數(shù)是負(fù)數(shù)，那么再減一個(gè)除數(shù)，使其變?yōu)榉秦?fù)數(shù)。

int mod(int a, int b) {int x = a / b, m;//x:商 m:余數(shù)m = a - x*b;if(m < 0)m = m - b;return m; }

以上兩種mod函數(shù)求兩個(gè)整數(shù)取模的值，在運(yùn)算數(shù)是正數(shù)、負(fù)數(shù)條件下都適用。
用mod函數(shù)求$d_0$的值，記錄在數(shù)組中。
而后計(jì)算$n=(n?d_0)/r$，再用同樣的方法求出下一個(gè)數(shù)位$d_1$。
如此循環(huán)，直到n為0。
最后輸出記錄的各位數(shù)字。輸出時(shí)，注意將10以上的數(shù)字轉(zhuǎn)為字母。

【題解代碼】

ybt 1820：【00NOIP提高組】進(jìn)制轉(zhuǎn)換

注意處理多組數(shù)據(jù)，要做狀態(tài)還原

#include<bits/stdc++.h> using namespace std; int num[50], ni; int mod(int a, int b) {for(int r = 0; r < abs(b); ++r){if((a-r)%b == 0)return r;} } int main() {int n, r, a, m;while(cin >> n >> r)//r:基數(shù) {ni = 0;//狀態(tài)還原 a = n;do//用do...while，即便a為0，也會(huì)填充到數(shù)組中 {m = mod(a, r);//"取模"結(jié)果 num[++ni] = m;//將余數(shù)填充到數(shù)組中 a = (a - m) / r; }while(a != 0);for(int i = ni; i >= 1; --i)//高位到低位輸出數(shù)字 cout << (num[i] < 10 ? char(num[i]+'0') : char(num[i]-10+'A'));//若超過(guò)10，轉(zhuǎn)為16進(jìn)制輸出 cout << endl;}return 0; }

洛谷 P1017 [NOIP2000 提高組] 進(jìn)制轉(zhuǎn)換

#include<bits/stdc++.h> using namespace std; int num[50], ni; int mod(int a, int b) {for(int r = 0; r < abs(b); ++r){if((a-r)%b == 0)return r;} } int main() {int n, r, a, m;cin >> n >> r;//r:基數(shù) a = n;do//用do...while，即便a為0，也會(huì)填充到數(shù)組中 {m = mod(a, r);num[++ni] = m;//將余數(shù)填充到數(shù)組中 a = (a - m) / r; }while(a != 0);cout << n << '=';for(int i = ni; i >= 1; --i)//高位到低位輸出數(shù)字 cout << (num[i] < 10 ? char(num[i]+'0') : char(num[i]-10+'A'));//若超過(guò)10，轉(zhuǎn)為16進(jìn)制輸出 cout << "(base" << r << ")";return 0; }

使用第二種mod函數(shù)寫法：

#include<bits/stdc++.h> using namespace std; int num[50], ni; int mod(int a, int b) {int x = a / b, m;m = a - x*b;if(m < 0)m = m - b;return m; } int main() {int n, r, a, m;cin >> n >> r;//r:基數(shù) cout << n << '=';a = n;do//用do...while，即便a為0，也會(huì)填充到數(shù)組中 {m = mod(a, r);num[++ni] = m;//將余數(shù)填充到數(shù)組中 a = (a - m) / r; }while(a != 0);for(int i = ni; i >= 1; --i)//高位到低位輸出數(shù)字 cout << (num[i] < 10 ? char(num[i]+'0') : char(num[i]-10+'A'));//若超過(guò)10，轉(zhuǎn)為16進(jìn)制輸出 cout << "(base" << r << ")";return 0; }

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 1820：【00NOIP提高组】进制转换 | 洛谷 P1017 [NOIP2000 提高组] 进制转换的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。