机试-数学问题

王道机试
算法
发布日期:   2018-07-16
文章字数:   2.3k

数位拆解

  • 例4.1 特殊乘法
#include<stdio.h>
int main(){
    int a,b;
    while(scanf("%d%d", &a, &b) != EOF){
        int buf1[20], buf2[20], size1 = 0, size2 = 0;
        while (a!=0){
            buf1[size1++] = a % 10;
            a /= 10;
        }
        while (b!=0){
            buf2[size2++] = b % 10;
            b /= 10;
        }
        int ans = 0;
        for (int i=0;i<size1;i++){
            for (int j=0;j<size2;j++){
                ans += buf1[i] * buf2[j];
            }
        }
        printf("%d", ans);
    }
    return 0;
}

进制转换

  • 例4.2 输出 A+B 的 m 进制数

使用 long long 来防止溢出。

#include<stdio.h>
int main(){
    int m;
    long long a, b;        //    确保不会溢出
    while (scanf("%d", &m) != EOF){
        if(m == 0)
            break;
        scanf("%lld%lld", &a, &b);
        a = a + b;
        int ans[50], size = 0;
        // while (a!=0){
        //     ans[size++] = a % m;
        //     a /= m;
        // }
        // 需要用 do while 循环， 防止测试用例出现 0 
        do{
            ans[size++] = a % m;
            a /= m;
        }while(a!=0);
        for (int i=size-1;i>=0;i--){
            printf("%d", ans[i]);
        }
        printf("\n");
    }
    return 0;
}
  • 例4.3 数制转换

将 n 进制数 a，转换成 b 进制数：首先将 n 进制转化成十进制，然后将此十进制转化为 b 进制。

#include<stdio.h>
#include<string.h>
int main(){
    int a, b;
    char str[40];
    while(scanf("%d%s%d", &a, str, &b) != EOF){
        int tmp = 0, length = strlen(str), c = 1;
        for (int i=length-1;i>=0;i--){
            int x;
            if (str[i] >= '0' && str[i] <= '9'){
                x = str[i] - '0';
            } 
            else if (str[i] >= 'a' && str[i] <= 'b'){
                x = str[i] - 'a' + 10;
            }
            else
                x = str[i] - 'A' + 10;
            tmp += x * c;
            c *= a;
        }

        char ans[40], size = 0;
        do{
            int x=tmp % b;
            ans[size++] = (x<10) ? x+'0':x-10+'A';
            tmp /= b;
        }while(tmp!=0);
        for(int i=size-1;i>=0;i--){
            printf("%c", ans[i]);
        }
        printf("\n");
    }
    return 0;
}

最大公约数

a,b的最大公约数同时也是 b,a mod b 的最大公约数。

我们不断重复这个过程，直到出现某个非0数和0，则该非0数即为最大公约数。

例4.4 最大公约数

#include<stdio.h>
int gcd(int a, int b){
    if (b==0)
        return a;
    else
        return gcd(b, a%b);
}

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

最小公倍数

a，b两数的最小公倍数为两数的乘积除以他们的最大公约数。

  • 例4.5 最小公倍数
#include<stdio.h>
int gcd(int a, int b){
    return b!=0 ? gcd(b, a%b):a;
}

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

素数筛法

判断整数 n 是否为素数，我们只需测试到 sqrt(n) 即可。若 n 不存在大于 sqrt(n) 的因数时，显然正确，若存在大于等于 sqrt(n) 的因数 y，则 z=n/y 必同时为 n 的因数，且其值小于等于 sqrt(n)，所以我们只需要测试到 sqrt(n)。

如何找出 0-1000000 中的所有素数？可以采用素数筛法，在获得一个素数时，将它所有的倍数都标记为非素数。

  • 例4.7 素数
#include<stdio.h>
int prime[10000];        //保存筛选出的素数
int primeSize;
bool mark[10001];        //若 mark[x] 为 true ,则表示该数 x 已被标记成非素数

void init(){
    for (int i=0;i<=10000;i++){
        mark[i] = false;
    }
    primeSize = 0;
    for (int i=2;i<=10000;i++){
        if (mark[i] == true)
            continue;
        prime[primeSize++] = i;
        for (int j=i*i;j<=10000;j+=i){
            mark[j] = true;
        }
    }
}

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

n

分解素因数

对一个 //(x//) 分解素因数即确定素数 //(p_1, p_2,…p_n//) 使其满足下式：

$$x = p_1^{e1}p_2^{e2}…p_n^{en}$$

除了素数，还要确定幂指数。

  • 例4.8 质因数的个数
#include<stdio.h>
bool mark[100001];
int prime[100001];
int primeSize;

void init(){
    primeSize = 0;
    for (int i=2;i<=10000;i++){
        if (mark[i] == true)
            continue;
        prime[primeSize++] = i; 
        for (int j=i*i;j<=10000;j+=i){
            mark[j] = true;
        }
    }
}

