پیاده سازی الگوریتم تقسیم دو تا چند جمله ای در ++C

[ehsan_faal]

سلام دوستان.
من برای تقسیم دو چند جمله ای به هم در حالتی که صرایب میتونن از نوع دابل یا مختلط باشن قصد دارم این الگوریتم رو در زبان ++C بنویسم:


degree(P):
return the index of the last non-zero element of P;
if all elements are 0, return -∞

polynomial_long_division(N, D) returns (q, r):
// N, D, q, r are vectors
if degree(D) < 0 then error
if degree(N) ≥ degree(D) then
q ← 0
while degree(N) ≥ degree(D)
d ← D shifted right by (degree(N) - degree(D))
q(degree(N) - degree(D)) ← N(degree(N)) / d(degree(d))
// by construction, degree(d) = degree(N) of course
d ← d * q(degree(N) - degree(D))
N ← N - d
endwhile
r ← N
else
q ← 0
r ← N
endif
return (q, r)

که یه مثال از روند مرحله به مرحله این الگوریتم هم میشه این:

0 1 2 3
----------------------
N: -42 0 -12 1 degree = 3
D: -3 1 0 0 degree = 1

d(N) - d(D) = 2, so let's shift D towards right by 2:

N: -42 0 -12 1
d: 0 0 -3 1

N(3)/d(3) = 1, so d is unchanged. Now remember that "shifting by 2"
is like multiplying by x2, and the final multiplication
(here by 1) is the coefficient of this monomial. Let's store this
into q:
0 1 2
---------------
q: 0 0 1

now compute N - d, and let it be the "new" N, and let's loop

N: -42 0 -9 0 degree = 2
D: -3 1 0 0 degree = 1

d(N) - d(D) = 1, right shift D by 1 and let it be d

N: -42 0 -9 0
d: 0 -3 1 0 * -9/1 = -9

q: 0 -9 1

d: 0 27 -9 0

N ← N - d

N: -42 -27 0 0 degree = 1
D: -3 1 0 0 degree = 1

looping again... d(N)-d(D)=0, so no shift is needed; we
multiply D by -27 (= -27/1) storing the result in d, then

q: -27 -9 1

and

N: -42 -27 0 0 -
d: 81 -27 0 0 =
N: -123 0 0 0 (last N)

d(N) < d(D), so now r ← N, and the result is:

0 1 2
-------------
q: -27 -9 1 → x2 - 9x - 27
r: -123 0 0 → -123

کدهایی که من نوشتم اینان:

/*
* PolynomialDegree.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/

#ifndef POLYDIV_POLYNOMIALDEGREE_H_
#define POLYDIV_POLYNOMIALDEGREE_H_
#include "armadillo"
using namespace arma;

namespace Coupler{
template<typename T>
auto getDegree(const arma::Col<T>& input)->size_t {
size_t degree = input.n_elem;
vec query = arma::real(input);
while (query(input.n_elem - degree) == 0) {
degree--;
}
return --degree;
}
}



#endif /* POLYDIV_POLYNOMIALDEGREE_H_ */



و

/*
* ShiftPolynomial.h
*
* Created on: Aug 24, 2015
* Author: Ehsan
*/

#ifndef POLYDIV_SHIFTPOLYNOMIAL_H_
#define POLYDIV_SHIFTPOLYNOMIAL_H_
#include "armadillo"
using namespace arma;
namespace Coupler{
template<typename T>
auto shiftPolynomial(const Col<T>& input, const int& howMuch)->Col<T> {
if (howMuch > 0) {
Col<T> result(input.n_elem + howMuch, fill::none);
result.rows(0, howMuch - 1).zeros();
result.rows(howMuch, result.n_elem - 1) = input;
return result;
}
return input;
}
}
#endif /* POLYDIV_SHIFTPOLYNOMIAL_H_ */



و

/*
* PolyDiv.h
*
* Created on: Aug 26, 2015
* Author: Ehsan
*/

#ifndef POLYDIV_POLYDIV_H_
#define POLYDIV_POLYDIV_H_
#include "PolynomialDegree.h"
#include "ShiftPolynomial.h"

namespace Coupler{
template<typename T1 ,typename T2>
auto polydiv(const Col<T1>& Nu,const Col<T2>& De)->Col<T1>{
auto Ndegree = Coupler::getDegree(Nu), Ddegree = Coupler::getDegree(De);
Col<T1> N{flipud(Nu)};
Col<T2> D{flipud(De)};
Col<T1> Q((Ndegree - Ddegree + 1),fill::zeros);
size_t smallD_Degree = 0;
while (Ndegree >= Ddegree) {
Col<T1> smallD = conv_to<Col<T1>>::from(Coupler::shiftPolynomial(D, (Ndegree - Ddegree)));
auto index = Ndegree - Ddegree;
smallD_Degree = Coupler::getDegree(smallD);
Q(index) = N(Ndegree) / smallD(smallD_Degree);
smallD *= Q(index);
N -= smallD;
Ndegree = Coupler::getDegree(Col<T1>{flipud(N)});
}
return flipud(Q);
}
}
#endif /* POLYDIV_POLYDIV_H_ */



و نهایتا تابع main :

#include <iostream>
#include "armadillo"
#include "PolyDiv.h"
using namespace arma;
using namespace std;

auto main()->int{
cx_vec D{{-9.074e-001,-3.645e-015},
{2.768e+001,-1.051e-013},
{-4.159e+001,-1.528e-013},
{+4.167e+001,+1.560e-013},
{+2.751e+001,+9.958e-014},
{+1.000e+000,+3.641e-015}};
vec N{-1,0,1};
cout<<Coupler::polydiv(D,N)<<endl;
return 0;
}



تنها تفاوتی که توی کد من با این الگوریتم هست اینه که اون برای محاسبه درجه و کلا کار با چند جمله ایها درجه ها رو از کم به زیاد در نظر گرفته یعنی اولین جمله درجه صفر داره و ..
ولی برای من چون ورودیها رو از یه سری تابع دیگه میگیرم و به تابع getDegree در جاهای دیگه هم نیاز دارم پس ترتیب چندجمله ایهام رو عکس در نظر گرفتم.

نمیدونم چرا این کد انگار توی یه حلقه بینهایت میفته و به محض فراخوانی تابع polydiv برنامه دیگه تموم نمیشه.

کسی میتونه راهنماییم کنه؟

لینک صفحه حاوی الگوریتم (http://rosettacode.org/wiki/Polynomial_long_division#C.2B.2B)

با تشکر

[rahnema1]

سلام
از روی کد octave که در همون سایت بود ایجوری نوشتم تست کنید ببینید درسته یا نه

#include "armadillo"
#include <tuple>
#include <iostream>
using namespace arma;
using namespace std;

template<typename T>
auto divide_poly(Col<T> numerator, const Col<T>& denominator)
{
auto gd = denominator.size();
auto pv = Col<T> (numerator.size(), fill::none);

pv.rows(0, gd - 1) = denominator;
pv.rows(gd, numerator.size() - 1).zeros();
auto q = Col<T>();
auto r = Col<T>();
if (numerator.size() >= gd ) {
while(numerator.size() >= gd) {
q.resize(q.size() + 1);
q(q.size() - 1) = numerator(0)/ pv(0);
numerator = numerator - pv * (numerator(0)/ pv(0));
numerator.rows(0,numerator.size() - 2) = numerator.rows(1, numerator.size() - 1);
numerator.resize(numerator.size() - 1);
pv.resize(pv.size() - 1);
}
r = numerator;

} else {
q.zeros(1);
r = numerator;
}
return std::make_tuple(q, r);
}
int main()
{
auto result = divide_poly(vec{1.0, -12.0, 0.0, -42.0}, vec{1.0, -3.0});

cout << std::get<0>(result) << std::endl;
cout << std::get<1>(result);
return 0;
}

[ehsan_faal]

من کد شما رو اینجوری تغییر دادم ولی اروری میده که من ازش سر در نمیارم:

#include "armadillo"
#include <tuple>
#include <iostream>
using namespace arma;
using namespace std;
template<typename T>
tuple<Col<T>, Col<T>> divide_poly(Col<T> numerator, const Col<T>& denominator) {
auto gd = denominator.size();
auto pv = Col<T>(numerator.size(), fill::none);

pv.rows(0, gd - 1) = denominator;
pv.rows(gd, numerator.size() - 1).zeros();
auto q = Col<T>();
auto r = Col<T>();
if (numerator.size() >= gd) {
while (numerator.size() >= gd) {
q.resize(q.size() + 1);
q(q.size() - 1) = numerator(0) / pv(0);
numerator = numerator - pv * (numerator(0) / pv(0));
numerator.rows(0, numerator.size() - 2) = numerator.rows(1,
numerator.size() - 1);
numerator.resize(numerator.size() - 1);
pv.resize(pv.size() - 1);
}
r = numerator;

} else {
q.zeros(1);
r = numerator;
}
return std::make_tuple(q, r);
}
int main() {
auto result = divide_poly(vec { 1.0, -12.0, 0.0, -42.0 }, vec { 1.0, -3.0 });

cout << std::get<0>(result) << std::endl;
cout << std::get<1>(result);
return 0;
}

متن ارور:


C:\Ceemple\user\Test\Source.cpp:26:22: error: redefinition of 'divide_poly' as different kind of symbol
tuple<Col<T>,Col<T>> divide_poly(Col<T> numerator, const Col<T>& denominator){
^
note: previous definition is here

راستی من ورودی هام یکیشون مختلط (صورت کسر) و اون یکی دابل.
به همین خاطر T1,T2 گذاشته بودم.

[rahnema1]

درسته using namespace نذاشته بودم
وقتی کامپایل می کنید std=c++1y- بذارید
از متن خطا اینجور بر میاد یا توی همون سورس یا سورس دیگه ای تابع divide_poly قبلا تعریف شده. اگه بتونید همین سورس را در یک فایل جدید بذارید و یا نام تابع را تغییر بدهید ببینید درست می شه

[ehsan_faal]

ممنون.حل شد:تشویق: