الگوریتم ضرب

[NIMA_1981]

سالام دوستان

میشه در مورد نوشتن الگوریتم ضرب به من کمک کنید - در حقیقت من می خوام یک عدد n رقمی را در یک عدد دیگه ضرب کنم - حالا این 2 تا عدد من در 2 تا vector از جنس integer قرار مگیره

میشه یک الگوریتم صحیح برای ضرب این دوتا عدد به من بگید

با تشکر

[mohammadriano]

سلام منظور شما رو متوجه نشدم
می خواهید از اپراتور (operator) تو برنامتون استفاده کنید؟

[senaps]

عدد های n رقمی رو در LONG INT ذخیره کنین....
بعدش هم که ضرب کنین و به خروجی بدین!:خجالت:

[NIMA_1981]

عدد های n رقمی رو در LONG INT ذخیره کنین....
بعدش هم که ضرب کنین و به خروجی بدین!:خجالت:
عزیزم نه اعداد بزرگتر از این رو میخوام صرب و جمع کنم


بله مثلا یک تابغ بنویسم که عمل ضرب رو برام انجام بده

[mohammadriano]

سلام
منظوورتون رو من متوجه نشدم اما اپراتور :
int operator *(int a,int b) { //o
int c; //o
;c = a*b
;return c
این از اپراتور * حالا اگه جواب نگرفتین منظور خودتون رو واضح تر و با حوصله در چند خط بنویسید
موفق باشید

[NIMA_1981]

بین دوست من این و که میدونم :لبخند:

مثلا 2 تا عدد داری که هر کدوم 200 رقم داره این عدد معمولا بزرگه که کامپیوتر نمیتونه این ها رو حساب کنه پس یکی از راهاش اینه که هر در تا عدد رو تی 2 تا آرایه بنویسیم بعد در هم دونه دونه در هم ضرب کنیم

[senaps]

مثلا 2 تا عدد داری که هر کدوم 200 رقم داره این عدد معمولا بزرگه که کامپیوتر نمیتونه این ها رو حساب کنه پس یکی از راهاش اینه که هر در تا عدد رو تی 2 تا آرایه بنویسیم بعد در هم دونه دونه در هم ضرب کنیم

عدد 200 رقمی یعنی از 3 هزار میلیارد هم بزرگ تر؟

نمی دونم چجوری میشه چنین اعدادی رو با هم ضرب کرد!! ولی چیزی که شما میخوای،
الگوریتمش میشه اینجوری که توی یه حلقه ی ساده، iوj رو که هر دو شمارنده های ارایه ها هستن رو در هم ضرب کنی!!اینجوری خونه های ارایه ها،دو به دو در هم ضرب شده،نتیجه توی ارایه ی سوم قرار میگیره!

[developing]

با سلام

شايد يادتون باشه كه وقتي مي خواستيم ضرب كردن رو توي ابتدايي ياد بگيريم از روش زير استفاده مي كرديم:
اعداد رو زير هم مي نوشتيم
بعد از سمت راست رقم اول عدد پاييني رو در ارقام عدد بالايي از راست به چپ ضرب مي كرديم.
براي رقم بعدي همين كار رو تكرار مي كرديم و در سطر بعدي مي نوشتيم البته با يك انتقال به چپِ عدد بدست آمده
در آخر تمام اعداد به دست آمده را با هم جمع مي كرديم.

اگه يادتون اومد الگوريتم زير كار بالا رو تكرار مي كنه و شما كافيه پياده سازيش كنيد:

1- هر دو عدد را در آرايه a , b قرار مي دهيم
2- يك متغير براي دريافت رقم نقلي در نظر مي گيريم و ابتدا آنرا صفر قرار مي دهيم.
3- آخرين عدد در آرايه a (منظور سمت راست ترين عدد) را
در عنصر اول آرايه b از راست به چپ ضرب مي كنيم. و آنرا با رقم نقلي جمع مي كنيم در اولين خانه آرايه ي c قرار مي دهيم. (اين كار را براي بقيه ي عناصر آرايه ي b تكرار مي كنيم.)
نكته: دستور سوم يك سطر از ضرب ها را بدست مي آورد.
دستور خط سوم را براي عناصر بعدي تكرار مي كنيم تا آرايه ي a به اتمام برسد. با اين تفاوت كه حاصلضرب عنصر a و عنصر b را علاوه بر جمع با رقم نقلي بايد با خانه ي متناظرش در C نيز جمع كنيم. و در هر بار كه سطري كامل شد.، يك خانه به سمت چپ در آرايه ي c مي رويم.
به طور مثال در ضرب 123 در 45 در هر مرحله جدول زير حاصل مي شود:
رقم نقلي به رنگ آبي
و آرايه ي C به رنگ قرمز مي باشد



مقدار عناصر آرايه ي c
رقم نقلي
ضرب 5 در 123

0000 0
0005 1
0015 1
0615 0

ضرب 4 در 123

0635 1
1535 0
4535




نكته: همواره تعداد عناصر آرايه ي c از بزرگترين مقدار عناصر a و b يكي بزرگتر است.

[senaps]

شايد يادتون باشه كه وقتي مي خواستيم ضرب كردن رو توي ابتدايي ياد بگيريم از روش زير استفاده مي كرديم:

عالی!! نمیدونم چرا هر وقت اسم ریاضیات میاد،من جا می مونم!!
واقعا عالی بود این الگوریتم!

[NIMA_1981]

با سلام

شايد يادتون باشه كه وقتي مي خواستيم ضرب كردن رو توي ابتدايي ياد بگيريم از روش زير استفاده مي كرديم:
اعداد رو زير هم مي نوشتيم
بعد از سمت راست رقم اول عدد پاييني رو در ارقام عدد بالايي از راست به چپ ضرب مي كرديم.
براي رقم بعدي همين كار رو تكرار مي كرديم و در سطر بعدي مي نوشتيم البته با يك انتقال به چپِ عدد بدست آمده
در آخر تمام اعداد به دست آمده را با هم جمع مي كرديم.

اگه يادتون اومد الگوريتم زير كار بالا رو تكرار مي كنه و شما كافيه پياده سازيش كنيد:

1- هر دو عدد را در آرايه a , b قرار مي دهيم
2- يك متغير براي دريافت رقم نقلي در نظر مي گيريم و ابتدا آنرا صفر قرار مي دهيم.
3- آخرين عدد در آرايه a (منظور سمت راست ترين عدد) را
در عنصر اول آرايه b از راست به چپ ضرب مي كنيم. و آنرا با رقم نقلي جمع مي كنيم در اولين خانه آرايه ي c قرار مي دهيم. (اين كار را براي بقيه ي عناصر آرايه ي b تكرار مي كنيم.)
نكته: دستور سوم يك سطر از ضرب ها را بدست مي آورد.
دستور خط سوم را براي عناصر بعدي تكرار مي كنيم تا آرايه ي a به اتمام برسد. با اين تفاوت كه حاصلضرب عنصر a و عنصر b را علاوه بر جمع با رقم نقلي بايد با خانه ي متناظرش در C نيز جمع كنيم. و در هر بار كه سطري كامل شد.، يك خانه به سمت چپ در آرايه ي c مي رويم.
به طور مثال در ضرب 123 در 45 در هر مرحله جدول زير حاصل مي شود:
رقم نقلي به رنگ آبي
و آرايه ي C به رنگ قرمز مي باشد



مقدار عناصر آرايه ي c
رقم نقلي
ضرب 5 در 123

0000 0
0005 1
0015 1
0615 0

ضرب 4 در 123

0635 1
1535 0
4535




نكته: همواره تعداد عناصر آرايه ي c از بزرگترين مقدار عناصر a و b يكي بزرگتر است.
دوست من ممنون فقط این الگوریتم یک اشکالی داره مثلا وقتی مجموع ضرب به اضافه عدد نقلی از 10 بزگتر بشه کل این عدد را وارد ماتریس مکنه در حالی که باید به 10 تقسیم بشه دوباره و مشکل دوم وقتی عدد اخر به اضافه عدد نقلی بازم از 10 بیشتر بشه باید دوباره تقسم بر 10 بشه مقدار عدد نقلی را در خانه بعدی بنویسه

[developing]

با سلام


دوست من ممنون فقط این الگوریتم یک اشکالی داره مثلا وقتی مجموع ضرب به اضافه عدد نقلی از 10 بزگتر بشه کل این عدد را وارد ماتریس مکنه در حالی که باید به 10 تقسیم بشه دوباره و مشکل دوم وقتی عدد اخر به اضافه عدد نقلی بازم از 10 بیشتر بشه باید دوباره تقسم بر 10 بشه مقدار عدد نقلی را در خانه بعدی بنویسه

حرف شما درسته من فكر مي كردم كه ديگه اين رو بدونيد ولي براي توضيح بيشتر:
1- در هر بار كه ضرب رو انجام مي ديد باقيمانده ي حاصلضرب به اضافه ي رقم نقلي به اضافه ي خانه ي مربوطه در آرايه ي c بر 10 رو،‌ بايد در خانه ي مورد نظر بنويسيد.
و 2- حاصلضرب به اضافه ي رقم نقلي به اضافه ي خانه ي مربوطه رو تقسيم بر 10 مي كنيم(اين يك تقسيم صحيح مي باشد) و در رقم نقلي قرار مي دهيم.

مثال در مورد اين توضيحات:
999 ضرب در 789
رقم نقلي به رنگ آبي
و آرايه ي C به رنگ قرمز مي باشد

ضرب 9 در 999

000000 0
000001 8
000091 8
008991 0


ضرب 8 در 999 با يك انتقال به چپ و جمع با مقادير قبل


009011 7
009911 7
088911 0
ضرب 7 در 999 با يك انتقال به چپ و جمع با مقادير قبل


089211 6
098211 6
788211

يك اشتباه: در مورد تعداد عناصر آرايه ي c من اشتباه كردم بايد تعدادش جمع تعداد عناصر دو آرايه ي a و b باشه.:خجالت::خجالت:

[sh4mid]

برو اینجا (http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic)