大数乗算の計算原理
5020 ワード
最近筆者はBATのようなIT会社を面接しているが、ネット筆記試験では大数乗算のような問題型が必要だとは思わなかった.個人的な理由もあって、長い間OJをブラシしないで、コードはすべてたたくことができませんでした.ここで今回の筆記試験の問題を記録します.例を挙げて本題を導入します:もしあなたに2つの整数を入力させるならば、整数の長さn(n<21)、それらの和を求めます.次に大数乗算の原理を述べ,コードの後ろに貼り付ける.演算原理:一般的なプログラミング言語で内定した長い整形のデータの長さも数十位にはならないが、面接官が100位以上のデータを計算させたらどうする?このときは文字列を十分に利用して操作しなければならない.1)文字列を用いて数字文字を格納し,演算時に数字文字を対応する整形に変換する.2)ビット累乗で結果を配列に記録する.(注意演算は右から左へ)3)配列内のデータがキャリーされている場合は、1桁進む必要があります.
コードを貼る(同じように、偶然のCoding with C):コード1:キャリーを反復に書き込む;
問題があれば、修正を指摘してください.
コードを貼る(同じように、偶然のCoding with C):コード1:キャリーを反復に書き込む;
#include
#include
#include
#define MAX_INPUT_SIZE 21//
#define MAX_RESULT_SIZE (MAX_INPUT_SIZE *2 - 1)//
void mult(char result[], char a[], char b[])
{
int a_len=strlen(a);//a
int b_len=strlen(b);//b
char carry=0;//
char tmp;//
int a_index, b_index, r_index;//
// ,
for (b_index = b_len - 1; b_index >=0; b_index--)
{//
for (a_index = a_len - 1; a_index >=0; b_index--)
{
r_index = (b_len-1-b_index) + (a_len-1-a_index);//
//string , ‘0’
tmp = (a[a_index] - '0') * (b[b_index] - '0') + result[r_index] + carry;// ,
result[r_index] = tmp % 10;
carry = tmp / 10;//
}
// ( )
while (carry)
{
// carry : , ( ) result 。
r_index++;
tmp = result[r_index] + carry;//
result[r_index] = tmp % 10;
carry = tmp / 10;
}
}
}
void print_result(char result[])
{
int i = MAX_RESULT_SIZE - 1;
while (!result[i])
{
i--;
}
while (i >= 0)
{
putchar(result[i--] + '0');
}
printf("
");
}
int main(int argc,char *argv)
{
//
char a[MAX_INPUT_SIZE], b[MAX_INPUT_SIZE],result[MAX_RESULT_SIZE];
//
memset(a, 0, MAX_INPUT_SIZE);
memset(b, 0, MAX_INPUT_SIZE);
memset(result, 0, MAX_RESULT_SIZE);
//
while(scanf("%s%s",&a,&b)!=EOF)
{
//
mult(result, a, b);
//
print_result(result);
}
return 0;
}
問題があれば、修正を指摘してください.