ضرب چند جمله ای ها

[Mahyaa]

این سوال من شاید بیشتر به الگوریتم مربوط بشه:متفکر: ولی چون میخوام با دلفی یا CBuilder پیاده سازی کنم ، اینجا مطرحش کردم.

من میخوام n تا چند جمله ای رو در هم ضرب کنم . چه DataStructure پیشنهاد میکنید .مثلا اگر از TList استفاده کنم ، درسته ؟:متفکر:

باتوجه به اینکه تعداد جملات این چند جمله ای ها ، باهم برابر نیست ! و این ضرب در چندین مرحله انجام میشه .

[dkhatibi]

احتمالا روشهای مطرح شده در کتابهای ساختمان داده بهترین روشها رو معرفی می کنند.
بهترین کار ساختن پشته ها و صفهایی از رشته هاست که در این کتابها مطرح شده اند

[Mahdi_Delphi]

میتونی خودت ساختمان داده ی مورد نیازت رو طراحی کنی.

با لیست های پیوندی جالب خواهد شد. چون فضای اضافی نمی گیره.

هر node هم میتونه یه جمله رو نگه داره.

[saeed_rezaee]

سلام.
من قبلا این کار رو با لیستهای پیوندی در پاسکال برای پروژه دانشگاه انجام دادم.
منتهی اون رو یدا نکردم که بعنوان نمونه بگذارم.
ولی بهترین جواب رو با لبستهای پیوندی میتونی بگیری.

[Mahyaa]

ممنون دوستان به خاطر راهنماییهاتون .

از لیست پیوندی استفاده کردم . هرجمله از این چند جمله ای را یک Record و خود چند جمله ای رو یک کلاس گرفتم و جواب گرفتم . اما یک مشکل وجود داره و اونهم سرعت محاسبه است . در عبارت های با درجه بالا سرعت کمی داره :اشتباه: .


type
TMonoNomialPtr = ^TMonoNomial;
TMonoNomial = record
Coefficient : Integer;
Exponent : Integer;
Next : TMonoNomialPtr;
end;
TPolyNomial = class
StartM : TMonoNomialPtr;
Num : Integer;
procedure AddNom(var aCurrentItem : TMonoNomialPtr; Coe , Exp : Integer);
procedure AppendNom(var aCurrentItem , aNewItem : TMonoNomialPtr);
procedure DelNom(BlackNom : TMonoNomial);
procedure ClearPoly;
function FindExpAndAdd(Coe , Exp : Integer) : Boolean;
procedure DisplayPoly;
end;


اگر فرض کنیم n تا چند جمله ای باشه : P1..Pn
کاری که من کردم اینه که در ضرب دو چند جمله ای P1 , P2 ، تک تک جملات P1 را در همه جملات P2 ضرب کردم و بعد چند جمله ای حاصل رو (R) در Pi ضرب کردم تا انتها .

مثلا در عباراتی مثل :


(X+1)^1456 * (x^45+1)^345 , ....

که توانها بزرگند ، سرعت خیلی پایین میاد .

ببخشید به خاطر اینکه سوالم طولانیه وممنون میشم اگه راهنمایی کنید و اشکال کارم رو بگید.

[Mahdi_Delphi]

مزیت این روش اینه که نیازی نیست جملاتی که ضریب صفر دارند رو ذخیره کرد.

مثلا 1+2x^2250 از درجه 2250 هست ولی فقط دارای دو جمله است.

ضرب n تا چند جمله ای هم اگه n بزرگ باشه و تعداد جملات هر چندجمله هم زیاد باشه مسلما کار وقت گیری هست ولی با بهینه کردن کد میشه سرعت کار رو بیشتر کرد.