програмирование
May 11, 2020
Вид производной многочлена
Это задача из курса: "Многопоточное программирование на C/C++" (stepik.org)
Задача простая - найти производную многочлена. Многочлен может быть большой, но только с неотрицательными целыми степенями и целыми коэффициентами. Подумайте, каким образом его лучше представить в памяти? Вывод должен быть без пробелов и в порядке убывания степеней, хотя ввод этому правилу может не удовлетворять. Также на ввод может быть подан многочлен с неприведенными слагаемыми.
Sample Input 1: x^2+x
Sample Output 1: 2*x+1
#include<iostream> #include<map> #include<string> #include<sstream> #include<regex> std::string derivative(std::string polynomial) { std::regex m("[+]?([-]?[0-9]*)[\\*]?(x?)[\\^]?([0-9]*)"); std::smatch sm; std::map<int, int> pow_k; while(regex_search(polynomial, sm, m) && polynomial.size() > 0) { int k = atoi(std::string(sm[1]).c_str()); int pow = atoi(std::string(sm[3]).c_str()); if (std::string(sm[2]) == "x") { if (pow == 0) pow = 1; if (k == 0) k = 1; if (std::string(sm[1]) == "-") k = -1; } pow_k[pow] += k; polynomial = sm.suffix(); } std::ostringstream result; auto begin = pow_k.rbegin(); auto end = pow_k.rend(); auto gets = [](int pow, int k){ std::ostringstream member; member << k * pow; if (pow > 1) member << "*x"; if (pow > 2) member << '^' << pow-1; return member.str(); }; if (begin != end) { result << gets( begin->first, begin->second ); ++begin; } for(; begin != end; ++begin) { if ( begin->first == 0 ) continue; if ( begin->second > 0 ) result << '+'; result << gets( begin->first, begin->second ); } return result.str(); }
Пришлось немного поработать с регулярными выражениями