Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Деление двух полиномов
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
PAB PAB вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.07.2006
По умолчанию 28.10.2006, 21:14

Подскажите,pls, алгоритм деления полиномов(многочленов). Если кто знает, то хотя бы формулу. Сам пытался реализовать деление уголком, но что-то закопался...может что еще есть
Ответить с цитированием
  (#2 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 28.10.2006, 23:52

Вот, и не поленился же... :)
Код:
#include <deque>
#include <stdexcept>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iostream>

typedef std::deque<double> Polinom;

// ====================================
// Вспомогательные функции
// ====================================

const double eps = .0000001;    // точность сравнения (не совсем корректно)
inline bool isZero( double num )          { return std::abs( num ) < eps; }
inline bool Equal( double n1, double n2 ) { return isZero( n1 - n2 ); }

// Делает старшим первый коэффициент, не равный 0;
inline Polinom& Normalize( Polinom &p )
{
    while ( p.size() != 0 && isZero( p.back() ) ) p.pop_back();
    return p;
}

// Сравнение полиномов
inline bool operator < ( const Polinom &p1, const Polinom &p2 )
{
    return p1.size() < p2.size() ||
           std::lexicographical_compare( p1.begin(), p1.end(), p2.begin(), p2.end() );
}

// Умножает полином на число
inline Polinom operator * ( const Polinom &p, double num )
{
    Polinom res( p.size() );
    std::transform( p.begin(), p.end(),
                    res.begin(),
                    std::bind2nd( std::multiplies<double>(), num )
                   );
    return Normalize( res );
}

// Умножает полином p на полином coef*(x^power)
inline Polinom Multiply( const Polinom &p, double coef, int power )
{
    Polinom res = p * coef;
    while ( power-- ) res.push_front( 0.0 );
    return Normalize( res );
}

// Складывает полиномы p1 и p2
inline Polinom operator + ( const Polinom &p1, const Polinom &p2 )
{
    Polinom r1( p1.size() ), r2( p2.size() );
    if ( p1.size() < p2.size() )
        r1.swap( r2 );
    std::transform( p1.begin(), p1.begin() + r2.size(),
                    p2.begin(),
                    r1.begin(), std::plus<double>()
                   );
    return Normalize( r1 );
}

// Унарный минус - возвращает полином -p
inline Polinom operator - ( const Polinom &p )
{
    Polinom res( p.size() );
    std::transform( p.begin(), p.end(), res.begin(), std::negate<double>() );
    return res;
}

// Вычитает из полинома p1 полином p2
inline Polinom& operator -= ( Polinom &p1, const Polinom &p2 )
{
    p1.swap( p1 + ( - p2 ) );
    return p1;
}



// ====================================
// Реализуемая функция
// ====================================

// Делит p1 на p2
Polinom Divide( const Polinom &p1, const Polinom &p2 )
{
    Polinom d1 = p1, d2 = p2;
    Normalize( d1 );
    Normalize( d2 );

    // проверка деления на 0
    if ( d2.size() == 0 )
        throw std::invalid_argument( "Divide by zero!" );

    // если p1 < p2, возвращаем 0
    if ( d1 < d2 )
        return Polinom();

    // res - результат
    Polinom res;
    while ( d2 < d1 )
    {
        double coef = d1.back() / d2.back();
        res.push_front( coef );
        d1 -= Multiply( d2, coef, d1.size() - d2.size() );
    }

    return res;
}

void DebugPrint( const Polinom &p )
{
    if ( p.size() == 0 ) std::cout << "0";
    for ( int i = p.size() - 1; i >= 0; --i )
    {
        if ( !isZero( p[i] ) )
        {
            if ( i != 0 )
                std::cout << p[i] << "*x^" << i << " + ";
            else
                std::cout << p[i];
        }
    }
    std::cout << std::endl;
}

int main()
{
    Polinom p1, p2;
    p1.push_back( 10.0 );
    p1.push_back( 5.0 );
    p1.push_back( 0.0 );
    p1.push_back( -3.0 );

    p2.push_back( -1.0 );
    p2.push_back( 0.5 );

    DebugPrint( p1 );
    DebugPrint( p2 );

    DebugPrint( Divide( p1, p2 ) );
}
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
При включении двух модулей памяти в двух канальном режиме компьютер не включается. gotosha Техническая поддержка 7 30.11.2011 05:59
Умножение полиномов где ошибки neitrosha Вопросы начинающих программистов 1 23.03.2011 10:56
Умножение полиномов многочленов neitrosha Вопросы начинающих программистов 0 21.03.2011 16:46
деление диска golova Windows XP 4 22.11.2010 12:03
деление диска golova Накопители 0 23.10.2010 15:43
Ввод полиномов пользователем на C++ Марьюшка Вопросы начинающих программистов 0 20.02.2008 02:45
Организовать в Lisp процедуру сложения двух полиномов lovelyevil Lisp 12 16.01.2008 22:49
Организовать в Lisp процедуру сложения двух полиномов NexX_33 Lisp 1 08.06.2007 13:48
Перемножение полиномов разных степеней Света Вопросы начинающих программистов 1 31.12.2005 02:01
Вычисление полиномов как делать Frick Pascal 12 13.12.2005 13:14
invfreqz - вычисление коэф.полиномов передаточной функции Озябкин Андрей Visual Basic 0 29.01.2005 07:38
Как сделать умножение полиномов Anonymous Алгоритмы 3 30.05.2003 14:32



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов