/* 俄罗斯式算法求大数乘 *//* 原理: 举例 ( 9 * 8 ) *//* (乘数) 9 (被乘数)8 *//* 4 16 *//* 2 32 *//* 1 64 *//* 将乘数为奇时的被乘数相加 8 + 64 = 72 OK ! *//* 这钟算法只比传统的好,分治法就比这种要好 *//* 编译环境: VC ++ 6.0 *//* Author: 江南孤峰 Time: 2006-10-24 */ #include <stdio.h>#include <ctype.h> #define MAX 1000 //存结果的数组大小,乘数较大时需要修改这里#define MULMAX 100 //存两个乘数的数组大小 void mul(char a[],char b[],int la,int lb);void divTwo(char a[],int *la);void add(char a[],char b[],int *la,int *lb);int input(char a[],char b[],int *la,int *lb); void mul(char a[],char b[],int length_a,int length_b){ // 求数组 a 与 b 中数相乘的结果 char result[MAX]; int la = length_a,lb = length_b,lr = 0,i = 0; while(a[0] != '0' || la != 0){ if(a[0] % 2) // 乘数为奇 add(result,b,&lr,&lb); divTwo(a,&la); // 乘数除 2 add(b,b,&lb,&lb); // 被乘数扩大一倍 } for(i = lr - 1; i >= 0; i --) putchar(result[i]);} void divTwo(char a[],int *la){ // 数组 a 中的数除 2 int rr,i = *la - 1,t; if(a[i] == '1') *la = i; for(rr = t = 0; i >= 0; i --){ t = rr + a[i] - 48; if( t >= 2 ){ a[i] = t / 2 + 48; rr = (t % 2) ? 10 : 0; } else{ if(a[i] == '1') rr = 10; a[i] = '0'; } }} void add(char a[],char b[],int *la,int *lb){ // 数组 a 与 数组 b的和 存于数组 a 中 int t,rr,n; for(t = rr = n = 0; n < *la && n < *lb; n ++){ t = rr + a[n] + b[n] - 96; a[n] = t % 10 + 48; rr = t / 10; } for(; n < *la; n ++){ if( !rr ) break; t = a[n] + rr; a[n] = t % 10 + 48; rr = t / 10; } for(; n < *lb; n ++){ t = b[n] + rr - 48; a[n] = t % 10 + 48; rr = t / 10; } if( rr ){ a[n] = '1'; n ++; } *la = n;} int input(char a[],char b[],int *la,int *lb){ // 输入两个数字数组 char stack[MULMAX]; int lena,lenb,i; printf("Input a:"); for(lena = 0;; lena ++){ scanf("%c",&stack[lena]); if(stack[lena] == '\n') break; if(stack[lena] < 48 || stack[lena] > 57) // 含有非数字 不合法 return 0; } for(i = 0; i < lena; i ++) a[i] = stack[lena-i-1]; printf("Input b:"); for(lenb = 0;; lenb ++){ scanf("%c",&stack[lenb]); if(stack[lenb] == '\n') break; if(stack[lenb] < 48 || stack[lenb] > 57) return 0; } if(a[lena-1] == 48 || stack[lenb] == 48)// 首位为 0 不合法 return 0; for(i = 0; i < lenb; i ++) b[i] = stack[lenb-i-1]; *la = lena; *lb = lenb; return 1;} int main(){ char a[MULMAX],b[MULMAX],c; int lena,lenb; while( 1 ){ if( input(a,b,&lena,&lenb) ) mul(a,b,lena,lenb); else{ getchar(); // 接收回车符 printf("Input error !\n"); } printf("\nContinue(y/n)? :"); c = getchar(); c = tolower(c); getchar(); // 接收回车符 if(c == 'y') continue; else break; } return 0;}
评论