Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <set>
- #include <vector>
- #include <utility>
- #include <iterator>
- #include <limits>
- #include <typeinfo>
- #include <functional>
- #include <iostream>
- #include <numeric>
- #include <cmath>
- #include <variant>
- #include <ranges>
- #include <vector>
- #include <list>
- #include <string>
- #include <vector>
- #include "src/Polynomial.cpp"
- #include <iomanip>
- #include <iostream>
- #include <string>
- #include <string_view>
- #include <type_traits>
- #define INT_SIZE 128
- #define INFINTY std::numeric_limits<int>::max()
- using basis_coefficients = std::vector<std::pair<float, float>>;
- using basis_polynomials = std::vector<std::vector<float>>;
- using coefs = std::vector<float>;
- using binomial_coefs = std::pair<float, float>;
- using namespace std;
- variant<bool, basis_polynomials> get_coefficients(float _pl, coefs _xi)
- {
- if(_xi.size() != set(_xi.begin(), _xi.end()).size())
- return false;
- float n = _xi.size();
- // for(int i = 0; i < _xi.size(); ++i){
- // cout << _xi[i] << ' ';
- // }
- // cout << '\n';
- basis_polynomials coefficients(n, coefs(2));
- for (float i = 0; i < n; ++i)
- {
- if (i == _pl)
- {
- coefficients[i][0] = INFINTY;
- coefficients[i][1] = INFINTY;
- }
- else
- {
- if(_xi[_pl] - _xi[i] == 0){
- for(int j = 0; j < _xi.size(); ++j){
- cout << _xi[j] << ' ';
- }
- cout << '\n';
- }
- coefficients[i][0] = 1 / (_xi[_pl] - _xi[i]);
- coefficients[i][1] = -_xi[i] / (_xi[_pl] - _xi[i]);
- }
- }
- basis_polynomials filtered_coefficients(n - 1, coefs(2));
- float j = 0;
- for (float i = 0; i < n; ++i)
- {
- if (coefficients[i][0] != INFINTY)
- {
- filtered_coefficients[j][0] = coefficients[i][1];
- filtered_coefficients[j][1] = coefficients[i][0];
- j++;
- }
- }
- return filtered_coefficients;
- }
- // coefs polynomialTimesPolynomial(coefs x, coefs y)
- // {
- // float n = x.size() + y.size() - 1;
- // coefs result(n, float(0));
- // for (float i = 0; i < x.size(); ++i)
- // {
- // for (float j = 0; j < y.size(); ++j)
- // {
- // result[i + j] += x[i] * y[j];
- // }
- // }
- // return result;
- // }
- // coefs calculateBasisLagrangePolynomial(basis_polynomials filtered_coefs)
- // {
- // float n = filtered_coefs.size();
- // coefs result(n + 1, float(0));
- // coefs tmp;
- // if (n == 1)
- // tmp = filtered_coefs[0];
- // else
- // tmp = polynomialTimesPolynomial(filtered_coefs[0], filtered_coefs[1]);
- // for (float i = 0; i < tmp.size(); ++i)
- // result[i] = tmp[i];
- // for (float i = 2; i < filtered_coefs.size(); ++i)
- // {
- // coefs tmp = polynomialTimesPolynomial(result, filtered_coefs[i]);
- // for (float j = 0; j < tmp.size(); ++j)
- // result[j] = tmp[j];
- // }
- // return result;
- // }
- // basis_polynomials calculateAllBasisLagrangePolynomial(coefs x)
- // {
- // float n = x.size();
- // basis_polynomials result;
- // for (float pl = 0; pl < n; ++pl)
- // result.push_back(calculateBasisLagrangePolynomial(get_coefficients(pl, x)));
- // return result;
- // }
- variant<bool, basis_polynomials> get_polynomial_l(coefs _xi)
- {
- variant<bool, vector<vector<int>>> ans;
- int n = _xi.size();
- basis_polynomials pli(n, coefs(n));
- for (float pl = 0; pl < n; ++pl)
- {
- variant<bool, basis_polynomials> check = get_coefficients(pl, _xi);
- if(holds_alternative<bool>(check))
- return false;
- basis_polynomials coefficients = get<basis_polynomials>(check);
- for (float i = 1; i < n - 1; ++i)
- {
- if (i == 1)
- {
- pli[pl][0] = coefficients[i - 1][0] * coefficients[i][0];
- pli[pl][1] = coefficients[i - 1][1] * coefficients[i][0] + coefficients[i][1] * coefficients[i - 1][0];
- pli[pl][2] = coefficients[i - 1][1] * coefficients[i][1];
- }
- else
- {
- coefs clone_pli(n, float(0));
- for (float val = 0; val < n; ++val)
- clone_pli[val] = pli[pl][val];
- coefs zeros_pli(n, float(0));
- float product_1;
- float product_2;
- for (float j = 0; j < n - 1; j++)
- {
- product_1 = clone_pli[j] * coefficients[i][0];
- product_2 = clone_pli[j] * coefficients[i][1];
- zeros_pli[j] += product_1;
- zeros_pli[j + 1] += product_2;
- }
- for (float val = 0; val < n; ++val)
- pli[pl][val] = zeros_pli[val];
- }
- }
- }
- cout << pli.size() << '\n';
- for(int i = 0; i < pli.size(); ++i){
- for(int j = 0; j < pli[i].size(); ++j){
- cout << pli[i][j] << ", ";
- }
- cout << " | ";
- }
- cout << "-> ";
- // vector<vector<int>> res;
- // int check = pli[0].size();
- // for(size_t i = 0; i < pli.size(); ++i){
- // vector<int> tmp_vec;
- // for(size_t j = 0; j < pli[i].size(); ++j){
- // float integerPart;
- // float fractionalPart = modf(pli[i][j], &integerPart);
- // if(fractionalPart == 0.0){
- // // cout << "int " <<integerPart << '\n';
- // int tmp = static_cast<int>(integerPart);
- // // res[i][j] = tmp;
- // tmp_vec.push_back(tmp);
- // }
- // if(tmp_vec.size() == check){
- // return false;
- // }
- // }
- // }
- // for(int i = 0; i < res.size(); ++i){
- // for(int j = 0; j < res[i].size(); ++j){
- // cout << res[i][j] << ' ';
- // }
- // cout << '\n';
- // }
- // if(res.size() == 0)
- // return false;
- return pli;
- }
- using int_coefs = vector<vector<int>>;
- variant<bool, Polynomial<int>> get_polynomial(coefs xi, coefs _yi)
- {
- variant<bool, Polynomial<int>> ans;
- float n = xi.size();
- basis_polynomials polynomial_l;
- bool bres;
- variant<bool, basis_polynomials> check = get_polynomial_l(xi);
- if(holds_alternative<bool>(check)){
- bres = get<bool>(check);
- return false;
- }
- polynomial_l = get<basis_polynomials>(check);
- for (float i = 0; i < n; ++i)
- {
- for (float j = 0; j < n; ++j)
- polynomial_l[i][j] *= _yi[i];
- }
- vector<float> Lagrange(n, float(0));
- for (float i = 0; i < n; ++i)
- {
- for (float j = 0; j < n; ++j)
- Lagrange[i] += polynomial_l[j][i];
- }
- for(int i = 0; i < Lagrange.size(); ++i){
- cout << Lagrange[i] << ' ';
- }
- cout << '\n';
- vector<int> res;
- for(size_t i = 0; i < Lagrange.size(); ++i){
- float integerPart;
- float fractionalPart = modf(Lagrange[i], &integerPart);
- if(fractionalPart == 0.0){
- res.push_back(static_cast<int>(Lagrange[i]));
- } else{
- return false;
- }
- }
- // Polynomial<int> res = Polynomial<int>(Lagrange);
- return Polynomial<int> {res};
- }
- bool IsPrime(const int n)
- {
- for (int i = 2; i * i <= n; i++)
- if (n % i == 0)
- return false;
- return n > 1;
- }
- set<int> toPrimeNumbers(int num)
- {
- num = abs(num);
- set<int> nums;
- if (num == 0)
- {
- return nums;
- }
- if (IsPrime(num))
- {
- nums.insert(num);
- return nums;
- }
- nums.insert(num);
- nums.insert(1);
- for (size_t i = 2; i * i <= num; ++i)
- {
- if (num % i == 0 && IsPrime(i))
- {
- nums.insert(i);
- nums.insert(num / i);
- }
- }
- return nums;
- }
- int gcd_n(const std::vector<int>& values) {
- if (values.empty())
- return -1;
- if (values.size() == 1)
- return values[0];
- int gcd_value = gcd(values[0], values[1]);
- for (int i = 2; i < values.size(); ++i) {
- gcd_value = gcd(gcd_value, values[i]);
- }
- return gcd_value;
- }
- pair<int, Polynomial<int>> ContPrim(Polynomial<int> f) {
- if (f == 0) {
- return make_pair(NULL, NULL);
- } else {
- // Get the coefficients of the polynomial
- vector<int> cl = f.get_coef();
- // Compute the greatest common divisor of the coefficients
- int cf = gcd_n(cl);
- for(size_t i = 0; i <= f.Degree(); ++i){
- cl[i] /= cf;
- }
- f.set_coef(cl);
- return make_pair(cf, f);
- }
- }
- set<pair<int, int>> CartesianS(set<int> A, set<int> B)
- {
- set<pair<int, int>> AxB;
- for (int a : A)
- {
- for (int b : B)
- {
- AxB.insert(make_pair(a, b));
- }
- }
- return AxB;
- }
- vector<vector<int>> CartesianSL(set<vector<int>> A, set<vector<int>> B)
- {
- vector<vector<int>> AxB;
- for (const vector<int> &a : A)
- {
- for (const vector<int> &b : B)
- {
- AxB.push_back(vector<int>(a.begin(), a.end()));
- AxB.back().insert(AxB.back().end(), b.begin(), b.end());
- }
- }
- return AxB;
- }
- set<vector<int>> SetOfLists(set<int> A)
- {
- set<vector<int>> B;
- for (int a : A)
- {
- B.insert({a});
- }
- return B;
- }
- set<vector<int>> CartesianLS(vector<set<int>> U)
- {
- int n = U.size();
- if (n == 0)
- {
- return {};
- }
- int N = 1;
- vector<set<vector<int>>> V(n);
- for (int i = 0; i < n; i++)
- {
- N *= U[i].size();
- V[i] = SetOfLists(U[i]);
- }
- if (N == 0)
- {
- return {};
- }
- set<vector<int>> P = V[0];
- for (int i = 1; i < n; i++)
- {
- set<vector<int>> temp;
- for (const vector<int> &p : P)
- {
- for (const vector<int> &v : V[i])
- {
- vector<int> new_p = p;
- new_p.insert(new_p.end(), v.begin(), v.end());
- temp.insert(new_p);
- }
- }
- P = temp;
- }
- return P;
- }
- // vector<int> DIV(vector<int> coefficients) {
- // while (coefficients.back() == 0) {
- // coefficients.pop_back();
- // }
- // return coefficients;
- // }
- // vector<int> QUO(vector<int> dividend, vector<int> divisor) {
- // int div_size = divisor.size();
- // int dif = dividend.size() - div_size + 1;
- // for (int i = 0; i < dif; i++) {
- // int coef = dividend[i] / divisor[0];
- // for (int j = 0; j < div_size; j++) {
- // dividend[i + j] -= coef * divisor[j];
- // }
- // }
- // return DIV(dividend);
- // }
- void printVector(const vector<int> &v)
- {
- cout << "[";
- for (int i = 0; i < v.size(); ++i)
- {
- cout << v[i];
- if (i != v.size() - 1)
- {
- cout << ", ";
- }
- }
- cout << "]";
- }
- void printSet(const set<int> &A)
- {
- copy(A.begin(), A.end(), ostream_iterator<int>(cout, " "));
- }
- struct Kroneker{
- int cf;
- Polynomial<int> prf;
- bool driven;
- Polynomial<int> x_a;
- Polynomial<int> quo;
- };
- int get_func_val(Polynomial<int> f, int xi){
- int res = f[0];
- for(size_t i = 1; i <= f.Degree(); ++i){
- res += f[i] * pow(xi, i);
- }
- return res;
- }
- struct Kroneker kroneker(Polynomial<int> f){
- int n = f.Degree();
- struct Kroneker ans;
- if(n == 0){
- ans.cf = abs(f[0]);
- return ans;
- }
- pair<int, Polynomial<int>> tmp = ContPrim(f);
- ans.cf = tmp.first;
- ans.prf = tmp.second;
- int m = n / 2;
- vector<int> x(m, 0);
- vector<int> y(m, 0);
- vector<set<int>> DY;
- for(size_t i = 0; i <= m; ++i){
- x[i] = i;
- y[i] = get_func_val(ans.prf, i);
- if(y[i] == 0){
- Polynomial<int> x_a{{-x[i], 1}};
- Polynomial<int> quo = (ans.prf / x_a).first; // возращается пара, возможен нецелочисленное деление
- ans.driven = false;
- ans.x_a = x_a;
- ans.quo = quo;
- return ans;
- }
- DY.push_back(toPrimeNumbers(y[i]));
- }
- set<vector<int>> M = CartesianLS(DY);
- vector<vector<float>> f_values;
- vector<vector<float>> vec_M;
- for(const auto& mu : M){
- vector<float> mu_values;
- vector<float> args;
- for(const auto& mu_elem : mu){
- mu_values.push_back(static_cast<float>(get_func_val(ans.prf, mu_elem)));
- args.push_back(static_cast<float>(mu_elem));
- }
- f_values.push_back(mu_values);
- vec_M.push_back(args);
- }
- for(size_t i = 0; i < vec_M.size(); ++i){
- variant<bool, Polynomial<int>> g = get_polynomial(vec_M[i], f_values[i]);
- if(holds_alternative<Polynomial<int>>(g)){
- // cout << "here" << '\n';
- Polynomial<int> h = get<Polynomial<int>>(g);
- // cout << h << '\n';
- pair<Polynomial<int>, int> tmp_rem = ans.prf / h;
- Polynomial<int> rem = ans.prf % h;
- if(h.Degree() >= 1 && rem[0] == 0 && rem.Degree() == -1 && tmp_rem.second == 1){
- if(h[h.Degree()] < 0){
- h *= -1;
- }
- ans.driven = false;
- ans.x_a = h;
- ans.quo = tmp_rem.first;
- return ans;
- }
- }
- }
- ans.driven = true;
- return ans;
- }
- int main0()
- {
- vector<set<int>> U = {{1, 2}, {3, 4, 5, 7}, {8, 9}}; // Пример списка множеств U
- set<vector<int>> result = CartesianLS(U);
- cout << "Cartesian product of U: ";
- for (const vector<int> &list : result)
- {
- printVector(list);
- cout << " ";
- }
- cout << endl;
- return 0;
- }
- int main1()
- {
- set<int> A = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; // Пример множества A
- set<vector<int>> result = SetOfLists(A);
- cout << "Set of lists B: ";
- for (const vector<int> &list : result)
- {
- printVector(list);
- cout << " ";
- }
- cout << endl;
- return 0;
- }
- int main2()
- {
- set<vector<int>> A = {{1}, {2}, {4}}; // Пример множества A
- set<vector<int>> B = {{1, 1}, {1, 2}, {2, 1}, {2, 2}}; // Пример множества B
- vector<vector<int>> result = CartesianSL(A, B);
- cout << "Cartesian product of A and B: ";
- for (const vector<int> &pair : result)
- {
- printVector(pair);
- cout << " ";
- }
- cout << endl;
- return 0;
- }
- int main3()
- {
- set<int> B = {1, 2, 3}; // Пример множества A
- set<int> A = {4, 5}; // Пример множества B
- set<pair<int, int>> result = CartesianS(A, B);
- cout << "Cartesian product of A and B: ";
- for (auto it = result.begin(); it != result.end(); ++it)
- {
- cout << "(" << it->first << ", " << it->second << ") ";
- }
- cout << endl;
- return 0;
- }
- int main4()
- {
- set<int> A;
- int a = -12;
- printSet(toPrimeNumbers(a));
- return 0;
- }
- int main(){
- Polynomial<int> f({8, 0, 0, 0, 2});
- Kroneker tmp = kroneker(f);
- cout << tmp.cf << '\n';
- cout << tmp.prf << '\n';
- cout << tmp.driven << '\n';
- cout << tmp.x_a << '\n';
- cout << tmp.quo << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement