2031 进制转换

关键字: 代码分享 杭电100题

问题描述

Problem Description

输入一个十进制数N,将它转换成R进制数输出。

Input

输入数据包含多个测试实例,每个测试实例包含两个整数N(32位整数)和R(2<=R<=16, R<>10)。

Output

为每个测试实例输出转换后的数,每个输出占一行。如果R大于10,则对应的数字规则参考16进制(比如,10用A表示,等等)。

Sample Input

7 2
23 12
-4 3

Sample Output

111
1B
-11

问题分析

Problem Analyse

本题是为C语言初学者提供的。

Algorithm Analyse

数制换算的一般方法:

  1. 把r进数转换成十进制数,只要把r(r是大于1的自然数)进制数写成r的各次幂的和的形式,然后按十进制计算结果。

    例如: (205.21)8 = 2 × 82 + 0 × 81 + 5 × 80 + 2 × 8-1 + 1 × 8-2

  2. 把十进制换成r进制,可以把十进制化成r的各次幂(各次幂的系数小于r而大于或等于0的整数)的和,从最高次幂起各次幂的系数就是依次的r进制从左到右各个数位上的数字。

  3. 当十进制数是整数时,采用“r除取余”法。即用数r除十进整数。取它的每次余数。例如:把(746)10化为一个八进制的数。

    8|746
      ----
      8|93 --- 2
       ---
      8|11 --- 5
       ---
       8|1 --- 3
        --
         0 --- 1
    

    得到(746)10 = (1352)8

  4. 当十进制是小数时,采用“r乘取整”法,即用数r乘十进制小数,每乘一次取一次整数,直至小数部分变成零为止。

    例如:把(0.8125)10化为二进制。

    0.|8125
     ×|   2
    -------
    1.|6250
     ×|   2
    -------
    1.|2500
     ×|   2
    -------
    0.|5000
     ×|   2
    -------
    1.|0000
    

    得到(0.8125)10 = (0.1101)2

  5. 把r1进制数转换成r2进制数,一般可以先把r1进制数转换成十进制数,再从十进制数转换成r2进制数。

算法实现

从上面的算法可以看出,数制转换需要逆序输出,就需要用到栈。所以我们直接用递归调用了。^_^

参考源码

redraiment使用Emacs Lisp批量迁移《HDU 2030-2039》