【程序设计训练】计算校验码

Dear 丶 2022-11-27 00:37 188阅读 0赞

> 个人思路仅供参考，如有不足欢迎交流。

## 【问题描述】 ##

传送一个B（B≤16）进制的数值N时，最后加上一个一位（B进制的）校验码，使得N加上校验位后能被B-1整除。比如十进制的数值12310，其校验码就是3，因为十进制数值123310能被9整除。16进制的数7816，其校验码为0，因为16进制的78016是15的倍数。超过十进制后，用字母a表示10，字母b表示11，字母c表示12，字母d表示13，字母e表示14，字母f表示15。

告诉你进制B，以及一个B进制的正整数N，要求你计算正整数N在B进制下的校验码。

## 【输入形式】 ##

输入第一行正整数t (10 ≤ n ≤ 100)，表示有多少组测试数据。

后面有t行，每行两个正整数B，N（2≤ B≤16），中间用一个空格隔开，B是10进制整数，N用B进制形式表示。测试数据保证没有非法的B进制数N（也即N中每一位都是在0到B-1之间，没有前导0）。

40%的测试数据N的位数L 1 ≤ L≤ 10；

30%的测试数据N的位数L 1 ≤ L≤ 10^2；

20%的测试数据N的位数L 1 ≤ L≤ 10^3；

10%的测试数据N的位数L 1 ≤ L≤ 10^4；

## 【输出形式】 ##

对于每组测试数据，输出一位占一行：正整数N在B进制下的校验码。（如果校验码可以为B-1，也可以为0，输出0）。

## 【样例输入】 ##

4
    10 123
    16 78
    16 1234321
    12 ab

## 【样例输出】 ##

3
    0
    e
    1

### 【样例说明】 ###

第一行的4表示有4组测试数据，下面四行，每行一组测试数据。

第一组测试数据 10进制数123 最后添加检验码3，10进制数1233是9（=10-1）的倍数

第二组测试数据 16进制数78 最后添加检验码0，16进制数780是15（=16-1）的倍数

第三组测试数据 16进制数1234321 最后添加检验码e（=14），16进制数1234321e是15（=16-1）的倍数

第四组测试数据 12进制数ab 最后添加检验码1，12进制数ab1是11（12-1）的倍数

### 【Tips】 ###

B进制的数能被B-1整除，当且仅当各位数字和能被B-1整除。

第一组测试数据 10进制数123 最后添加检验码3，10进制数1233各位数字和是9，是9的倍数

第二组测试数据 16进制数78 最后添加检验码0，16进制数780各位数字和是15，是15的倍数

第三组测试数据 16进制数1234321 最后添加检验码e，16进制数1234321e各位数字和是30，是15的倍数

第四组测试数据 12进制数ab 最后添加检验码1，12进制数ab1各位数字和是22，是11的倍数

## 【思路和做法】 ##

由于很多数据中数的长度明显过长，所以采用了从头到尾类似于竖式除法的方式来计算，类似于另一题[“A除以B”][A_B]。  
提交代码如下（10/10分，C++）：

//37.校验码
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    bool check(string _num, int base)
    {
        
        int len = _num.length();      //加上校验码之后数的位数
        int temp = 0, t_num = 0;      //每次除法的被除数、当前位置的数字（t_num和r赋值为0是为了消除警告）
        int r = 0;                    //最后的余数
        for (int i = 0; i < len; i++) //从高位开始，类似于用竖式做除法
        {
        
            switch (_num[i]) //为当前位置数字赋值
            {
        
            case '0':
            {
        
                t_num = 0;
                break;
            }
            case '1':
            {
        
                t_num = 1;
                break;
            }
            case '2':
            {
        
                t_num = 2;
                break;
            }
            case '3':
            {
        
                t_num = 3;
                break;
            }
            case '4':
            {
        
                t_num = 4;
                break;
            }
            case '5':
            {
        
                t_num = 5;
                break;
            }
            case '6':
            {
        
                t_num = 6;
                break;
            }
            case '7':
            {
        
                t_num = 7;
                break;
            }
            case '8':
            {
        
                t_num = 8;
                break;
            }
            case '9':
            {
        
                t_num = 9;
                break;
            }
            case 'a':
            {
        
                t_num = 10;
                break;
            }
            case 'b':
            {
        
                t_num = 11;
                break;
            }
            case 'c':
            {
        
                t_num = 12;
                break;
            }
            case 'd':
            {
        
                t_num = 13;
                break;
            }
            case 'e':
            {
        
                t_num = 14;
                break;
            }
            case 'f':
            {
        
                t_num = 15;
                break;
            }
    
            default:
                break;
            }
            temp = t_num + temp * base; //temp=本位数字+上一位数字*base
    
            if (temp < base && i == 0) //_num的第一位<base，
                continue;
            else
            {
        
                r = temp % (base - 1); //余数
                temp = r;              //本次计算的余数继承到下一次计算
            }
        }
        if (r == 0) //最后余数为0，即能够整除
        {
        
            cout << _num[len - 1] << endl; //输出校验码
            return true;                   //找到校验码
        }
        return false; //没有找到校验码
    }
    
    int main()
    {
        
        int n;            //测试数据有n组
        int base;         //base进制
        string num, _num; //输入的数、加上校验码之后的数
        cin >> n;
        for (int i = 0; i < n; i++)
        {
        
            cin >> base >> num;
            for (int j = 0; j < base; j++) //校验码j从0到base-1
            {
        
                switch (j)
                {
        
                case 0:
                {
        
                    _num = num + '0';
                    break;
                }
                case 1:
                {
        
                    _num = num + '1';
                    break;
                }
                case 2:
                {
        
                    _num = num + '2';
                    break;
                }
                case 3:
                {
        
                    _num = num + '3';
                    break;
                }
                case 4:
                {
        
                    _num = num + '4';
                    break;
                }
                case 5:
                {
        
                    _num = num + '5';
                    break;
                }
                case 6:
                {
        
                    _num = num + '6';
                    break;
                }
                case 7:
                {
        
                    _num = num + '7';
                    break;
                }
                case 8:
                {
        
                    _num = num + '8';
                    break;
                }
                case 9:
                {
        
                    _num = num + '9';
                    break;
                }
                case 10:
                {
        
                    _num = num + 'a';
                    break;
                }
                case 11:
                {
        
                    _num = num + 'b';
                    break;
                }
                case 12:
                {
        
                    _num = num + 'c';
                    break;
                }
                case 13:
                {
        
                    _num = num + 'd';
                    break;
                }
                case 14:
                {
        
                    _num = num + 'e';
                    break;
                }
                case 15:
                {
        
                    _num = num + 'f';
                    break;
                }
                default:
                    break;
                }
                if (check(_num, base) == true) //获取到校验码
                {
        
                    break;
                }
            }
        }
        return 0;
    }

[A_B]: https://blog.csdn.net/m0_49777295/article/details/107760035