洛谷千题详解 | P1017 [NOIP2000 提高组] 进制转换【C++、Java、Pascal、Python语言】

博主主页：Yu·仙笙

专栏地址：洛谷千题详解

目录

题目描述

输入格式

输出格式

输入输出样例

解析：

那么怎么把负数转成正数？

j-=m（j为原先算出来的负数，m为进制数）

n/m=a

n-a*m=j

n-a*m-m=j-m

n-(a+1)*m=j-m

n++（此时n已经/=m）

C++源码：

Pascal源码：

Java源码：

Python源码：

---

-------------------------------------------------------------------------------------------------------------------------------- 

-------------------------------------------------------------------------------------------------------------------------------- 

题目描述

我们可以用这样的方式来表示一个十进制数: 将每个阿拉伯数字乘以一个以该数字所处位置为指数,以 10 为底数的幂之和的形式。例如 123 可表示为 1×102+2×101+3×100 这样的形式。

与之相似的，对二进制数来说，也可表示成每个二进制数码乘以一个以该数字所处位置为指数,以 2 为底数的幂之和的形式。

一般说来，任何一个正整数 R 或一个负整数 −R 都可以被选来作为一个数制系统的基数。如果是以 R 或 −R 为基数,则需要用到的数码为 0,1,....R−1。

例如当 R=7时,所需用到的数码是 0,1,2,3,4,5,6，这与其是 R 或 −R 无关。如果作为基数的数绝对值超过 10,则为了表示这些数码，通常使用英文字母来表示那些大于 9 的数码。例如对 16 进制数来说,用 A 表示 10,用 B 表示 11，用 C 表示 12，以此类推。

在负进制数中是用 −R 作为基数，例如 −15（十进制）相当于 110001 （−2进制），并且它可以被表示为 2 的幂级数的和数：

110001=1×(−2)5+1×(−2)4+0×(−2)3+0×(−2)2+0×(−2)1+1×(−2)0

设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数。

-------------------------------------------------------------------------------------------------------------------------------- 

输入格式

输入的每行有两个输入数据。

第一个是十进制数 n。 第二个是负进制数的基数−R。

-------------------------------------------------------------------------------------------------------------------------------- 

输出格式

输出此负进制数及其基数，若此基数超过 10，则参照 16 进制的方式处理。

-------------------------------------------------------------------------------------------------------------------------------- 

输入输出样例

输入 #1

30000 -2

输出 #1

30000=11011010101110000(base-2)

输入 #2

-20000 -2

输出 #2

-20000=1111011000100000(base-2)

输入 #3

28800 -16

输出 #3

28800=19180(base-16)

输入 #4

-25000 -16

输出 #4

-25000=7FB8(base-16)

-------------------------------------------------------------------------------------------------------------------------------- 

解析：

我们都知道，首先按照10进制转成n进制的做法：

对这个数不断除以n，将余数一一存储，最后倒序输出。

那么有一个问题，此处原数和进制数都有可能为负数，也就意味着余数可能为负数，那么我们不可能输出像-100-100这种数。

那么怎么把负数转成正数？

我们基本思路分两点：

1. 把负数转成符合n进制余数规律的正数
2. 让转得的正数符合余数的计算模式

---

1. 把负数转成符合n进制余数规律的正数

我们先来探讨一下二进制余数的规律：

那么我们只需让负数余数规律也为010101……，就解决了。

我们发现，每一组数，他们对应的间隔区间内的数是相等的。那么我们只需跳到它前面一个区间的数即可，因为区间长度为-m,（m为进制）。那么就转换成：

j-=m（j为原先算出来的负数，m为进制数）

让转得的正数符合余数的计算模式

光转成正数还不够，因为还不符合余数的计算。

众所周知，我们令n为被除数，m为除数和进制数,a为商,j为余数，可以得到：

n/m=a

n-a*m=j

根据我们刚刚推得的算法：j-=m，那么此时方程2两端同时减去m，得

n-a*m-m=j-m

提公因式，得

