アルゴリズムのまとめ——大整数加算

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ビットになる可能性があるからである.実際のプログラミングでは、配列の大きさを適切に決めるのに苦労する必要はありません.少し大きくしてもかまいません.うっかりこの「適切」な数値を計算していないと、配列が小さくなり、境界を越えたエラーが発生しないようにします.
リファレンス:
#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である.