競技プログラミング風 標準C++ライブラリ入門【第7回】


競技プログラミング風 標準C++ライブラリ入門【第7回】

今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。

問題を理解したら、テストコードをコンパイル・実行していただきたい。そのままだと実行時に「NG」が表示される。 コードを完成させ、「Good Job!」を表示させてすっきりしてほしい。グッドラック!

目次

降順ソート(難易度:★★★☆☆)

問題

int[] 型のar, 要素数szを受け取り、要素を降順にソートする関数 void sortArrayDesc(int ar[], int sz) を実装しなさい。

例えば、{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} が渡された場合は、結果は {9, 6, 5, 5, 4, 3, 3, 2, 1, 1} となる。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace 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);
}
void sortArrayDesc(int ar[], int sz) {
    //  ToDo: 標準ライブラリの関数を使って、サイズ sz の配列 ar をソートする
}
int main()
{
    int ar0[] = {123};
    const int sz0 = sizeof(ar0)/sizeof(int);
    sortArrayDesc(ar0, sz0);
    DO_TEST( vector<int>(ar0, ar0+sz0) == vector<int>({123}) );
    int ar[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    const int sz = sizeof(ar)/sizeof(int);
    sortArrayDesc(ar, sz);
    DO_TEST( vector<int>(ar, ar+sz) == vector<int>({9, 6, 5, 5, 5, 4, 3, 3, 2, 1, 1}) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

16進数文字列変換(難易度:★★★☆☆)

問題

int型の値を受け取り、それを16進数文字列(10~15 を ‘a’~’f’ で表現)に変換する関数 string hexstr(int h) を実装しなさい。

例えば、100 が渡された場合は “64” を、10 が渡された場合は “a” を返す。

#include <iostream>       //  標準入出力ライブラリ
#include <sstream>
#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 hexstr(int h) {
    return "";    //  ToDo: 標準関数を使い、ここを書き換えて、h を16進数文字列に変換したものを返す
}
int main() {
    DO_TEST( hexstr(0x123) == "123" );
    DO_TEST( hexstr(123) == "7b" );
    DO_TEST( hexstr(-1) == "ffffffff" );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

バイナリサーチ(難易度:★★★☆☆)

問題

昇順にソートされた文字列配列 const string* ar、文字列数 SZ、検索する文字列 str を引数で受け取り、 ar[ix] >
= str となる最初の ix を返す二分探索関数 int my_lower_bound(const string* ar, int SZ, const string& str) を実装しなさい。

例えば、{“a”, “bb”, “bbb”, “bbb”, “cde”} に対して “a” を検索した場合は 0 が、”bb” を検索した場合は 1 が返る。 “ax” のようにリストに無い文字列を検索した場合は “ax” より大きい最初の文字列は “bb” なので 1 が返る。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace 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);
}
int my_lower_bound(const string* ar, int SZ, const string& str) {
    //  ToDo: 標準ライブラリの関数を使って、昇順ソートされた文字列配列から str を二分検索し、そのインデックスを返す
    return 0;
}
int main()
{
    string ar[] = {"a", "bb", "bbb", "bbb", "cde"};
    const int SZ = sizeof(ar) / sizeof(string);
    DO_TEST(my_lower_bound(ar, SZ, "bbb") == 2);
    DO_TEST(my_lower_bound(ar, SZ, "ab") == 1);
    DO_TEST(my_lower_bound(ar, SZ, "z") == SZ);
    cout << "\nGood Job!\n";
    return 0;
}
ヒント
解答例
解説

関連記事

競技プログラミング風 標準C++ライブラリ入門【第12回】

競技プログラミング風 標準C++ライブラリ入門【第12回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただき […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第11回】

競技プログラミング風 標準C++ライブラリ入門【第11回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただき […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第10回】

競技プログラミング風 標準C++ライブラリ入門【第10回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただき […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第9回】

競技プログラミング風 標準C++ライブラリ入門【第9回】 これまでに競技プログラミング風 標準C++ライブラリ入門 を2シーズン、8回にわたりお届けしたが、各方面に好評だったので、 さらにおかわり(シーズン3)として【第 […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第8回】

競技プログラミング風 標準C++ライブラリ入門【第8回】 今回で本シリーズも最後だ。競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。 問題を理解したら、テストコードをコンパイル・実行し […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第7回】

競技プログラミング風 標準C++ライブラリ入門【第7回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただきた […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第6回】

競技プログラミング風 標準C++ライブラリ入門【第6回】 今回も、標準C++ライブラリの基本をマスターするための競技プログラミング風問題を解いていただこう。 問題を理解したら、テストコードをコンパイル・実行していただきた […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第5回】

競技プログラミング風 標準C++ライブラリ入門【第5回】 これまでに競技プログラミング風 標準C++ライブラリ入門 を4回にわたりお届けしたが、各方面に好評だったので、 おかわり(シーズン2)として【第5回】~【第8回】 […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第4回】

競技プログラミング風 標準C++ライブラリ入門【第4回】 今回で本シリーズも最後だ。今回も競技プログラミング風問題を解いて、標準C++ライブラリにより詳しくなっていただこう。 問題を理解したら、テストコードをコンパイル・ […]
コメントなし

競技プログラミング風 標準C++ライブラリ入門【第3回】

競技プログラミング風 標準C++ライブラリ入門【第3回】 今回も、標準C++ライブラリ入門のための競技プログラミング風問題を解いて、標準C++ライブラリに親しんでいただきたい。 問題を理解したら、テストコードをコンパイル […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP