はじめに
今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。
各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。
まず、問題を読んで正しく理解し、テストコード部分をIDEやテキストエディタまたはweb上のコンパイラ (ideonなど)で保存・ビルド・実行し、アウトプットに「NG」が表示されるのを確認してほしい。 次に、テストコードの「ToDo:」部分のコードを完成させて、「NG」ではなく「Good Job!」が表示されるようにできれば問題クリアだ。
「ヒント」「解答例」「解説」はデフォルトでは非表示になっており、中身を読みたい場合は【show】ボタンを押せば表示される。 これらをすぐに読むのではなく、ちゃんと解答を考え、使用する標準ライブラりのクラス・関数をweb検索して勉強し、 コード記述・ビルド・実行してからそれらを読むのを強く推奨する。なにごとも自分で考え、いろいろ試した上で、解答などを見るようにするのが肝要だ。 その方が解答が印象に残り問題解決方法が記憶に定着しやすいのだ。
問題はノンジャンルとするが、競技プログラミング問題に多いパズル的要素は少なめにし、実務的な問題よりにするようにした。
難易度的には「標準C++ライブラリ入門」よりは若干上がってるかもしれないが、極端に難しい問題はないので、 どんどん問題を解いていただきたいと思っている。
目次
任意精度整数 加算(難易度:★★☆☆☆)
「任意精度整数」とは、精度(桁数)を必要なら(メモリが許す限り)いくらでも伸ばす(増やす)ことができる整数のことだ。 本問題では、”31415926535″ のように、string 型の数字文字列で任意精度整数を表すものとする。
というわけで、string 型の任意精度整数2つを引数で受け取り、その和の任意精度整数文字列を返す関数 string add(const string& x, const string& y) を実装しなさい。
例えば、add(“123”, “1234”) は、”1357″ を、add(“99”, “1”) は、”100″ 返す。
#include <iostream> // 標準入出力ライブラリ #include <string> using namespace std; // std 名前空間使用 #define DO_TEST(exp) do_test(exp, __LINE__) void do_test(bool b, int line) { if( b ) return; // OK cout << "\nNG at line " << line << "\n"; exit(1); } string add(const string& x, const string& y) { // ToDo: ここにコードを記述し、引数の和を文字列として返す return ""; } int main() { DO_TEST(add("100", "123") == "223"); DO_TEST(add("999", "1") == "1000"); DO_TEST(add("31", "999") == "1030"); DO_TEST(add("314159265358979323846", "999") == "314159265358979324845"); cout << "3141592653589793238462643383279 + 5028841971693993751058209749445923078164 = "; cout << add("3141592653589793238462643383279", "5028841971693993751058209749445923078164") << "\n"; DO_TEST(add("3141592653589793238462643383279", "5028841971693993751058209749445923078164") == "5028841974835586404648002987908566461443"); cout << "\nGood Job!\n"; return 0; }
任意精度整数 乗算(難易度:★★☆☆☆)
string 型の任意精度整数(前問参照)を2つ引数で受け取り、その積の任意精度整数文字列を返す関数 string mul(const string& x, const string& y) を実装しなさい。
また、その下請け関数として、string 型の任意精度整数と1文字を引数で受け取り、その積の任意精度整数文字列を返す関数 string mul(const string& x, char c) も実装しなさい。
例えば、mul(“123”, ‘2’) は “246” を、mul(“22”, “22”) は “464” を返す。
#include <iostream> // 標準入出力ライブラリ #include <string> using namespace std; // std 名前空間使用 #define DO_TEST(exp) do_test(exp, __LINE__) void do_test(bool b, int line) { if( b ) return; // OK cout << "\nNG at line " << line << "\n"; exit(1); } string add(const string& x, const string& y) { // mul() の下請けとして使用する加算関数 auto mxl = max(x.size(), y.size()); string ans(mxl, ' '); int carry = 0; auto ix = x.rbegin(); auto iy = y.rbegin(); for(auto itr = ans.rbegin(); itr != ans.rend(); ++itr) { char cx = ix != x.rend() ? *ix++ : '0'; char cy = iy != y.rend() ? *iy++ : '0'; *itr = cx + cy - '0' + carry; if( *itr > '9' ) { // 桁上りの場合 carry = 1; *itr -= 10; } else carry = 0; } if( carry ) ans = '1' + ans; return ans; } string mul(const string& data, char c) { // ToDo: ここにコードを記述し、引数の積を文字列として返す return ""; } string mul(const string& x, const string& y) { // ToDo: ここにコードを記述し、引数の積を文字列として返す return ""; } int main() { DO_TEST( mul("123", '0') == "0" ); DO_TEST( mul("0", '2') == "0" ); DO_TEST( mul("123", '2') == "246" ); DO_TEST( mul("55", '5') == "275" ); DO_TEST( mul("999", '9') == "8991" ); // DO_TEST( mul("11", "11") == "121" ); DO_TEST( mul("999", "9") == "8991" ); // const int LIMIT = 69; string ans = "1"; for (int m = 2; m <= LIMIT; ++m) { ans = mul(ans, to_string(m)); } cout << LIMIT << "! = " << ans << "\n"; // cout << "\nGood Job!\n"; return 0; }
競技プログラミング風 標準C++ライブラリ入門 連載目次リンク
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |