POJ1220-NUMBER BASE CONVERSION(任意进制转换)

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2020年7月21日13:11:25 评论

一、题目描述

Description

Write a program to convert numbers in one base to numbers in a second base. There are 62 different digits: { 0-9,A-Z,a-z }
HINT: If you make a sequence of base conversions using the output of one conversion as the input to the next, when you get back to the original base, you should get the original number.

Input

The first line of input contains a single positive integer. This is the number of lines that follow. Each of the following lines will have a (decimal) input base followed by a (decimal) output base followed by a number expressed in the input base. Both the input base and the output base will be in the range from 2 to 62. That is (in decimal) A = 10, B = 11, ..., Z = 35, a = 36, b = 37, ..., z = 61 (0-9 have their usual meanings).

Output

The output of the program should consist of three lines of output for each base conversion performed. The first line should be the input base in decimal followed by a space then the input number (as given expressed in the input base). The second output line should be the output base followed by a space then the input number (as expressed in the output base). The third output line is blank.

Sample Input

Sample Output

Source

Greater New York 2002

二、题目解析

题目的意思是实现62进制内任意进制数据的转换,其中A-Z表示10-35,a-z表示36-62。

这道题目一共考察了两个问题点,第一个是进制转换,第二个是大数据处理。更倾向于考察第二个问题点。

看了很多题解,百度上的题解基本都是copy的,一模一样的代码套进去,都没有说明白为什么要这样,没有任何价值。最后是google到的一篇题解才真正明白,其实解题的思路很简单,就是实现进制转换的短除法,然后处理除法过程中的大数据运算。

2.1 进制转换

解题前首先要搞清楚进制之间的转换逻辑,A进制转B进制如何转?

一般的思路是先从当前进制转到10进制,再从10进制转成目标进制。

从其他进制转换成十进制的办法是按权相加:

POJ1220-NUMBER BASE CONVERSION(任意进制转换)

从十进制转成其他进制的办法是短除法:

POJ1220-NUMBER BASE CONVERSION(任意进制转换)

2.2 大数计算

除了进制转换以外,最重要的功能就是除法的实现了,如何通过除法来获取余和商。

因为题目给的数据范围过大,如果用整形来保存数据,肯定是不够的,即使是long long或者更大的类型,都不足以容纳下题目所要求的数据范围。因此,数据只能用字符数组来保存,每个数组元素表示1位数字。

那么这道题目就转变成了通过字符串数组来求商和余数的问题了,只要循环求出所有的商和余数,问题就解决了。

三、代码

代码一共分为几个步骤:

  1. 将字符数组中的每个元素都转成整形,方便运算。
  2. 对每个元素求商和余数,模拟短除法,记录余数。
  3. 反转所有的余数,转成字符形式,输出。

第一部分,62进制字符和数字之间的相互转换:

第二部分,任意进制转换函数:

第三部分,main函数:

要注意的一个问题是输出格式是三行,每行输出后面都要有一个空行。

POJ1220-NUMBER BASE CONVERSION(任意进制转换)

单元测试案例

POJ1220-NUMBER BASE CONVERSION(任意进制转换)

马谦马谦马谦
  • 本文由 发表于 2020年7月21日13:11:25
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/poj1220-number-base-conversion.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: