《算法笔记》3.5小节——入门模拟->进制转换

问题A：又一版 A+B

题目

题目描述

输入两个不超过整型定义的非负 10 进制整数 A 和 B（\(≤2^{31-1}\)），输出 A+B 的 m ( 1 < m <10 )进制数。

输入

输入格式：测试输入包含若干测试用例。每个测试用例占一行，给出 m 和 A，B 的值。 当 m 为 0 时输入结束。

输出

输出格式：每个测试用例的输出占一行，输出 A+B 的 m 进制数。

样例输入

2 4 5
8 123 456
0

样例输出

1001
1103

提示

注意输入的两个数相加后的结果可能会超过int和long的范围。

题解

思路

根据书上的除基取余法就好了。需要注意两点，第一点就是int与long溢出，那么我们用long long；第二个就是最后要输出一个空格。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    long long m, a, b;
    while (true)
    {
        scanf("%lld", &m);
        if (m == 0)
        {
            break;
        }
        scanf("%lld %lld", &a, &b);
        long long sum = a + b;
        long long res[100], num = 0;
        do
        {
            res[num++] = sum % m;
            sum /= m;
        } while (sum != 0);
        for (long long i = num - 1; i >= 0; i--)
        {
            printf("%d", res[i]);
        }
        cout << endl;
    }

    system("pause");
    return 0;
}

问题B：

题目

题目描述

求任意两个不同进制非负整数的转换（2进制～16进制），所给整数在long所能表达的范围之内。 不同进制的表示符号为（0，1，...，9，a，b，...，f）或者（0，1，...，9，A，B，...，F）。

输入

输入只有一行，包含三个整数a，n，b。a表示其后的n 是a进制整数，b表示欲将a进制整数n转换成b进制整数。a，b是十进制整数，2 =< a，b <= 16。

输出

可能有多组测试数据，对于每组数据，输出包含一行，该行有一个整数为转换后的b进制数。输出时字母符号全部用大写表示，即（0，1，...，9，A，B，...，F）。

样例输入

4 123 10

样例输出

27

提示

用字符串存储和表示不同进制的数。

题解

思路

这题我用的比较简单的思路，但是相应的就是时间代价增加但是能通过，就还不错。

思路就是先转成十进制，再转成 b 进制，最后根据res[j]的值，如果大于等于 10 则需要转为数字，ASCII 码要熟记。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    long a, b;
    string n;
    while (cin >> a >> n >> b)
    {
        long dA = 0, dN = 0, baseNum = 1;
        int count = n.length();
        // 先转为十进制
        for (int i = count - 1; i >= 0; i--)
        {
            // 字符转数字，分为小写、大写与数字字符
            if (n[i] >= 'a' && n[i] <= 'f')
            {
                dN = n[i] - 'a' + 10;
            }
            else if (n[i] >= 'A' && n[i] <= 'F')
            {
                dN = n[i] - 'A' + 10;
            }
            else
            {
                dN = n[i] - 48;
            }
            dA += dN * baseNum;
            baseNum *= a;
        }
        int res[40], num = 0;
        // 再转换成b进制
        do
        {
            res[num++] = dA % b;
            dA /= b;
        } while (dA != 0);
        // 如果res[j]的值大于10，则需要转换为字母，否则以数字形式输出
        for (int j = num - 1; j >= 0; j--)
        {
            if (res[j] >= 10)
            {
                printf("%c", res[j] - 10 + 65);
            }
            else
            {
                printf("%d", res[j]);
            }
        }
        printf("\n");
    }

    system("pause");
    return 0;
}

问题C：进制转换

题目

题解

思路

参考：

问题 C: 进制转换_ActionBeam的博客-CSDN博客

这题想的有点复杂了，没做出来，看了一下人家的思路，很清晰：模拟手算除法的过程，一直进行除法运算，然后计算余数即可。

代码

#include <stdio.h>
#include <string.h>
#include <iostream>

char mod(char str[]) //模拟辗转相除法求出每一个余数
{
    int div, temp = 0;
    for (int i = 0; i < strlen(str); i++)
    {
        div = ((str[i] - '0') + temp * 10) / 2; //求出每一轮的被除数
        temp = ((str[i] - '0') + temp * 10) % 2;
        str[i] = div + '0'; //将每一位对应的商放回数组对应的位上,全为0时表示已经结束
    }
    return temp + '0';
}

int isEmpty(char str[]) //  判断所给数组是否已经全部除完
{
    int i;
    for (i = 0; i < strlen(str); i++)
    {
        if (str[i] != '0')
        {
            return 0;
        }
    }
    if (i == strlen(str))
        return 1;
}

int main()
{
    int i = 0;
    char str[200], result[200] = "";
    while (scanf("%s", str) != EOF)
    {
        i = 0;
        do
        {
            result[i++] = mod(str);
        } while (!isEmpty(str));
        result[i] = '\0'; //注意要把最后一个字符设为'\0'表示这个字符串已经结束,不然可能会连续输出上一次位清空的数据
        for (i = strlen(result) - 1; i >= 0; i--)
            printf("%c", result[i]);
        printf("\n");
    }
    system("pause");
    return 0;
}

问题D：八进制

题目

题目描述

输入一个整数，将其转换成八进制数输出。

输入

输入包括一个整数N(0<=N<=100000)。

输出

可能有多组测试数据，对于每组数据， 输出N的八进制表示数。

样例输入

9
8
5

样例输出

11
10
5

题解

思路

我说这题很简单应该没人反对。

代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
    int in;
    while (scanf("%d", &in) != EOF)
    {
        int res[20], num = 0;
        do
        {
            res[num++] = in % 8;
            in /= 8;
        } while (in != 0);
        for (int i = num - 1; i >= 0; i--)
        {
            printf("%d", res[i]);
        }
        printf("\n");
    }

    system("pause");
    return 0;
}