10702

题目

[M5.7**] 输入 $n(n<10000)$ ，通过割圆术计算圆周率精确到小数点后 $n$ 位的值。

解析

马青公式：

$$\frac{\pi }{4}=4\arctan \frac{1}{5}-\arctan \frac{1}{239}$$

结合反正切函数的泰勒级数展开：

$$\arctan (x)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\cdots$$

答案

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

long g_base = 10000;

void clear_big_num(long *a, int size) {
    for (int i = 0; i < size; i++) {
        a[i] = 0;
    }
}

void print_big_num(long *a, int n) {
    printf("%ld.", a[0]);
    for (int i = 1; i <= n / 4; i++) {
        printf("%04ld", a[i]);
    }
    printf("\n");
}

void copy_big_num(long *dest, long *src, int size) {
    memcpy(dest, src, size * sizeof(long));
}

void add_big_num(long *a, long *b, long *result, int size) {
    long carry = 0;
    for (int i = size - 1; i >= 0; i--) {
        result[i] = a[i] + b[i] + carry;
        if (result[i] >= g_base) {
            carry = result[i] / g_base;
            result[i] %= g_base;
        } else {
            carry = 0;
        }
    }
}

void sub_big_num(long *a, long *b, long *result, int size) {
    long borrow = 0;
    for (int i = size - 1; i >= 0; i--) {
        result[i] = a[i] - b[i] - borrow;
        if (result[i] < 0) {
            borrow = 1;
            result[i] += g_base;
        } else {
            borrow = 0;
        }
    }
}

void mul_small_num(long *a, int multiplier, long *result, int size) {
    long carry = 0;
    for (int i = size - 1; i >= 0; i--) {
        long temp = a[i] * multiplier + carry;
        result[i] = temp % g_base;
        carry = temp / g_base;
    }
}

void div_small_num(long *a, int divisor, long *result, int size) {
    long remainder = 0;
    for (int i = 0; i < size; i++) {
        long temp = a[i] + remainder * g_base;
        result[i] = temp / divisor;
        remainder = temp % divisor;
    }
}

void calc_arctan_series(int inverse_x, int size, long *result) {
    int inverse_x_sq = inverse_x * inverse_x;
    long *term = (long *)malloc(size * sizeof(long));
    long *temp_term = (long *)malloc(size * sizeof(long));

    clear_big_num(result, size);
    clear_big_num(term, size);

    term[0] = g_base / inverse_x;
    copy_big_num(result, term, size);

    for (int k = 3; ; k += 2) {
        div_small_num(term, inverse_x_sq, term, size);

        copy_big_num(temp_term, term, size);
        div_small_num(temp_term, k, temp_term, size);

        if ( (k / 2) % 2 == 1 ) {
            sub_big_num(result, temp_term, result, size);
        } else {
            add_big_num(result, temp_term, result, size);
        }

        int is_zero = 1;
        for(int i = 0; i < size; i++) {
            if(term[i] != 0) {
                is_zero = 0;
                break;
            }
        }
        if (is_zero) {
            break;
        }
    }

    free(term);
    free(temp_term);
}

int main() {
    int n;
    scanf("%d", &n);

    int array_size = n / 4 + 4;

    long *pi = (long *)malloc(array_size * sizeof(long));
    long *term1 = (long *)malloc(array_size * sizeof(long));
    long *term2 = (long *)malloc(array_size * sizeof(long));
    long *temp = (long *)malloc(array_size * sizeof(long));

    calc_arctan_series(5, array_size, temp);
    mul_small_num(temp, 4, term1, array_size);

    calc_arctan_series(239, array_size, temp);
    mul_small_num(temp, 1, term2, array_size);

    sub_big_num(term1, term2, pi, array_size);
    mul_small_num(pi, 4, pi, array_size);

    print_big_num(pi, n);

    free(pi);
    free(term1);
    free(term2);
    free(temp);

    return 0;
}