一元稀疏多项式的计算
2024-12-27 20:44:37 # 学点什么

什么是一元稀疏多项式？

是指只有一个未知数，且多项式中非零系数项的数量远少于总项数的多项式。其一般形式可以表示为：P(x) = anx^n + a{n-1}x^{n-1} + … + a_1x + a_0，其中n为多项式的最高次数，a_i为第i项的系数，且大部分a_i为0。

将项抽象为一个类后，不难发现，需要处理到的难点有：将输入、输出时字符串与类的相互转换，运算符优先级和括号的匹配，以及数学建模。用到的C++特性有：类、模板、栈、运算符重载、构造函数和析构函数。最终的功能实现有：多项式间的加、减、乘、除，任意阶微分和部分多项式的任意阶积分。（不考虑-1阶幂函数的求积分）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//util.h
#pragma once
#include <string>
#include <vector>
#include <sstream>
#include "polynomial.h"
#include "mstack.hpp"
#include <regex>

std::string polynomialToString(Polynomial p);
Polynomial singleStringToPolynomial(std::string s);
Polynomial mainParse(std::string &s);
//terms.h
#pragma once

class Term // 项
{
public:
    Term();
    Term(double c, int e);
    double coefficient = 0; // 系数
    int exponent = 0;    // 指数
    Term* front = nullptr;
    Term* next = nullptr;

};
//Polynomial.h
#pragma once
#include "term.h"

class Polynomial {
  int n = 0;
  Term *head = nullptr;
  Term *tail = new Term(0, 0);

public:
  ~Polynomial();

  bool put(double coefficient, int exponent);

  void update(double coefficient, int exponent);

  void clear();

  int size();

  void normalize();

  Term *getHead();

  Term *getTail();

  Polynomial calc(int n);

  Polynomial diff(int n);

  Polynomial operator+(Polynomial &p);

  Polynomial operator-(Polynomial &p);

  Polynomial operator*(Polynomial &p);

  Polynomial operator/(Polynomial &p);

  Polynomial &operator=(Polynomial &p);
};

#include "calc.h"
//cal.h
#pragma once
#include "polynomial.h"
#include "term.h"

Polynomial addOrSub(Polynomial &a, Polynomial &b, bool add);

Polynomial mul(Polynomial &a, Polynomial &b);

Polynomial div(Polynomial a, Polynomial &b);

Polynomial ccalc(Polynomial &a, int n);

Polynomial cdiff(Polynomial &a, int n);

//mstack.hpp
#pragma once
#include <iostream>

template<typename Ty>
class Mstack
{
public:


    void push(Ty x){
        //arr[++topPos] = x;
        arr.push_back(x);
    }

    Ty top(){
        if (arr.empty()) {
            throw "xxx";
        }
        //return arr[topPos];
        return arr.back();
    }

    void pop(){
        // if (topPos >= 0) {
        //     topPos--;
        // }
        arr.pop_back();
    }
    bool empty() {
        //return topPos == -1;
        return arr.empty();
    }

