الگوریتم ضرب دو عدد صحیح بزرگ

[MORY8161]

سلام دوستان

من واقعا دارم کلافه میشم ازتون خواهش میکنم کمکم کنید

الگوریتم ضرب دو عدد صحیح بزرگ رو همراه با مرتبه اجرائیش رو لازم دارم

لطفا کمکم کنید

[afceaglee2013]

خیلی ساده س .. به همون روشی که خودمون 2 عدد رو ضرب میکنیم .. تنها تفاوتش اینه که زیر خط کسری 3 سطر (در ضرب 2عدد 3 رقمی) نداریم
ضرب 2 عدد 123 و 987 رو در نظر بگیرید
همونطور که در شکل میبینید فرض میکنیم عدد 123 در آرایه ی A و عدد 987 در آرایه ی B قرار دارد و آرایه ی C هم حاصل ضرب رو در خودش ذخیره میکنه .. برای کم شدن محاسبات و راحت ترشدن فهم مسئله 2 عدد a و b رو در آرایه ی خودش برعکس میکنیم (برای برعکس کردن میتونید بعد از خوندن رشته از ورودی اون رو بر عکس کنید) باز هم برای راحت تر کردن برنامه اگر عدد ها رو به صورت رشته خونده باشید بهتره از کد اسکی هر کاراکتر 48 واحد که کد اسکی صفر است رو کم کنید تا آرایه خود عدد رو داشته باشه نه کاراکتر مربوط به عدد رو .. چون در محاسبات و ضرب و جمع ما محتوای عددی رو لازم داریم نه کد اسکی کراراکتر رو

2 حلقه ی تو در تو به طول های هر عدد انتخاب کنبد فرض میکنیم شمارنده حلقه مربوط به عدد 123 متغییر i و شمارنده مربوط به عدد 987 متغییر j بوده و حلقه ی i داخل حلقه ی j است .. (شمارنده های حلقه ها از 0 شروع میشن)
داخل حلقه ی i دستور سمت چپ رو بتویسید

c[i+j]=a[i]*b[j] in neveshteye finglish arzeshe gazayi nadarad

بعد از اینکه از حلقه ی i خارج شد (قسمت پایین حلقه ی j) آرایه ی C شامل این اعداد است 21 , 14 ,7 ,0 ,0 ,0 (سمت راست در شکل)
که باید یکان هر عضو از آرایه در محل خود مانده و دهگان به مقدار عضو بعدی اضافه شود که نهایتا در این مثال خواهیم داشت 1 ،6 ،8 (این قسمت برای سادگی مسئله از قسمت اصلی کد جدا شده که میتوان در بدنه ی اصلی و داخل حلقه i نوشت)

حال یک واحد به مقدار j اضافه شده و دوباره همین عملیات انجام میشود (قسمت وسطی و سمت چپ شکل) .. توجه کنید که شمارنده آرایه ی C
i+j است که مقدار متغییر J باعث می شود فرضا در این مثال وقتی عدد 8 به اعضای آرایه ی A ضرب میشود حاصل ضرب 8 و 3 در عضو شماره 1 و ... قرار داده شود همچنین در ضرب عدد 9 به اعضای آزایه ی A حاصل ضرب 9 و 3 در عضو شماره 2 از آرایه ی C قرار بگیرد