コラム２ 「ああ（そうか）！」アルゴリズム 【珠玉のプログラミング】

問題への回答。

1

単語と辞書だけが与えられた場合：

与えられた単語を正規化。

辞書をシーケンシャルに読み、読みだした単語の正規化結果と 与えられた単語の正規化結果を比較、 一致していたら、読みだした単語を記録。

辞書の最後に到達すれば、全てのアナグラムが見つかったことになる。

辞書を操作する時間とメモリがある場合：

辞書の各単語を正規化。

正規化結果をキー、正規化前の単語をバリューとした連想配列を作っておく。

単語が与えられたらそれを正規化したものを使い要素を検索をする。

2

問題Aの解法と同様に2分探索する。

ただし、要素が欠けている方ではなく、多い方を探索していく。

3

外側のループの終了条件がわからず答えをみた。

question3.cppで実装。

4

とばした

5

a bcにわけて配列の回転を行う。

bcaになる。

bc aに分け、bcの部分に対して配列の回転を行う。

cbaになる。

6

「誤った一致」をどのように整理しておくとよいか：

分からん

同じ数字になる可能なすべての名前のセットを返す関数をどう書くか：

予め数字をキー、名前を値にした連想配列を作っておき、 ある名前の数字が与えられたらそれを引数にとって 連想配列から要素を検索した結果を返す。

7

わからん

8

わからん

9

これはソートの種類によって変わらない？問題の解釈の仕方が違う？

10

電球いっぱいに水を入れて、その水の体積を秤で測る。

感想

あんまり"AHA!"という感覚は得られなかったが、問題の解法にすぐとびつくのではなく、一呼吸おいて考えてみることは大事だと思う。

ソースコード

// question3.cpp

#include <iostream>
#include <numeric>
#include <vector>

void rotate(std::vector<int>& v, const int i) {
  const int n = v.size();

  for(int cnt = 0; cnt < std::gcd(i, n); cnt++) {
    int t = v[cnt];
    int dst = cnt;

    while(1) {
      int src = dst + i; 
      if (src >= n) src = src % n;
      if (src == cnt) break;
      v[dst] = v[src];
      dst = src;
    }

    v[dst] = t;
  }
}

int main(int argc, char** argv) {

  if(argc != 3) {
    std::cout << "error: wrong number of arguments" << std::endl;
    return 0;
  }

  const int n = std::atoi(argv[1]);
  const int i = std::atoi(argv[2]);

  if(n < i) {
    std::cout << "error: n < i" << std::endl;
    return 0;
  }

  std::vector<int> v(n);

  std::iota(v.begin(), v.end(), 0);

  rotate(v, i);

  return 0;
}

珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造