机试--数学问题

机试中，有一些与数字相关的题目：进制转换、最大公约数、最小公倍数、素数、高进度整整数运算（无法用数值类型变量直接存储）。本文对于这几个部分的一些常见题，进行归纳总结。

进制转换

整数二进制方式显示 [北邮上机题]

十进制转二进制，使用除留取余法，注意余数的先后顺序与该数二进制顺序相反，因此将余数按顺序存放，逆序输出即可

#include <iostream>
#include <cstdio>
#include <vector>   //容器，可变长度的"数组"
#include <string>

using namespace std;

void Bit(int num){
    vector<int> NumBit;
    int BitNum = 0;
    while(num != 0){
        NumBit.push_back(num % 2);
        num /= 2;
    }

    for (int i = NumBit.size()-1; i >= 0 ; i--) {
        printf("%d",NumBit[i]);
    }
    printf("\n");

    return;
};

int main(){
    int n;
    int num;
    string s = "";
    scanf("%d",&n);
    while(n--){
        scanf("%d",&num);
        Bit(num);
    }
    return 0;
}

大型正整数二进制显示 [清华上机题]

在C与C++中较大的整数无法存储进行直接的算数运算。因此，对于大数的处理一般需要使用字符串的方法。本题与上一题有相似之处，只是本题的数据无法存储，因此无法进行算术的除、取余操作。可以通过定义字符串的方式，实现字符串数字的除法、取余。进而套用上一题的方法。

对于字符串的：

取余操作：只需取当前字符串的最后一位做算术的取余操作，其结果即是整个字符串数的取余结果。

除法操作：与我们平时在草稿纸上算的步骤一样，依次从高到低对字符串数的每个元素进行：
除2 、取余操作。即可得到该字符串数除2的结果字符串。该过程中注意：取余的目的是为了，在下次除操作前，将上一位的余数与当前为合并作为被除数。对于除完后的结果中可能前几位是0，需要去掉多余的0，方便除留取余法推出循环。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;
string divide(string num, int divider){  //字符串除法
    string answer; //商
    int carry = 0; //上一位的余数
    for(int i=0; i<num.size(); i++){
        int dividend = num[i]-'0' + carry*10 ;
        answer += ('0' + dividend / divider);   
        carry = dividend % divider; //取余
    }

    int post = 0; //标示answer中不为0的第一个数字字符【重要】
    while (answer[post] == '0'){
        post++;
    }
    return answer.substr(post);
};
void printBit(string sNum){ //十进制转二进制
    vector<int> NumBit;
    while(sNum.size() != 0){
        NumBit.push_back((sNum[sNum.size()-1]-'0') % 2);
        sNum = divide(sNum,2);
    }
    for(int i=NumBit.size()-1; i>=0; i--){
        printf("%d",NumBit[i]);
    }
    printf("\n");
    return;
};
int main(){
    string sNum;
    while(cin >> sNum){
        printBit(sNum);
    }
    return 0;
}

求一个十进制数的逆序数。[清华机上机题]

逆序数：对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。

本题与上一题，有一定的联系。将大数的十进制（字符串形式）转换为二进制【上题内容】，接下来需要：将得到的二进制转换成新的大数的十进制（字符串形式）。

转换过程中涉及到：字符串数与一位整数的加法和乘法

加法：将加数作为低位的进位，从后向前遍历字符串数的每一个位：当前位与进位相加，对10取余为求加法结果，对10取模为当前位加法向上一位的进位。注意即使进位为0，也要继续遍历高位，进行求和操作。否则结果会丢失高位信息。。如果加法遍历完后，最高位有进位需要给结果修正：最高位补1。

乘法：对于被乘数进行从后向前遍历：当前位乘上乘数并加上后一位的进位，对10取余为乘法结果，对10取模为进位。如果最高位有进位，结果和加法一样需要类似的修正。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;

