به کمک اين الگوريتم شما مي توانيد اعداد صحيح بزرگ را در هم ضرب کنيد. عمل اصلي در دو تابع MultiplyLargNumbers و doCarry انجام مي شود. تابع اول دو آرايه از اعداد صحيح را دريافت کرده و حاصاضرب آنها را برمي گرداند. براي محاسبه حاصاضرب از الگوريتم زير استفاده مي شود:
تابع doCarry براي يکاني کردن اعداد موجود در خانه هاي آرايه به کار مي رود. با توجه به اينکه نتيجه حاصل از تابع قبلي مي تواند اعداد بزرگتر از 10 باشد و اينکه براي درست دريافت نتيجه درست از اين الگوريتم، اعداد موجود در خانه هاي آرايه بايد کوچکتر از 10 باشد از اين تابع استفاده مي کنيم که رقم يکان را در اعداد بزرگتر از 10 در همان خانه نگه ذاشته و دهگان را به خانه بعدي اضافه مي کند.
اين الگوريتم براي اعداد تا چهار رقمي بهترين روش مي باشد ولي براي اعداد بزرگتر از آن بهتر است با روش تقسيم و حل از اين الگوريتم به همراه يک تابع بازگشتي کمکي استفاده نماييد.
کد C ( با سی++ فرقی نداره فقط کافیه printf ها رو با cout و بجای scanf ها هم از cin استفاده کنید.)
#define MAX_DIGITS 2048
// اعداد بصورت آرايه اي از نوع اعداد صحيح نگهداري خواهند شد
// انديس 0 مقدار يکان و انديس 1 مقدار دهگان و ... را ذخيره خواهند کرد
void MultiplyLargNumbers(int *a, int *b, int *ret, int d);
void doCarry(int *a, int d);
void getNum(int *a, int *d_a, int order);
void printNum(int *a, int d);
int main() {
int a[MAX_DIGITS]; // اولين عدد براي ضرب
int b[MAX_DIGITS]; // دومين عدد براي ضرب
int r[6 * MAX_DIGITS]; // نتيجه محاسبات در اين متغير قرار مي گيرد
int d_a; // طول اولين عدد
int d_b; // طول دومين عدد
int d; // حداکثر طول مجاز براي ضرب دو عدد
int i, j; // شمارنده حلقه
clock_t start; // براي محاسبه زمان لازم براي اجراي الگوريتم
// طول بزرگترين عدد وارد شده براي عمل ضرب را به عنوان شمارنده حلقه در نظر مي گيريم
// دو برابر شمارنده حلقه را به عنوان طول حاصاضرب دو عدد در نظر مي گيريم
//و در آرايه هاي وارد شده از طول خود عدد تا اين خانه را برابر صفر مي کنيم
i = (d_a > d_b) ? d_a : d_b;
for(d = 1; d < i; d *= 2);
for(i = d_a; i < d; i++) a[i] = 0;
for(i = d_b; i < d; i++) b[i] = 0;
//براي محاسبه مدت زمان اجرا، زمان فعلي سيستم را نگه مي داريم
//پس از پايان کار زمان سيستم را دوباره مي گيريم و از آن کم مي کنيم
//مقدار باقي مانده زمان اجرا بر حسب ميلي ثانيه مي باشد
start = clock();
for(j = 0; j < i; j++) {
MultiplyLargNumbers(a, b, r, d); // حاصلضرب دو آرايه را حساب مي کند
doCarry(r, 2 * d); // آرايه را يکاني مي کند
}
//دو آرايه از اعداد صحيح دريافت کرده و حاصلضرب آنها را برمي گرداند
//اعداد موجود در خانه هاي آرايه حاصلضرب مي تواند بزرگتر از 10 باشد
//که پس از پايان کار بايد اين اعداد يکاني شوند
void MultiplyLargNumbers(int *a, int *b, int *ret, int d) {
//اعداد موجود در آرايه را بررسي کرده و در صورتي که بزرگتر از 10 باشند
//رقم يکان را نگه داشته و رقم دهگان را به انديس بعدي اضافه مي کند
void doCarry(int *a, int d) {
int c;
int i;
c = 0;
for(i = 0; i < d; i++) {
a[i] += c;
if(a[i] < 0) {
c = -(-(a[i] + 1) / 10 + 1);
} else {
c = a[i] / 10;
}
a[i] -= c * 10;
}
if(c != 0) fprintf(stderr, "Overflow %d\n", c);
}
//عدد را از ورودي گرفته و در آرايه قرار مي دهد و طول آرايه را نيز برمي گرداند
void getNum(int *a, int *d_a, int order) {
int c;
int i;
*d_a = 0;
printf("Please enter %dth number: ", order);
while(true) {
c = getchar();
if(c == '\n' || c == EOF) break;
if(*d_a >= MAX_DIGITS) {
fprintf(stderr, "using only first %d digits\n", MAX_DIGITS);
while(c != '\n' && c != EOF) c = getchar();
}
a[*d_a] = c - '0';
++(*d_a);
}
// عدد را معکوس کرده و اولين رقم را در اولين خانه آرايه قرار مي دهد
for(i = 0; i * 2 < *d_a - 1; i++) {
c = a[i], a[i] = a[*d_a - i - 1], a[*d_a - i - 1] = c;
}
}
void printNum(int *a, int d) {
int i;
for(i = d - 1; i > 0; i--) if(a[i] != 0) break;
for(; i >= 0; i--) printf("%d", a[i]);
}
علاقه مندی ها (Bookmarks)