Работа с многочленами С++ классы

[Марго Ивановна]

Реализовать в виде класса набор подпрограмм для выполнения операций с многочленами от одной переменной: возведение в натуральную степень k и деление с остатком;
Есть ли какой-нибудь алгоритм для этих операций? Для возведения в степень хотела использовать уже реализованную функцию умножения, но не выходит. Может, ее изменить и доработать? Потому что после введения в степень результат мне нужно будет использовать.

умножение

koof - коэффициент при x;
stepen - степень x;
stepen[0] - свободный элемент;

mnogochlen mnogochlen :: operator *(mnogochlen m)

{mnogochlen d;
int i,j;

for (i=0;i<=100;i++)
{
d.koof[i]=0;
}

for (i=0;i<=stepen;i++)
{
for(j=0;j<=m.stepen;j++)
{
d.koof[i+j]+=koof[i]*m.koof[j];
}
}

d.stepen=m.stepen+stepen;


return d ;
}

возведение в степень

Поманю, что результат затирается, и получается, что умножение идет уже с новыми коэффициентами, и в дальнейшем результат нельзя использовать. Как поправить положение?

void mnogochlen::stepeyn()
{int i,n,j;
mnogochlen d;



cout<<"Введите степень, к утороую нужно возвести многочлен"<>n;

if(n=0){d.stepen=0; d.koof[0]=1;}
else{
if(n=1) { d.stepen=stepen; for(i=0;i<=stepen;i++){d.koof[i]=koof[i];}}
else{for(i=2;i<=stepen;i++){d.koof[i]=koof[i];}}
for(i=0;i<=n;i++)
{for(j=0;j<=n;j++)
{
d.koof[i+j]+=koof[i]*d.koof[j];

}}


}

d.vivod();
}

@темы: Вопрос, C++, Алгоритм

Comments

[Скептичный циник]

> Для возведения в степень хотела использовать уже реализованную функцию умножения, но не выходит.
Возведение x в степень n это умножение x самого на себя n раз. Посему, можно реализовать обычным циклом. Если хочется поизвращаться, то можно использовать быстрое возведение или БПФ с треугольником.

> после введения в степень результат мне нужно будет использовать
В таком случае возвращайте результат возведения из метода (return) вместо его вывода. Тогда результат возведения можно будет использовать на месте вызова метода.

> Как поправить положение?
А зачем сохранять промежуточные возведения? 2^4 = 2*2*2*2 = 4*2*2 = 8*2 = 16.

Из приведённого кода мне, например, не очень понятно как выглядит класс многочлена, как пытаетесь использовать указанные функции и какие ошибки получаете при компиляции/запуске.

Очепятки:
– "=" это присваивание, а сравнение "=="
– "<>" это аналог "!=", а побитовый сдвиг выглядит так "<<"

И что означает магическое число 100?

[Марго Ивановна]

Скептичный циник, из всего поняла, что проглядела опечатки, что можно будет возвратить массив.

И что означает магическое число 100?

а почему не 100. Сомневаюсь, что многочлен будет более этого числа. Поэтому и зануляю для дальнейших вычислений до него, чтобы не было "грязи". Хотя признаю, что логичнее сделать до числа равного m.stepen+stepen

А зачем сохранять промежуточные возведения? 2^4 = 2*2*2*2 = 4*2*2 = 8*2 = 16.

какие промежуточные? не совсем понятно.

Возведение x в степень n это умножение x самого на себя n раз.

Только вот сложность этого алгоритма будет О(k^2*n), где k - степень многочлена, а n - степень, в которую он возводится.

[Марго Ивановна]

St.Shorh, не совсем понимаю, чем это может помочь. Коэффициенты считать, степень каждый раз. Никак не могу сообразить как все это реализовать. ^^"""

[Скептичный циник]

Марго Ивановна
> а почему не 100. Сомневаюсь, что многочлен будет более этого числа.
Эм, так что всё-таки оно означает? Максимальную степень?

> логичнее сделать до числа равного m.stepen+stepen
Да, логичнее. Для динамических размеров массивов нужно использовать кучу вручную или вектор.

Если уже перегружен оператор умножения многочлена на многочлен и корректно работает, то реализовать возведение в степень можно несколькими способами. Отличаются они математическими алгоритмами и вычислительной сложностью алгоритма: "в лоб" (по определению степени), треугольник Паскаля или через БПФ. Как правильно заметила St.Shorh выше, у первого способа максимальная вычислительная сложность среди указанных: O(k^2*n) против, ЕМНИП, O(n^2) и O(n*log(n,2)) соответственно. Да поправят меня математики здесь присутствующие (:

Для примера, возьмём возведение в степень "в лоб" (просто потому, что писать меньше и проще):

#include <iostream>
#define MAX_LEN 100
#define TYPE int
using namespace std;

class Poly {
    public:
        TYPE coefs[MAX_LEN];

        Poly();
        Poly(TYPE[]);
        string toString();
        Poly pow(int);
        Poly operator*(Poly);
};

Poly Poly::pow(int pow) {
    Poly res(this->coefs);
    for (int i=0; i<pow-1; ++i) {
        res = res*(*this);
    }
    return res;
};

int main() {
    TYPE arr[MAX_LEN] = {1, -5, 2};
    Poly poly(arr);

    // Возводим, например, в четвёртую степень
    Poly poly2 = poly.pow(4);

    return 0;
}