string divide(string sNum,int divider){   //字符串除法
    string answer; //最后除的结果--商
    int carry = 0; //上一位的余数
    for(int i=0; i<sNum.size(); i++){
        int dividend = (sNum[i]-'0') + carry*10; //当前位的被除数
        answer += ('0'+ (dividend / divider)); //当前位的商
        carry = dividend % 2;
    }

    int post = 0; //商字符串中不为0的第一字符位置
    while(answer[post] == '0'){    //去除结果中前面多余的0
        post++;
    }
    return answer.substr(post);
}

string multiple(string sNum,int factor){  //字符串乘法
    string answer;
    int carry = 0;
    for(int i=sNum.size()-1; i>=0; i--){
        int temp = (sNum[i]-'0')  * factor + carry;
        answer = char('0'+(temp % 10)) + answer;   //从低位到高位分别乘二得到结果
        carry = temp / 10;
    }

    if(carry == 1){     //因为乘的是2，所以进位只能是1
        answer = '1' + answer;
    }
    return answer;
}

string add(string sNum, int adder){
    string answer;
    int carry = adder;
    for(int i=sNum.size()-1; i>=0; i--){
        int temp = sNum[i]-'0' + carry; //把要加的一位整数（0或1）当成当前位后一位的进位
        carry = temp / 10;
        answer = char('0' +temp%10) + answer ;  //需要进行类型转换，否则无法将int型并入字符串
        //if(carry == 0) 没有进位，加法依然要继续，否则丢失高位值
        //    break;
    }

    if(carry == 1){ //最高位有进位
        answer = "1" + answer;
    }
    return answer;
}



void printInvertBinNum(string sNum){

    //十进制字符串 转 二进制
    vector<int> InvertBinary;
    while(sNum.size() != 0){
        InvertBinary.push_back( (sNum[sNum.size()-1]-'0') % 2 ); //取余
        sNum = divide(sNum,2);
    }

    //二进制 转 十进制字符串
    string answer = "0";
    for(int i=0; i<InvertBinary.size(); i++){  //对于求二进制逆序数来说： InvertBinary中保存的是逆序数的正序二进制
        answer = multiple(answer,2); //对于中间结果右移一位
        answer = add(answer,InvertBinary[i]); //加上低位的值
    }
    for (int j = 0; j < answer.size(); ++j) {
        printf("%c",answer[j]);
    }
    printf("\n");
    return;
}

int main(){
    string sNum;
    while(cin>>sNum){
        printInvertBinNum(sNum);
    }

    return 0;
}

M进制转N进制

由于M，和N的值都有可能大于10，所以有字符串的形式存储M进制数和N进制数。因此需要现将M进制的数转换为数值形式，这里将其转换为我们熟悉的十进制是一种常见的方式，通过十进制作为两种不同进制字符串形式转换的桥梁。即 M进制字符串形式 –> 十进制数值形式 –> N进制字符串形式。在其中注意一些细节问题，如需要将高于10进制的数中的英文字符转换为数字，将高于10的数字转换为英文字符。这是于小于10的进制转换所不需要考虑的问题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include <vector>

using namespace std;

int CharToInt(char c){
    if('0'<=c && c<='9'){
        return c-'0';
    }else{
        return c-'A'+10;
    }
};

char IntToChar(int x){
    if (x<10){
        return '0'+x;
    }else{
        return x-10 + 'a';
    }
}



int main(){
    int m,n;
    string str,Nmum;
    while(scanf("%d %d",&m,&n)) {
        cin >> str;
        long long number = 0;

        for (int i = 0; i < str.size(); ++i) {  //M进制转为10进制
            number *= m;
            number += CharToInt(str[i]);
        }

        vector<char> answer;
        while(number != 0){
            answer.push_back(IntToChar(number%n));
            number /= n;
        }

        for (int j = answer.size()-1; j >= 0; --j) {
            printf("%c", answer[j]);
        }
        printf("\n");
    }
    return 0;
}

总结

进制转换的问题，最为重要的是转换的方法： 1.正向除留取余法，2.逆向移位求和法。注意在做两种运算的过程中1的输出、2的输入的数据的顺序与正常情况下的相反。
在此基础之上，有时需要考虑到输入数据的方式：

