C/C++_2019_7_19(超長正整数加算)
7782 ワード
戦略を立てる中で、千里の外に勝つ!
タイトルの説明
超長正整数加算|時間制限:1秒|メモリ制限:32768 Kアルゴリズムを設計して2つの超長正整数の加算を完了してください.
インタフェースの説明
説明の入力
2文字列の数値を入力
出力の説明
加算した結果を出力し、string型
例
入力99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
テーマ解析
本題はアナログ加算です.
問題を解く構想.
加算演算は、各ビットの値が現在の対応ビットの2数の和+進位に等しい.加算であるため、現在のビットの和は最大19(9+9+進位1)であるため、発生する進位は最大1である.したがって、第1ステップ:対応ビットの和を計算し、対応ビット加算+前のビットの進位第2ステップ:現在のビットの値を更新し、%10を更新し、値を文字(-‘0’)に変換して文字結果に格納する第3ステップ:進位を更新し、/10を計算し、次のビットの値を計算する.最後のステップ:計算が終わった後、キャリーが1の場合、最上位にキャリーが発生したことを示しますので、もう1つ追加する必要があります.これが最後の結果です.結果が生成された後,逆置が必要となり,最終結果が得られる.
サンプルコード
タイトルの説明
超長正整数加算|時間制限:1秒|メモリ制限:32768 Kアルゴリズムを設計して2つの超長正整数の加算を完了してください.
インタフェースの説明
/* 。
: String addend: String augend: : */
public String AddLongInteger(String addend, String augend) {
/* */
return null;
}
説明の入力
2文字列の数値を入力
出力の説明
加算した結果を出力し、string型
例
入力99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999
テーマ解析
本題はアナログ加算です.
問題を解く構想.
加算演算は、各ビットの値が現在の対応ビットの2数の和+進位に等しい.加算であるため、現在のビットの和は最大19(9+9+進位1)であるため、発生する進位は最大1である.したがって、第1ステップ:対応ビットの和を計算し、対応ビット加算+前のビットの進位第2ステップ:現在のビットの値を更新し、%10を更新し、値を文字(-‘0’)に変換して文字結果に格納する第3ステップ:進位を更新し、/10を計算し、次のビットの値を計算する.最後のステップ:計算が終わった後、キャリーが1の場合、最上位にキャリーが発生したことを示しますので、もう1つ追加する必要があります.これが最後の結果です.結果が生成された後,逆置が必要となり,最終結果が得られる.
サンプルコード
#include
#include
#include
using namespace std;
string addStrings(string num1, string num2) {
//
int i = num1.size() - 1;
int j = num2.size() - 1;
string result = "";
//
int carry = 0;
while (i >= 0 || j >= 0){
if (i >= 0){
carry += num1[i] - '0';
}
if (j >= 0){
carry += num2[j] - '0';
}
// 10
result += (char)(carry % 10 + '0');
// 10,
carry /= 10;
i--;
j--;
}
// , , 1
if (carry == 1){
result += '1';
}
//
reverse(result.begin(), result.end());
return result;
}
int main(){
string s1, s2;
while(cin>>s1>>s2){
cout<<addStrings(s1, s2)<<endl;
}
return 0;
}