    void clear() {
        //topPos = -1;
        arr.clear();
    }
private:
    //Ty arr[5]{}; //1000
    std::vector<Ty> arr;
    //int topPos = -1;
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
                                           //plcynomail.cpp
#include "polynomial.h"
#include "calc.h"

Polynomial::~Polynomial() {
  // clear();
  // delete tail;
}

bool Polynomial::put(double coefficient, int exponent) {
  Term *node = new Term(coefficient, exponent);
  if (head == nullptr) {
    head = node;
    head->next = tail;
    tail->front = head;
    n++;
    return true;
  }
  for (Term *term = getHead(); term != tail; term = term->next) {
    if (term->exponent < exponent) {
      if (term->front != nullptr) {
        node->front = term->front;
        node->next = term;
        term->front->next = node;
        term->front = node;
      } else {
        node->next = head;
        head->front = node;
        head = node;
      }
      n++;
      return true;
    }
    if (term->exponent == exponent)
      return false;
  }

  node->front = tail->front;
  node->next = tail;
  tail->front->next = node;
  tail->front = node;
  n++;
  return true;
}

void Polynomial::update(double coefficient, int exponent) {
  Term *node = new Term(coefficient, exponent);
  if (head == nullptr) {
    head = node;
    head->next = tail;
    tail->front = head;
    n++;
    return;
  }
  for (Term *term = getHead(); term != tail; term = term->next) {
    if (term->exponent < exponent) {
      if (term->front != nullptr) {
        node->front = term->front;
        node->next = term;
        term->front->next = node;
        term->front = node;
      } else {
        node->next = head;
        head->front = node;
        head = node;
      }
      n++;
      return;
    }
    if (term->exponent == exponent) {
      term->coefficient += coefficient;
      if (term->front->coefficient > -0.0000000005 &&
          term->front->coefficient < 0.000000000) {
        if (term == head)
          head = term->next;
        else
          term->front->next = term->next, term->next->front = term->front;
        delete term;
      }
      return;
    }
  }

  node->front = tail->front;
  node->next = tail;
  tail->front->next = node;
  tail->front = node;
  n++;
}

void Polynomial::clear() {
  n = 0;
  for (Term *node = getHead(); node != nullptr && node != tail;) {
    node = node->next;
    delete node->front;
  }
}

int Polynomial::size() { return n; }

void Polynomial::normalize() {
  for (Term *node = getHead(); node != nullptr && node != tail;) {
    node = node->next;
    if (node->front->coefficient > -0.0000000005 &&
        node->front->coefficient < 0.0000000005) {
      Term *term = node->front;
      if (term == head)
        head = node;
      else {
        node->front = term->front;
        node->front->front->next = node;
      }
      delete term;
    }
  }
}

Term *Polynomial::getHead() { return head; }

Term *Polynomial::getTail() { return tail; }

Polynomial Polynomial::calc(int n) { return ccalc(*this, n); }

Polynomial Polynomial::diff(int n) { return cdiff(*this, n); }

Polynomial Polynomial::operator+(Polynomial &p) {
  return addOrSub(*this, p, true);
}

Polynomial Polynomial::operator-(Polynomial &p) {
  return addOrSub(*this, p, false);
}

Polynomial Polynomial::operator*(Polynomial &p) { return mul(*this, p); }

Polynomial Polynomial::operator/(Polynomial &p) { return div(*this, p); }

Polynomial &Polynomial::operator=(Polynomial &p) {
  if (this == &p)
    return *this;
  Term *last = tail;
  n = p.size();
  for (Term *node = p.getTail(); node->front != nullptr; node = node->front) {
    Term *term = new Term(node->front->coefficient, node->front->exponent);
    term->next = last;
    last->front = term;
    head = term;
    last = term;
  }
  return *this;
}
                                              //calc.cpp
#include "calc.h"
#include "polynomial.h"

Polynomial addOrSub(Polynomial &a, Polynomial &b, bool add) {
  Polynomial res;
  Term *na = a.getHead(), *nb = b.getHead(), *ta = a.getTail(),
       *tb = b.getTail();
  for (; na != ta && nb != tb;) {
    if (na->exponent > nb->exponent)
      res.put(na->coefficient, na->exponent), na = na->next;
    else if (na->exponent < nb->exponent)
      res.put(add ? nb->coefficient : -nb->coefficient, nb->exponent),
          nb = nb->next;
    else {
      const double c =
          na->coefficient + (add ? nb->coefficient : -nb->coefficient);
      if (c <= -0.0000000005 || c > 0.0000000005)
        res.put(c, na->exponent);
      na = na->next, nb = nb->next;
    }
  }
  if (na != ta) {
    for (; na != ta;) {
      res.put(na->coefficient, na->exponent);
      na = na->next;
    }
  }
  if (nb != tb) {
    for (; nb != tb;) {
      res.put(add ? nb->coefficient : -nb->coefficient, nb->exponent);
      nb = nb->next;
    }
  }
  return res;
}

Polynomial mul(Polynomial &a, Polynomial &b) {
  Polynomial res;
  for (Term *na = a.getHead(), *ta = a.getTail(), *tb = b.getTail(); na != ta;
       na = na->next) {
    for (Term *nb = b.getHead(); nb != tb; nb = nb->next) {
      res.update(na->coefficient * nb->coefficient,
                 na->exponent + nb->exponent);
    }
  }
  res.normalize();
  return res;
}

Polynomial div(Polynomial a, Polynomial &b) {
  Term *c = a.getHead(), *d = b.getHead(), *ta = a.getTail(), *tb = b.getTail();
  Polynomial res;
  while (c->exponent >= d->exponent) {
    Term t = {c->coefficient / d->coefficient, c->exponent - d->exponent};
    res.put(t.coefficient, t.exponent);
    for (Term *node = c, *term = d; node != ta && term != tb;) {
      int e = term->exponent + t.exponent;
      if (node->exponent > e)
        node = node->next;
      else if (node->exponent < e)
        term = term->next;
      else
        node->coefficient -= t.coefficient * term->coefficient,
            node = node->next, term = term->next;
    }
    a.normalize();
    c = a.getHead();
  }
  return res;
}

Polynomial ccalc(Polynomial &a, int n) {
  Term *t = a.getTail();
  Polynomial res;
  for (Term *node = a.getHead(); node != t; node = node->next) {
    double c = node->coefficient;
    int e = node->exponent;
    for (int i = e + 1; i <= e + n; ++i) {
      c = c / i;
    }
    res.put(c, e + n);
  }
  res.normalize();
  return res;
}

Polynomial cdiff(Polynomial &a, int n) {
  Term *t = a.getTail();
  Polynomial res;
  for (Term *node = a.getHead(); node != t; node = node->next) {
    double c = node->coefficient;
    int e = node->exponent;
    if (e > 0 && e - n < 0) continue;
    for (int i = e; i > e - n; --i) {
        c = c * i;
    }
    res.put(c,e - n);
  } 
  res.normalize();
  return res;
}

核心代码如上所示。留存作纪念。

上一页
2024-12-27 20:44:37 # 学点什么