由于高于10进制，存储使用字符串方便。对于这种可以想办法把输入转为10进制数值，根据题目要求作处理。
需要输入的数远大于数值类型的存储范围，使用字符串存储。对于该类数据的运算，不能使用数值型，因为无法存储中间结果。需要实现字符串级别的“算术运算”。要注意定义运算过程中的一些细节，如运算后结果的修正，考虑最高位进位问题等。

最大公约数与最小公倍数

这种题需要对于最大公约数和最小公倍数的判别方法熟悉。

最大公约数

对于 a, b 两数，求其最大公约数的思路是：

把求 a, b的最大公约数 —> b, a%b的最大公约数（数学推理过程略） 注意b作为除数不能为0

这样不断递归的缩小范围，直到求某个数与0 的最大公约数，即非0数为最大公约数

#include<iostream>
#include<cstdio>

using namespace std;

int MaxFactor(int a, int b){
    if(b==0){
        return a;
    }else{
        return MaxFactor(b,a%b);
    }

};

int main(){
    int m,n;

    while(scanf("%d %d",&m,&n)) {

        printf("%d",MaxFactor(m,n));
        printf("\n");
    }
    return 0;
}

最小公倍数

求最小公倍数思路是基于最大公约数的：
a,b 的最小共倍数是 a*b / 最大公约数

质数/素数

质数或者素数a：只能被1和本身整出的正整数（小于2的数一定不是素数）。用所有小于sqrt(a)的数除a,如果存在整除的情况则不是素数。

判断一个数是否为素数

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;

bool JudgeSuNum(int n){
    if(n < 2){                //小于2的数一定不是素数
        return false;
    }
    int bound = sqrt(n);
    for (int i = 2; i < bound; ++i) {
        if (n%i == 0){
            return false;
        }
    }
    return true;
};


int main(){
    int n;

    while(scanf("%d",&n)) {

        printf("%d",JudgeSuNum(n));
        printf("\n");
    }
    return 0;
}

对于一定大范围的数，判断其是否为素数，对于每一个数遍历判别，显然是有些耗时，效率不高。是否有更好的方法呢？——-素数筛选法

素数筛选法的思想是：假设当前大于1的数都为素数，遍历所有数，用已确定的素数，去标记后面是该素数倍数的数为非素数。通过选出不是素数的数，剩余的则是素数。

输出1到给定n之间的素数

#include<iostream>
#include<cstdio>
#include<vector>

using namespace std;

const int MAXN = 10001;
bool isPrime[MAXN];
vector<int> prime;

void Initial(){
    for (int i = 0; i < MAXN; ++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for (int j = 2; j < MAXN; ++j) {
        if(!isPrime[j]){
            continue;
        }
        prime.push_back(j);
        for (int i = j*j; i < MAXN; i+=j) {  //从当前素数j的j倍开始，小于j的倍数的数 由 小于j的素数标记。i的“自增”为j的倍数
            isPrime[i] = false;
        }
    }
    return;
};

int main(){

    Initial();
    int n;

    while(scanf("%d",&n) != EOF) {
        bool isOutput = false;
        for (int i = 0; i < prime.size() && prime[i]<n; ++i) {
            isOutput = true;
            printf("%d ",prime[i]);
        }
        if(!isOutput){
            printf("-1");
        }
        printf("\n");
    }
    return 0;
}

分解质因数

给定一个数N（1<N<1E9），将其分解为多个质因数相乘

分解质因数，需要用到上题素数筛选法，通过素数筛选法确定 1～sqrt(1E9)+1 之间的素数。

遍历素数序列：用素数取整除 N，如果成功则为N的质因数，输出。直到所有的素数都遍历结束。

遍历结束后需要判断 N 整除前面得到的质因数的结果是否大于1，如果大于一，则存在大于 sqrt(1E9)+1的质因数。需要输出。

（对于N来说之多存在一个大于 sqrt(n）的质因数）

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

const int MAXN = 40000;
bool isPrime[MAXN];
vector<int> prime;

void Initial(){
    for (int i = 0; i < MAXN; ++i) {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for (int j = 2; j < MAXN; ++j) {
        if(!isPrime[j]){
            continue;
        }
        prime.push_back(j);
        for (int i = j*j; i < MAXN; i=i+j) {  //从当前素数j的j倍开始，小于j的倍数由小于j的素数标记其不为素数。i 的值为j的倍数
            isPrime[i] = false;
        }
    }
    return;
};

int main(){

    Initial();
    int n;
    while(scanf("%d",&n) != EOF) {

        for (int i = 0; i < prime.size() && prime[i]<=n; ++i) {
            while(n%prime[i] == 0){
                printf("%d ",prime[i]);
                n /= prime[i];
            }

        }

        if (n > 1){   //未出尽的数大于则是素因数
            printf("%d",n);
        }
        printf("\n");
    }
    return 0;
}

快速幂

对于 a^b 的快速算法思路：

将b分解为若干个2^k的和如： 3^29 , 其中b为29 = 1 + 4 + 8 + 16;

a^b = a^k1 * a^k2 * … * a^km, 3^29 = 3^1 * 3^4 * 3^8 * 3^16;

这样 3^1 = 3
      3^2 = 3^1 * 3^1      一次计算
   
      3^4 = 3^2 * 3^2      二次计算
   
      3^8 = 3^4 * 3^4      三次计算
    
      3^16 = 3^8 * 3^8     四次计算

      3^29 只需要计算四次   普通乘法需要29次

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>

using namespace std;

long long aEb(long a, long b){
    long answer = 1;

    while(b != 0){     
        if(b%2 == 1){
            answer *= a;
        }
        b /= 2;        
        a *= a;  
    }
    return answer;
};


int main(){
    int a,b;
    while(scanf("%d%d",&a,&b) != EOF) {
        printf("%lld",aEb(a,b));
        printf("\n");
    }
    return 0;
}

高精度整数运算C++类是现实

高进度数之所以不好处理的在于无法存储。一般有两种比较常见的处理方式：

用字符串存储

用数组存储

用字符串存储，在编写相应的算术运算实现时，对字符串操作由于字符串的长度不一，两个高进度整数运算时需要考虑具体的处理问题比较多。用数组存储，好处是通过指定存储数组的空间，算术运算实现时，不需要考虑太多运算过程中的数的长度的影响，因为为存储数的数组元素中的大于数长度的部分值置为0，便于大数与小数的运算。确点是需要实现分配容纳数的大量空间，利用效率不一定高。

一下的算法是基于数组存储高进度整数的。数组存储以十进制的方式，从0～MAXN的下标依次存储数的个位、十位、百位、….

高进度整数表示的类定义

const int MAXN  = 10000;  //最大能存储的10进制数的位数

struct BigInteger{
    int digit[MAXN];  //从0～MAXN 存放数字的 个位 十位 百位 ...
    int length;

    BigInteger();
    BigInteger(int x);
    BigInteger(string str);
    BigInteger(const BigInteger& b);
    BigInteger operator=(int x);
    BigInteger operator=(string str);
    BigInteger operator=(const BigInteger& b);
    bool operator<=(const BigInteger& b);
    bool operator==(const BigInteger& b);

    BigInteger operator+(const BigInteger& b);
    BigInteger operator-(const BigInteger& b);
    BigInteger operator*(const BigInteger& b);
    BigInteger operator/(const BigInteger& b);
    BigInteger operator%(const BigInteger& b);

    friend istream& operator>>(istream& in, BigInteger& x);
    friend ostream& operator<<(ostream& out, BigInteger& x);


};

高进度整数类的构造函数实现


BigInteger::BigInteger() {
    memset(digit,0,sizeof(digit));
    length = 0;
}

BigInteger::BigInteger(int x) {
    memset(digit,0, sizeof(digit));
    length = 0;

    if(x == 0){                //对于0的特殊处理
        digit[length++] = x;
    }
    while(x != 0){
        digit[length++] = x%10;
        x /= 10;
    }
}

BigInteger::BigInteger(string str) {
    memset(digit,0, sizeof(digit));
    length = 0;

    for (int i = str.size()-1; i >= 0; --i) {  //注意数组存储的方式从低位到高位
        digit[length++] = str[i]-'0';
    }
}

BigInteger::BigInteger(const BigInteger &b) {
    memset(digit,0,sizeof(digit));
    length = b.length;

    for (int i = 0; i < length; ++i) {
        digit[i] = b.digit[i];
    }
}

赋值运算符的重载

BigInteger BigInteger::operator=(int x) {
    memset(digit,0, sizeof(digit));
    length = 0;

    if(x == 0){
        digit[length++] = x;
    }
    while(x != 0){
        digit[length++] = x%10;
        x /= 10;
    }
    return *this;
}

BigInteger BigInteger::operator=(string str) {
    memset(digit,0, sizeof(digit));
    length = 0;

    for (int i = str.size()-1; i >= 0; --i) {
        digit[length++] = str[i]-'0';
    }
    return *this;
}

BigInteger BigInteger::operator=(const BigInteger &b) {
    memset(digit,0, sizeof(digit));
    length = b.length;

    for (int i = 0; i < length; ++i) {
        digit[i] = b.digit[i];
    }

    return *this;
}

输入、输出运算符重载

istream& operator>>(istream& in,BigInteger &x){
    string str;
    in>>str;
    x = str;
    return in;
}

ostream& operator<<(ostream& out,const BigInteger &x){
    for (int i = x.length-1; i >= 0; --i) {
        out<< x.digit[i];
    }
    return out;
}

高进度正整数的算术运算

a. 比较

bool BigInteger::operator<=(const BigInteger& b){
    if(length < b.length){
        return true;
    }else if(b.length < length){
        return false;
    }else{
        for (int i = length-1; i >= 0; --i) {
            if (digit[i] == b.digit[i]){
                continue;
            }else{
                return digit[i] < b.digit[i];
            }
        }

        return true;
    }
}

bool BigInteger::operator==(const BigInteger &b) {
    if(length != b.length){
        return false;
    }else{
        for (int i = length-1; i >= 0; --i) {
            if (digit[i] != b.digit[i]){
                return false;
            }
        }
    }
    return true;
}

b. 加法

BigInteger BigInteger::operator+(const BigInteger &b) {
    BigInteger answer;
    int carry = 0;
    int bound = length>b.length ? length:b.length;
    for (int i = 0; i < bound; ++i) {
        int temp = digit[i] + b.digit[i] + carry;
        answer.digit[answer.length++] = temp % 10;
        carry = temp / 10;
    }

    if(carry == 1){  //最高位有进位
        answer.digit[answer.length++] = 1;
    }

    return answer;
}

加法运算比较简单，以两个数中最大的长度为遍历边界，对于每一位进行加和，留下和中小于10的部分，大于10的作为进位，加入高位的求和中。

注意：两数的每一位遍历加和完成后，要判断最高位是否有进位（即进位的标记是否为1），如果有进位，则求和的结果在最高位前补1；

c. 乘法

BigInteger BigInteger::operator*(const BigInteger &b) {
    BigInteger answer;
    int carry = 0;
    answer.length = length + b.length;
    for (int i = 0; i < length;  ++i) {                 //模拟：每位与乘数每一位运算后的，同权的位结果求和
        for (int j = 0; j < b.length; ++j) {
            answer.digit[i+j] += digit[i] * b.digit[j];
        }
    }

    for (int k = 0; k < answer.length; ++k) {           //对于answer结果中的每一位超过10的进行修正进位
        answer.digit[k+1] += answer.digit[k] / 10;
        answer.digit[k] %= 10;
    }

    while(answer.digit[answer.length-1] == 0 && answer.length > 1){   //消除结果中多余的0
        answer.length--;
    }

    return answer;
}

乘法：稍微复杂一点

模拟手动计算乘法的过程，即将乘数的从最低位一次去乘被乘数，要注意一个细节： 乘数的第i位 * 被乘数的第j位 = 结果的第(i+j)位。将对应结果的权值相同的位加起来。

此时等到的结果中，每一位的值都可能大于10，需要对这些位做调整，将大于10的部分进位到高位，留下小于10的部分作为当前位的值。

乘法结果中可能存在连续多个高位到最高位为0，需要去除多余的0.否则对于根据数字有效长度判断大小的函数，会产生错误的比较结果。（如： 000 > 0）

d.减法

BigInteger BigInteger::operator-(const BigInteger &b) {     //只使用于大数减小数的减法
    BigInteger answer;
    //大数为this指向的对象，b为小数的对象
    int carry = 0;
    int bound = length;
    for (int i = 0; i < bound; ++i) {
        int temp = digit[i] - b.digit[i] - carry;
        if (temp >= 0){         // 如果 被减数 大于等于 (减数+借位)则不需要进位
            answer.digit[answer.length++] = temp;
            carry = 0;   // 如果没有借位需要把carry从1置为0否则会影响以后计算的结果
        }else{
            answer.digit[answer.length++]  = 10 + temp;
            carry = 1;
        }
    }

    while(answer.digit[answer.length-1] == 0 && answer.length > 1){  //去除结果中多余的0
        answer.length--;
    }
    return answer;
}

减法：
从被减数的低位到高位：依次减去（减数对应权的位+低位相当前位的借位）。减后结果有两种情况：

结果<0 ,此时就需要向高位借位。结果+10 修正，借位置1

结果>=0,此时结果无需修正，但是注意要将借位位置为0
减法同样需要对于结果中多余的0进行修正

e. 除法

BigInteger BigInteger::operator/(const BigInteger &b) {
    BigInteger answer;
    answer.length = length;
    BigInteger remainder = 0;
    BigInteger temp = b;   // temp 存在的意义在于 比较运算符 <= 前的对象不能是const 类型。
    for (int i = length-1; i >= 0; --i) {

        if (!(remainder.length == 1 && remainder.digit[0] == 0)){   //余数不为0
            for (int j = remainder.length-1; j >= 0; --j) {  //高位余数右移（向高位的方向移动）
                remainder.digit[j+1] = remainder.digit[j];
            }
            remainder.length++;
        }

        remainder.digit[0] = digit[i]; //当前位并如余数中 ，成为新的被除对象
        while(temp <= remainder){        //除操作
            remainder = remainder - temp;
            answer.digit[i]++;
        }
    }
    while (answer.digit[answer.length-1] == 0 && answer.length > 1){
        answer.length--;
    }

    return answer;
}

除法的操作：与加法、减法、乘法的不同之处在于，除法运算是从高位到低位的顺序
遍历被除数的每一位：

高位的余数*10（右移一位）与当前位并入，作为新的被除对象。

对于被除对象的除操作可以表达为：对被处对象不断的减去除数，对于最终商的当前位置不断加1，直到被除对象小于除数。此时被处对象的值就是当前位余数的值

遍历被除数的下一位

f. 取余
取余操作是与除法紧密相关的操作，即除法最终的余数，即位所求。
因此，取余的算法几乎与除法算法相同，只是移除了不需要保存的除法的商。

BigInteger BigInteger::operator%(const BigInteger &b) {
    BigInteger remainder = 0;
    BigInteger temp = b;   // temp 存在的意义在于 比较运算符 <= 前的对象不能是const 类型。
    for (int i = length-1; i >= 0; --i) {

        if (!(remainder.length == 1 && remainder.digit[0] == 0)){   
            for (int j = remainder.length-1; j >= 0; --j) {
                remainder.digit[j+1] = remainder.digit[j];
            }
            remainder.length++;
        }

        remainder.digit[0] = digit[i];
        while(temp <= remainder){
            remainder = remainder - temp;
        }

    }
    return remainder;

}