Developer

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

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

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

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

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

目次

加算関数(難易度:★★☆☆☆)

問題

int型引数2つを取り、その和を返す関数オブジェクトを返す関数 function addFunc() を実装しなさい。

例えば、「auto f = addFunc();」で加算関数オブジェクトを作成後に、f(1,2) を実行すると 3 を返す。

#include <iostream>       //  標準入出力ライブラリ
#include <functional>
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);
}
function<int (int, int)> addFunc() {
    return nullptr;      //  ToDo: 標準関数を使い、ここを書き換え、加算関数オブジェクトを返す
}
int main() {
    auto f = addFunc();
    DO_TEST(f != nullptr);
    DO_TEST( f(123, 456) == 579);
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・関数オブジェクトを生成するにはラムダ式を使うといいぞ。
・ラムダ式は「[](仮引数宣言) { 関数本体定義 }」という構文だぞ。

解答例
function<int(int, int)> addFunc() {
    return [](int lhs, int rhs) { return lhs + rhs; };      //  加算を行う関数オブジェクト(ラムダ式)を返す
}
解説

関数オブジェクトを生成するにはラムダ式を使うのが簡単だ。 ラムダ式の構文は「[](仮引数宣言){ 関数本体定義 }」だ。
カギ括弧([])中にはキャプチャする変数を指定可能だが、本問題では使用しないので空とする。
丸括弧中には、通常の関数定義と同じ用に仮引数リストを記述する。本問題の場合は、加算を行う2つの仮引数を記述する。
最後に、にょろ括弧({})中に、関数の本体を記述する。本問題の場合は、仮引数2つの和を返すので「{ return lhs + rhs; }」と記述する。

関数オブジェクトの型は「function<関数型指定>」と記述する。 関数型は「返値型(仮引数型, …)」と記述するんだぞ。

途中取り出し(難易度:★★☆☆☆)

問題

string型第1引数strのix番目からlen文字を文字列として返す関数 string my_mid(const string& str, int ix, int len) を実装しなさい。

先頭文字からの場合、ix: 0 とする。ix がマイナスの値の場合は、末尾から前に向かってlen文字を文字列として返すものとする。

例えば my_mid(“abcde”, 0, 3) は “abc” を、my_mid(“abcde”, -1, 3) は “cde” を返す。

my_mid(“abc”, 5, 2) や my_mid(“abc”, -5, 2) の様に、ix が範囲外の場合は “” を返すものとする。
また、len が長すぎる場合は、有効な長さまでの文字列を返すものとする。例えば my_mid(“abc”, 2, 3) は “c” を返す。

#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 my_mid(const string& str, int ix, int len) {
    //  ToDo: 標準関数を使い、ここを書き換えて、str の ix 番目から len 文字を返す
    //  ix がマイナス値の場合は末尾からix文字目から、先頭に向かって len 文字を返す
    return "";
}
int main() {
    DO_TEST( my_mid("123", 1, 1) == "2" );
    DO_TEST( my_mid("abcde", -1, 2) == "de" );
    DO_TEST( my_mid("123", 5, 1) == "" );
    DO_TEST( my_mid("123", -5, 1) == "" );
    DO_TEST( my_mid("123", 2, 3) == "3" );
    DO_TEST(my_mid("123", -3, 3) == "1");
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・string str から途中の文字列を取り出すには str.substr(ix, len) を使うぞ。
・ix は取り出す最初の位置(0オリジン)で、len は取り出す文字数だぞ。
・substr(ix, len) は ix < 0 に対応してないので、自前で対応しないといけないぞ。

解答例
string my_mid(const string& str, int ix, int len) {
    if (ix >= 0) {      //  ix が0以上の場合は、substr() をコールするだけ
        if (ix >= str.size()) return "";    //  ix 範囲チェック
        //  str.substr(ix, len) はlenが大きすぎる場合に対応しているので、処理不要
        return str.substr(ix, len);
    }
    else {    //  ix がマイナスの場合は、末尾から文字列を取り出す
        if (-ix > str.size()) return "";    //  ix 範囲チェック
        int first = str.size() + ix + 1 - len;  //  取り出し開始位置
        if (first < 0) {    //  取り出し開始位置がマイナスの場合
            len += first;   //  len を減らし
            first = 0;      //  文字列先頭から取り出す
        }
        return str.substr(first, len);
    }
}
解説

string から途中の文字列を取り出すには substr(ix, len) を使う。ix は取り出し開始位置、len は文字数だ。
substr() はixがマイナスの場合には対応していないので、まずはif文でixが0以上かどうかを判定し、 そうであればsubstr()をコールする。
ixがマイナスだった場合は、取り出す先頭位置を計算し、そこからlen文字を取り出す。

シャフル(難易度:★★☆☆☆)

問題

要素数52の(トランプの)カードデッキ配列を引数で受け取り、要素をシャフル(カード順序をランダムにする)する関数 void my_shuffle(vector<int>& deck) を実装しなさい。

なお、各カードの値は 0~51 で、値を13で割った商はクローバ・スペード・ハート・ダイヤモンドを表し、 値を13で割った剰余はカードの数字-1を表す(0-12 が A, 2,… Q, K を表す)ものとする。 具体的には、値0はクラブのエースを、値14はスペードの2を、値51はダイヤモンドのKを表す。

また、シャフルするために乱数を使用する場合は、テストコードで定義している g_mt() を使用しなさい。

#include <iostream>       //  標準入出力ライブラリ
#include <vector>
#include <random>
using namespace std;    //  std 名前空間使用
std::random_device g_rnd;     // 非決定的な乱数生成器
std::mt19937 g_mt(g_rnd());            // メルセンヌ・ツイスタの32ビット版乱数生成関数
#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);
}
const int N_CARD = 52;      //  13*4, カード種類数
bool isShuffled(const vector<int>& deck) {        //  カードがシャフルされているか判定
    vector<int> vc(52, 0);
    int mx = 0;
    for(int i = 1; i != deck.size(); ++i) mx = max(mx, vc[abs(deck[i-1] - deck[i])] += 1);
    return mx < 8;
}
void my_shuffle(vector<int>& deck) {
    //  ToDo: 標準関数を使い、ここを書き換えて、deck の要素をシャフルする
}
int main() {
    vector<int> deck;
    for(int i = 0; i != N_CARD; ++i) deck.push_back(i);
    DO_TEST( !isShuffled(deck) );
    my_shuffle(deck);
    DO_TEST( isShuffled(deck) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・指定範囲をシャフルしたい場合は std::shuffle(first, last, randFunc) を使うんだぞ。
・first, last はシャフルしたい範囲だ。
・randFunc はシャフル時に使用する乱数関数オブジェクトだぞ。
・本問題では g_mt を定義済みなので、これを使用するといいぞ。

解答例
void my_shuffle(vector<int>& deck) {
    shuffle(deck.begin(), deck.end(), g_mt);    //  乱数関数 g_mt を使って、指定範囲をシャフル
}
解説

指定範囲をシャフルしたい場合は std::shuffle(first, last, randFunc) を使う。 first, last はシャフルしたい範囲で、randFunc はシャフル時に使用する乱数関数だ。 本問題では、コンテナクラスの要素をシャフルするので、begin(), end() で範囲を指定する。 乱数関数はテストコードで定義しているメルセンヌ・ツイスタアルゴリズムによる乱数生成関数の g_mt を使用する。
なので、「shuffle(deck.begin(), deck.end(), g_mt);」をコールするだけで、範囲をシャフルしてくれるぞ。

ちなみに、シャフル処理を自前で実装するには、以下のようにするとよい。

void my_shuffle(vector& deck) {
    for (int i = 0; i != deck.size() - 1; ++i) {
        int k = g_mt() % (deck.size() - i) + i;     //  deck[i] と交換する相手を乱数で決める
        swap(deck[i], deck[k]);     //  交換
    }
}

最初は52枚の中からランダムに1枚を選び、それと1枚目を交換する。 次は2枚目からの51枚目の中からランダムに1枚を選び、それと2枚目を交換する。
これを51枚目まで繰り返すとカードがシャフルされたことになる。

このアルゴリズムは人間が行うシャフルとは異なるが、51回の処理で完全にランダムにシャフルすることができる。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。