NOJ数据结构实验002——高精度计算PI值

爱被打了一巴掌 2022-10-22 05:26 144阅读 0赞

题目及要求![ji][]  
解题思路：  
使用泰勒展开将题目可视化。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
通过双向循环链表的存储结构计算a，即先算k\* a（k-1）再算 k\* a(k-1)/(2k+1)，并将此数据放入链表num中，之后将num与sum两个链表所表示的数据相加，不断重复上述过程，计算次数越多越精确。  
在本题中，笔者限于实力，只能先将PI值进行许多次计算，再在输出时截断至所需位数。这对时间或空间来说都是一场灾难。大佬则可根据下图来确定每次所需计算次数来节省时间和空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]  
代码：

#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;
    }

[ji]: /images/20221022/3429d70384b54e77aa66b8f7b287214b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221022/bb5cf4da93544a0aa636a16ed7f0668a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/4a73fac6c99741b89e935ad65f27fd86.png