Cum se face simplificatorul de ecuații algebrice în c++? [închis] (Programare, C++)

Ans a intrebat.

De fapt, încep să învăț c++ și aș fi foarte recunoscător dacă cineva m-ar putea ajuta să fac primii pași. trebuie să fac simplificator de ecuații algebrice în c++. De exemplu această ecuație:x+5+6+3y+3+2ysar trebui să apară ca aceasta:x+5y+14Nu există împărțire, dar programul ar trebui să funcționeze cu +, – și *.Știu că este ușor pentru majoritatea dintre voi, dar eu mă blochez și aș fi bucuros dacă cineva mi-ar putea spune cum ar trebui să încep cu asta :/

Vă mulțumesc anticipat,Ans 🙂

Comentarii

  • Arată-ne ce ai făcut până acum… –  > Por Dabiuteef.
  • Arată-ne ce ai încercat până acum înainte de a întreba. De asemenea, dacă acest lucru nu trebuie să fie în c++, python are o bibliotecă numită sympy care face acest lucru foarte bine (precum și o mulțime de alte matematici simbolice). –  > Por Asher Mancinelli.
  • Aceasta este de fapt o sarcină foarte complexă. –  > Por Galik.
  • @Asher Mancinelli știu cum să fac ultima parte a acesteia, dar nu știu cum să încep. Am încercat să folosesc buclele „for” și „while”, dar nu a funcționat. Așa că, sincer, pot spune că nu am făcut nimic :/ Din păcate trebuie făcut în c++, prefer și Python. –  > Por Ans.
  • Este vorba de polinoame, nu de ecuații algebrice. Mult mai ușor de simplificat. –  > Por Potatoswatter.
2 răspunsuri
Potatoswatter

În primul rând, definește exact cu ce fel de matematică trebuie să lucrezi. Este vorba de polinoame, nu de ecuații algebrice. Mult mai ușor de simplificat.

Apoi, alegeți o structură de date pentru a reprezenta polinoamele. Un polinomial este o sumă de termeni, fiecare cu un coeficient și un set de variabile cu exponenți. În acest caz, toți coeficienții și exponenții vor fi numere întregi. Și să presupunem că aceste numere întregi vor fi cuprinse între plus sau minus un miliard.

Deja putem defini câteva clase.

#include <vector>
#include <cstdint>

typedef std::int32_t value;

struct power {
    char variable;
    value degree;
};

struct monomial {
    value coefficient;
    std::vector< power > product;
};

struct polynomial {
    std::vector< monomial > sum;
};

În continuare, definiți intrarea și ieșirea pe clase pentru formatul de text dat.

#include <iostream>

std::istream & operator >> ( std::istream & is, power & obj ) {
    // Skip leading space.
    std::istream::sentry s( is );

    // Read one character for the variable name.
    // Require that it be a letter.
    if ( is && std::isalpha( is.peek() ) ) {
        is >> obj.variable;
    } else {
        // Otherwise, the input is invalid.
        is.clear( std::ios::failbit );
    }

    // Read the exponent if its presence is indicated by a ^.
    if ( is ) {
        if ( is.peek() == '^' ) {
            is.ignore();
            is >> obj.degree;
        } else {
            obj.degree = 1;
            is.clear();
        }
    }
    return is;
}

std::ostream & operator << ( std::ostream & os, power const & obj ) {
    os << obj.variable;
    if ( obj.degree != 1 ) {
        os << '^' << obj.degree;
    }
    return os;
}

std::istream & operator >> ( std::istream & is, monomial & obj ) {
    obj.coefficient = 1;
    obj.product.clear();

    // Read a sequence of numbers and exponentiated variables,
    // optionally separated by * .
    bool did_read_asterisk = false;

    do {
        // Try reading a coefficient. (And ignore leading space.)
        value coefficient;
        if ( is >> coefficient ) {
            obj.coefficient *= coefficient;
        } else if ( is.rdstate() & std::ios::failbit ) {
            // If it was absent, tell iostream to resume input.
            is.clear( is.rdstate() & ~ std::ios::failbit );

            // Read a power instead.
            power p;
            if ( is >> p ) {
                obj.product.push_back( p );
            }

            // It's OK if the power was missing too, unless there was a * .
            if ( ! did_read_asterisk && ( is.rdstate() & std::ios::failbit ) ) {
                is.clear( is.rdstate() & ~ std::ios::failbit );
                return is;
            }
        }
        did_read_asterisk = false;

        // Skip trailing space.
        if ( is >> std::ws ) {
            if ( is.eof() ) {
                // Succeed if this is the end of input.
                return is;
            }
            if ( is.peek() == '*' ) {
                is.ignore();
                did_read_asterisk = true;
            }
            if ( is.peek() == '+' || is.peek() == '-' ) {
                break;
            }
        }
    } while ( is );

    return is;
}

std::ostream & operator << ( std::ostream & os, monomial const & obj ) {
    if ( obj.coefficient != 1 || obj.product.empty() ) {
        os << obj.coefficient;
    }
    for ( power const & p : obj.product ) {
        os << p;
    }
    return os;
}

std::istream & operator >> ( std::istream & is, polynomial & obj ) {
    // Skip leading space and reject EOF.
    std::istream::sentry s( is );

    // If there is no minus sign, start positive.
    bool positive = true;
    if ( is && is.peek() == '-' ) {
        is.ignore();
        positive = false;
    }

    // Read a sequence of monomials separated by + or - signs.
    monomial m;
    while ( is >> m ) {
        if ( ! positive ) m.coefficient = - m.coefficient;
        obj.sum.push_back( m );

        is >> std::ws;
        char next_op = is.peek();
        if ( is && ( next_op == '+' || next_op == '-' ) ) {
            is.ignore();
            positive = next_op == '+';

        } else if ( ! is.bad() ) {
            // Succeed if the next operator is missing.
            is.clear();
            return is;
        }
    }
    return is;
}

std::ostream & operator << ( std::ostream & os, polynomial const & obj ) {
    bool skip_leading_plus = true;

    for ( monomial const & m : obj.sum ) {
        if ( m.coefficient > 0 && ! skip_leading_plus ) {
            os << '+';
        }
        os << m;
        skip_leading_plus = false;
    }
    return os;
}

În continuare, scrieți logica de simplificare.

#include <algorithm>

struct variable_order {
    bool operator() ( power lhs, power rhs ) {
        return lhs.variable < rhs.variable;
    }
};
struct variable_same {
    bool operator() ( power lhs, power rhs ) {
        return lhs.variable == rhs.variable;
    }
};

monomial simplify( monomial in ) {
    std::sort( in.product.begin(), in.product.end(), variable_order{} );
    for ( auto it = in.product.begin();
        ( it = std::adjacent_find( it, in.product.end(), variable_same{} ) )
             != in.product.end(); ) {
        value degree = it->degree;
        it = in.product.erase( it );
        it->degree += degree;
    }
    in.product.erase( std::remove_if( in.product.begin(), in.product.end(),
        []( power p ) { return p.degree == 0; } ), in.product.end() );
    return in;
}

struct power_order {
    bool operator() ( power lhs, power rhs ) {
        return lhs.variable < rhs.variable? true
             : lhs.variable > rhs.variable? false
             : lhs.degree < rhs.degree;
    }
};
struct power_same {
    bool operator() ( power lhs, power rhs ) {
        return lhs.variable == rhs.variable
            && lhs.degree == rhs.degree;
    }
};

struct product_order {
    bool operator() ( monomial lhs, monomial rhs ) {
        return std::lexicographical_compare( lhs.product.begin(), lhs.product.end(),
                                             rhs.product.begin(), rhs.product.end(),
                                             power_order{} );
    }
};
struct product_same {
    bool operator() ( monomial lhs, monomial rhs ) {
        return std::equal( lhs.product.begin(), lhs.product.end(),
                           rhs.product.begin(), rhs.product.end(),
                           power_same{} );
    }
};

polynomial simplify( polynomial in ) {
    for ( auto & m : in.sum ) {
        m = simplify( m );
    }
    std::sort( in.sum.begin(), in.sum.end(), product_order{} );
    for ( auto it = in.sum.begin();
        ( it = std::adjacent_find( it, in.sum.end(), product_same{} ) )
             != in.sum.end(); ) {
        value coefficient = it->coefficient;
        it = in.sum.erase( it );
        it->coefficient += coefficient;
    }
    in.sum.erase( std::remove_if( in.sum.begin(), in.sum.end(),
        []( monomial m ) { return m.coefficient == 0; } ), in.sum.end() );

    // Represent zero rather than "nothing."
    if ( in.sum.empty() ) in = polynomial{{ monomial{ 0, {} } }};

    return in;
}

În cele din urmă, legați totul împreună.

int main() {
    polynomial p;
    std::cin >> p;
    std::cout << simplify( p ) << '
';
}

Vedeți, C++ nu este atât de rău!

Asher Mancinelli

Aceasta este, de fapt, o problemă destul de dificilă. Presupunând că primiți datele sub forma unui șir de caractere, trebuie să împărțiți șirul pe operatori pentru a obține componente individuale, cum ar fi 2x sau 14y. Apoi trebuie să verificați ce variabile sunt prezente în expresie folosind un fel de expresie regulată și să convertiți valorile în vectori în orice spațiu vectorial în care vă veți afla. De exemplu, dacă decideți că numărul maxim de variabile cu care veți lucra este 2, spațiul vectorial va fi în R3. De exemplu, 5x va deveni [0,5,0] unde primul element reprezintă numărul de numere fără sufixul variabilei, al doilea element dacă este numărul de x, iar al treilea este numărul de y. În final, ar trebui să aveți un număr mare de vectori, pe care îi puteți aduna într-un singur vector și converti acest lucru înapoi într-un șir de caractere pentru a fi afișat pe ecran. Bibliotecile Python, cum ar fi sympy, vă cer să introduceți variabilele pe care le veți utiliza, astfel încât să știe în mod intern în ce spațiu vectorial va calcula.

Să luăm întrebarea dumneavoastră ca exemplu. Aceasta ar trebui să primească șirul x+5+6+3y+3+2y și ar despărți semnele plus și ar elimina spațiile suplimentare, obținând șirurile separate x, , 5, , 6, , etc. Apoi, veți converti șirurile în vectori, în acest caz ar fi [0,1,0], , [5,0,0], , [6,0,0], , [0,0,3]… unde primul element reprezintă numărul de numere fără sufix variabil, al doilea element dacă este numărul de x, etc. Apoi veți aduna toți vectorii pentru a obține un vector final de [14,1,5], , iar apoi îl veți converti din nou într-un șir de caractere, ’14+1x+5y’, , și veți imprima acest lucru pe ecran.

Acesta este un concept din algebra liniară numit izomorfism, prin care puteți converti un set de vectori într-un alt spațiu vectorial, astfel încât problema să fie mai ușoară (sau posibilă) din punct de vedere computațional. În cazul dvs. ați transforma un set de vectori în P2 (polinom de gradul al doilea) în R3 (vector de gradul al treilea în setul numerelor reale), ați simplifica expresia și ați converti vectorul R3 înapoi în P2 pentru a-l da înapoi utilizatorului. După cum sunt sigur că vă dați seama, această problemă ar putea fi un pic mai mult decât erați pregătiți, cu o mare dependență de matematică, dar ar putea fi un exercițiu bun pentru dumneavoastră. În orice caz.

Sper să vă fie de ajutor!

Comentarii

  • Exemplul de intrare nu are spații. Oricum, extractorul numeric din iostreams C++ nu necesită spațiu la sfârșit. Fără o bibliotecă de expresii regulate pentru o divizare sofisticată, ar fi probabil mai simplu (și mai convențional pentru C++) să construiți o gramatică și un parser simplu. –  > Por Potatoswatter.
  • Am vrut să spun că ar trebui să se împartă pe operatori, editat. I️ am încercat să fiu cât mai amănunțit posibil, așa funcționează bibliotecile de calcul simbolic, așa că așa am descris procesul. –  > Por Asher Mancinelli.

Tags: