博客

题目及要求


解题思路：

使用泰勒展开将题目可视化。



通过双向循环链表的存储结构计算a，即先算k* a（k-1）再算 k* a(k-1)/(2k+1)，并将此数据放入链表num中，之后将num与sum两个链表所表示的数据相加，不断重复上述过程，计算次数越多越精确。

在本题中，笔者限于实力，只能先将PI值进行许多次计算，再在输出时截断至所需位数。这对时间或空间来说都是一场灾难。大佬则可根据下图来确定每次所需计算次数来节省时间和空间。



代码：

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

typedef struct Node{
    int data;
    struct Node *pre;
    struct Node *next;
}Node, *LinkList;

 LinkList num, sum;

LinkList InitList ();                    //初始化链表
void ExtendList(LinkList m, int data);  //延长链表
void MulList(LinkList L, int son);      //乘法
void DivList(LinkList m, int mother);   //除法
void AddList(LinkList m, LinkList n);   //加法
void PrintList(LinkList m, int n);      //输出链表数据
void DesList(LinkList m);               //销毁链表

int main()
{
    int n;
    scanf("%d", &n);
    num = InitList ();//num储存每次运算结果
    sum = InitList ();//sum储存最终结果
    for (int i = 0; i < 600; i++) {
        //使两者可储存足够多的位数
        ExtendList(num,0);
        ExtendList(sum,0);
    }
    for (int j = 1, k = 3; j < 2000; j++) {
        MulList(num, j);  //乘
        DivList(num, k);  //除
        AddList(num, sum);//加
        k += 2;
    }
    PrintList(sum, n);     //输出
    DesList(num);//销毁两者
    DesList(sum);
    return 0;
}

LinkList InitList ()
{     //初始化链表
    LinkList m;
    m = (LinkList) malloc (sizeof(Node));
    m -> data = 2;
    m -> pre = m;
    m -> next = m;
    return m;
}

void ExtendList(LinkList m, int data)
{    //延长链表
    LinkList tmp, s;
    tmp = m;
    if(tmp == NULL){
        return;
    }
    tmp = tmp -> pre;
    s = (LinkList) malloc (sizeof(Node));
    s -> data = data;
    s -> next = tmp -> next;
    s -> pre = tmp;
    tmp -> next -> pre = s;
    tmp -> next = s;
}

void MulList(LinkList m, int son)
{       //乘法
    int tmp, ret = 0;
    LinkList p;
    p = m -> pre;
    while(p != m) {
        tmp = p -> data * son + ret;
        p -> data = tmp % 10;
        ret = tmp /10;   //进位
        p = p ->pre;
    }
    p -> data += ret;

}

void DivList(LinkList m, int mother)
{       //除法
    int tmp, ret = 0;
    LinkList p;
    p = m;
    while(1) {
        tmp = p -> data + ret * 10;
        ret = tmp % mother;  //余数
        p -> data = tmp / mother;
        p = p -> next;
        if(p == m) break;
    }
}

void AddList(LinkList m, LinkList n)
{     //加法
    int tmp, ret = 0;
    LinkList p, q;
    p = m -> pre;
    q = n -> pre;
    while (1){
        tmp = p->data + q->data + ret;
        q -> data = tmp % 10;
        ret = tmp / 10;
        p = p -> pre;
        q = q -> pre;
        if(p == m -> pre)  break;
    }
}

void PrintList(LinkList m, int n)
{     //输出链表数据
    LinkList p;
    p = m;
    printf("%d.", p -> data);
    p = p -> next;
    for (int i = 0; i < n; i++) {
        printf("%d", p -> data);
        p = p -> next;
    }
    printf("\n");
}

void DesList(LinkList m)
{    //销毁链表
    LinkList tmp;
    tmp = m -> next;
    while(tmp != m) {
        m -> next = tmp -> next;
        free(tmp);
        tmp = m -> next;
    }
    m -> pre = m;
    free(m);
    m = NULL;
}