数组模拟 - 进制转化

92 阅读 0 评论 61 点赞

我是靠谱客的博主殷勤狗，这篇文章主要介绍数组模拟 - 进制转化，现在分享给大家，希望可以做个参考。

今天来介绍一下如何用数组模拟的手段，实现进制转换。首先就是精度问题，由于long long存不住数位过多的数，所以才采用数组模拟的手段，和上次讲到的高精度数组模拟如出一辙，先字符串读入，再转成int数组，根据题意要求加工int数组，按顺序输出即可。话不多说，放三道题，感受下：

<1> 1的个数

Description

给定一个十进制整数N，求其对应2进制数中1的个数。

Input

第一个整数表示有N组测试数据，其后N行是对应的测试数据，每行为一个整数。

Output

N行，每行输出对应一个输入。

Sample Input

Sample Output

思路：

该题主要应用到了二进制的性质，一道水题，放一下我AC代码。

本人AC代码：

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int cas;
ll n;

int main() {
   scanf("%d", &cas);
   while(cas--) {
       int cnt = 0;
       scanf("%lld", &n);
       while(n) {
           if(n & 1) {
               cnt++;
               n--;
           }
           else n >>= 1;   // 也可以写成 else n /= 2; 但是左移这种写法这样更便于理解
       }
       printf("%dn", cnt);
   }

}

<2> 二进制转十六进制

Description

输入一个二进制的数，要求输出该二进制数的十六进制表示。在十六进制的表示中，A~F表示10~15。

Input

第一行是测试数据的组数n，后面跟着n行输入。每组测试数据占一行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是10000。

Output

n行，每行输出对应于一个输入，表示该二进制数转化成十六进制数的结果。

Sample Input

2
100000
111

Sample Output

20
7

思路：

由于二进制转十六进制的时候，需要，从低位到高位，四位一个得转化，所以存在最高的几位凑不够四位的情况，举个例子，011011，低四位1011可以转为16进制的B，剩下两个高位01，通常方法，补前导0补到四位，补成0001，然后转为十六进制的1，所以结果为1B。这里介绍一下一个别的技巧，详见代码。

本人AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int Maxx = 1e5 + 7;
int cas;
char s[Maxx];
int a[Maxx];

int main() {
   scanf("%d", &cas);
   while(cas--) {
       scanf("%s", s);
       int l = strlen(s);
       for(int i = 0; i < l; i++) a[i] = s[i] - '0';
       int tmp = l % 4; //这个就是我刚说的技巧，t的值就是最高位（按四位一组来看）的位数
       int ans = 0;
       if(tmp) { //如果最高位凑不够四位，先将最高位这几位转为10进制，以%X形式输出即为16进制
           for(int i = 0; i < tmp; i++) ans += a[i] * pow(2, tmp - 1 - i);
           printf("%X", ans);
       }
       for(int i = tmp; i < l; i += 4) { //接下来就将剩下的数位，四位一个转成对应的10进制数，以%X输出即为16进制
           ans = a[i] * 8 + a[i + 1] * 4 + a[i + 2] * 2 + a[i + 3] * 1;
           printf("%X", ans);
       }
       printf("n");
   }

}

<3> 二进制转三进制

Description

输入一个2进制的数，要求输出该2进制数的3进制表示。
在3进制的表示中，只有0，1，2三种符号。

Input

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个以0和1组成的字符串，字符串长度至少是1，至多是64。

Output

n行，每行输出对应一个输入。

Sample Input

2
10110
1011

Sample Output

211
102

思路：

该题我的处理方式是以十进制作为中转，即 二 -> 十 -> 三，由于精度的问题，这里选择用 unsigned long long 声明转化过来的十进制数。然后进行模3除3操作倒序输出即可，由于我用来模拟模拟的数组下标十从1开始的，所以要对0单独特判，详见代码。

本人AC代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long long LLU;
const int Maxx = 1e2 + 7;
int cas;
char s[Maxx];
int a[Maxx];
int ans[Maxx];

int main() {
   scanf("%d", &cas);
   while(cas--) {
       memset(ans, 0, sizeof(ans));
       scanf("%s", s);
       int l = strlen(s);
       for(int i = 0; i < l; i++) a[i] = s[i] - '0';
       LLU d = 0; //中转成十进制
       LLU tmp = 1;
       for(int i = l - 1; i >= 0; i--) {
           d += (LLU)(a[i] * tmp); // 别用pow( )，本人用WA亲测过pow( )会失精
           tmp *= 2;
       }
       //printf("%llun", d);
       int pos = 0;
       if(d == 0) {
           puts("0");
           continue;
       }
       while(d) {
           pos++;
           ans[pos] = d % 3;
           d /= 3;
       }
       for(int i = pos; i >= 1; i--) printf("%d", ans[i]);
       printf("n");
   }
}