n-(a+1)*m=j-m

但我们还要让j-m符合余数计算模式，即符合n-a*m=j的形式。

显然，此时a=a+1正好符合n-a*m=j的形式。所以：

n++（此时n已经/=m）

-------------------------------------------------------------------------------------------------------------------------------- 

C++源码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
using namespace std;
//std::ios::sync_with_stdio(false);
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define LL long long
#define ll long long
#define inf 1e-5
const int INF=1<<30;
const int MAX=40000;
const int mod=1e9+7;
int P[20];
char b[100];
char bit[100];
int N,R;
void getBit(){
    int i,j,ans;
    for(i=0;i<10;i++){
        b[i]=i+'0';
    }
    for(i=0;i<=26;i++){
        b[i+10]=i+'A';
    }
}
int main(int argc,char *argv[]){
    //freopen("in.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取
    //freopen("out.txt","w",stdout); //输出重定向，输出数据将保存在out.txt文件中
    //srand(time(NULL));//有的OJ不能加这句话
    int M,i,j,ans,k;
    getBit();
    while(~scanf("%d%d",&M,&R)){
        N=M;
        R=abs(R);
        memset(bit,0,sizeof(bit));
        if(N>0){
            for(i=0;N!=0;i++){
                k=N%R;
                if(i%2==0){
                    bit[i]=b[k];
                    N/=R;
                }else{
                    k=k?R-k:0;
                    bit[i]=b[k];
                    N=(int)ceil((double)N/(double)R);
                }
            }
        }else{
            N=abs(N);
            for(i=0;N!=0;i++){
                k=N%R;
                if(i%2==0){
                    k=k?R-k:0;
                    bit[i]=b[k];
                    N=(int)ceil((double)N/(double)R);
                }else{
                    bit[i]=b[k];
                    N/=R;
                }
            }
        }
        printf("%d=",M);
        for(i=strlen(bit)-1;i>=0;i--){
            printf("%c",bit[i]);
        }
        printf("(base-%d)\n",R);
    }
return 0;
}

-------------------------------------------------------------------------------------------------------------------------------- 

Pascal源码：

var m,n,i,x,y:longint;
s:string;
begin
        readln(n,x);
        s:='';m:=n;//保存取值
        while(m<>0)do
        begin
                y:=m mod x;
                m:=m div x;
                if y<0 then
                begin
                        inc(m);
                        y:=y-x;
                end;
                if(y<10)then s:=chr(y+48)+s else s:=chr(y+55)+s;
        end;
        write(n,'=',s,'(base',x,')');
        readln;
end.

-------------------------------------------------------------------------------------------------------------------------------- 

Java源码：

import java.util.Scanner;
 
public class P1017 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        final char[] num = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
        char[] ans = new char[1000];
        int temp, i = 0;
        int n = sc.nextInt();
        int R = sc.nextInt();
        temp = n;
 
        while (n != 0) {
            int mod = n % R;
            int t = n / R;
            if (mod < 0) {
                mod -= R;
                t++;
            }
            n = t;
            ans[i++] = num[mod];
        }
 
        System.out.print(temp + "=");
        for (int j = i - 1; j >= 0; j--)
            System.out.print(ans[j]);
        System.out.print("(base" + R + ")");
    }
}
 

-------------------------------------------------------------------------------------------------------------------------------- 

Python源码：

"""
P1017 [NOIP2000 提高组] 进制转换（python3实现）
https://www.luogu.com.cn/problem/P1017
"""
 
def zhuan(n,r):
 
            if n==0:
                        return
 
            m=n%r
 
            if m<0:
                        m-=r
                        n+=r
 
            if m>=10:
                        m=m+65-10
            else:
                        m+=48
 
            zhuan(n//r,r)
 
            print(chr(m),end="")
 
            return
 
ans=""
 
n,r=map(int,input().split())
 
print(n,end="=")
 
zhuan(n,r)
 
print("(base%d)"%r)
 

--------------------------------------------------------------------------------------------------------------------------------