一次看懂进制转换(阶乘是关键) - HDU 2031

说起进制转换,最常见的莫过于十进制与二进制的转换操作,因为经常要进行位运算,位运算性能一般都会优于整数运算,对于追求性能的童鞋不可谓不争之地。

对于二进制的转换,我们通常有这样的公式,例如对于一个二进制111001,转换为十进制xx:

x=1×25+1×24+1×23+0×22+0×21+1×20x=1×25+1×24+1×23+0×22+0×21+1×20

事实上,对于任意R进制ABCDEF,转换为十进制xx,我们可以写成如下形式:

x=A×R5+B×R4+C×R3+D×R2+E×R1+F×R0x=A×R5+B×R4+C×R3+D×R2+E×R1+F×R0

那么反过来,对于一个十进制的xx,如果求得RR进制的数呢。

由上述公式,我们不难可以得出一个推导式:

F=x%RF=x%R

E=(x−F)/R%RE=(x−F)/R%R

依次倒退,直到求得A。

每次求一个字母(如F、E、D、C、B、A),都是减去取模的值,然后除以R,再对R取模。然后取得每个位置的字符拼成R进制值。

思路往往不难寻找,再复杂的问题,只要一点点抽丝剥茧,最后也会变得易于理解。

进制转换问题还有一个从M进制转换为N进制的问题,这个问题可以用10进制作为中间转换,也有一种称之为短除法的做法,本篇不深入讲解,后面再发一篇文章说明吧。

嗯,接着看题~

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

源代码:GCC

#include <stdio.h>

//R是小于16的,如果大于16,修改这个表的大小
const char set[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};

int main()
{
  int decimal, base, result[1007];

  //输入十进制数字和需要转换的进制
  while (scanf("%d %d", &decimal, &base) != EOF) {
    //处理负数
    if (decimal < 0) {
      printf("-");
      decimal = -decimal;
    }

    int cnt = 0;

    //进制转换
    //例如:对于16进制3B2A
    //转换成十进制为 A * 16^0 + 2 * 16^1 + B * 16^2 + 3 * 16^3 = 10997
    while (decimal) {
      //取余,获得进制位数
      int tmp = decimal % base;
      //减少一个阶乘
      decimal /= base;
      //存入数据
      result[cnt++] = tmp;
    }

    //倒着输出,一直到0
    for (int i = cnt - 1; i >= 0; i--)
      printf("%c", set[result[i]]);

    printf("\n");
  }

  return 0;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-10-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏目标检测和深度学习

常用排序算法总结(1)

14220
来自专栏Java帮帮-微信公众号-技术文章全总结

八大排序算法详解_面试+提升

八大排序算法详解_面试+提升 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排...

40690
来自专栏mathor

十大经典排序算法(动图演示)

不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面。 时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。 ...

2.3K40
来自专栏数据结构与算法

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是,通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记...

34370
来自专栏程序员互动联盟

八大排序算法

排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说...

42580
来自专栏mathor

小和问题

 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组的小和。

26340
来自专栏算法channel

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

442110
来自专栏糊一笑

非比较排序算法总结与实现

之前一篇文章介绍了几种常用的比较排序算法,下面介绍的是几种非比较排序算法。 非比较排序算法内部引用的都是计数排序,当然你也可以将计数排序换为其他的比较排序算法。...

33180
来自专栏AI派

TensorFlow 修炼之道(1)——张量(Tensor)

TensorFlow名字可以拆解为两部分:Tensor、Flow。其中,Tensor 就表示张量。

53640
来自专栏云霄雨霁

字符串排序----三向字符串快速排序

25200

扫码关注云+社区

领取腾讯云代金券