Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
1 / 1 / 2
Регистрация: 11.11.2016
Сообщений: 165
1

Деление многочленов

11.05.2017, 14:44. Показов 2718. Ответов 4
Метки нет (Все метки)

Помогите,пожалуйста!
Застрял,конкретно.
Есть класс многочленов,представленный в виде двусвязного списка. Не могу сделать функцию деления(про остаток вообще молчу) хотя бы это сделать.Пользовался этим алгоритмом:Деление многочленов
проверьте,что не так(
C++
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
struct Element
{
    double a; //коэффициент
    int b; //степень
    Element * sled;
    Element * pred;
    Element();
};
 
class Spisok
{
    Element *first;
    Element * end;
public:
    Spisok()
    {
        first = NULL;
        end = NULL;
    }
    Spisok(const Spisok & s)
    {
        first = end = NULL;
        Element *t = s.first;
        while (t != 0)
        {
            Add(t->a, t->b);
            t = t->sled;
        }
 
    }
int kol() //метод подсчета кол-ва элементов в узле
    {
        Element *s = first;
        int i = 0;
        while (s != NULL)
        {
            s = s->sled;
            i++;
        }
        return i;
    }
void Add(double x, int y);
Spisok umnojeniye1(double w); 
Spisok deleniye(Spisok m) //сам дурацкий метод!
    {
        Spisok u, y;
        Element *s = end;
        int k = kol() - 1;
        while (s != NULL)
        {
            u.Add(s->a, k);
            s = s->pred;
            k--;
        }
        Element *s1 = m.end;
        k = kol();
        int k1 = m.kol();
        cout << k1 << ' ' << k << endl;
        for (int i = k1; i < k; i++)
            y.Add(0, 0);
        k1 = k - 1;
        double w;
        while (s1 != NULL)
        {
            y.Add(s1->a, 0);
            s1 = s1->pred;
 
        }
        s = y.first;
        while (s != NULL)
        {
            s->b = k1;
            s = s->sled;
            k1--;
 
        }
        Spisok otvet;
        s1 = u.first;
        while (u.first->b >=y.first->b  )
        {
            w = u.end->a / y.end->a;
            y.umnojeniye1(w);
            u = u.vichitaniye(y);
            otvet.Add(w, 0);
            y.umnojeniye1(1.0 / w);
            u.udaleniye(u.kol());
            u.stepen();
            y.udaleniye(1);
 
        }
 
 
        return otvet;
    }
Spisok  stepen() //для изм-ия степеней после удаления
    {
        int k = kol()-1;
        Element *s = first;
        while (s != NULL)
        {
            s->b = k;
            s = s->sled;
            k--;
 
        }
        return *this;
    }
Spisok vichitaniye(Spisok m); //метод вычитания
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.05.2017, 14:44
Ответы с готовыми решениями:

Деление многочленов
https://www.cyberforum.ru/cpp-beginners/thread328191.html Из этой темы был представлен алгоритм...

Деление двух многочленов
Привет всем! Было дано задание реализовать деление многочленов с комплексными коэффициентами через...

Деление многочленов 4 степени
Доброго времени суток! Необходимо было реализовать алгоритм, делящий два многочлена 4 степени с...

Деление многочленов от двух переменных
Есть многочлен от двух переменных, заданный следующей структурой: struct Monom { int...

4
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
11.05.2017, 19:35 2
Menshakovich, проверь, пожалуйста, на больших степенях
Кликните здесь для просмотра всего текста

C++
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
#include <algorithm> // sort
#include <iostream>
#include <limits>
#include <list>
#include <sstream>
#include <string>
#include <utility> // pair
#include <vector>
using namespace std;
 
using Item = pair<int,double>;
using Poly = list<Item>;
 
vector<double> AllCoef (const Poly* pol, int pwr) {
  vector<double> coef (pwr+1, 0.0);
  for (const Item& itm : *pol)
    coef[pwr-itm.first] = itm.second;
  return coef; // implicit move(), compiler optimization
} // AllCoef()
 
void PrintPolynom (Poly* pol) {
  if (pol->size() == 0) {
    cout << 0;
    return;
  }
  bool firstTime = true;
  for (Item& p : *pol) {
    if (! firstTime)
      cout << "; ";
    cout << p.first << " " << p.second;
    firstTime = false;
  }
} // PrintPolynom()
 
void NormPolynom (Poly* pol) {
  if (pol->size() == 0)
    return;
  // Привести подобные степени
  auto bgn = begin(*pol);
  while (bgn != end(*pol)) {
    auto p = *bgn;
    int pwr = p.first;
    double cft = p.second;
    auto nxt = bgn; ++nxt;
    while (nxt != end(*pol)) {
      auto q = *nxt;
      if (q.first != pwr)
        ++nxt;
      else {
        cft += q.second;
        nxt = pol->erase(nxt);
      }
    }
    if (cft == p.second)
      ++bgn;
    else {
      p.second = cft;
      auto del = bgn;
      bgn = pol->insert(bgn, p);
      pol->erase(del);;
    }
  }
  // Упорядочить по убыванию степеней
  pol->sort ([] (Item& p1, Item& p2)
    { return p1.first > p2.first; });
  // Удалить старшие нули
  bgn = begin(*pol);
  while (bgn != end(*pol) && (*bgn).second == 0) {
    pol->erase(bgn);
    bgn = begin(*pol);
  }
} // NormPolynom()
 
Poly* DivPolynom (Poly* pol1, Poly* pol2, Poly** rem) {
  const int pwr1 = pol1->front().first;
  const int pwr2 = pol2->front().first;
  if (pwr1 < pwr2)
    throw logic_error ("DivPolynom: pwr1 < pwr2");
  Poly* pol = new Poly;
  *rem = new Poly;
  vector<double> cf1 = AllCoef (pol1,  pwr1);
  vector<double> cf2 = AllCoef (pol2,  pwr2);
  for (int i = 0; i <= pwr1 - pwr2; ++i) {
    if (cf1[i] == 0) continue;
    // Вычисляем и размещаем коэффициент частного
    double c = cf1[i] / cf2[0];
    int k = pwr1 - i - pwr2;
    pol->emplace_back (make_pair (k, c));
    // Пересчитываем коэффициенты остатка
    cf1[i] = 0;
    for (unsigned j = 1; j < cf2.size(); ++j)
      cf1[i+j] -= cf2[j] * c;
  }
  // Размещаем коэффициенты остатка в полиноме
  double eps = numeric_limits<double>::epsilon();
  for (unsigned i = 1; i < cf1.size(); ++i) {
    if (abs (cf1[i]) > eps)
      (*rem)->emplace_back (make_pair (pwr1 - i, cf1[i]));
  }
  NormPolynom (pol);
  NormPolynom (*rem);
  return pol;
} // DivPolynom()
 
Poly* AddPolynom (Poly* pol1, Poly* pol2) {
  Poly* pol = new Poly;
  int pwr = max (pol1->front().first, pol2->front().first);
  vector<double> cf1 = AllCoef (pol1,  pwr);
  vector<double> cf2 = AllCoef (pol2,  pwr);
  for (int i = 0; i <= pwr; ++i) {
    Item itm = make_pair (pwr - i, cf1[i] + cf2[i]);
    if (itm.second != 0)
      pol->emplace_back(itm);
  }
  //NormPolynom (pol);
  return pol;
} // AddPolynom()
 
Poly* SubtPolynom (Poly* pol1, Poly* pol2) {
  Poly* pol = new Poly;
  int pwr = max (pol1->front().first, pol2->front().first);
  vector<double> cf1 = AllCoef (pol1,  pwr);
  vector<double> cf2 = AllCoef (pol2,  pwr);
  for (int i = 0; i <= pwr; ++i) {
    Item itm = make_pair (pwr - i, cf1[i] - cf2[i]);
    if (itm.second != 0)
      pol->emplace_back(itm);
  }
  //NormPolynom (pol);
  return pol;
} // SubtPolynom()
 
Poly* MultPolynom (Poly* pol1, Poly* pol2) {
  Poly* pol = new Poly;
  for (Item& p1 : *pol1) {
    for (Item& p2 : *pol2) {
      Item itm = make_pair (p1.first + p2.first
        ,p1.second * p2.second);
      if (itm.second != 0)
        pol->emplace_back (itm);
    }
  }
  NormPolynom (pol);
  return pol;
} // MultPolynom()
 
Poly* GetPolynom (istream& in) {
  Poly* pol = new Poly;
  string line, str1;
  int pwr; double cft;
  getline (in, line);//, '\n');
  istringstream elm1 (line);
  while (getline (elm1, str1, ';')) {
    istringstream elm2 (str1);
    elm2 >> pwr;
    elm2 >> cft;
    pol->emplace_back (make_pair (pwr, cft));
  }
  return pol;
} // GetPolynom()
 
void main () { // При вводе с клавиатуры (cin)
  // конец полинома по клавише Enter
  istringstream sin1 ("2 1; 1 2; 0 1"); // x^2 + 2x + 1
  istringstream sin2 ("1 1; 0 1");      // x + 1
  Poly* pol1 = GetPolynom (sin1);
  cout << "Origin 1\n";
  PrintPolynom (pol1);
  Poly* pol2 = GetPolynom (sin2); //cin);
  cout << "\nOrigin 2\n";
  PrintPolynom (pol2);
  Poly* pol3;
  Poly* pol4 = DivPolynom (pol1, pol2, &pol3);
  cout << "\npol4\n";
  PrintPolynom (pol4);
  cout << "\npol3\n";
  PrintPolynom (pol3);
}
0
1 / 1 / 2
Регистрация: 11.11.2016
Сообщений: 165
11.05.2017, 20:02  [ТС] 3
ввел 2x^6+2x^4+3x+4
второй также оставил.
ответ получился не совсем таким. первые 3 члена норм,а дальше несоответствие
0
21 / 21 / 10
Регистрация: 11.09.2015
Сообщений: 103
11.05.2017, 22:17 4
Menshakovich, для твоего примера моя программа даёт правильный ответ:
2x^5-2x^4+4x^3-4x^2+4x-1 + 5/(x+1).
Также для примера из "Справочника по математике" А.А Рывкина и др. изд.2, М.1970, стр.60 ответ программы совпадает с приведённым в книге:
(8x^4-3x^2+6x+4) / (2x^2+3x+1) = 4x^2-6x+5.5 и остаток -4.5x-1.5
А тебя поздравляю, соврамши! Учись считать на бумаге столбиком!

Добавлено через 13 минут
Правильность деления можно проверить умножением и сложением
Кликните здесь для просмотра всего текста

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void main () { // При вводе с клавиатуры (cin)
  // конец полинома по клавише Enter
  istringstream sin1 ("6 2; 4 2; 1 3; 0 4"); // 2x^6+2x^4+3x+4
  istringstream sin2 ("1 1; 0 1");        // x + 1
  Poly* pol1 = GetPolynom (sin1);
  cout << "Origin 1\n";
  PrintPolynom (pol1);
  Poly* pol2 = GetPolynom (sin2); //cin);
  cout << "\nOrigin 2\n";
  PrintPolynom (pol2);
  Poly* pol3;
  Poly* pol4 = DivPolynom (pol1, pol2, &pol3);
  cout << "\npol4\n";
  PrintPolynom (pol4);
  cout << "\npol3\n";
  PrintPolynom (pol3);
  Poly* pol5 = MultPolynom (pol4, pol2);
  Poly* pol6 = AddPolynom (pol5, pol3);
  cout << "\npol6\n";
  PrintPolynom (pol6);
}
0
1 / 1 / 2
Регистрация: 11.11.2016
Сообщений: 165
12.05.2017, 22:37  [ТС] 5
мдээ.апхах.Спасибо)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.05.2017, 22:37

Деление многочленов(полиномов). доделать класс
Суть задания - сделать класс-полином со основными арифметическими операциями между многочленами....

Нужны советы как реализовать сложение, вычитание, умножение полиномов/многочленов и деление на число
Всем здравствуйте! надеюсь написать с вашей помощью программку для сложения, вычитания и умножения...

Задача про деление яблок (целочисленное деление)
Ребят,помогите с задачкой,как написать input.txt и output.txt? Помогите решить задачу. C++....

Сумма многочленов
Всем привет. Помогите пожалуйста. Дан многочлен P(x) степени n. Получить многочлен P(x+1)-P(x) ....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru