Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

[C++] Операции с полиномами

6.7K
04 мая 2007 года
Ginza9
96 / / 30.06.2006
Недавно вы мне помогли исправить ошибочку при вводе полиномов. Теперь же возникла другая, вернее она и тогда имела место быть. Суть проблемы в операции сложения двух полиномов. Если первый полином, допустим, 1x^2+7x^3+9x^4+3x^1, а второй - 8x^4+9x^3+5x^2+1x^1, то на выходе мы получим верный полином: 17x^4+16x^3+6x^2+4x^1. Если же в одном из полиномов есть, например, член x^5, а в другом такого члена не наблюдается, то начинаются проблемы. И еще одна проблема в операции умножения. Прошу помощи)

Класс Term:

Код:
class Term {
    public:
        int a,pow;
        Term();
        Term(int t);
        Term(int b,int c);
        friend Term operator+(const Term &obj1,const Term &obj2);
        Term operator+=(const Term &obj);
        friend Term operator*(const Term &obj1,const Term &obj2);
        Term &operator=(const Term obj);
        friend ostream &operator<<(ostream &stream,Term &obj);
        friend Polynomial;
};


Класс Polynomial:

Код:
class Polynomial {
    public:
        Term poly[6];
        int degree;
        Polynomial();
        Polynomial(int a);
        Polynomial(Term b);
        friend ostream &operator<<(ostream &stream,Polynomial obj);
                friend istream &operator>>(istream &stream,Polynomial &obj);
        friend Polynomial operator+(Polynomial &obj1,Polynomial &obj2);
        friend Polynomial operator*(Polynomial &obj1,Polynomial &obj2);
        void sort();
    private:
        bool Order;
};


Реализация методов класса Term:

Код:
Term &Term::operator=(const Term obj) {
        a=obj.a;
        pow=obj.pow;
        return *this;
}

Term operator+(const Term &obj1,const Term &obj2) {
        Term tmp;
        tmp.a=obj1.a+obj2.a;
        tmp.pow=obj2.pow;
        return tmp;
}

Term operator*(const Term &obj1,const Term &obj2) {
    Term tmp;
    tmp.a=obj1.a*obj2.a;
    tmp.pow=obj1.pow+obj2.pow;
    return tmp;
}

Term Term::operator+=(const Term &obj) {
    a+=obj.a;
    pow=obj.pow;
    return *this;
}

Term::Term() {
    a=pow=0;   
}

Term::Term(int t) {
    a=t;
    pow=0;
}

Term::Term(int b,int c) {
    a=b;
    pow=c;
}

ostream &operator<<(ostream &stream,Term &obj) {
    stream << obj.a << "x^" << obj.pow;
    return stream;
}


Реализация методов класса Polynomial:

Код:
Polynomial::Polynomial() {
    Term A(0,0);
    degree=0;
    poly[0]=poly[1]=poly[2]=poly[3]=poly[4]=poly[5]=A;
}

Polynomial::Polynomial(int a) {
    Term A(a,0);
        Term B(0,0);
    degree=0;
    poly[0]=A;
        poly[1]=poly[2]=poly[3]=poly[4]=poly[5]=B;
}

Polynomial::Polynomial(Term A) {
        Term B(0,0);
    degree=0;
    poly[0]=A;
        poly[1]=poly[2]=poly[3]=poly[4]=poly[5]=B;
}

ostream &operator<<(ostream &stream,Polynomial obj) {
    for(int i=0;i<6;i++) {
        stream << obj.poly << endl;
        }
    return stream;
}

Polynomial operator+(Polynomial &obj1,Polynomial &obj2) {
        Polynomial tmp;
    int p;
    bool flag=false;
    obj1.sort();
    obj2.sort();
    for(int i=0;i<6;i++) {
        p=obj1.poly.pow;
        tmp.poly=obj1.poly;
        for(int j=0;j<6;j++) {
            if(obj2.poly[j].pow==p) {
                            tmp.poly+=obj2.poly;
                flag=true;
            }
            if(flag==false) {
                tmp.poly=obj2.poly;
                flag=true;
            }

        }
    }
    return tmp;
}

Polynomial operator*(Polynomial &obj1,Polynomial &obj2) {
        int i;
        int j;
        Polynomial tmp;
    Term A(0,0);
        for(i = 0; i <6; i++) {
            tmp.poly = A;
        }
        for(i = 0; i <6; i++) {
            for(j = 0; j <6; j++) {
                    tmp.poly = tmp.poly+obj1.poly[j]*obj2.poly;
            }
        }
    return tmp;
}



void Polynomial::sort() {
    Term tmp;
    int k;
    for(int i=0;i<6;i++) {
        k=i;
        tmp=poly;
        for(int j=i+1;j<6;j++) {
            if(poly[j].pow>tmp.pow) {
                k=j;
                tmp=poly[j];
            }
        }
        poly[k]=poly;
        poly=tmp;  
    }
}
istream &operator>>(istream &stream,Polynomial &obj) {
        Term A;
    int i=0,k=0;
    char buf[20];
    char c=0;
    while(c!='\n') {
        c=getchar();
        if(c=='+' || c=='-' || c=='\n') {
                        buf=' ';
            A=Parse(buf);
            obj.poly[k]=A;
            k++;
            i=0;
        }
        buf=c;
        i++;
    }
        return stream;
}


Вспомогательные функции для парсинга:

Код:
void Polynomial::sort() {
    Term tmp;
    int k;
    for(int i=0;i<6;i++) {
        k=i;
        tmp=poly;
        for(int j=i+1;j<6;j++) {
            if(poly[j].pow>tmp.pow) {
                k=j;
                tmp=poly[j];
            }
        }
        poly[k]=poly;
        poly=tmp;  
    }
}

int CountDigits(char *p) {
        int k=0;
        for(int i=0;i<strlen(p);i++) {
                if((int)p>=47 && (int)p<=58) k++;
        }
        return k;
}

Term Parse(char *t) {
    Term A;
        int l=0,m=0,pow,num;
        unsigned int i,k,h;
        char *pows,*nums;
        bool flag=false;
        pows=(char *)malloc(CountDigits(t));
        nums=(char *)malloc(CountDigits(t));
        for(i=0;i<strlen(t);i++) {
                if(t=='^') {
                        k=i+1;
                        while(t[k]!='+' && t[k]!='-' && t[k]!='\n' && k<strlen(t)) {
                                pows[l]=t[k];
                                l++;
                                k++;
                        }
                        pow=atoi(pows);
                        break;
                }
                else {
Label:                        if((int)t>=48 && (int)t<=57) {
                                if(flag==true) {
                                        i++;
                                        goto Label;
                                }
                                h=i;
                                while(t[h]!='x' && t[h]!='\n' && h<strlen(t)) {
                                        nums[m]=t[h];
                                        m++;
                                        h++;
                                }
                                num=atoi(nums);
                                flag=true;
                        }
                }
        }
        A.pow=pow;
    A.a=num;
        free(pows);
        free(nums);
    return A;
}


Функция main()
Код:
void main() {
    Polynomial B,C;
        cout << "First: ";
        cin >> B;
        cout << "Second: ";
        cin >> C;
    cout << B;
        cout << "\n";
        cout << C;
        cout << "\n";
        cout << B+C;
    cout << "\n";
    cout << "B*C:"  << endl;
    cout << B*C;
        getch();
}
7.8K
04 мая 2007 года
Hrew
185 / / 23.04.2007
простите, сил нет в коде разбираться, поэтому задам два очевидных вопроса:
1. в чем собственно ошибка заключается
2. если один из многочленов = 8x^4+9x^3+5x^2+1x^1, а во втором содержится х^5, то как Вы храните в памяти первый (так как есть или как 0*х^5+8x^4+9x^3+5x^2+1x^1)
6.7K
04 мая 2007 года
Ginza9
96 / / 30.06.2006
1. Ошибка заключается в том, что путаются все степени и коэффициенты. Некоторые вообще отсутствуют в выходном полиноме.
2. Храню так, как есть. Была идея выискивать различия между многочленами и дополнять какой-либо из них термом 0x^k, но на чем-то споткнулся в плане реализации. Если предложите какой-нибудь стоящий алгоритм, то буду очень признателен.
622
04 мая 2007 года
nilbog
507 / / 19.12.2006
вообще полином представляйте как вектор
8x^4+9x^3+5x^2+1x^1 === (0,1,5,9,8)
начиная с нулевой степени
тогда все будет очень просто - все действия можно производить как векторами сложение и тп и тд
даже дифференцирование это не более чем умножение вектора мн-а на матрицу )
я так просмотрел код ваш слишком все там усложнено
6.7K
04 мая 2007 года
Ginza9
96 / / 30.06.2006
Цитата: nilbog
вообще полином представляйте как вектор
8x^4+9x^3+5x^2+1x^1 === (0,1,5,9,8)
начиная с нулевой степени
тогда все будет очень просто - все действия можно производить как векторами сложение и тп и тд
даже дифференцирование это не более чем умножение вектора мн-а на матрицу )
я так просмотрел код ваш слишком все там усложнено



Я так тоже хотел сначала сделать. Но задание есть задание. Там четко описано, какие классы должны быть. Да и потом, смотрите: ввожу я полином - 4x^1+5x^2+9x^4+8x^3+189x^256

Так это вектор тогда будет vector={0,4,5,8,9,0,0,...,256}. Это же ужасть.

7.8K
04 мая 2007 года
Hrew
185 / / 23.04.2007
Цитата: nilbog
вообще полином представляйте как вектор


пытаюсь вспомнить и не могу - в С++ есть библиотека для работы с векторами или надо класс писать руками?

622
04 мая 2007 года
nilbog
507 / / 19.12.2006
Цитата: Ginza9
ввожу я полином - 4x^1+5x^2+9x^4+8x^3+189x^256

Так это вектор тогда будет vector={0,4,5,8,9,0,0,...,256}. Это же ужасть.


ну чтож поделать - за все хорошее приходится платить

6.7K
04 мая 2007 года
Ginza9
96 / / 30.06.2006
Так что делать?
7.8K
04 мая 2007 года
Hrew
185 / / 23.04.2007
Цитата: Ginza9
Так что делать?


Вариант 1. Думать
Вариант 2. Ждать пока кто-нибудь не найдет баг в Вашем коде или не изобретет работающий алгоритм.

P.S. А заданьицем не поделитесь? Хотя бы в сокращенном виде - какие классы и функции обязательно должны быть реализованы

622
04 мая 2007 года
nilbog
507 / / 19.12.2006
Цитата: Ginza9

2. Храню так, как есть. Была идея выискивать различия между многочленами и дополнять какой-либо из них термом 0x^k, но на чем-то споткнулся в плане реализации. Если предложите какой-нибудь стоящий алгоритм, то буду очень признателен.


ну если уж так нужно то сумму наверно так искать
берем один многочлен (слагаемое) и затем все присутствующие степени второго ищем в первом
если находим то коэф складываем если нет то добавляем в нужное место еще один элемент нужной степени
в таком наверно ключе
здесь будем за счет выйгрыша в памяти проигрывать по скорости в поиске вставках и тп

если там умножение то (распишите себе на бумажке умножение полиномов) и станет ясно как подыскивать нужные коэффиценты и перемножать

6.7K
04 мая 2007 года
Ginza9
96 / / 30.06.2006
Вот задание.
[ATTACH]1804[/ATTACH]
6.7K
15 мая 2007 года
Ginza9
96 / / 30.06.2006
Класс Полиномов доделал самостоятельно. Если кому-то интересно, то пишите в личку.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог