アルゴリズムのまとめ——大整数加算
2429 ワード
問題の説明は200ビットを超えない2つの非負の整数の和を求める.
入力データ
2行あり、各行は200ビットを超えない非負の整数であり、余分なプリアンブル0はありません.
しゅつりょくようきゅう
1行、すなわち加算された結果.結果に余分なプリアンブル0は存在しない,すなわち結果が342であれば0342に出力できない.
入力サンプル
22222222222222222222
33333333333333333333
出力サンプル
Output Sample:
55555555555555555555
問題を解く構想.
まず、200ビットの整数を格納する問題を解決します.任意のC/C++固有のタイプの変数は保存できないことは明らかです.最も直感的な考えは、文字列で保存できることです.文字列は本質的に文字配列であるため、プログラミングを容易にするために、配列unsigned an[200]で200ビットの整数を保存し、an[0]にビット数を保存し、an[1]に10ビット数を保存し、an[2]に100ビット数を保存することもできます.では、2つの大きな整数加算をどのように実現するか.方法は簡単で、小学生の列の縦式をシミュレートして加算して、個位から1位ずつ加算して、10を超えてあるいは達成すると進位します.すなわち、第1の数をunsigned an 1[201]で保存し、第2の数をunsigned an 2[200]で表し、次いでビット毎に加算し、加算した結果を直接an 1に格納する.キャリー処理に注意してください.また,an 1配列長を201としたのは,2つの200ビットの整数が加算され,結果として201ビットになる可能性があるからである.実際のプログラミングでは、配列の大きさを適切に決めるのに苦労する必要はありません.少し大きくしてもかまいません.うっかりこの「適切」な数値を計算していないと、配列が小さくなり、境界を越えたエラーが発生しないようにします.
リファレンス:
実現テクニック1.実際のプログラミングでは、配列の大きさを適切に決めるのに苦労する必要はありません.少し大きくしてもかまいません.この「適切」な数値を誤って計算しないように、配列が小さくなり、境界を越えたエラーが発生しないようにします.
2.文25は、1文字形式の数字をunsigned型に変換する数である.例えば、文字’8’をunsigned型数8に変換する.charタイプの変数は,本質的にはintタイプであり,値は文字のAsciiコードである.文字’0’〜文字’9’のAscii符号は連続的に増加するので、‘8’〜‘0’の値は8である.
入力データ
2行あり、各行は200ビットを超えない非負の整数であり、余分なプリアンブル0はありません.
しゅつりょくようきゅう
1行、すなわち加算された結果.結果に余分なプリアンブル0は存在しない,すなわち結果が342であれば0342に出力できない.
入力サンプル
22222222222222222222
33333333333333333333
出力サンプル
Output Sample:
55555555555555555555
問題を解く構想.
まず、200ビットの整数を格納する問題を解決します.任意のC/C++固有のタイプの変数は保存できないことは明らかです.最も直感的な考えは、文字列で保存できることです.文字列は本質的に文字配列であるため、プログラミングを容易にするために、配列unsigned an[200]で200ビットの整数を保存し、an[0]にビット数を保存し、an[1]に10ビット数を保存し、an[2]に100ビット数を保存することもできます.では、2つの大きな整数加算をどのように実現するか.方法は簡単で、小学生の列の縦式をシミュレートして加算して、個位から1位ずつ加算して、10を超えてあるいは達成すると進位します.すなわち、第1の数をunsigned an 1[201]で保存し、第2の数をunsigned an 2[200]で表し、次いでビット毎に加算し、加算した結果を直接an 1に格納する.キャリー処理に注意してください.また,an 1配列長を201としたのは,2つの200ビットの整数が加算され,結果として201ビットになる可能性があるからである.実際のプログラミングでは、配列の大きさを適切に決めるのに苦労する必要はありません.少し大きくしてもかまいません.うっかりこの「適切」な数値を計算していないと、配列が小さくなり、境界を越えたエラーが発生しないようにします.
リファレンス:
#include
#include
#define MAX_LEN 200
int an1[MAX_LEN+10];
int an2[MAX_LEN+10];
char szLine1[MAX_LEN+10];
char szLine2[MAX_LEN+10];
int main()
{
scanf("%s", szLine1);
scanf("%s", szLine2);
int i, j;
// memeset an1 sizeof(an1) 0
//sizeof(an1) an1
//memset string.h
memset( an1, 0, sizeof(an1));
memset( an2, 0, sizeof(an2));
// szLine1 an1 ,
//an1[0]
int nLen1 = strlen( szLine1);
j = 0;
for( i = nLen1 - 1;i >= 0 ; i --)
an1[j++] = szLine1[i] - '0';
int nLen2 = strlen(szLine2);
j = 0;
for( i = nLen2 - 1;i >= 0 ; i --)
an2[j++] = szLine2[i] - '0';
for( i = 0;i < MAX_LEN ; i ++ ) {
an1[i] += an2[i]; //
if( an1[i] >= 10 ) { //
an1[i] -= 10;
an1[i+1] ++; //
}
}
bool bStartOutput = false; // 0
for( i = MAX_LEN; i >= 0; i -- ) {
if( bStartOutput)
printf("%d", an1[i]); // 0 ,
else if( an1[i] ) {
printf("%d", an1[i]);
bStartOutput = true; // 0 , 0 }
}
//--------------------------------------------------------------------------------
return 0;
}
実現テクニック1.実際のプログラミングでは、配列の大きさを適切に決めるのに苦労する必要はありません.少し大きくしてもかまいません.この「適切」な数値を誤って計算しないように、配列が小さくなり、境界を越えたエラーが発生しないようにします.
2.文25は、1文字形式の数字をunsigned型に変換する数である.例えば、文字’8’をunsigned型数8に変換する.charタイプの変数は,本質的にはintタイプであり,値は文字のAsciiコードである.文字’0’〜文字’9’のAscii符号は連続的に増加するので、‘8’〜‘0’の値は8である.