算法设计与分析：大整数的加减乘除运算

为了完成本关任务，你需要掌握：1.大整数的思想，2.大整数加法，3.大整数减法，4.大整数与整数的乘法，5.大整数乘法，6.大整数与整数的除法，7.n的阶乘求解思路。

Shining0596

3236人浏览 · 2023-05-11 19:47:46

Shining0596 · 2023-05-11 19:47:46 发布

任务描述

本关任务：掌握大整数的基本思想，并运用大整数的基本运算计算出常规整数n的阶乘，然后统计大整数n!中数字0的个数。

测试说明

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确，测试数据保证10001>n>0。

以下是平台的测试样例：

测试输入： 10 预期输出： 2

输入格式： 第1行：整数n 输出格式： 第1行：n!中数字0的个数

Tips：注意整数乘法越界的情况

//
//  main.cpp
//  step1
//
//  Created by ljpc on 2018/12/4.
//  Copyright © 2018年 ljpc. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

// 最大长度N，分块长度K
const int N = 10001;
const int K = 10000;
const int T = (int)log10(K); // K=10000, T=4

void char_to_int(char *s, int *c)
{
    // *s = 1234567890
    // *c = 0000 .... 0012 3456 7890 (K=10000, T=4, c[0] c[1] .... c[N-2] c[N-1])
    // i  = 0         N-3  N-2  N-1  (c的下标索引i)
    int L = (int)strlen(s);
    for (int i=N-1; i>=0; i--) {
        c[i] = 0;
        if (L>=0) {
            for (int j=0; j<T; j++) {
                if (L-T+j < 0) {
                    continue;
                }
                c[i] = c[i] * 10 + s[L-T+j] - '0';
            }
            L -= T;
        }
    }
}

void output(int *c)
{
    // *c = 0000 .... 0012 3456 7890 (K=10000, T=4, c[0] c[1] .... c[N-2] c[N-1])
    // i  = 0         N-3  N-2  N-1  (c的下标索引i)
    // out= 1234567890
    bool flag = true;
    for (int i=0; i<N; i++) {
        if (flag && c[i]==0) {
            continue;
        }
        if (flag) { // 第一个非0数字：大数的头块
            printf("%d", c[i]);
            flag = false;
        }
        else { // 大数头块之后的 T 数字块
            int TK = K/10;
            int tmp = c[i];
            while (TK) {
                printf("%d", tmp/TK);
                tmp %= TK;
                TK /= 10;
            }
        }
    }
    printf("\n");
}

void add(int *a, int *b, int *c)
{
    int carry = 0;
    for (int i=N-1; i>=0; i--) {
        c[i] = 0;
        c[i] = a[i] + b[i] + carry;
        carry = c[i] / K;
        c[i] = c[i] % K;
    }
    
}

void sub(int *a, int *b, int *c)
{
    int borrow = 0;
    for (int i=N-1; i>=0; i--) {
        c[i] = 0;
        c[i] = a[i] - b[i] - borrow;
        if (c[i] >= 0) {
            borrow = 0;
        }
        else {
            c[i] = c[i] + K;
            borrow = 1;
        }
    }
    
}

void mul1(int *a, int b, int *c)
{
    long long tmp = 0;
    int carry = 0;
    for (int i=N-1; i>=0; i--) {
        tmp = (long long)a[i] * (long long)b + (long long)carry;
        c[i] = (int)(tmp % K);
        carry = (int)(tmp / K);
    }
    
}

void mul2(int *a, int *b, int *c)
{
    long long tmp = 0;
    int carry = 0;
    for (int i=N-1; i>=0; i--) {
        c[i] = 0;
    }
    for (int i=N-1; i>=0; i--) { // b[i]
        carry = 0;
        for (int j=N-1, idc=i; j>=0&&idc>=0; j--, idc--) { // a[j]
            tmp = (long long)a[j] * (long long)b[i] + (long long)carry + (long long)c[idc];
            c[idc] = (int)(tmp % K);
            carry = (int)(tmp / K);
        }
    }
    
}

int div(int *a, int b, int *c)
{
    long long tmp = 0;
    int remain = 0;
    for (int i=0; i<N; i++) {
        tmp = (long long)a[i] + (long long)remain * (long long)K;
        c[i] = (int)(tmp / b);
        remain = (int)(tmp % b);
    }
    return remain;
    
}

int calc(int n)
{
    // 请在这里补充代码，完成本关任务
    /********* Begin *********/
    int a[N] = {0};
    int c[N] = {0};
    a[N-1] = 1;
    for (int i=2; i<=n; i++) {
        mul1(a, i, c);
        for (int j=0; j<N; j++) {
            a[j] = c[j];
            c[j] = 0;
        }
    }
    int tot = 0;
    /*  方法一
    while (1) {
        bool flag = true;
        for (int i=0; i<N; i++) {
            if (a[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            break;
        }
        int r = div(a, 10, c);
        if (r==0) {
            tot++;
        }
        // a = 10 * c + r
        for (int j=0; j<N; j++) {
            a[j] = c[j];
            c[j] = 0;
        }
    }
     */
    // 方法二
    int tmp = 0;
    bool flag = true;
    for (int i=0; i<N; i++) {
        if (flag && a[i]==0) {
            continue;
        }
        if (flag) {
            tmp = a[i];
            flag = false;
        }
        else {
            tmp = a[i] + K;
        }
        while (tmp) {
            if (tmp % 10 == 0) {
                tot++;
            }
            tmp /= 10;
        }
    }
    
    return tot;
    
    
 
    /********* End *********/
}

int main(int argc, const char * argv[]) {
    
    int n;
    
    scanf("%d", &n);
    
    int tot = calc(n);
    printf("%d\n", tot);

    return 0;
}