int main(){
    init();
    int n;
    while (scanf("%d", &n) != EOF){
        int ansPrime[30];
        int ansSize = 0;
        int ansNum[30];
        for(int i =0;i<primeSize;i++){
            if(n%prime[i] == 0){
                ansPrime[ansSize] = prime[i];
                ansNum[ansSize] = 0;
                while(n%prime[i] == 0){
                    ansNum[ansSize]++;
                    n /= prime[i];
                    // printf("%d", prime[i]);
                }
                ansSize++;
                if (n==1)
                    break;
            }
        }
        if(n!=1){
            ansPrime[ansSize] = n;
            ansNum[ansSize++] = 1;
        }
        int ans = 0;
        for(int i=0;i<ansSize;i++){
            ans += ansNum[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}
  • 例4.9 整除问题

给定n,a 求最大的 k 使得 n! 可以被 a^k 整除但不能被 a^(k+1) 整除。

n! 和 a^k 可能非常大，甚至不能用 long long 类型来保存，无法直接求余判断是否存在整除关系

二分求幂

  • 例4.10 人见人爱 A^B

求 A^B 的最后三位数表示的整数，A^B可能非常大，不容易保存，而我们注意到 A^B 的后三位数只与 A 的后三位数和 B 有关，所以我们在计算过程中只需要保存中间结果的后三位。

以2^31为例，了解二分求幂：

$$2^{31}=2^12^22^42^82^{16}$$

#include<stdio.h>
int main(){
    int a,b;
    while(scanf("%d%d", &a, &b) != EOF){
        if (a == 0 && b == 0)
            break;
        int ans = 1;
        while(b!=0){
            if(b%2 == 1){
                ans *= a;
                ans %= 1000;
            }
            b /= 2;
            a *= a;
            a %= 1000;
        }
        printf("%d\n", ans);
    }
    return 0;
}

高精度整数

我们通常用一个结构体来保存高精度整数：

struct bigInteger{
    int digit[1000];
    int size;
}

digit 数组用来保存大整数中每若干位的数字，我们这里使用每 4 位为一个单位保存，size 为 digit数组中第一个我们还没使用过的数组单元，如 123456789，digit[0]=6789,digit[1]=2345,digit[2]=1,size=3。

  • 例4.11 a+b
#include<stdio.h>
#include<string.h>

struct bigInteger{
    // 高精度整数结构体
    int digit[1000];
    int size;        //下一个我们未使用的数组单元

    void init(){
        for (int i=0;i<1000;i++){
            digit[i] = 0;
            size = 0;
        }
    }

    void set(char str[]){
        init();
        int L = strlen(str);
        for (int i=L-1, j=0, t=0, c=1;i>=0;i--){
            // j控制每四个字符转换为一个数字，t临时保存字符转换为数字的中间值，c 表示当前位的权重
            t += (str[i] - '0') * c;
            j++;
            c *= 10;
            if (j == 4 || i == 0){
                c = 1;
                digit[size++] = t;
                j = 0;
                t = 0; 
            }

        }
    }

    void output(){
        for (int i=size-1;i>=0;i--){
            if (i!=size-1)
                printf("%04d", digit[i]);
            else
                printf("%d", digit[i]);
        }
    }

    bigInteger operator + (const bigInteger &A) const{
        // 加法运算符重构
        bigInteger ret;
        ret.init();
        int jinwei = 0; // 进位
        for (int i=0;i<A.size || i<size;i++){
            int tmp = A.digit[i] + digit[i] + jinwei;
            jinwei = tmp / 10000;
            ret.digit[ret.size++] = tmp % 10000;
        }
        if (jinwei != 0){
            ret.digit[ret.size++] = jinwei;
        }
        return ret;
    }
}a,b,c;

char str1[1000], str2[1000];
int main(){
    while (scanf("%s%s", str1, str2) != EOF){
        a.set(str1);
        b.set(str2);
        c = a + b;
        c.output();
    }
    return 0;
}

下面讨论高精度乘法，这里主要讨论高精度整数乘以一般小整数的运算。

  • 例4.12 N 的阶乘

输入的数据可能不大，但是输出的结果可能非常大

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

struct bigInteger
{
    int digit[1000];
    int size;
    void init(){
        for (int i=0;i<1000;i++){
            digit[i] = 0;
        }
        size = 0;
    }

    void set(int x){
        init();
        do{
            digit[size++] = x % 10000;
            x /= 10000;
        }while(x!=0);
    }

    void output(){
        for (int i=size-1;i>=0;i--){
            if (i!=size-1)
                printf("%04d", digit[i]);
            else
                printf("%d", digit[i]);
        }
        printf("\n");
    }

    bigInteger operator * (int x) const{
        bigInteger ret;
        ret.init();
        int jinwei = 0;
        for (int i=0;i<size;i++){
            int tmp = x * digit[i] +jinwei;
            jinwei = tmp / 10000;
            tmp %= 10000;
            ret.digit[ret.size++] = tmp;
        }
        if (jinwei != 0){
            ret.digit[ret.size++] = jinwei;
        }
        return ret;
    }
}a;

int main(){
    int n;
    while (scanf("%d", &n) != EOF){
        a.init();
        // a.set(1);
        a.digit[0] = 1;
        a.size = 1;
        for (int i=1;i<=n;i++){
            a = a * i; 
        }
        a.output();
    }
    return 0;
}
  • 例4.13 进制转换

大数的进制转化，将 M 进制的整数 x 转换为 N 进制的数，这其中涉及到高精度整数与普通整数的求积，高精度整数之间的求和，高精度整数除以普通整数，高精度整数对普通整数求模等。

#include<stdio.h>
#include<string.h>
#define maxDigits 100
struct bigInteger{
    int digits[maxDigits];
    int size;
    void init(){
        for (int i=0;i<maxDigits;i++){
            digits[i] = 0;
        }
        size = 0;
    }

    void set(int x){
        init();
        do{
            digits[size++] = x % 10000;
            x /= 10000;
        }while(x!=0);
    }

    void output(){
        for (int i=size-1;i>=0;i--){
            if (i!=size-1)
                printf("%04d",digits[i]);
            else
                printf("%d", digits[i]);
        }
        printf("\n");
    }

    bigInteger operator * (int x) const{
        bigInteger ret;
        ret.init();
        int jinwei = 0;
        for (int i=0;i<size;i++){
            int tmp = x*digits[i] + jinwei;
            jinwei = tmp / 10000;
            tmp %= 10000;
            ret.digits[ret.size++] = tmp;
        }
        if (jinwei!=0)
            ret.digits[ret.size++] = jinwei;
        return ret;
    }

    bigInteger operator + (const bigInteger &A) const{
        bigInteger ret;
        ret.init();
        int jinwei = 0;
        for (int i=0;i<A.size || i<size;i++){
            int tmp = A.digits[i] + digits[i] + jinwei;
            jinwei = tmp / 10000;
            tmp %= 10000;
            ret.digits[ret.size++] = tmp;
        }
        if (jinwei!=0)
            ret.digits[ret.size++] = jinwei;
        return ret;
    }

    bigInteger operator / (int x) const {
        bigInteger ret;
        ret.init();
        int yushu = 0;
        for (int i=size-1;i>=0;i--){
            int t = (yushu * 10000 + digits[i]) / x;
            int r = (yushu * 10000 + digits[i]) % x;
            ret.digits[i] = t;
            yushu = r;
        }
        ret.size = 0;
        for (int i=0;i<maxDigits;i++){
            if (digits[i]!=0)
                ret.size = i;
        }
        ret.size++;
        return ret;
    }

    int operator % (int x) const {
        int yushu = 0;
        for (int i=size-1;i>=0;i--){
            int t = (yushu * 10000 + digits[i]) / x;
            int r = (yushu * 10000 + digits[i]) % x;
            yushu = r;
        }
        return yushu;
    }
}a,b,c;

char str[10000];
char ans[10000];
int main(){
    int n,m;
    while (scanf("%d%d", &m, &n) != EOF){
        scanf("%s", str);
        int L = strlen(str);
        a.set(0);    //用来保存转换成 10 进制的 m 进制数
        b.set(1);    // 转换过程中每一位的权重

        for (int i=L-1;i>=0;i--){
            int t;
            if (str[i] >= '0' && str[i] <= '9')
                t = str[i] - '0';
            else
                t = str[i] - 'A' + 10;
            a = a + b * t;
            b = b * m;
            // b.output();
        }
        int size = 0;
        do{
            //将10进制转换成 n 进制
            int t = a % n;
            if (t>=10)
                ans[size++] = t - 10 + 'a';
            else
                ans[size++] = t + '0';
            a = a / n;
            // a.output();
        }while(a.digits[0] != 0 || a.size != 1);

        for (int i=size-1;i>=0;i--){
            printf("%c", ans[i]);
        }
        printf("\n");
    }
    return 0;
}
文章作者: lovelyfrog
文章链接: http://lovelyfrog.github.io/2018/07/16/wangdaojishi3/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 lovelyfrog !
王道机试
 上一篇
机试-图论 机试-图论
预备知识我们可以用标准库(STL)中的标准模版 std::vector 来使用邻接链表。 首先定义一个结构体，包括邻接结点和边权值 struct Edge{ int nextNode; int cost; }; 为每个结
2018-07-18 算法
王道机试
下一篇 
机试-数据结构 机试-数据结构
一.栈的应用堆栈是一种数据项按序排列的数据结构，使用 stack 标准模版需要加上头文件 #include ，并使用标准命名空间。 用 stack S，定义一个保存元素类型为int的堆栈 S S.push(i) 向堆栈中压进一个数值为
2018-07-15 算法
王道机试
  目录